Fibonacci Sequence

[ComradeNikolai]

Well, suffice it to say I was bored, so I wrote a little (5 line) python program to calculate terms of the Fibonacci sequence.

The 1001th term is:
70330367711422815821835254877183549770181269836358 73274260490508715453711819693357974224949456261173 34877504492417659910881863632654502236471060120533 74121273867339111198139373125598767690091902245245 323403501

It's still computing the 1000 000th term or I'd have that for you, too. It has 110 000 terms to go.

[tennispro9911]

I believe that is the 1001th term, not the 1000th term.

The 1000th term is 43466557686937456435688527675040625802564660517371 78040248172908953655541794905189040387984007925516 92959225930803226347752096896232398733224711616429 96440906533187938298969649928516003704476137795166 849228875.

[whitetiger0990]

Can your 5 lines of python beat my 3 lines of perl? =P

use bignum;
$b=1;
$x++,($a,$b)=($b,$a+$b),print"$x|$a\n"while(1);

And tennispro9911 is right, I think you forgot that the first two numbers in the series is '1'.

Can we see your program? =]

(I like perl *glances at his signature =D*)

[ComradeNikolai]

Oh, yeah, my bad; it is the 1001th term. That makes the one my computer chugged all night for the million and first term, and it was bigger than the gnome terminal can display :yikes: ... so I don't have it.

Here's the program, as requested
#! /usr/bin/python
a,b,c = 0,1,1000
while c > 0:
a,b,c = b, a+b, c-1
print b
c could be modified to get any given term, adjusting for the first term already being calculated. I'm not sure if there's a more efficient way of doing this in Python, just started learning it.

Perl impresses me.

[EricVanWyk]

Python can do it in 1:

for z in range(N-1): print vars().setdefault('a',[1,1]) and a.append(a.pop(0)+a[0]) or a[0][0]

Stolen shamelessly from Bengt Richter. Put your term in place of N.

That being shown, this is the antithesis of the language and good coding practice. As one who has had to work with tools coded in Perl, all I will say is that obfuscation isn't nearly as cool as perlers think it is. I'd rather work with something written in a hundred lines of python than in 5 lines of perl.

[tennispro9911]

I did it in java, because thats what I use regularly, along with Easy C for FIRST. I think though I can write a program that can find the millionth term that runs in only a couple minutes. I'll test it out later.

I also need to output to a file instead of a screen.

[ComradeNikolai]

Mine probably could run in less than hours or a few minutes, but I had a horribly bad computer which I was using it; Windows 98 lags the computer, so it's running Ubuntu.

[tennispro9911]

The millionth term is way too long to display. I tried, took up a couple thousand lines on my browser. I also can't include a file in the post because the limit for a txt file is 100 kb and my file is 204.1 kb. For anyone who wants to check if their program works correctly, the first few digits are 195328212870775773163201494759625.....

It took me 0:29:843 (min:sec:millis) to calculate it, and 1:21:467 total to calculate it and output it to a file. The number is so fricken large it took longer to write it to a file. How often can you say that?

[tennispro9911]

So I changed my program to break up the files to about 90 kb each file. Here are my files. First one contains first x digits and so on and so forth. 90k digits in the first two files.

[ComradeNikolai]

What language did you use for that? I would try it in C++, but I know that C++ has roundoff due to not allowing such large numbers...

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

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

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