Fibonacci Sequence

[tennispro9911]

A bad computer slows it down by a linear multiplier. Say if my computer is 2.0 Ghz and your computer is 200 MHz then it would take your comp about 10 times longer to run the same program, depending on things running in the background. I doubt your computer is slower than 200 MHz, so if it takes a whole night to run, then it would still take an hour or so to run on a "fast" computer. That said, obviously if you don't calculate every term in between, you can calculate the nth term much much faster, which is why I could calculate the millionth in 29 sec instead of a few hours.

[tennispro9911]

I used Java. I used the BigInteger class. Otherwise I would have roundoff errors as you said.

[ComradeNikolai]

Ah, yes, Java. I should learn that sometime... after I finish learning C++ and learn Python. Maybe if I hook myself up with the AP CS exam next year, I'll be motivated enough to learn Java (our school doesn't offer AP CS, but I was able to take AP English without the class this year, so I don't see a difference there).

What kind of hardware do you have on the computer you did that on?
Oh, just FYI, I think the computer I did this on originally has 256 MB RAM and less than a 1 GHz processor... not fun...

[tennispro9911]

I'm on a Lenovo laptop right not. T40. 1 GB RAM, 1.59 GHz processor. So its not the latest and greatest, but at the same time it works well, and faster than your machine. My home desktop is better. I'm going to run it on that and see what happens. For kicks I'd see how high I can get. I got to the 10,000,000th term in about 37 minutes, and I'm guessing it would take around 50 hours to get to 100,000,000 if the pattern continues.

[ComradeNikolai]

Try the 100 000 000 and post the results... THAT would take a lot of text documents.

[tennispro9911]

I'll try to. I think I found a way to make my program significantly faster. With a new algorithm and my desktop computer it took ~9 sec to get the millionth term and 3:22:000 for the 5,000,000th. I'll try 100 mil. My guess is about 15-20 hour run time.

[Ian Curtis]

Originally Posted by tennispro9911

I'll try to. I think I found a way to make my program significantly faster. With a new algorithm and my desktop computer it took ~9 sec to get the millionth term and 3:22:000 for the 5,000,000th. I'll try 100 mil. My guess is about 15-20 hour run time.

If you're going for speed, wouldn't it be a little bit faster to just use the explicit definition?

[tennispro9911]

I tried that, but it didn't work for me, with such large numbers. Feel free to see if you can get it to work yourself.

[ComradeNikolai]

Would you care to share this new algorithm? I'm interested to see it.

[bobwrit]

I found a mathimatical function to define it, thus eliminating recursion. Have fun...

((x^n)-(-x)^(-n))/sqrt(5)

where x is (1+sqrt(5))/2 and n is the Nth term of the sequence.