Re: RPL prog for Fibonacci on HP 48G needs minor modification. help. Message #49 Posted by Oliver Unter Ecker on 10 July 2012, 11:44 a.m., in response to message #36 by wildpig
If we're comparing implementations, here's what ND1 (an iOS RPL calc) does internally:
for real numbers:
"fib": function(n) { if (n<0 || n>1400) throw Error("bad arg"); if (n <= 1) return n; var a = 0; var b = 1; var val; for (var i=2; i<=n; i++) { val = a+b; a = b; b = val; } return val; },
then in the BigInt class:
"fib": function(bn) { return calculator.functions.matrix.pow([[BigInteger.ZERO,BigInteger.ONE], [BigInteger.ONE,BigInteger.ONE]], parseInt(bn.toString()))[1][0]; }
where it also re-defines, unobtrusively, the real version like so
calculator.functions["fib_real"] = calculator.functions["fib"]; // move built-in function to new place
calculator.functions["fib"] = function(x) { return (x>77 ? BigNum.fib(BigNum.fromNumber(x)) : calculator.functions["fib_real"](x)); };
The net effect is that F(77) and lesser are implemented through iteration, and anything above that goes through matrix exponentiation.
The result function is usable as fib or FIB in RPL and other supported languages.
If someone wanted to make fib work like negafib, they'd inject a new implementation of fib and it would do a true overwrite, which "takes" globally. No flashing or app update necessary, as the run-time is a dynamic VM. (The calc is "ROM-less".)
There's also a fibmod function which comes in handy, if you need to solve PE #314...
|