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.

Technology can never substitute for knowledge.

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

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

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

Technology can never substitute for knowledge.

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 ]

Technology can never substitute for knowledge.

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.

When I tried the exponential formula it gave fib(10) = 55.004.

Everything has got its own deadline including one's EGO!

[CodeBarn] [Java Concepts-easily] [Corey's articles] [SCJP-SUN] [Servlet Examples] [Java Beginners FAQ] [Sun-Java Tutorials] [Java Coding Guidelines]

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

*n*) time . . .

. . . but I can't understand it

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

Technology can never substitute for knowledge.

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

*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

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 ]

Technology can never substitute for knowledge.

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?

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.

Technology can never substitute for knowledge.

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.

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

Technology can never substitute for knowledge.

Sheriff

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

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

It is sorta covered in the JavaRanch Style Guide. |