Portable Propeller Based Fibonacci Number Generator

bomber

Using a Basic Stamp version of a Fibonacci number generator, I created a Propeller version. It is able to generate Fibonacci numbers up to 1,836,311,903! It is designed to run off of a C3 (using only TV output and an LED hooked up to pin 15). The code can be easily modified to give output to the PST or VGA output.

EDIT: Rev 1.4 of code released.
The main differencs are as follows:

1) No "magic" numbers
2) Waits for the monitor to 'initalize' (our monitor takes several seconds to realize it is recieving a signal)
3) Increased timing duration

EDIT: Rev 1.5 of code released.
Adds a zero at the beginning of the sequence.

Heater.

Working up to a little over a billion is a bit limiting.
As an exercise can you modify your code such that it's biggest result is limited only by the memory available?
Although I guess the universe might end before it produces that result:)

Heater.

By the way, when your result overflows C will become negative. I would prefer if your end condition test just checked for C less than zero rather than comparing to that "magic number".

bomber

The "magic number" is actually the last number in the sequence before C is negative.

Heater.

I realize that. But that implies that you know your biggest possible result before you run your program. Which implies there is no point to the program because you have done all the work already.
Ok in this case you can run the loop till it fails then patch the number into your source. But what if the Prop were a 64 bit machine? It might take a long while to run and you may never be able to finish writing your program.

Dave Hein

It seems like the Fibonacci series converges to something like 1.6**N. So there should be the same number of steps to go from 2**32 to 2**64, as there were in going from 1 to 2**32. It should only run twice as long on a 64-bit machine as it would on a 32-bit one.

Humanoido

http://answers.yahoo.com/question/index?qid=20080224134015AAj7qZA

Heater.

Good point Dave.
I was thinking in terms of the recursive fibo which, can take a long time, and forgot for a second that here it is done the easy way.
But my argument about that magic number still stands.
Now what about that big number version?

Heater.

Wait a minute Dave.
As we progress through the fibo sequence the numbers are getting bigger at an increasing rate. So aren't there a lot less steps between the biggest 32 bit fibo number and the biggest 64 bit one than we have to get to biggest 32 bitter? Given a 64 bit machine it should take less time to get there.

bomber

OK, I revised the code. Code is up top.

Heater.

Cool.

Now I don't mean to pick on you but we should get this right if we are going to do it at all.

The fibo sequence is 0, 1, 1, 2, 3, 5, 8...
By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

Your program omits the first zero.

bomber

@Heater: Fixed! Rev 1.5 above.

Heater.

Dave,

Well I never.

The biggest 32 bit integer fibo is fibo(46) at 1836311903

The biggest 64 bit integer fibo is fibo(92) at 7540113804746346429

So there are 47 fibo's in 32 bits, and the next 32 bit gains us 46 more.