I'm playing with Google riddle from some code.jam event.

As a result of play I have function [here without any optimization and argument checking]:

public long findMaxF(long d, long b) {

long f = 0;

if (b==1) {

f=d;

} else if (b==d) {

f=(1<<d)-1; // 2^d - 1

} else {

f = findMaxF(d-1,b)+findMaxF(d-1,b-1)+1;

}

return f;

}

I have even less complicated version giving identical results:

public long findMaxF(long d, long b) {

long f = 0;

if (d<b) b=d;

if (b==1) {

f=d;

} else {

f = findMaxF(d-1,b)+findMaxF(d-1,b-1)+1;

}

return f;

}

I know that it is possible to calculate it without recursion... but I don't know how ;-) My only idea for now was to "simulate" some kind of stack ;-) with keeping list of directions how we moved on recursion tree, but I don't like this idea ;-)

`d`

and `b`

may be really big, not simply thousands but also millions and billions [but if `b`

is greater then 32 this method will return something bigger then 2^32 so more then 4 billions with something following]My code works great with small set of data but totally fails with large :-) For now it fails because StackOverflowError :-) but why not if

`d`

is counted in millions ;-)Even my idea with simulated stack will fails with such big values.......

I feel that it should be possible to not only avoid recursion [this is sure ;-)] but that this should be done in "linear" way, with 1 pass algorithm....

OK, I divide with you my sadness ;-) I feel better now ;-)

[

**Update: 09/07/2008**]

Yesterday I decided that it cannot be in this way that I cannot do this ;-)

I decide to analyze this function. I thought in this way, first of all, if we will draw 3d chart of this function and as x we will use d, and as y we will use b, this function will have results only in are between y=1 and line described by y=x.

Additionally when y = 1, this function will return value d [so value of x], and on this line y=x [b=d] it will take value 2

^{b}-1. So I'm interested what kind of function describes value of this function with fixed b value....

I printed results for function for d=20 and b from 1 to 20....

I put it into spreadsheet and checked what if I will calculate f(n)-f(n-1).... :-)

I got some results, and those results was symmetrical... It was a clue ;-)

Difference between next values of function was described by binomial coefficient :-)

Binomial coefficient is described by:

So I needed to calculate factorial.... Thought by sad memories from fighting with recursion for original function I decided to use "linear" algorithm ;-) When I was using

`BigInteger`

it was working, and was able to calculate binomial coefficient for almost anything in finite time.... but this finite time might be counted in decades ;-)I analyzed formula to calculate coefficient, changed code, this worked but still was slooooowwww.

Finally I found in Wikipedia article about binomial coefficient in programming languages. I used it, and it's working :-)

Similar posts

^{beta}

How to create valid file name?

How we may use Google Earth Plugin? :-)

How to get negative number from size() in LinkedList in Java? ;-)

Abuse of Booleans ;-)

Which language is fastest? ;-)

## No comments:

## Post a Comment