## Tuesday, July 8, 2008

### It's why Great Apes are like us :-)

Very interesting video showing how one of great apes species - bonobo - is able not only to use tools and fire, but also to use language and play Pac-Man ;-)

http://www.ted.com/index.php/talks/susan_savage_rumbaugh_on_apes_that_write.html

This video helps in understanding people supporting Great Ape Project.

Similar postsbeta
Export documents to Box.net from your OpenOffice.org with OOo2GD :-)
Amazon Prime Video suxx
Yeah! :-) Will see Sam Harris and Yuval Noah Harari :-)
Early access version of OOo2GD 1.7.0 with partial MacOS support
Why people are so afraid of terrorists?

## Sunday, July 6, 2008

### Recursion is evil ;-)

Recursion is evil :-)

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 2b-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:
n!/(k!(n-k)!)

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 postsbeta
How to create valid file name?
How we may use Google Earth Plugin? :-)
Abuse of Booleans ;-)
Which language is fastest? ;-)
It's alive... still ;-)