Fibonacci Sequence

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

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?