This week's book giveaway is in the OCMJEA forum. We're giving away four copies of OCM Java EE 6 Enterprise Architect Exam Guide and have Paul Allen & Joseph Bambara on-line! See this thread for details.

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???

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.

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.

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

Joined: Jan 09, 2008
Posts: 525

posted

0

Running your code, a bit modified (for a 10 digit result) gave the following output:

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.

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.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

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).

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

Joined: Jan 09, 2008
Posts: 525

posted

0

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 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.

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

Joined: Jan 09, 2008
Posts: 525

posted

0

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.

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.

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

Joined: Jan 09, 2008
Posts: 525

posted

0

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 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

Joined: Mar 05, 2008
Posts: 3012

10

posted

0

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?

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.

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

Joined: Mar 05, 2008
Posts: 3012

10

posted

0

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

Joined: Oct 13, 2005
Posts: 38509

23

posted

0

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:

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

Joined: Mar 05, 2008
Posts: 3012

10

posted

0

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.

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

Joined: Mar 05, 2008
Posts: 3012

10

posted

0

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.

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

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here

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.