run time problem
Hello;
The following is the code for recursive fibonacci , but i got a problem with run my code, when run my code with "java Fib 20", it come up the result in 1 second, but when I run my code with "java Fib 50" or up to 50,
I wait for 10 mins, i could not see any things, I am runing in linux machine, Could anyone tell me why ?
Thanks
import java.math.BigInteger;
class Fib{
publicstaticvoid main(String[] args){
int n = Integer.parseInt(args[0]);
System.out.println("recursiveBigFib: " + recursiveBigFib(n));
}
publicstatic BigInteger recursiveBigFib(finalint n){
if (n <= 2)
return BigInteger.ONE;
else
return recursiveBigFib(n - 1).add(recursiveBigFib(n - 2));
}
}
[1464 byte] By [
kill1234] at [2007-9-30 13:36:12]
That thing is exploding on you.
50 calls 49 and 48.
49 calls 48 and 47
48 x2 calls 47x2 and 46x2
47 x3 calls 46x3 and 45x3
46x5 calls 45x5 and 44x5
45x8 calls 44x8 and 43x8
44x 13 calls 43x13 and 42 x 13
43x 21 calls 42x21 and 41x21
42x 34 calls
By the time you get to 0 this is going to be massive.
Wish I could see the funciton but i cant=/ Either way I know its possible to make single recursive calls by feeding forward what you already know instead of these 2 calls per a call that cause the explosion.
could you show me on my code?
Basically for every recursive call you have two more recursive calls. As a paradym thats bad. The number of calls grows explosively. My instructor once gave me similiar code for a tree balancing cept it wasnt an excercise =)
I left your code the same. I added mine in another class.If you comment out your call you can do fib 50 in seconds.You can verify the results are the same by doing n = 10. Crank it up to n=30 with and without the speed difference to verify and then crank it up to n =50 BUT COMMENT OUT THE CALL TO THE OLD ROUTINE. And marvel at how fast single recursive are compared to double recursive.
import java.math.BigInteger;
class Fibber{
class BIPair{
BigInteger fibn;
BigInteger fibnminus;
}
BIPair recursiveBigFib(int n){
BIPair ret = new BIPair();
BIPair nminusret = null;
if(n <=2){
ret.fibn = BigInteger.ONE;
ret.fibnminus = BigInteger.ONE;
}else{
nminusret = recursiveBigFib(n-1);
ret.fibn = nminusret.fibn.add( nminusret.fibnminus);
ret.fibnminus = nminusret.fibn;
}
return ret;
}
void execute(int n)
{
BIPair bip = recursiveBigFib(n);
System.out.println("Execute recursiveBigFib: " + bip.fibn);
}
}
class Fib {
public static void main(String[] args) {
Fibber fibber = new Fibber();
int n = 10;
System.out.println("recursiveBigFib: " + recursiveBigFib(n)); // DONT CALL THIS WITH BIG N
fibber.execute(n); //THIS HANDLES BIG N JUST FINE
}
public static BigInteger recursiveBigFib(final int n) {
if (n <= 2)
return BigInteger.ONE;
else
return recursiveBigFib(n - 1).add(recursiveBigFib(n - 2));
}
}
I cranked my version up to n = 200 and 2 to 3 seconds later it spit out this:
Execute recursiveBigFib: 280571172992510140037611932413038677189525
In fact nobody ever mentioned it in school but in recursion that involves 2 recursive calls for each recursive call is fundamentally bad I think. Theres no case where its worth doing.
http://forum.java.sun.com/thread.jsp?forum=426&thread=539561&tstart=0&trange=30 http://pw1.netcom.com/~hjsmith/Fibonacc/DDJFibL.html http://icl.pku.edu.cn/yujs/MathWorld/math/f/f043.htm
Thanks jeremiahrounds;
your one is faster 3 time than my one when i use n=30.
but I got a question with your one's result, why I use the number 0 to 100, the speed almost same, when i use the n=1000, then i can see some diferrent on speed?
1) Execute recursiveBigFib: 1
It take 9 to run 0
2) Execute recursiveBigFib: 2
It take 10 to run 3
3) Execute recursiveBigFib: 5
It take 9 to run 5
4) Execute recursiveBigFib: 8
It take 9 to run 6
5) Execute recursiveBigFib: 6765
It take 10 to run 20
6) 5) Execute recursiveBigFib: 12586269025
It take 11 to run 50
7) Execute recursiveBigFib: 354224848179261915075
It take 10 to run 100
8) Execute recursiveBigFib: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
It take 17 to run 1000
Thanks Ragnvald_id2;But it does not aswer my question.
Thats fascinating on the time stamps.
Most likely its the JIT optimizing the new call more then anything.
The calls are linear. Theres n-1 calls to the recursive function.
The next step in the evolution if your looking at speed that closely is to get rid of recursion. This will run in a loop nicely starting at the bottom values instead of the top. Then get rid of the new call. Then it should be faster.
> In fact nobody ever mentioned it in school but in
> recursion that involves 2 recursive calls for each
> recursive call is fundamentally bad I think. Theres
> no case where its worth doing.
Threre's nothing wrong with 2-recursion. Quicksort is a double recursive algorithm. The running time of recursive algorithms is given by recurrence relations. If you've had a class in algorithms they should've at least mentioned this. If the solution of the given recurrence is exponential, (as in the OP's code) the algorithm is no good. However, often higher order recursion leads to very fast algorithms. This is the case with quicksort, and Strassen' matrix multiplication algorithm which is 4-recursive.
[nobr]Well there are several other approaches that might interest you. Memoization and plain old iteration springs to mind:
import java.util.HashMap;
import java.math.BigInteger;
/** Several ways of implementing the fiboniac function. */
public class Memoize {
static final BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE);
static final HashMap memoized_results = new HashMap();
{
memoized_results.put(BigInteger.ZERO, BigInteger.ZERO);
memoized_results.put(BigInteger.ONE, BigInteger.ONE);
}
/** The classic recursive implementation */
public BigInteger fib_rec(BigInteger n) {
if (n.compareTo(BigInteger.ZERO) < 1) {
return BigInteger.ZERO;
} else if (n.compareTo(BigInteger.ONE) == 0) {
return BigInteger.ONE;
} else {
return fib_rec(n.subtract(BigInteger.ONE)).add(fib_rec(n.subtract(TWO)));
}
}
/** Trading a little memory for more speed.<br>
More precisely the size of a HashMap plus n * the size of two BigInteger instances.
*/
public BigInteger fib_memoized(BigInteger n) {
if (n.compareTo(BigInteger.ZERO) < 1) {
return BigInteger.ZERO;
} else if (!memoized_results.containsKey(n)) {
memoized_results.put(n, fib_memoized(n.subtract(BigInteger.ONE)).add(fib_memoized(n.subtract(TWO))));
}
return (BigInteger)memoized_results.get(n);
}
/** Forget about recursion altogether, and calculate fib iteratively.<br>
This is the fastest approach of the three.<br>
As an added bonus it does not need a big stack to calculate fiboniac of large values of n.<br>
It calculates fib(1000000) in 295 seconds on my machine (Athlon MP 1900+ Linux, JDK 1.4.2)
*/
public BigInteger fib_iterative (BigInteger n) {
BigInteger a = BigInteger.ZERO;
BigInteger b = BigInteger.ONE;
while (n.compareTo(BigInteger.ZERO) == 1) {
n = n.subtract(BigInteger.ONE);
BigInteger a_temp = a;
a = b;
b = b.add(a_temp);
}
return a;
}
public static void main (String[] args) {
BigInteger n = new BigInteger("10");
/*
// now the fun begins. Pick larger values
// The recursive approach starts taking a _long_ time around n > 40
// memoization (and recursion btw.) will blow the stack at some point depending on the stack size
BigInteger n = new BigInteger("20");
BigInteger n = new BigInteger("30");
BigInteger n = new BigInteger("40");
BigInteger n = new BigInteger("50");
BigInteger n = new BigInteger("100");
BigInteger n = new BigInteger("1000");
BigInteger n = new BigInteger("10000");
BigInteger n = new BigInteger("100000");
// fib_iterative runs in 295 seconds on my machine for n = 1E6
BigInteger n = new BigInteger("1000000");
*/
long before;
// if you have plenty of time then uncomment this block for n > ~40
before = System.currentTimeMillis();
System.out.println(new Memoize().fib_rec(n));
System.out.println("recursion took" + (System.currentTimeMillis() - before) + " ms.");
before = System.currentTimeMillis();
System.out.println(new Memoize().fib_memoized(n));
// new Memoize().fib_memoized(n); // use this one for large values of n
System.out.println("memoization took " + (System.currentTimeMillis() - before) + " ms.");
before = System.currentTimeMillis();
System.out.println(new Memoize().fib_iterative(n));
//new Memoize().fib_iterative(n); // use this one for large values of n
System.out.println("iteration took" + (System.currentTimeMillis() - before) + " ms.");
}
}
[/nobr]
two comments:
first: the execution of the vanilla recursive Fib algorithm run on the number N requires Fib(N) steps. Since Fib(N) is exponential in N, the recursive Fib has an exponential runtime and no surprise works quickly only for very small N.
To see that it is exponential notice what you are doing when you evaluate it for some small numbers
F(0) = 1 // this come directly -- takes 1 step
F(1) = 1 // also comes directly -- takes 1 step
F(2) = F(1) + F(0) = 1 + 1 -- adds 2 numbers
F(3) = F(2) + F(1) = (F(1) + F(0)) + F(1) = (1 + 1) + 1 = 1+1+1 adds 3 numbers
F(4) = F(3) + F(2) = (F(2) + F(1)) +(F(1) + F(0)) = ((F(1)+F(0))+F(1)) + (F(1)+F(0)) = 1 + 1 + 1 + 1 + 1 = add 5 ones
Basically the recursive Fib routine is a way to count to Fib(N) by repeatedly adding 1, yes you will add numbers bigger than one but you did it like this: add one to one to get 2. now add 1 to two to get 3. now remember that while you add one to one to get 2. now add the 2 to the 3 to get 5. you just did 4 adds to get up to 5. Not efficient.
One view of the problem is that you are continually evaluating the same subproblems over and over. For example in the calculation of F(4) it broke into F(3) plus F(2) which requires me to evaluate F(2) BUT the subproblem F(3) also required me to evaluate F(2) when I broke it down.
That is what the first comment was saying, it just said it from the top down. The vanilla recursive routine will solve the same problem over and over and over. When you do F(100) you figures out F(5) in the branch comming from F(99) and also from the branch of F(98) but even worse, you figured out F(5) in both branches comming from the breakdown of F(99) into F(98) and F(97) as well as both branches from the F(98) which broke into F(97) and F(96) so thats 4 times and the process goes on and on, you are evaluating an exponential number of F(5) as you go to larger N.
Look up Dynamic Programming in any Algorithms textbook and they will list the memoization as the standard way of eliminating this problem from the class of Recursive functions that share this particular problem. The trick is simply to never do the same subproblem twice. When you compute Fib(5) once, if you need it again, just look it up in a table rather than recursively compute it.
Using that trick, which was shown by another poster, you turn the problem from exponential to linear (except for the fact that doing arithmetic on BigIntegers is not itself linear, one single addition takes a longer time as the length of the numbers increases)
When you use that method to compute F(100) it still breaks down into F(99) + F(98) since neither of these exist it must recurse to (F(98) + F(97)) + F(98) and that is where you win. You will only actually compute one of those F(98) the other you read out of a table.
The morale of the story is not that recursion or even double recursion is bad, the morale is that exponential runtime is bad and if you aren't careful it is easy to build exponential runtime algorithms.
Now Comment Number 2:
The recursive algorithm has exponential runtime, the iterated algorithm has linear runtime, Do you know the Order LogN algorithm?
Here it is - (not in Java, sorry, just in math) Let M be the 2x2 matrix
0 1
1 1
and look a what you get when you apply that matrix to some arbitrary 2 element vector
(a, b) x M = (b, a+b)
pretty awesome, eh? If you think of the vector as being the last two elements in a fib series, the matrix M shifted you over one notch. The series goes a, b, a+b, b+(a+b) .... each multiplication by M shifts you one step further in the series.
so to compute Fib(n) you basically look at (1,1) x M^n
if you want the millionth fib number you just raise M to the millionth power and there you are. The logN speed up now happens because you can raise to integer powers in log N time.
First you note that if you multiply M*M you get M^2. If you multiply that result by itself you get M^4, by repeated squaring you get all the powers of two very rapidly. Now if you represent the exponent, n, in binary, you will see that it is just a list of the powers of 2 that you need to multiply together to get the final result.
There you have it. The Order LogN Fib algorithm. Way faster than linear.
Is there an even better one? Technically, yes, A brief glance at the CRC standard Math tables tells us that there is an exact formula for the Fib numbers, namely:
F(n) = 1/sqrt(5)(((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n )
So just punch that into your calcualtor and there you have it O(1). Of course, you must be sure to carry out the square root calculation to enough digits of precision that you get the right answer. And by the time you deal with the realities of dealing with long long numbers you are back up to taking actual seconds to get your results.
Enjoy!
Is there an even better one? Technically, yes, A brief glance at the CRC standard Math tables tells us that there is an exact formula for the Fib numbers, namely:
F(n) = 1/sqrt(5)(((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n )
exact and floating point math does not mix well ;-)
Try implementing the function and running it against one of the non-floating point implementations a range of values of n say for n = 0..100 and see how often the results differs in the lover digits.
floating point? who said anything about floating point? I wrote a mathematical expression which is a statement about the real numbers, which are mathematical entities that are not the same thing as floating point numbers. The exact formula is exact. I was not implying an implementation in floating point.
It is a common mistake among programmers who have neither experience in scientific programming or numerical analysis to assume that you can just translate any random math formula into floating point numbers and get a numerically valid result.
If you want to get numerical results from the mathematical expression you must do as I said and use sufficient precision to get the results you want, and when you are talking millions of digits, yes, you are correct a trivial floating point implementation will not get exact results once you get beyond the limits of the precision.
However before you go slamming floating point for being non exact, go ahead and do this little exercise. Open up the standard Windows calculator and put it in scientific mode.
punch the buttons: 5 x^y .5 + 1 = / 2 = x^y 100 = / 5 x^y .5 =
and compare the number you get to the value that an earlier posters listed for fib(100). Is that close enough for you?
There is no problem getting exact results from floating point arithmetic, you just have to know what you're doing.
Thanks for your time to show me different example, it is very helpfull for me to see different method.
Thanks for your analysis, it is very clearly.
Will you please provide a piece of java source code that implements your formula in a way that gives exact results.
Preferably an implementation that is not sufficiently more complicated mathematically or programming vice than the other code snippets posted in this thread, so it will be understandable for people with the level of experience you can expect for people originating, following or contributing to this thread or similar threads on this forum.
By publishing such an implementation you can teach people that it is indeed possible both theoretically and in practical programming to do what you suggest doing. By only stating the formula without any further explanation as to how to implement it, you are misleading the newbies on this forum into beleiving either that it will lead to exact results when implemented the strait forward way ie. floating point, or that formulas like it are bound to yield inexact results but do so very fast.
Here is the trivial code that just uses floats directly. As you can see, it gives exact results up to about fib(70) at which point the precision of the double is insufficient to keep giving valid results.
if I wanted to go further, I would replace the doubles in this routine with BigDecimals so that I could get greater floating point precision and it would work exactly the same, except that since there is not a Math.sqrt routine that works on BigDecimal, I would need to write a square root routine and similarly since there is no pow routine, I would also need to write a raise to a power routine. In addition I would need to write a routine that would determine the precision necessary to carry out the calculation, The quick and dirty way being to loop over increasing precisions until the extra precision is not changing the result.
Of course by the time you write all that code, you have invested real time in code writing and code debugging AND more importantly, without a more sophisticated means of determining the proper precision, I have taken a supposedly direct method that was supposed to be a constant time algorithm and turned it into something that probably runs on the order of N which is not much better than the matrix algorithm that I gave which is much simpler to understand and implement.
If you look back to my first post, I threw out the direct calculation NOT as a practical method of evaluating fib but rather as a theoretically faster big O means of calculation. In theory the direct method is O(1) constant time. In reality just constructing the value of SQRT(5) out to N decimal places requires doing some form of Newton Raphson convergence and will require at least N operations if not NlgN or something like that. I haven't done the actual analysis and don't intend to.
A lot of the BIG O stuff is bullshit, that is why they wave their hands and say "forget all the constants like kN^2 + c it is just order N^2" it is an approximation. The analysis typically assumes that you can do a multiplication in ONE step. This is true for every number up to the machine size and then that assumption starts to fail. Big O is just one tool of many, in the analysis of algorithms, Expected performance is at least as useful as Worst Case performance.
What I was trying to do in my original post was to show the very nice matrix formulation for the fib series, a trick that converts a linear algorithm to an NlgN, and a trick that works mutatis mutandis for nearly any simple linearly defined recursive function. I tossed off the direct calculation as a theoretical result, because that is the nature of all the little Big O discussions, they are all Math results, are all theory, and are not necessarily practical, and that is why I pointed out that precision problems that exist in trying to do the direct solution. The direct solution is not really direct from a code stand point. I was not trying to suggest it as practical.
Anyway, here is the code that shows that the direct value actually works. (If you look closly, you will see that I did not even implement the formula that I passed on earlier, I only put in about half of that. I leave it as an exercise to the analytically minded to determine why it was safe for me to throw out half of the expression and what the consequences are for this calculation, and yes, I used to teach calculus in college and always leave some exercise for the reader)
public class Fib {
public static void main(String[] args){
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
double phi = (Math.sqrt(5.0) + 1)/2.0;
double sqrt5 = Math.sqrt(5.0);
for(int i = 0; i < 100; i++){
// a&b used to iteratively compute fib
BigInteger temp = a;
a = b;
b = temp.add(b);
// floating point calculation does it directly
// .. up until the precision of the double causes it to fail
double exact = Math.round(Math.pow(phi,i+2)/sqrt5);
// print the values computed in the two different ways.
System.out.println(i+2 + ":" + a + " " + exact);
}
}
}
intial portion of output is:
2:1 1.0
3:2 2.0
4:3 3.0
5:5 5.0
6:8 8.0
7:13 13.0
8:21 21.0
9:34 34.0
10:55 55.0
11:89 89.0
12:144 144.0
13:233 233.0
14:377 377.0
15:610 610.0
16:987 987.0
17:1597 1597.0
18:2584 2584.0
19:4181 4181.0
20:6765 6765.0
21:10946 10946.0
22:17711 17711.0
23:28657 28657.0
24:46368 46368.0
25:75025 75025.0
26:121393 121393.0
27:196418 196418.0
28:317811 317811.0
29:514229 514229.0
30:832040 832040.0
31:1346269 1346269.0
32:2178309 2178309.0
33:3524578 3524578.0
34:5702887 5702887.0
35:9227465 9227465.0
36:14930352 1.4930352E7
37:24157817 2.4157817E7
38:39088169 3.9088169E7
39:63245986 6.3245986E7
40:102334155 1.02334155E8
41:165580141 1.65580141E8
42:267914296 2.67914296E8
43:433494437 4.33494437E8
44:701408733 7.01408733E8
45:1134903170 1.13490317E9
46:1836311903 1.836311903E9
47:2971215073 2.971215073E9
48:4807526976 4.807526976E9
49:7778742049 7.778742049E9
50:12586269025 1.2586269025E10
51:20365011074 2.0365011074E10
52:32951280099 3.2951280099E10
53:53316291173 5.3316291173E10
54:86267571272 8.6267571272E10
55:139583862445 1.39583862445E11
56:225851433717 2.25851433717E11
57:365435296162 3.65435296162E11
58:591286729879 5.91286729879E11
59:956722026041 9.56722026041E11
60:1548008755920 1.54800875592E12
61:2504730781961 2.504730781961E12
62:4052739537881 4.052739537881E12
63:6557470319842 6.557470319842E12
64:10610209857723 1.0610209857723E13
65:17167680177565 1.7167680177565E13
66:27777890035288 2.7777890035288E13
67:44945570212853 4.4945570212853E13
68:72723460248141 7.2723460248141E13
69:117669030460994 1.17669030460994E14
70:190392490709135 1.90392490709135E14
71:308061521170129 3.0806152117013E14
72:498454011879264 4.98454011879265E14
73:806515533049393 8.06515533049395E14
74:1304969544928657 1.30496954492866E15
75:2111485077978050 2.111485077978055E15
76:3416454622906707 3.416454622906716E15
77:5527939700884757 5.527939700884772E15
78:8944394323791464 8.944394323791488E15
79:14472334024676221 1.447233402467626E16
80:23416728348467685 2.3416728348467748E16
Thanks for your clarification, I feel it will help the readers of this thread understand that doing calculations like fib using floating point and getting exact results is no easy matter.
You need a mathematical way of figuring out how much precision you need and how much precision a certain implementation will give you. ie. the trivial implementation using java doubles will not even be able to calculate fib(n) correct for all values of n in in 0..100 .
You also need the mathematical know-how needed to rearrange your formula to better take advantage of the hardware floating point system provided by the cpu and runtime libraries. It followes by implication that you need an intimate knowledge of the floating point system and libraries as well.
You also need to know a handfull of floating point algorithms and datastructures by heart so you can either roll your own floating point implementation suited for the purpose at hand or use your knowledge to locate a 3.party implementation that will suit your purposes.
All in all this is something you can only expect of a small number of people who spent several years of their enginering/mathematics/physics degree work studying exactly this area.
