Fibonacci sequence: Difference between revisions
Content deleted Content added
Befunge ftw! |
+D |
||
Line 38: | Line 38: | ||
^ .:\/*8"@"\%*8"@":\ < |
^ .:\/*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}}== |
=={{header|Forth}}== |
||
: fib ( n -- fib ) |
: fib ( n -- fib ) |