How to estimate the number of recursive calls

How to estimate the number of recursive calls that would be used by the code

Code:

---

public static double binomial(int N, int k, double p)
{
if ((N == 0) || (k < 0)) return 1.0;
return (1.0 - p)*binomial(N-1, k) + p*binomial(N-1, k-1);
}

---

to compute binomial(100, 50)???

I am looking for the formula that gives me the exact number of calls
I sent an email to writer of the book that I found this problem in it and he answered me:

Quote:

---

Hint: calculate the number of calls for some small values of N and k and consider functions that involve N! (N factorial) and k! (k factorial).

---

but still nothing and I am confused:confused:

So, which small values for N and k did you try?

Quote:

---

Originally Posted by D_Drmmr

So, which small values for N and k did you try?

---

I wrote a program that gives me the numbes but for (100,50) it takes too long
I am sure that there is a formul

Code:

---

(1,0)=3
(2,0)=5
(2,1)=7
(3,0)=7
(3,1)=13
(3,2)=15
(4,0)=9
(4,1)=21
(4,2)=29
(4,3)=31
(5,0)=11
(5,1)=31
(5,2)=51
(5,3)=61
(5,4)=63
(6,0)=13
(6,1)=43
(6,2)=83
(6,3)=113
(6,4)=125
(6,5)=127
(7,0)=15
(7,1)=57
(7,2)=127
(7,3)=197
(7,4)=239
(7,5)=253
(7,6)=255
(8,0)=17
(8,1)=73
(8,2)=185
(8,3)=325
(8,4)=437
(8,5)=493
(8,6)=509
(8,7)=511

---

Quote:

---

Originally Posted by arira

I wrote a program that gives me the numbes but for (100,50) it takes too long
I am sure that there is a formul

---

Of course, and the question is about finding that formula, rather than the specific answer.

Let's take the following approach: write a function f that expresses the number of recursive calls in terms of n and k.
Forgetting the check on the value of n and k for a minute, it should be obvious that f(n, k) = f(n - 1, k) + f(n - 1, k - 1).
You can expand this further in steps by substituting this formula for the elements on the right hand side. I.e. the second step yields f(n, k) = f(n - 2, k) + 2 * f(n - 2, k - 1) + f(n - 2, k - 2).
Repeat this for a few steps and then have a look at this: http://en.wikipedia.org/wiki/Pascal's_triangle
That should help you to find a more general formula for f(n, k). Once you have that, you can consider how to introduce the if condition in the function.

I tried before all of this and I think no one knows the answer in the world and wanna give up because it takes my time too much and spent enough time for this problem.

number of recursive calls :

Code:

---

f(n, k) = f(n - 1, k) + f(n - 1, k - 1) + 1

---

thanks

Quote:

---

Originally Posted by arira

I tried before all of this and I think no one knows the answer in the world and wanna give up because it takes my time too much and spent enough time for this problem.

---

I think I have a solution.

Each call to f gives rise to two new calls to f recursively. One can think of the call pattern as an imaginary binary tree. Each call to f represents a node and the first f call in f goes to the left child node and the second to the right child node.

If k is equal to n or bigger then the recursion will be limited by n only. The imaginary binary tree will be complete and have a depth of n. The number of nodes, or rather f calls, will be 2^(n+1) - 1. Say n=1 for example that will give 3 f calls and if n=2 there are 7.

Now if k is made smaller than n it will start limiting the recursion. The imaginary binary tree will no longer be complete. Certain branches will be ignored because k becomes negative in some call paths and that will stop the recursion before it reaches the maximum depth determined by n. This happens each time the second call to f in f has been called k+1 times along a call path (the first call to f in f leaves k unchanged).

The question becomes: How many nodes, that is f calls, in the imaginary binary tree won't be visited because of k? If those are subtracted from the total number of nodes of the complete binary tree we have the number of actual f calls. An analysis is somewhat involved. If a node (f call) in the complete binary tree is on a path below more than k+1 right side child nodes (calls to the second f in f) then it will never be reached (because of the k limit) and should be subtracted from the total.

The result is simple and somewhat surprising. The number of never performed f calls can be found in Pascal's triangle! They're in a subtriangle defined by n and k. One simply add up all binominal coefficients of that subtriangle and double the sum.

Code:

---

Pascal's triangle
-----------------
1:        1 1
2:      1 2 1
3:      1 3 3 1
4:    1 4 6 4 1
5:    1 5 10 10 5 1
6:  1 6 15 20 15 6 1
7:    ...

---

The subtriangle for f(n,k) is from k+1 to n-1. To show how the subtriangle is extracted is easiest with an example.

If n=4 and k=1 the subtriangle is from 2 to 3 and looks like this:

Code:

---

Subtriangle (from k+1=2 to n-1=3)
---------------------------------
2:      1
3:      1 3

---

All coefficients are added and the sum is doubled. That's the number of f calls that should be removed from the maximum total (which is 2^(n+1) - 1 according to the formula above). So we have f(4,1) = (2^(4+1) - 1) - 2*(1 + 1+3) = (32 - 1) - 2*5 = 21.

If instead n=6 and k=2 one gets a subtriangle from 3 to 5 like:

Code:

---

Subtriangle (from k+1=3 to n-1=5)
---------------------------------
3:      1
4:    1 4
5:    1 5 10

---

And f(6,2) = (2^(6+1) - 1) - 2*(1 + 1+4 + 1+5+10) = (128-1) - 2*22 = 83.

Since Pascal's triangle can be calculated in quadratic time an f(n,k) algorithm based on that will be O(N^2). On the other hand binominal coefficients quickly become very large so f(100, 50) is hardly tractable with standard hardware supported arithmetics.

Quote:

---

Originally Posted by nuzzle

I think I have a solution.

Each call to f gives rise to two new calls to f recursively. One can think of it as a binary tree. Each call to f represents a node and the first f call in f goes to the left and the second to the right.

If k is equal to n or bigger then the recursion will be limited by n only. The imaginary binary tree will be complete and have a depth of n. The number of nodes, or rather f calls, will be 2^(n+1) - 1. Say n=1 for example that will give 3 f calls.

Now if k is made smaller than n it will start limiting the recursion. The imaginary binary tree will no longer be complete. Certain branches will be ignore because k has become smaller than 0 for certain paths and the recursion will stop until it reaches the maximum depth sey by n. This happens each time the second call to f in f has been called k+1 times because then k becomes negative (the first call to f in f leaves k unchanged)

The question now becomes: How many nodes, that is f calls, in the imaginary binary tree won't be visited because of k? If those are subtracted from the total number of nodes of the complete binary tree we have the number of actual f calls.

An analysis is somewhat involved. If a node is reached after more than k+1 "right child" calls to f then it should be subtracted from the total. But the result is simple and somewhat surprising. The number of not performed f calls can found in Pascal's triangle. One simply cuts out a subtriangle and add up all coefficients.

Code:

---

Pascal's triangle
---------------
1:        1 1
2:      1 2 1
3:      1 3 3 1
4:    1 4 6 4 1
5:    1 5 10 10 5 1
6:  1 6 15 20 15 6 1

---

Now if n=4 and k=1 you cut out this subtriangle from k+1 to n-1.

Code:

---

Subtriangle (cut from k+1=2 to n-1=3)
---------------------------------------------
2:      1
3:      1 3

---

You add up the numbers and double the sum. That's the number of nodes (f calls) that should be removed from the total which is 2^(n+1) - 1 according to the formula above. So we have f(4,1) = (2^(4+1) - 1) - 2*(1 + 1+3) = (32 - 1) - 2*5 = 21.

If instead n=6 and k=2 you get,

Code:

---

Subtriangle (cut from  k+1=3 to n-1=5)
---------------------------------------------
3:      1
4:    1 4
5:    1 5 10

---

And f(6,2) = (2^(6+1) - 1) - 2*(1 + 1+4 + 1+5+10) = (128-1) - 2*22 = 83.

Since Pascal's triangle can be calculated in quadratic time the algorithm is O(N^2). On the other hand binominal coefficients quickly become very large so f(100, 50) is hardly tractable with standard arithmetic.

---

thank for your answer
but there is only one thing remains
I sent an mail to the writer of the book that I found this problem and he answered me

Code:

---

Hint: calculate the number of calls for some small values of N and k and consider functions that involve N! (N factorial) and k! (k factorial).

---

where is the factorial in this formula?:ehh:

Quote:

---

Originally Posted by arira

where is the factorial in this formula?

---

Pascal's triangle consists of binominal coefficients (n|k) defined as n! / (k! * (n-k)!) so there are lots of factorials in the solution. I wouldn't say that hinting at factorials is such a great help really but maybe the author has some other solution approach in mind where they play a more prominent role.

In my solution binominals appear because they have a combinatorial interpretation. (n|k) tells how many ways there are to order k of n elements. There may be a deeper reason why they appear as a subtriangle of Pascal's triangle or maybe it's just coincidental. I couldn't say but it's interesting.

The entries in Pascal's triangle can be expressed in terms of factorials ( https://en.wikipedia.org/wiki/Pascal...e#Combinations ). By nuzzle's analysis, you are summing over entries in the triangle. Presumably there is some analytical solution.

To follow up: possibly of interest, though perhaps at an excessive level of detail: http://mathworld.wolfram.com/BinomialSums.html

Quote:

---

Originally Posted by BioPhysEngr

Presumably there is some analytical solution.

---

Maybe the sum of binominals I have in my solution can be reduced to factorials but computationally it may be better to keep the binominals. It's because of the relationship with Pascal's triangle in this case. Factorials becomes awfully big very quickly and require lots of multiplications to compute. Binominals on the other hand stay smaller and if the recurrent Pascal's triangle algorithm is used only additions are needed. For example the factorial 20! is 2432902008176640000 while the binominal (20|10) is just 184756.

I looks like the OP is using Java and it sports a standard class for arbitrary-precision integers called BigInteger. Using BigInteger in combination with the very efficient recurrent Pascal's triangle algorithm would make it possible I think to find the exact solution to even something as big as f(100,50) in reasonable time.

Quote:

---

Originally Posted by nuzzle

Maybe the sum of binominals I have in my solution can be reduced to factorials but computationally it may be better to keep the binominals. It's because of the relationship with Pascal's triangle in this case. Factorials becomes awfully big very quickly and require lots of multiplications to compute. Binominals on the other hand stay smaller and if the recurrent Pascal's triangle algorithm is used only additions are needed. For example the factorial 20! is 2432902008176640000 while the binominal (20|10) is just 184756.

I looks like the OP is using Java and it sports a standard class for arbitrary-precision integers called BigInteger. Using BigInteger in combination with the very efficient recurrent Pascal's triangle algorithm would make it possible I think to find the exact solution to even something as big as f(100,50) in reasonable time.

---

I know what you mean but our purpose is to find a formula not a better way to calculate binomial
we can say in formula 50! and don't need to calculate it because it is formula

Quote:

---

Originally Posted by arira

I know what you mean but our purpose is to find a formula not a better way to calculate binomial
we can say in formula 50! and don't need to calculate it because it is formula

---

Well, in the outset you were desperate for even a solution to this problem and now you've been presented with both an analytical formula and an algorithm for its efficient calculation.

I'm sure you can take it from here, can't you? :)

Quote:

---

Originally Posted by nuzzle

Well, in the outset you were desperate for even a solution to this problem and now you've been presented with both an analytical formula and an algorithm for its efficient calculation.

I'm sure you can take it from here, can't you? :)

---

yeah I think I can do :)
many thank to you

This is the biggest integer I've ever calculated,

f(2000, 1000) =
1209534321 9735098552 2903522586 7446778809 8668638152
9033033273 7325193927 2634582289 8869424817 6781461447
0294409273 1357601491 2317637051 5305036720 9372516932
2073305244 1230852872 8460082699 4515592105 7639325243
8822463388 1260473484 3111276259 8987157639 2918042559
8529937335 7198161486 1757772413 3263187077 6197841476
0695661597 2817042973 3181299132 5620020547 1522883226
1828324145 3410507555 2256126444 3935238098 3367645450
2592255180 5298299119 7437362408 6333913348 2328527571
0095093958 9645321675 9311085561 7293560592 5007747916
5565749079 7322221063 3340124528 3282046444 6579215765
1962457506 7927119801 7132820676 0505220292 2739198418
495

I took just a second on an ordinary desktop. Quite amazing.

The code is written in Java using BigInteger and the recurrent Pascal's triangle algorithm.

Code:

---

import java.math.BigInteger;
import java.util.ArrayList;

public class Main {

                // the rows of Pascal's triangle one by one
        static class PascalRows extends ArrayList<BigInteger> {
                {        add(BigInteger.ONE);}
                public void nextRow() {
                        BigInteger f = get(0);
                        for (int i=1,N=size(); i<N; i++) {
                                final BigInteger s = get(i);
                                set(i, f.add(s));
                                f = s;
                        }
                        add(BigInteger.ONE);
                }
        }
                // 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,N=n-k-1; i<N; i++) {
                        pascal.nextRow();
                        for (int j=0; j<=i; j++) sum = sum.add(pascal.get(j));
                }
                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!");
                System.out.println(f(2000,1000));
        }
}

---

This was a nostalgic trip down memory lane. I haven't used Java or Eclipse for years.

BigInteger is something of a fossil. It's the only surviving reminder of a proud initiative called Java Grande. It was active at the peak of the Java hype age when there still was no limit to what Java could and should be used for. So much effort and now it's just a faint memory in the senile minds of a few elders who still remember Java in its hayday. So sad. :)

http://www.javagrande.org/

But BigInteger still is nice and handy. I wish Boost offered an arbitrary precision arithmetics package (at least I haven't seen any).

Quote:

---

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.

Quote:

---

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 = n-i-1;
                        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(L-1))); // 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=n-k-1; 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");
        }
}

---

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=n-k-1. 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.

Quote:

---

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=n-k-1. 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(N-1, k, p) + p*binomial1(N-1, k-1, p);
    }

---

can u give a sample for your formula?

Quote:

---

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 n-1=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 n-k-2} 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 performance-wise 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 = n-i-1;
                        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(L-1)));
                }
                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");
        }
}

---

just for the c++ glory, here is an off-the-top-of-my-head 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 ).

Quote:

---

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.

Quote:

---

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!(n-k-1)! = [(n-k)/(k+1)] (n k).

Quote:

---

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!(n-k-1)! = [(n-k)/(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.