Fibonacci sequence: Difference between revisions
(→{{header|Logo}}: +Mathematica) |
(→{{header|Java}}: Added analytic method) |
||
Line 327: | Line 327: | ||
if(n <= 2) return 1; |
if(n <= 2) return 1; |
||
return recFibN(n-1) + recFibN(n-2); |
return recFibN(n-1) + recFibN(n-2); |
||
}</java> |
|||
===Analytic=== |
|||
This method works up to the 92<sup>nd</sup> Fibonacci number. After that, it goes out of range. |
|||
<java>public static long anFibN(long n){ |
|||
double p= (1 + Math.sqrt(5)) / 2; |
|||
double q= 1 / p; |
|||
return (long)((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5)); |
|||
}</java> |
}</java> |
||
Revision as of 06:04, 15 June 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
E
def fib(n) { var s := [0, 1] for _ in 0..!n { def [a, b] := s s := [b, a+b] } return s[0] }
(This version defines fib(0) = 0
because OEIS A000045 does.)
Forth
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
Fortran
Recursive
In ISO Fortran 90 or later, use a RECURSIVE function:
module fibonacci contains recursive function fibR(n) result(fib) integer, intent(in) :: n integer :: fib select case (n) case (:0); fib = 0 case (1); fib = 1 case default; fib = fibR(n-1) + fibR(n-2) end select end function fibR
Iterative
In ISO Fortran 90 or later:
function fibI(n) integer, intent(in) :: n integer, parameter :: fib0 = 0, fib1 = 1 integer :: fibI, back1, back2, i select case (n) case (:0); fibI = fib0 case (1); fibI = fib1 case default fibI = fib1 back1 = fib0 do i = 2, n back2 = back1 back1 = fibI fibI = back1 + back2 end do end select end function fibI end module fibonacci
Test program
program fibTest use fibonacci do i = 0, 10 print *, fibr(i), fibi(i) end do end program fibTest
Output
0 0 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55
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>
Analytic
This method works up to the 92nd Fibonacci number. After that, it goes out of range. <java>public static long anFibN(long n){ double p= (1 + Math.sqrt(5)) / 2; double q= 1 / p; return (long)((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5)); }</java>
Joy
DEFINE fib == [small] [] [pred dup pred] [+] binrec .
Logo
to fib_acc :n :f :g if :n < 2 [output :g] output fib_acc :n-1 :g :f+:g end to fib :n output fib_acc :n 0 1 end
Mathematica
Mathematica already has a built-in function Fibonacci
, but a simple recursive implementation would be
fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n - 1] + fib[n - 2]
An optimization is to cache the values already calculated:
fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]
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>
Pop11
define fib(x); lvars a , b; 1 -> a; 1 -> b; repeat x - 1 times (a + b, b) -> (b, a); endrepeat; a; enddefine;
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
V
Generate n'th fib by using binary recursion
[fib [small?] [] [pred dup pred] [+] binrec].