
December 16th, 2012, 06:09 AM
#16
Re: How to estimate the number of recursive calls
Originally Posted by nuzzle
I wish Boost offered an arbitrary precision arithmetics package (at least I haven't seen any).
boost.multiprecision has recently passed the review process and will be added to some next boost release. It still has some weaknesses from the design POV, but it's a great library IMO.

December 19th, 2012, 04:49 AM
#17
Re: How to estimate the number of recursive calls
Originally Posted by nuzzle
I took just a second on an ordinary desktop. Quite amazing.
Just for fun I've optimized the code in my previous reply.
It's based on two features. First, Pascal's triangle is symmetrical so only one half needs be calculated. Second, the recurrence algorithm works also with a cumulative Pascal's triangle without additional cost. Cumulative means that each number in the triangle is no longer an individual binominal but the sum of all binominals to the left on the same row. This means that not all numbers in the subtriangle needs be summed anymore, only the number at the far right on each row (because it's in effect the row sum).
These changes together speed up the algorithm about 4 times. So f(2000,1000) for example which took about 1 second before now takes 1/4 of a second. To push it a little I tried f(10000,5000). It's an enormous integer with about 3000 digits. It took just 40 seconds.
Here's the optimized code.
Code:
import java.math.BigInteger;
import java.util.ArrayList;
public class Main {
// the rows of Pascal's cumulative triangle one by one
static class PascalRows {
public PascalRows() {row.add(BigInteger.ONE);}
public int size() {return n+1;}
public BigInteger get(int i) { // now "virtual" access to row numbers
if (i+i <= n) return row.get(i); // left row half
i = ni1;
return (i<0) ? pow : pow.subtract(row.get(i)); // right row half
}
public void nextRow() {
n++;
pow = pow.shiftLeft(1);
BigInteger f = row.get(0);
final int L = row.size();
for (int i=1; i<L; i++) { // same recurrence now generates cumulative row
final BigInteger s = row.get(i);
row.set(i, f.add(s));
f = s;
}
if ((n & 1) == 0) row.add(pow.subtract(row.get(L1))); // row middle number
}
private int n = 0; // row number
private BigInteger pow = BigInteger.ONE; // known row sum
private final ArrayList<BigInteger> row = new ArrayList<BigInteger>();
}
// sum of all binominals of a subtriangle of Pascal's triangle
static BigInteger subTriangle(int n, int k) {
BigInteger sum = BigInteger.ZERO;
final PascalRows pascal = new PascalRows();
for (int i=0; i<k; i++) pascal.nextRow();
for (int i=0,L=nk1; i<L; i++) {
pascal.nextRow();
sum = sum.add(pascal.get(i)); // no row loop, instead rightmost number added
}
return sum;
}
// f(n,k) = 2 * (2^n  subTriangle(n,k))  1
static BigInteger f(int n, int k) {
return BigInteger.ONE.shiftLeft(n).subtract(subTriangle(n,k)).shiftLeft(1).subtract(BigInteger.ONE);
}
public static void main(String[] args) {
System.out.println("Hello World!");
long start = System.nanoTime();
System.out.println(f(2000,1000));
long stop = System.nanoTime();
System.out.println("time: " + (stop  start)*0.000000001 + " seconds");
}
}
Last edited by nuzzle; December 19th, 2012 at 07:21 AM.

December 19th, 2012, 09:52 AM
#18
Re: How to estimate the number of recursive calls
I've just reread the problem statement in post #1 and, unless I'm missing something, there should be an easier solution: you could just identify a recursion branch with a path in the n,k plane. Then, the number of calls equals exactly the number of paths from a starting point (n,k) to the border {(n,k) n=0 or k=1} where paths should not touch the k=1 line more than once, times two minus one ( because of the first call ).
now, the vertical border {(0,j)j>1} gives just a sum of binomials : sum{j=0 to k}binomial(n,j)
the horizontal border {(j,1)j>=0} gives a sum where each term is the number of all possible paths to (j,1) minus the (j+1)term ( due to the fact that paths moving horizontally on the k=1 line should not be counted ) up to j=nk1. Terms cancel term by term leaving just a binomial(n,k+1).
Hence, the number of calls is just 2*( sum{j=0 to k+1} binomial(n,j) )  1 that can be computed in linear time by using the usual binomial recursive relations ( I've not checked the result above deeply, but a quick numerical check gives the same results as in post #3 and #15 ). Moreover, a constant time approximation for big n can be quickly obtained by approximating the binomial sum via the error function.
Last edited by superbonzo; December 19th, 2012 at 09:59 AM.
Reason: typos

December 19th, 2012, 04:05 PM
#19
Re: How to estimate the number of recursive calls
Originally Posted by superbonzo
I've just reread the problem statement in post #1 and, unless I'm missing something, there should be an easier solution: you could just identify a recursion branch with a path in the n,k plane. Then, the number of calls equals exactly the number of paths from a starting point (n,k) to the border {(n,k) n=0 or k=1} where paths should not touch the k=1 line more than once, times two minus one ( because of the first call ).
now, the vertical border {(0,j)j>1} gives just a sum of binomials : sum{j=0 to k}binomial(n,j)
the horizontal border {(j,1)j>=0} gives a sum where each term is the number of all possible paths to (j,1) minus the (j+1)term ( due to the fact that paths moving horizontally on the k=1 line should not be counted ) up to j=nk1. Terms cancel term by term leaving just a binomial(n,k+1).
Hence, the number of calls is just 2*( sum{j=0 to k+1} binomial(n,j) )  1 that can be computed in linear time by using the usual binomial recursive relations ( I've not checked the result above deeply, but a quick numerical check gives the same results as in post #3 and #15 ). Moreover, a constant time approximation for big n can be quickly obtained by approximating the binomial sum via the error function.
If you mean binomial the formula that I posted in #1 it is wrong formula for calculate binomial because it always answers 1 to us
the right formula for binomial is
Code:
public static double binomial1(int N, int k, double p) {
if (N == 0 && k == 0) return 1.0;
if (N < 0  k < 0) return 0.0;
return (1.0  p) *binomial1(N1, k, p) + p*binomial1(N1, k1, p);
}
can u give a sample for your formula?

December 20th, 2012, 09:12 AM
#20
Re: How to estimate the number of recursive calls
Originally Posted by superbonzo
2*( sum{j=0 to k+1} binomial(n,j) )  1
That seems to be correct indeed. I have arrived at this formula,
f(n,k) = 2 * (2^n  subtriangle(n,k))  1
I now realise that the subtriangle sum can be calculated with less effort using the row beneath it. There's a standard formula that goes like this,
bin(n,0) + bin(n+1,1) + bin(n+2,2) + ... + bin(n+k,k) = bin(n+k+1,k)
It states that all subtriangle diagonal sums (from upper left to lower right) exist as binominals in the row immediately under the subtriangle. For example,
Code:
Subtriangle (from k+1=3 to n1=5)

3: 1
4: 1 4
5: 1 5 10

6: 1 6 15
In this subtriangle from rows 3 to 5 the diagonal sums are found on row 6 like this,
15 = 1+4+10
6 = 1+5
1 = 1
So rather than summing all binominals inside the subtriangle one can as well sum fewer on the row below. I can't believe I missed this but I did. Anyway my formula now becomes,
f(n,k) = 2 * (2^n  sum{j=0 to nk2} bin(n,j))  1
Noting that 2^n is the total sum of all binominals on row n the expression reduces to what you suggest,
f(n,k) = 2 * (sum{j=0 to k+1} bin(n,j))  1
Now if the cumulative version of the recurrence algorithm for Pascal's triangle is used the sum in this formula is for free and the complexity for f(n,k) in fact can be considered constant. In practice the binominal calculations and the arbitrary precision arithmetics will make it closer to quadratic though.
Here's the new code. It's somewhat simpler in structure but performancewise it's as before,
Code:
import java.math.BigInteger;
import java.util.ArrayList;
public class Main {
// the rows of Pascal's cumulative triangle one by one
static class PascalRows {
public PascalRows() {row.add(BigInteger.ONE);}
public int size() {return n+1;}
public BigInteger get(int i) {
if (i+i <= n) return row.get(i);
i = ni1;
return (i<0) ? pow : pow.subtract(row.get(i));
}
public void nextRow() {
n++;
pow = pow.shiftLeft(1);
BigInteger f = row.get(0);
final int L = row.size();
for (int i=1; i<L; i++) {
final BigInteger s = row.get(i);
row.set(i, f.add(s));
f = s;
}
if ((n & 1) == 0) row.add(pow.subtract(row.get(L1)));
}
private int n = 0;
private BigInteger pow = BigInteger.ONE;
private final ArrayList<BigInteger> row = new ArrayList<BigInteger>(); // current row
}
// sum of binominals from 0 to k+1 on row n
static BigInteger sum(int n, int k) {
final PascalRows pascal = new PascalRows();
for (int i=0; i<n; i++) pascal.nextRow();
return pascal.get(k+1); // no actual summing because row is cumulative
}
// 2 * sum(n,k)  1
static BigInteger f(int n, int k) {
return sum(n,k).shiftLeft(1).subtract(BigInteger.ONE);
}
public static void main(String[] args) {
System.out.println("Hello World!");
long time = System.nanoTime(;
System.out.println(f(2000,1000));
time = System.nanoTime()  time;
System.out.println("time: " + time*0.000000001 + " seconds");
}
}
Last edited by nuzzle; December 21st, 2012 at 09:21 AM.

December 21st, 2012, 09:47 AM
#21
Re: How to estimate the number of recursive calls
just for the c++ glory, here is an offthetopofmyhead implementation using the NTL big int library:
Code:
#include <NTL/ZZ.h>
NTL::ZZ recursion_count( NTL::ZZ const& n, NTL::ZZ const& k )
{
NTL::ZZ result, next, j, kp1 = k + 1;
for( next = 1; j <= kp1; ++j )
{
result += next;
next *= n  j;
next /= j + 1;
}
return 2 * result  1;
}
my timings for the f(2000,1000) and f(10000,5000) are 2 and 37 milliseconds, respectively ( VS2010, fully optimized ).

December 21st, 2012, 02:38 PM
#22
Re: How to estimate the number of recursive calls
Originally Posted by superbonzo
just for the c++ glory,
Well, then we should be using the same algorithm. The one I implemented in Java isn't that suitable for the simpler formula we now have.
My crystal ball told me you have been basing your algorithm on what's tagged as (Gray's Theory) here,
http://en.wikipedia.org/wiki/Pascal's_triangle
I implemented that in Java and retrofitted your variable names and it came out pretty close to what you have,
Code:
import java.math.BigInteger;
public class Main {
// 2 * (sum of binominals from 0 to k+1 on row n)  1
static BigInteger f(int n, int k) {
final BigInteger N = BigInteger.valueOf(n+1);
final BigInteger K = BigInteger.valueOf(k+1);
BigInteger next = BigInteger.ONE;
BigInteger result = next;
for (BigInteger j = BigInteger.ONE; j.compareTo(K) <= 0; j = j.add(BigInteger.ONE)) {
next = next.multiply(N.subtract(j)).divide(j);
result = result.add(next);
}
return result.shiftLeft(1).subtract(BigInteger.ONE);
}
public static void main(String[] args) {
System.out.println("Hello World!");
long time = System.nanoTime();
for (int i=0; i<10; i++) f(2000,1000);
time = (System.nanoTime()  time) / 10;
System.out.println("time: " + time*0.000000001 + " seconds");
}
}
I ran it for f(2000,1000) and f(10000,5000) and they clocked in at 4 and 70 milliseconds respectively. So the C++ version was twice as fast as the Java version. That's not conclusive of course since we are using different computers but I have a feeling this result quite well reflects the true state of affairs. I think it's quite impressive of Java to be that close to C++. Especially considering that BigInteger is immutable so there are plenty of heap allocations taking place behind the scene.
Last edited by nuzzle; December 22nd, 2012 at 03:20 AM.

December 22nd, 2012, 03:23 AM
#23
Re: How to estimate the number of recursive calls
Originally Posted by nuzzle
My crystal ball told me you have been basing your algorithm on what's tagged as (Gray's Theory) here
I have no idea what grey's theory is; the algorithm in my post is just the verbatim application of (n k+1) = n!/(k+1)k!(nk1)! = [(nk)/(k+1)] (n k).

December 22nd, 2012, 04:09 AM
#24
Re: How to estimate the number of recursive calls
Originally Posted by superbonzo
I have no idea what grey's theory is; the algorithm in my post is just the verbatim application of (n k+1) = n!/(k+1)k!(nk1)! = [(nk)/(k+1)] (n k).
Nevertheless, according to the link I supplied that's called Gray's Theory.
It's never too late to learn something new, even though you of course wouldn't need to.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a CodeGuru survey question.
Featured
