Anonymous user
Fibonacci sequence: Difference between revisions
+D
(Befunge ftw!) |
(+D) |
||
Line 38:
^ .:\/*8"@"\%*8"@":\ <
=={{header|D}}==
Here are four version of Fibonacci Number generating functions.<br>
''FibD'' has an argument limit of magnitude 82 due to floating point precision, the others have a limit of 92 due to overflow (long).<br>
The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results.<br>
All four functions have extended to deal with negative argument.
<d>module fibonacci ;
import std.stdio ;
import std.math ;
import std.conv ;
long FibD(int m) { // Direct Calculation, correct for abs(m) <= 82
const real sqrt5r = 0.44721359549995793928L ; // 1 / sqrt(5)
const real golden = 1.6180339887498948482L ; // (1 + sqrt(5)) / 2 ;
real sign = (m < 0) && (1 & m ^ 1) ? -1.0L : 1.0L ;
return rndtol(pow(golden, abs(m)) * sign * sqrt5r) ;
}
long FibI(int m) { // Iterative
int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
int n = m < 0 ? -m : m ;
if (n < 2)
return n ;
long prevFib = 0 ;
long thisFib = 1 ;
for(int i = 1 ; i < n ;i++) {
long tmp = thisFib ;
thisFib += prevFib ;
prevFib = tmp ;
}
return thisFib*sign ;
}
long FibR(int m) { // Recursive
if (m == 0 || m == 1) return m ;
return (m >= 0) ? FibR(m-1) + FibR(m-2) : (1 & m ^ 1) ? - FibR(-m) : FibR(-m) ;
}
long FibO(int m) { // Optimized Recursive
static long[] fib = [0,1] ;
int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
int n = m < 0 ? -m : m ;
if(n >= fib.length )
fib ~= FibO(n-2) + FibO(n-1) ;
return fib[n]*sign ;
}
void main(string[] args) {
int k = args.length > 1 ? toInt(args[1]) : 10 ;
writefln("Fib(%3d) = ", k) ;
writefln("D : %20d <- %20d + %20d", FibD(k), FibD(k - 1), FibD(k - 2) ) ;
writefln("I : %20d <- %20d + %20d", FibI(k), FibI(k - 1), FibI(k - 2) ) ;
if( abs(k) < 36 || args.length > 2) // set a limit for recursive version
writefln("R : %20d <- %20d + %20d", FibR(k), FibO(k - 1), FibO(k - 2) ) ;
writefln("O : %20d <- %20d + %20d", FibO(k), FibO(k - 1), FibO(k - 2) ) ;
}</d>
Output for n = 83:
<pre>Fib( 83) =
D : 99194853094755496 <- 61305790721611591 + 37889062373143906
I : 99194853094755497 <- 61305790721611591 + 37889062373143906
O : 99194853094755497 <- 61305790721611591 + 37889062373143906</pre>
=={{header|Forth}}==
: fib ( n -- fib )
| |||