Question: How best to explain this curious behaviour of a Compiled Fibonacci program?

FunWithFibonacci.mw contains a short program with curious behaviour.

f := proc(n) option remember; if n < 2 then 1; else f(n - 1) + f(n - 2); end if; end proc;
F := Compiler:-Compile(f);

This gives a warning message that I don't understand, but never mind*.  I don't know much about the compiler, except that it uses float[8] or complex[8] as universal data types somehow. And maybe I am wrong about that, too.

Now F(n) returns the same number as combinat[fibonacci](n+1) for small n.  This is fine, the difference is one of indexing.  Both f and F return the same thing for small n.  Good.  Both return *integers*.  Checking with whattype confirms that.

Now, F(100) returns a large NEGATIVE integer.  Ok then, this looks like an overflow of an unsigned integer somewhere.

Even before that, though, F(91) returns an integer that is *plausible* but *wrong* :  7540113804746345472 where it should be 7540113804746346429.

So.  My explanation is that the compiler is, indeed, using float[8] internally, and then (for whatever reason) silently converting to integer on return.  Because floats are being used internally, numbers bigger than 2^53 cannot be represented exactly and rounding errors occur.  This happens at f(78) and F(78) which return 14472334024676221 and 14472334024676220 respectively.  

The sign error happens with F(92), where f(92) is just bigger than 2^63.  This suggests that an unsigned 64 bit integer is what the compiler is silently casting its result as.

The help file says "Integer data are limited to word-sized integers on the current hardware. Computations that produce larger integers will raise an overflow exception." So, the overflow exception is being suppressed?

* I may have figured out the error message: if I replace "f" internally by procname, maybe that will fix it.  Will try. Ok, if I do that, the warning message is suppressed, great.  G(30) works, great, though curiously slowly.  G(100) goes into an infinite loop.

Documentation doesn't talk about recursive programs or interaction with option remember.  So maybe that's not allowed?

Please Wait...