Fibonacci sequence: Difference between revisions
(+D) |
(→{{header|D}}: Fixed English) |
||
Line 39: | Line 39: | ||
=={{header|D}}== |
=={{header|D}}== |
||
Here are four |
Here are four versions 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> |
''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> |
The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results.<br> |
||
All four functions have |
All four functions have support for negative arguments. |
||
<d>module fibonacci ; |
<d>module fibonacci ; |
||
import std.stdio ; |
import std.stdio ; |
||
Line 96: | Line 96: | ||
I : 99194853094755497 <- 61305790721611591 + 37889062373143906 |
I : 99194853094755497 <- 61305790721611591 + 37889062373143906 |
||
O : 99194853094755497 <- 61305790721611591 + 37889062373143906</pre> |
O : 99194853094755497 <- 61305790721611591 + 37889062373143906</pre> |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
: fib ( n -- fib ) |
: fib ( n -- fib ) |
Revision as of 18:41, 1 March 2008
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
The Fibonacci sequence is a sequence of numbers defined as such:
Where n is an integer greater than 2: F1 = F2 = 1 Fn = Fn-1 + Fn-2
Write a function to generate the nth Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).
BASIC
Iterative
<qbasic>FUNCTION itFib (n) IF (n <= 2) THEN
itFib = 1
ELSE
ans = 0 n1 = 1 n2 = 1 n = n - 2 DO WHILE (n > 0) ans = n1 + n2 n1 = n2 n2 = ans n = n - 1 LOOP itFib = ans
END IF END FUNCTION</qbasic>
Recursive
<qbasic>FUNCTION recFib (n) IF (n <= 2) THEN
recFib = 1
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF END FUNCTION</qbasic>
Befunge
00:.1:.>:"@"8**++\1+:67+`#@_v ^ .:\/*8"@"\%*8"@":\ <
D
Here are four versions of Fibonacci Number generating functions.
FibD has an argument limit of magnitude 82 due to floating point precision, the others have a limit of 92 due to overflow (long).
The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results.
All four functions have support for negative arguments.
<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:
Fib( 83) = D : 99194853094755496 <- 61305790721611591 + 37889062373143906 I : 99194853094755497 <- 61305790721611591 + 37889062373143906 O : 99194853094755497 <- 61305790721611591 + 37889062373143906
Forth
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
Java
Iterative
<java>public static long itFibN(int n){ if(n <= 2)return 1; long ans = 0; long n1 = 1; long n2 = 1; for(n -= 2;n > 0;n--){ ans = n1 + n2; n1 = n2; n2 = ans; } return ans; }</java>
Recursive
<java>public static long recFibN(int n){ if(n <= 2) return 1; return recFibN(n-1) + recFibN(n-2); }</java>
MAXScript
Iterative
fn fibIter n = ( if n <= 2 then ( 1 ) else ( fib = 1 fibPrev = 1 for num in 3 to n do ( temp = fib fib += fibPrev fibPrev = temp ) fib ) )
Recursive
fn fibRec n = ( if n <= 2 then ( 1 ) else ( fibRec (n - 1) + fibRec (n - 2) ) )
Python
Iterative
<python>def fibIter(n):
if n <= 2: return 1 fibPrev = 1 fib = 1 for num in xrange(2, n): temp = fib fib += fibPrev fibPrev = temp return fib</python>
Recursive
<python>def fibRec(n):
if n <= 2: return 1 else: return fibRec(n-1) + fibRec(n-2)</python>