Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!

# Project Euler Problem 25

rajarshi roy
Greenhorn
Posts: 21
I was trying problem 25 given in the site Project Euler .

It goes like this

The Fibonacci sequence is defined by the recurrence relation:

F_(n) = F_(n−1) + F_(n−2), where F_(1) = 1 and F_(2) = 1.

Hence the first 12 terms will be:

F_(1) = 1
F_(2) = 1
F_(3) = 2
F_(4) = 3
F_(5) = 5
F_(6) = 8
F_(7) = 13
F_(8) = 21
F_(9) = 34
F_(10) = 55
F_(11) = 89
F_(12) = 144

The 12th term, F_(12), is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Now here I have a problem.No data type that I know can hold a number 1000 digit long..Anyways,I wrote a code

Evidently,this code cannot compute what I want,simply because the data type is not suitable to hold such a huge number.So,what can I do to deal with this kind of situation and get the desired output???

Rob Spoor
Sheriff
Posts: 20605
60
BigInteger is capable of storing integer (i.e. non-fractional numbers) of any size. You can switch to that, or throw an exception. C# does the latter unless overflowing is enabled.

If you want to throw an exception, either throw ArithmeticException or a custom subclass of it.

Jim Hoglund
Ranch Hand
Posts: 525
First, the return value for n < 3 should be 1 rather than n. Also, rather
than implementing the recurrance relation directly, which recalculates
the entire sequence for each call, you should keep track of intermediate
values.

Jim ... ...

Rob Spoor
Sheriff
Posts: 20605
60
There are at least 4 ways of calculating fib(n) and this is the best known but also the slowest, as it is quadratic in the number of calls to fib.
Other ways are the linear algorithm Jim is referring to, a logarithmic algorithm that is based on a matrix form, and then there is the approximation formula. See Fibonacci number for more info.

Jim Hoglund
Ranch Hand
Posts: 525
Running your code, a bit modified (for a 10 digit result) gave the following output:

x=46 fib(x)=1134903170 calls=5942430100Jim ... ...

Ulf Dittmer
Rancher
Posts: 42968
73
I think using BigInteger is a bit against the spirit of those problems. You could use an array of a 1000 ints, each representing one digit, and implement addition on top of that.

Garrett Rowe
Ranch Hand
Posts: 1296
Ulf Dittmer wrote:I think using BigInteger is a bit against the spirit of those problems. You could use an array of a 1000 ints, each representing one digit, and implement addition on top of that.

I respectfully disagree. I think the spirit of this problem is that there is an easy to see 'naive' algorithm which may not terminate for many hours (or days maybe, I haven't done the math) and there is a less obvious algorithm that will return relatively instantaneously. The fact that a Java int is only 32 bits is a language implementation detail that is outside the scope of the problem. In some languages the algorithm and the the way the method (function? / procedure?) is called won't even change, all that you have to do is change the type ascription from Int to Integer.

Henry Wong
author
Marshal
Posts: 21373
84
I really really recommend that you don't do the fib calculation recursively. Instead, just hold the last two fib values, which you can then use to calculate the next value -- by just adding, move the fib to the prevfib, and the new value into place.

This way, you can calculate the fib and check the length as you go along. For example, to calculate the fib of 4782, I can do it in a single loop of that many iterations and check the size while doing so. To do so recursively, you will need a ridiculous number of fib() calls, which is then in a loop to check the length to get to 4782.

The first algorithm can take seconds while the second can take minutes (or even hours).

Henry

Campbell Ritchie
Sheriff
Posts: 49733
69
Rob Prime wrote:There are at least 4 ways of calculating fib(n) and this is the best known but . . . it is quadratic in the number of calls to fib. . . .
Surely exponential? 1.618^n where n is the ordinal number in the best-known Fibonacci series.

There are potentially other Fibonacci series which don't begin 1, 1, but we can ignore them for the purpose of this exercise.

Jim Hoglund
Ranch Hand
Posts: 525
Here is an algorithm that works pretty well up to f(103). You will see
that f(104) overloads long and is truncated. Now, on to 1000 digits.Jim ... ...

Rob Spoor
Sheriff
Posts: 20605
60
Campbell Ritchie wrote:
Rob Prime wrote:There are at least 4 ways of calculating fib(n) and this is the best known but . . . it is quadratic in the number of calls to fib. . . .
Surely exponential? 1.618^n where n is the ordinal number in the best-known Fibonacci series.

Whatever. An exploding number of calls, that's good enough for me.

Paul Clapham
Sheriff
Posts: 21298
32
Garrett Rowe wrote:I respectfully disagree. I think the spirit of this problem is that there is an easy to see 'naive' algorithm which may not terminate for many hours (or days maybe, I haven't done the math) and there is a less obvious algorithm that will return relatively instantaneously.

Indeed. There's a one-liner for this problem which doesn't require calculating any Fibonacci numbers.

Jim Hoglund
Ranch Hand
Posts: 525
Boy, I would sure like to see that "one liner." Anyway, the answer is f(4787) and the
code below gets you there quite quickly. It's linear of course. I did the adds across
a pair of StringBuilder objects of 1000 characters and exit when they overflow. I forgot to mention that the result strings are reversed with the 10^0
column on the left. I didn't bother to flip them around.

Jim ... ...

Rob Spoor
Sheriff
Posts: 20605
60
What's that 48 doing there? Oh wait, that's '0'

Sahil Kapoor
Ranch Hand
Posts: 316
I think for such problems you need not really to find fiboneci number.

Like, i encountered one similar problem which goes like this :-

Find the number of zero's in 276 ! ie 276 factorial.

In order to answer this we need not to calculate factorial of 276 , infact there is certain mathematic logic which quickly finds answer to such problems.
I am indeed sure that this problem also belongs to such similar category. I think topics in Number theory could help to solve your problem.

Thanks
Cheers!!!

Henry Wong
author
Marshal
Posts: 21373
84
Jim Hoglund wrote:Boy, I would sure like to see that "one liner." Anyway, the answer is f(4787) and the
code below gets you there quite quickly.

I actually got a different answer -- which I actually hinted at in a post a few days ago. My answer is...

x = 4782
fib (x) = 10700662663827589367649805844573968850836838966321516650132352033753145206046940406218891475824897926578046948881775
919574843364666725699595129960304612627480924821861440694330512347744427502737817530875793916661921492591867595539664228371
489431130746995034395470019854326097230672901928705264472437261177158218255484911205250132014786129659313817922355596574520
395061375514678375432291196021299340482607061753977068470682028954869026661854351245219003694806413574474709117076197669456
910700980243934396174741037369125032313655321647736970231677550515951735184605799549194109677783732296657965816465139034881
542563101842241902598460880001101862555502454939371136516570394476295847145485234259504285824253060835444354282126110089928
637950480068943303097732178348645431132057656598684562886168087186938352973506439862976406600007235629179052070511640776148
124918858309459405666883391093509444565763576661516193177537928916615813271596168774879838218204925203484738743847367719345
12787029218636250627816

Henry

Mike Simmons
Ranch Hand
Posts: 3090
14
Jim's answer is the first Fibonacci number >= 10^1000. Henry's is the first >= 10^999. Since the problem asked for 1000 digits, and 10^999 is a one followed by 999 zeroes, for 1000 digits total... Henry's answer is correct for the problem as stated.

Jim Hoglund
Ranch Hand
Posts: 525
Okay, since I didn't really wring out my code, I will gladly concede victory to Henry.
But Henry, let's see your algorithm. That's more interesting anyway. If anyone cares,
I can explain how I developed mine, and clean it up a bit. This is a great exercise.

Jim ... ...

Henry Wong
author
Marshal
Posts: 21373
84
Jim Hoglund wrote:
But Henry, let's see your algorithm. That's more interesting anyway.

Sure... but I cheated. I used the BigInteger, as I just wanted to get to the result.

Henry

Mike Simmons
Ranch Hand
Posts: 3090
14
Hmmm... looks like the same algorithm I used to check it, with a few cosmetic differences - I just used one main method, and compared against a BigInteger of 10^999 rather than using toString().length(). But I'm curious about the synchronization everywhere, since nothing in the program seems to use threading. Is that just part of your default style now when writing a class? I think it would be hard to use this class in a thread-safe manner without additional synchronization anyway, since there would be no guarantee that getFib() and getFibIndex() would have any particular relationship to each other if another thread could call incFibIndex() in between calls. Am I missing something?

Henry Wong
author
Marshal
Posts: 21373
84
Mike Simmons wrote:But I'm curious about the synchronization everywhere, since nothing in the program seems to use threading. Is that just part of your default style now when writing a class? I think it would be hard to use this class in a thread-safe manner without additional synchronization anyway, since there would be no guarantee that getFib() and getFibIndex() would have any particular relationship to each other if another thread could call incFibIndex() in between calls. Am I missing something?

That's just habit. Sometimes I don't even know that I am doing it -- such as in this case. But, at least, when classes do become used in a threaded manner, I also have the habit of reviewing and refactoring the stuff too.

Henry

Ashish Schottky
Ranch Hand
Posts: 93
After reading this problem, it appears to be more difficult than it really is.
I found the answer by working it out in paper and pencil and yes ofcourse with calculator.
Here is what I did.

Consider the golden ratio as (1+sqrt(5))/2=phi
Comparin the number of digits to power of 10, we can see in general will have x digits.
So any number which has 1000 digits will be greater than 10**999.

nth fibonacci number is given by
phi**n/sqrt(5) . SO according to our conditions:
phi**n/sqrt(5) > 10**999
solving this inequality gives us n=4782.

And here is the program:

Mike Simmons
Ranch Hand
Posts: 3090
14
Well, that does give the right answer to the stated problem. But in my opinion, that's just luck. The problem is that your equation
nth fibonacci number is given by
phi**n/sqrt(5) .

is only approximately correct. It's a nice approximation, but you can't trust it to be exact. It's tempting to think it's "good enough" for large enough values of n, but it isn't really. Even when we're solving for n and rounding down, which can eliminate much of the error in this formula, but not all. Your prorgram based on this formula happens to give the correct solution for digits = 1000, and digits = 1001 for that matter - but it gives incorrect results (off by one) for digits = 999, or digits = 1002. And many more. Here's a demonstration:

Campbell Ritchie
Sheriff
Posts: 49733
69
Nice solution, Mike, which when I tried it gave two wrong three right two wrong three right etc. I presume that is simply coincidence.

I thought, has that anything to do with the imprecision of floating-point arithmetic? So I tried it with Speedcrunch, which works to 50 digits, and got these results:
(999 + log(5) / 2) / log((sqrt(5) + 1) / 2) = 4781.859270753068860133
I got the results
990: 4734
991 4739
992 4744
993 4748
994 4753
995 4758
996 4763
997 4768
998 4772
999 4777
1000 4782
1001 4787
1002 4791
1003 4796
1004 4801
1005 4806
1006 4811
1007 4815
1008 4820
1009 4825
So it would not appear that arithmetical imprecision is the culprit. If you try the formula with rounding up in all instances, it might work better. Try changing line 33 to
int n = (int) ((power + Math.log10(divider)) / Math.log10(phi)) + 1;

Mike Simmons
Ranch Hand
Posts: 3090
14
Campbell Ritchie wrote:If you try the formula with rounding up in all instances, it might work better. Try changing line 33 to
int n = (int) ((power + Math.log10(divider)) / Math.log10(phi)) + 1;

Good call. This appears to give correct solutions for all digits > 1. (At least to the limits of the datatypes, which is more than enough for this application.) Apparently I was mistaken about how good an approximation that formula is.

Luigi Plinge
Ranch Hand
Posts: 441
Jim Hoglund wrote:Boy, I would sure like to see that "one liner."

This is it as a 1-liner, if you have very long lines, and don't care for readability.

But... uh, if I wanted to write concise code I wouldn't be doing it in Java!Finds the correct (exact) answer in 0.69 seconds.

Mike Simmons
Ranch Hand
Posts: 3090
14
Um, I believe Jim H was referring to this previous comment:
Paul Clapham wrote:There's a one-liner for this problem which doesn't require calculating any Fibonacci numbers.

This could well be a reference to the phi-based solution that Ashish put forward, with Campbell's corrected rounding. Though I think it does still require some justification in terms of accuracy, since the formula is still an approximation. How do we know it's really "good enough", without actually checking the Fibonacci numbers? (Not that such justification isn't possible - I'd just like to know what exactly it is.) Or perhaps Paul was referring to something else entirely.

Shamsudeen Akanbi
Ranch Hand
Posts: 85
1
Feeling guilty.... Anyway thanks a lot Henry.

Winston Gutkowski
Bartender
Posts: 10492
64
Luigi Plinge wrote:This is it as a 1-liner, if you have very long lines, and don't care for readability.

And my answer to that is this (writted a while ago by me own fair hand):

Newlines are for namby-pambies
Indentation too
Spaces for the faint of heart
So which of those are you?
Real coders know the score
that nothing could be finer
than to compress all their thought
into a one-liner.

Winston

Ivan Jozsef Balazs
Rancher
Posts: 981
5
Mike Simmons wrote:
is only approximately correct.

Let f denote (1+sqrt(5))/2 and g denote (1-sqrt(5))/2.
We observe f**2 = (1+5+2.sqrt(5))/4 = (3+sqrt(5))/2 = 1 + f and similarly
g**2 = (1+5-2.sqrt(5))/4 = (3 - sqrt(5))/2 = g + 1
So f and g are solutions of the equation h**2 = h + 1.

Now if h**2 = h + 1 then multiplied with h**n,
h**(n+1) = h ** ( n+1) + h**n
that is, the series h**n satisfies the same recursion as the Fibonacci series.
So any liner combination satisfies the same recursion, given its being linear.

Let us now consider this linear combination

G(n) = (f**n - g ** n) / sqrt(5)

For n=1, G(1) = (f-g)/sqrt(5) = 1
For n=2, G(2) = (f**2 - g**2 )/sqrt(5) but f and g both satisfy h**2=h+1, so
G(2) = (f+1 - (g+1)) / sqrt(5) = (f-g)/sqrt(5) = 1

That is, the above G series satisfies the recursion equation of the Fibonacci series, and they even coincide on n=1 and n=2.
So they are equal.

So G(n) yields a closed formula for F(n), with the main term (f**n)/sqrt(5) giving a much stronger approximation than asymptotic, because
the difference is g**n / sqrt(5), with g being between -1/2 and -1, so its powers alternate in the sign and rapidly tend toward zero.

Steve Fahlbusch
Bartender
Posts: 605
7
Very Nice..... Thanks