This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.

Is there a way to do this? I just programmed the fibonacci sequence using a simple loop, however, after 91 iterations with a 'long' data type, it dies (well, keeps going into the negative and then into the positive, back and forth, etc), and with a double it ends up at "infinity" after awhile.

I know the huge super computers do a lot with calculating pi to some obscene digit, and someone said he calculated fibonacci to the 10 millionth digit using a C++ program, and it took 31 hours to compute on a 1.6GHz machine. So my question is, is there a way to get around the arcitecture problems with 64 bit and get to numbers that surpass that, somehow?

Does it require additional programming and figuring out how to add integers together and put them together in a long string (easy part, of course, the math for it might be harder), or is there something else?

A friend I know used the BigDecimal class for his pi computing, but even that has limitations.

Also, sorry in advance if this belongs somewhere else. I'm not sure if it goes into the I/O thread or advanced questions.

Chris, For the fibonacci sequence, BigInteger seems more appropriate than BigDecimal since you don't have any decimal values involved. I don't think BigInteger has any limit (other than the size of overall memory.)

I didn't even think to see if there was a BigInteger class.

Makes it a few more lines but WHOOT!

I can get to over 5,000 iterations with this, now.

Now I just need to put the stream to a file...

Christopher Young
Ranch Hand

Joined: Nov 02, 2007
Posts: 63

posted

0

As a sidenote, does anyone know how far the fibonacci sequence has been calculated to?

I've gotten it up to the 100,000th digit, and I know it's been done to the 10 millionth, and with some tinkering (read: lots) to my program I'm able to save the data to resume at a later date (though i'll have to make backups because stuff gets screwed if the program terminates for whatever reason) so that I don't have to start from scratch. (take that back, i made it wipe the old data near the end but backups are still good). Are there currently any big-scale projects (like www.mersenne.org) to calculate fibonacci? [ December 27, 2007: Message edited by: Chris Young the second ]

Slightly inaccurate to call it "the" Fibonacci series; there are many different possible Fibonacci series, but the one we usually use is the Fibonacci series beginning with fib(1) = 1 and fib(2) = 1.

You can calculate any Fibonacci number in that series with the formula phi^n/sqrt(5) and rounding to an integer, where phi is the Golden Ratio.

I have tried Fibonacci numbers starting 1 1 with BigInteger, and I got a stack overflow somewhere in the region of n = 8000. Don't know whether using -Xmx would help. This sort of calculation sounds like the sort of thing a general-purpose application language is not really designed for. I have tried the same things as an exercise in the Oz language and it got to fib(10000) in a second or so.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43935

33

posted

0

BTW: When I tried Fibonacci numbers (usual series) I didn't get overflow in a long number until no 92. What are you getting for fib(10)? It ought to be 55. You should start from fib(1) = 1 and fib(2) = 1. There isn't really a fib(0), but you presume it would be 0. When I tried the exponential formula it gave fib(10) = 55.004.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43935

33

posted

0

. . . and when I tried the exponential formula for 10000000 it gave 1.12983437822539976032 E 2089876. I haven't checked it by hand. It is worth finding out how many Fibonacci numbers have been calculated, don't know whether that number could be published.

It's worth noting that although the Fibonacci series is usually defined using a recursive formula, it's quite easy to calculate it in an iterative way, thus preventing any overflow problems.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43935

33

posted

0

As Ulf Dittmer hints, a lot of recursive programming can also be done with iteration. You use the recursive methods so as to become familiar with recursion.

I also know a recursive algorithm for Fibonacci numbers which runs in O(n) time, and I know of an algorithm which runs in O(logn) time . . .

. . . but I can't understand it

Christopher Young
Ranch Hand

Joined: Nov 02, 2007
Posts: 63

posted

0

I stopped trusting recursion onxw my teacher showed me that it can kill a program and suck up memory after we did an exercise with recursion to show us the importance of using proper ways for the recursive function to stop (I'm not saying recursion has no use, I've used it to be fancy, but IMO for things that can be memory intensive things its not a good idea).

So when I built it I was using a simple for loop.

And I get 89 after ten iterations. I start the first value at 0 and the secon at 1. At 9 it is 55. I start the loop off at number 1 (instead of 0), as well. Not 100% sure if that makes a difference (I picked 1 because I know for loops don't add the first time through, so it'd be like getting a count at the number 1, if that makes sense).

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43935

33

posted

0

89 is the 11th Fibonacci number if you start with 1 1. Count them: 1 1 2 3 5 8 13 21 34 55 89. You have got an out-by-one error; maybe the simplest way to correct it is to start with 0 in your loop rather than 1.

Recursion is a nice simple way to sort out some knotty problems, eg

examining the entire file system on a computer.

I had to create a compiler and had to write half of it by hand; when calculating class dependencies I found putting a recursion in the right place sorted all my class dependencies out very simply.

The most efficient sort algorithms (merge and quicksort) are recursive.

So you do need to learn recursion. You always look at the Fibonacci algorithms because they are inefficient when recursing. They have exponential complexity, with O(1.618^n) complexity. Look up 1.618 and see what it has to do with Fibonacci numbers.

It is possible to create an efficient recursive Fibonacci algorithm, and you get a method like thisYes, recursion can be memory intensive, but on a PC with a GB or two of RAM that isn't too serious. It can be simpler and therefore less error-prone, and remember "less error-prone" takes priority over everything else. CR

Christopher Young
Ranch Hand

Joined: Nov 02, 2007
Posts: 63

posted

0

How serious is the out by one error in terms of accuracy over a long period?

Christopher Young
Ranch Hand

Joined: Nov 02, 2007
Posts: 63

posted

0

By that I mean I'm really only missing a few early numbers as far as I can tell (it goes 1, 3, 5, 8, 13, 21, for me), and my question is, with it doing that, will the number I get be accuracte except for its true place in the sequence? Or will I eventually start getting imprecise numbers?

I'm not using any doubles or anything like that.

Of course it would mean if i published the number somewhere I'd have to either get the sequence 100% correct or explain the first few numbers in the sequence... Wouldn't it?

EDIT (because i don't feel like a third post): I just fixed the off by one problem by setting the first value to 1 and the second to 0 (as opposed to the other way around).

I'm still kinda curious on the accuracy thing for integers. If it is off by one in the loop, but accurate otherwise will it stay so? or will it eventually return errornous? After 500,000 iterations it seems ok (just off by one) soI think I've solved my own problem here, but if anyone has input I'd be glad to hear it.

Also, are there any ways to overcome the IO problem I experience after awhile? Writing to a file is simple, however the only method I figured out was to copy the values of the BigInteger objects to a string using their toString() method, which is what eats away a lot of the time (and, incidentally, memory). As I will be running it on a computer with about 112MB ram that might be an issue at some point. Although I do intend to upgrade the ram on that at some point (probaly just feed it my old RAM when i upgrade my main computer). I know one of the toString calls is unneccessary (so i'm taking it out) but is there a way to bypass that step altogether? Because thats the part that gets very memory intensive after awhile.

Other than that IO bound issues are hardware related, correct? [ December 28, 2007: Message edited by: Chris Young the second ]

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43935

33

posted

0

Is an out-by-one error serious? If you ask a mathematician they would tell you that an error of 1 in 1.12983437822539976032 E 2089876 is absolutely disastrous. In cryptography an error of 1 might be disastrous; if you want a prime number and instead get something like 2^873465834, you end up with a public key which can be factorised in a few seconds, and no security in whatever you encrypted.

I know you will find websites where they say fib(0) = 1 and fib(1) = 1, but I think that is mistaken and it ought to read fib(1) = 1 and fib(2) = 1. There probably isn't really such a thing as fib(0), but you can pretend that fib(0) = 0 and get all your calculations to work all right. If you really are getting 1, 3, 5, 8, then you have a serious error somewhere. You are more likely to be getting 1, 2, 3, 5, 8, 13. This is the classical programmer's out-by-one error, where you are one place off in the sequence. Any programmer ought to know how to find and correct that sort of error when using recursion and loops; it is always worthwhile working out a simple example and trying it out (eg fib(10) = 55). You are getting correct Fibonacci numbers starting from 1, 2; the actual values will be the same as Fibonacci numbers starting from 1, 1, but you get to each value one earlier. One cannot tell about the arithmetic without checking 2089877 digits, but I can't see any arithmetical errors anywhere. If you start with fib(1) = 1, fib(2) = 0, you have not sorted your out-by-one, but only shoved it in the other direction. You will end up with a series like this: 1, 0, 1, 1, 2, 3, 5, 8 . . . You see it has the same values but they occur later than normal.

You could only publish values if you can demonstrate that you have something novel, meaning that Fibonacci numbers of that magnitude really are unknown. You would be expected to include details of the algorithm and show the first few members of the series so as to demonstrate you are calculating them right. If you have an out-by-one they would say you are using the algorithm incorrectly. Remember the formula I quoted earlier (phi^n/sqrt(5) and round to the nearest integer) is a lot faster, but might have precision problems using floating-point arithmetic.

As for output to your file, you realise that classes like Formatter have methods which take BigInteger as an argument?

Christopher Young
Ranch Hand

Joined: Nov 02, 2007
Posts: 63

posted

0

Thanks. Actually, the way it works when I print it to the screen is the first ten are (1, 1, 2, 3, 5, 8 13, 21, 34, 55) even though the starting second value is a 0 (which is something I had fixed completely by accident), so its my assumption that the sequence works correctly and would continue to do so, barring any errors on the computer. And it certainly works for the 300th number.

And by publish, you mean an official publication, right? You make it sound like if I was able to do so it'd be a big thing (I was actually just talking about a website somewhere, like a personal thing)? I've run some tests and compared the values I get to outside sources and for other numbers (in the 1000s range) it seems to be working correctly because the numbers I get and the numbers they get seem to match up.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43935

33

posted

0

You're welcome.

Yes, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 is correct for the first ten numbers. If you had an out-by-one you have compensated for it. You ought to check it by printing 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 and 10 55. It would only be worthwhile publishing in a journal or something if you can demonstrate that nobody else has that many Fibonacci numbers. I found this mathematical website where you can get it to calculate Fibonacci numbers. I suspect somebody has already calculated bigger Fibonacci numbers.

Christopher Young
Ranch Hand

Joined: Nov 02, 2007
Posts: 63

posted

0

Where do I find the formatter class for writing BigInteger objects directly to a file?

I can't find it in java.io. Would it be somewhere else?

If you look at the Java API, the lower left frame has a list of all classes it covers. There you can find Formatter. (There's also an index, linked at the top of the page.) However Formatter is unusual in that you usually don't use it directly - you usually use it indirectly through other classes and methods, like String's format() method, or PrintWriter's format() method. You may benefit from reading an article like this one instead.

"I'm not back." - Bill Harding, Twister

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43935

33

posted

0

That article you quoted is very helpful, Jim. Johny: look at the Formatter class in java.util, not java.util.logging.

[edit]Sorry, I am calling Chris Johny. I ought to have read the post properly first. Sorry again.[/edit] [ December 29, 2007: Message edited by: Campbell Ritchie ]