speed of Newton's binomial by recursion

[BabySeven]

Hi,I have to have faster code (count Newton's binomial) , and I have not any idea how do this.
assumptions: use recursion, use only one function, 0<=K<=N<=33

int newton(int N, int K)
{

if (N == K || K == 0) return 1;
else if(K<N && N<=33) return newton(N-1, K-1) + newton(N-1, K);
}

[ne555]

expand the recursive calls

newton(N, K) = newton(N-1, K-1) + newton(N-1, K)
newton(N, K) = [newton(N-2, K-2) + newton(N-2, K-1)] + [newton(N-2, K-1) + newton(N-2, K)]

notice that newton(N-2, K-1) is computed twice, if you keep exploding the expression you'll find more repeated operands

so, to speed up the algorithm, avoid repeating computations


exercise for the reader: ¿what's the complexity of the algorithm?

[lastchance]

You avoid repeating computations by memoising (storing what you have already computed).

I would guess the complexity is O(N^2) with memoisation and O(2^N) without, but I'm sure @ne555 will put me right if not.

[jonnin]

Hi,I have to have faster code

its a small # of numbers. can't you just precompute them?

[Duthomhas]

@jonnin
Chances are this is a "basic algorithms" homework. I dont think it likely any precomputation will count for grade.

[jonnin]

Sure, that works too, but there is an old expression about polishing a poo that comes to mind. Making bad code faster is pointless. I can fine tune bubble sort all day and never get any speed out of it.

[Duthomhas]

Okay, so, how are you going to precompute it?

[lastchance]

Induction, not recursion.

#include <iostream>
#include <vector>
using namespace std;

using INT = unsigned long long;

int main()
{
   const int NMAX = 33;
   vector< vector<INT> > nCr;

   for ( int n = 0; n <= NMAX; n++ )
   {
      vector<INT> row( 1 + n );
      for ( int r = 0; r <= n; r++ ) row[r] = ( r == 0 || r == n ? 1 : nCr[n-1][r-1] + nCr[n-1][r] );
      nCr.push_back( row );
   }


   for ( int n = 1; n <= NMAX; n++ )
   {
      cout << n << "Cr = ";
      for ( int r = 0; r <= n; r++ ) cout << nCr[n][r] << ' ';
      cout << '\n';
   }
}

[jonnin]

Okay, so, how are you going to precompute it?

Run the 'too slow' algorithm one time and dump the answers to code.
preferably, using the 'memory' of what you already did concept to make that less painful if you run it out for a very large number? The above runs in the online compiler PDQ, but if you want it even faster, you can just spew the output from a pre-built table.

The run once thing only works for tractable problems, of course. And, honestly, for this one, you probably could have looked up the hard-coded answers online.

[Ganado]

Duthomhas wrote:

Chances are this is a "basic algorithms" homework.

If I were a betting man, I'd say chances are this is a "code competition" question. Not that it makes the question any less valid (well, sometimes).
Notice the tell-tale sign of bounds given in the prompt 0<=K<=N<=33, that the competitor mistakenly thinks they need to put as if-conditions in the actual code.

[lastchance]

Didn't we have some fun with this a while back?
http://www.cplusplus.com/forum/lounge/227531/

It was a lot cooler to make it look right than to compute the coefficients.

[deleted account xyzzy]

This topic was a hoot as well:

http://www.cplusplus.com/forum/beginner/265417/

[Duthomhas]

Ganado wrote:

If I were a betting man, I'd say chances are this is a "code competition" question.

Hmm, you are absolutely right. I’m sorry my brain didn’t read the clues correctly.

Though, I’ll still bet that precomputed results are not permitted by the competition’s rules. (I could be wrong, though!)


Love the cod fish. I’m sorry I missed that one.





Now I’m hungry for some halibut or something...

[deleted account xyzzy]

Love the cod fish. I’m sorry I missed that one.

That makes me even more glad I saved the link, so I could share it. :)

I "like" how the OP dropped his "do all the work for me for free" turd and hasn't bothered to reply back. Even after some people offered legitimate help.