Fibonacci sequence: Difference between revisions
(added ocaml) |
|||
| Line 325: | Line 325: | ||
) |
) |
||
) |
) |
||
=={{header|OCaml}}== |
|||
===Iterative=== |
|||
<ocaml>let fib_iter n = |
|||
if n <= 2 then |
|||
1 |
|||
else let fib_prev = ref 1 |
|||
and fib = ref 1 in |
|||
for num = 2 to n - 1 do |
|||
let temp = !fib in |
|||
fib := !fib + !fib_prev; |
|||
fib_prev := temp |
|||
done; |
|||
!fib</ocaml> |
|||
===Recursive=== |
|||
<ocaml>let rec fib_rec n = |
|||
if n <= 2 then |
|||
1 |
|||
else |
|||
fib_rec (n - 1) + fib_rec (n - 2)</ocaml> |
|||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
Revision as of 19:09, 16 April 2008
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). Support for negative n errors is optional.
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"@":\ <
C++
Using unsigned int, this version only works up to 48 before fib overflows. <cpp>#include <iostream>
int main() { unsigned int a = 1, b = 1; unsigned int target = 48; for(unsigned int n = 3; n <= target; ++n) { unsigned int fib = a + b; std::cout << "F("<< n << ") = " << fib << std::endl; a = b; b = fib; }
return 0; } </cpp>
This version does not have an upper bound.
<cpp>#include <iostream>
- include <gmpxx.h>
int main() { mpz_class a = mpz_class(1), b = mpz_class(1); mpz_class target = mpz_class(100); for(mpz_class n = mpz_class(3); n <= target; ++n) { mpz_class fib = b + a; if ( fib < b ) { std::cout << "Overflow at " << n << std::endl; break; } std::cout << "F("<< n << ") = " << fib << std::endl; a = b; b = fib; }
return 0; }</cpp>
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 ;
Fortran
Recursive
In ISO Fortran 90 or later, use recursive function:
RECURSIVE FUNCTION FIB(N)
INTEGER, INTENT(IN) :: N
INTEGER :: FIB
SELECT (N)
CASE (:0); FIB = 0
CASE (1); FIB = 1
CASE DEFAULT; FIB = FIB(N-1) + FIB(N-2)
END SELECT
END FUNCTION FIB
Iterative
In ISO Fortran 90 or later:
FUNCTION FIB(N)
INTEGER, INTENT(N) :: N
INTEGER, PARAMETER :: FIB0 = 0, FIB1 = 1
INTEGER :: FIB, BACK1, BACK2, I
SELECT (N)
CASE (:0); FIB = FIB0
CASE (1); FIB = FIB1
CASE DEFAULT
FIB = FIB1
BACK1 = FIB0
DO I = 2, N
BACK2 = BACK1
BACK1 = FIB
FIB = BACK1 + BACK2
END DO
END SELECT
END FUNCTION FIB
Haskell
With lazy lists
This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:
fib = 1 : 1 : zipWith (+) fib (tail fib)
The nth Fibonacci number is then just
fib !! n
With matrix exponentiation
With the (rather slow) code from Matrix exponentiation operator
import Data.List
xs <+> ys = zipWith (+) xs ys
xs <*> ys = sum $ zipWith (*) xs ys
newtype Mat a = Mat {unMat :: [[a]]} deriving Eq
instance Show a => Show (Mat a) where
show xm = "Mat " ++ show (unMat xm)
instance Num a => Num (Mat a) where
negate xm = Mat $ map (map negate) $ unMat xm
xm + ym = Mat $ zipWith (<+>) (unMat xm) (unMat ym)
xm * ym = Mat [[xs <*> ys | ys <- transpose $ unMat ym] | xs <- unMat xm]
fromInteger n = Mat [[fromInteger n]]
we can simply write
fib n = last $ head $ unMat $ (Mat [[1,1],[1,0]]) ^ n
So, for example, the ten-thousendth Fiboncacci number starts with the digits
*Main> take 10 $ show $ fib (10^5) "2597406934"
IDL
Recursive
function fib,n
if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)
end
Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo.
Iterative
function fib,n
psum = (csum = 1uL)
if n lt 3 then return,csum
for i = 3,n do begin
nsum = psum + csum
psum = csum
csum = nsum
endfor
return,nsum
end
Execution time O(n). Limited by size of uLong to fib(49)
Analytic
function fib,n
q=1/( p=(1+sqrt(5))/2 )
return,round((p^n+q^n)/sqrt(5))
end
Execution time O(1), only limited by the range of LongInts to fib(48).
J
See J Wiki: Fibonacci Sequence.
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)
)
)
OCaml
Iterative
<ocaml>let fib_iter n =
if n <= 2 then
1
else let fib_prev = ref 1
and fib = ref 1 in
for num = 2 to n - 1 do
let temp = !fib in
fib := !fib + !fib_prev;
fib_prev := temp
done;
!fib</ocaml>
Recursive
<ocaml>let rec fib_rec n =
if n <= 2 then 1 else fib_rec (n - 1) + fib_rec (n - 2)</ocaml>
Oz
fun{FibI N} %% Iterative using Cell
Temp = {NewCell 0}
A = {NewCell 0}
B = {NewCell 1}
in
for I in 1..N do
Temp := @A + @B
A := @B
B := @Temp
end
@A %% return result
end
fun{Fibi N} %% Iterative(or Recursive?) by arguments swapping
fun{FibIter N A B}
if N == 0 then B
else {FibIter N-1 A+B A} end
end
in
if N < 2 then N
else {FibIter N 1 0} end
end
fun{FibR N} %% Simple Recursive
if N < 2 then N
else {FibR N-1} + {FibR N-2} end
end
Perl
<perl>#!/usr/bin/perl -w
my $a = 1; my $b = $a;
my $target = 500;
for( my $n = 3; $n <= $target; ++$n ) {
my $fib = $a + $b;
if($fib < $b)
{
print "Overflow at $n\n";
last;
}
print "F($n): $fib\n";
$a = $b;
$b = $fib;
} </perl>
PostScript
Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:
%#!PS
% We want the 'n'th fibonacci number
/n 13 def
% Prepare output canvas:
/Helvetica findfont 20 scalefont setfont
100 100 moveto
%define the function recursively:
/fib { dup
3 lt
{ pop 1 }
{ dup 1 sub fib exch 2 sub fib add }
ifelse
} def
(Fib\() show n (....) cvs show (\)=) show n fib (.....) cvs show
showpage
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>
Tcl
proc fib {n} { if { $n < 3 } then { return 1 } else { return [expr [fib [expr $n-1]]+[fib [expr $n-2]]] } }
E.g.:
fib 7 ;==> 13
UnixPipes
Uses fib and last as file buffers for computation. could have made fib as a fifo and changed tail -f to cat fib but it is not line buffered.
echo 1 |tee last fib ; tail -f fib | while read x do cat last | tee -a fib | xargs -n 1 expr $x + |tee last done