Fibonacci sequence: Difference between revisions
m
FutureBasic entry moved out of the Basic group
(→{{header|PL/0}}: Added a solution.) |
m (FutureBasic entry moved out of the Basic group) |
||
| (71 intermediate revisions by 33 users not shown) | |||
Line 245:
JNZ LOOP ; jump if not zero
RET ; return from subroutine</syntaxhighlight>
The range may be easily be extended from the 13th (=233) to the 24th (=46368) Fibonacci number with 16-bit addition using DAD. The code here assumes the CP/M operating system.
<syntaxhighlight>
;-------------------------------------------------------
; useful equates
;-------------------------------------------------------
bdos equ 5 ; BDOS entry
cr equ 13 ; ASCII carriage return
lf equ 10 ; ASCII line feed
space equ 32 ; ASCII space char
conout equ 2 ; BDOS console output function
putstr equ 9 ; BDOS print string function
nterms equ 20 ; number of terms (max=24) to display
;-------------------------------------------------------
; main code begins here
;-------------------------------------------------------
org 100h
lxi h,0 ; save CP/M's stack
dad sp
shld oldstk
lxi sp,stack ; set our own stack
lxi d,signon ; print signon message
mvi c,putstr
call bdos
mvi a,0 ; start with Fib(0)
mloop: push a ; save our count
call fib
call putdec
mvi a,space ; separate the numbers
call putchr
pop a ; get our count back
inr a ; increment it
cpi nterms+1 ; have we reached our limit?
jnz mloop ; no, keep going
lhld oldstk ; all done; get CP/M's stack back
sphl ; restore it
ret ; back to command processor
;-------------------------------------------------------
; calculate nth Fibonacci number (max n = 24)
; entry: A = n
; exit: HL = Fib(n)
;-------------------------------------------------------
fib: mov c,a ; C holds n
lxi d,0 ; DE holds Fib(n-2)
lxi h,1 ; HL holds Fib(n-1)
ana a ; Fib(0) is a special case
jnz fib2 ; n > 0 so calculate normally
xchg ; otherwise return with HL=0
ret
fib2: dcr c
jz fib3 ; we're done
push h ; save Fib(n-1)
dad d ; HL = Fib(n), soon to be Fib(n-1)
pop d ; DE = old F(n-1), now Fib(n-2)
jmp fib2 ; ready for next pass
fib3: ret
;-------------------------------------------------------
; console output of char in A register
;-------------------------------------------------------
putchr: push h
push d
push b
mov e,a
mvi c,conout
call bdos
pop b
pop d
pop h
ret
;---------------------------------------------------------
; Output decimal number to console
; HL holds 16-bit unsigned binary number to print
;---------------------------------------------------------
putdec: push b
push d
push h
lxi b,-10
lxi d,-1
putdec2:
dad b
inx d
jc putdec2
lxi b,10
dad b
xchg
mov a,h
ora l
cnz putdec ; recursive call
mov a,e
adi '0'
call putchr
pop h
pop d
pop b
ret
;-------------------------------------------------------
; data area
;-------------------------------------------------------
signon: db 'Fibonacci number sequence:',cr,lf,'$'
oldstk: dw 0
stack equ $+128 ; 64-level stack
;
end
</syntaxhighlight>
{{out}}
<pre>
Fibonacci number sequence:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
</pre>
=={{header|8086 Assembly}}==
Line 651 ⟶ 759:
end while
return(fnext)
</syntaxhighlight>
=={{header|Agda}}==
<syntaxhighlight lang="agda">
module FibonacciSequence where
open import Data.Nat using (ℕ ; zero ; suc ; _+_)
rec_fib : (m : ℕ) -> (a : ℕ) -> (b : ℕ) -> ℕ
rec_fib zero a b = a
rec_fib (suc k) a b = rec_fib k b (a + b)
fib : (n : ℕ) -> ℕ
fib n = rec_fib n zero (suc zero)
</syntaxhighlight>
Line 1,608 ⟶ 1,730:
233 233
121393 121393</pre>
==={{header|bootBASIC}}===
Variables in bootBASIC are 2 byte unsigned integers that roll over if there is an overflow. Entering a number greater than 24 will result in an incorrect outcome.
<syntaxhighlight lang="BASIC">
10 print "Enter a ";
20 print "number ";
30 print "greater ";
40 print "than 1";
50 print " and less";
60 print " than 25";
70 input z
80 b=1
90 a=0
100 n=2
110 f=a+b
120 a=b
130 b=f
140 n=n+1
150 if n-z-1 goto 110
160 print "The ";
170 print z ;
180 print "th ";
190 print "Fibonacci ";
200 print "Number is ";
210 print f
</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 cls
110 for i = 0 to 20 : print fibor(i); : next i
120 print
130 for i = 0 to 20 : print fiboi(i); : next i
140 print
150 for i = 0 to 20 : print fiboa(i); : next i
160 end
170 sub fibor(n) : 'Recursive
180 if n < 2 then
190 fibor = n
200 else
210 fibor = fibor(n-1)+fibor(n-2)
220 endif
230 end sub
240 sub fiboi(n) : 'Iterative
250 n1 = 0
260 n2 = 1
270 for k = 1 to abs(n)
280 sum = n1+n2
290 n1 = n2
300 n2 = sum
310 next k
320 if n < 0 then
330 fiboi = n1*((-1)^((-n)+1))
340 else
350 fiboi = n1
360 endif
370 end sub
380 sub fiboa(n) : 'Analytic
390 fiboa = int(0.5+(((sqr 5+1)/2)^n)/sqr 5)
400 end sub</syntaxhighlight>
{{out}}
<pre>0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765</pre>
==={{header|Commodore BASIC}}===
Line 1,642 ⟶ 1,827:
print "Fibonacci Sequence"
for i = 0 to 20
let s = a + b
let a = b
let b = s
print s
{{out| Output}}<pre>Fibonacci Sequence
2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 </pre>
==={{header|FreeBASIC}}===
Line 1,779 ⟶ 1,965:
end</syntaxhighlight>
==={{header|GFA Basic}}===
Line 2,229 ⟶ 2,269:
<pre>
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994
</pre>
==={{header|Minimal BASIC}}===
{{works with|QBasic}}
{{works with|BASICA}}
{{works with|Chipmunk Basic}}
{{works with|GW-BASIC}}
{{works with|IS-BASIC}}
{{works with|MSX Basic}}
<syntaxhighlight lang="qbasic">110 REM THE ARRAY F HOLDS THE FIBONACCI NUMBERS
120 DIM F(22)
130 LET F(0) = 0
140 LET F(1) = 1
150 LET N = 1
160 REM COMPUTE THE NEXT FIBBONACCI NUMBER
170 LET F(N+1) = F(N)+F(N-1)
180 LET N = N+1
190 PRINT F(N-2);
200 REM STOP AFTER PRINTING 20 NUMBERS
210 IF N < 22 THEN 170
220 END</syntaxhighlight>
==={{header|MSX Basic}}===
{{works with|QBasic}}
{{works with|Chipmunk Basic}}
{{works with|GW-BASIC}}
<syntaxhighlight lang="qbasic">100 CLS
110 FOR N = 0 TO 15: GOSUB 130: PRINT FIBOI; : NEXT N
120 END
130 REM Iterative Fibonacci sequence
140 N1 = 0
150 N2 = 1
160 FOR K = 1 TO ABS(N)
170 SUM = N1 + N2
180 N1 = N2
190 N2 = SUM
200 NEXT K
210 IF N < 0 THEN FIBOI = N1 * ((-1) ^ ((-N) + 1)) ELSE FIBOI = N1
220 RETURN</syntaxhighlight>
==={{header|Palo Alto Tiny BASIC}}===
<syntaxhighlight lang="basic">
10 REM FIBONACCI SEQUENCE
20 INPUT "ENTER N FOR FIB(N)"N
30 LET A=0,B=1
40 FOR I=2 TO N
50 LET T=B,B=A+B,A=T
60 NEXT I
70 PRINT B
80 STOP
</syntaxhighlight>
{{out}}
2 runs.
<pre>
ENTER N FOR FIB(N):9
34
</pre>
<pre>
ENTER N FOR FIB(N):13
233
</pre>
Line 2,535 ⟶ 2,635:
PRINT
'*****sample inputs*****</syntaxhighlight>
==={{header|Quite BASIC}}===
<syntaxhighlight lang="qbasic">100 CLS
110 rem The array F holds the Fibonacci numbers
120 ARRAY f : rem DIM f(22) para Quite BASIC and MSX-BASIC
130 LET f(0) = 0
140 LET f(1) = 1
150 LET n = 1
160 rem Compute the NEXT Fibbonacci number
170 LET f(n+1) = f(n)+f(n-1)
180 LET n = n+1
190 PRINT f(n-2);" ";
200 rem STOP after printing 20 numbers
210 IF n < 22 THEN GOTO 170</syntaxhighlight>
==={{header|Run BASIC}}===
Line 2,758 ⟶ 2,872:
150 END
</syntaxhighlight>
==={{header|True BASIC}}===
Line 3,049 ⟶ 3,141:
==={{header|Yabasic}}===
====Iterative====
<syntaxhighlight lang="vbnet">sub fibonacciI (n)
local n1, n2, k, sum
n1 = 0
n2 = 1
Line 3,057 ⟶ 3,152:
n2 = sum
next k
if n <
return n1 * ((-1) ^ ((-n) + 1))
else
return n1
end if
end sub</syntaxhighlight>
====Recursive====
Only positive numbers
<syntaxhighlight lang="vbnet">sub fibonacciR(n)
if n <= 1 then
return n
else
return fibonacciR(n-1) + fibonacciR(n-2)
end if
end sub</syntaxhighlight>
====Analytic====
Only positive numbers
<syntaxhighlight lang="vbnet">sub fibonacciA (n)
return int(0.5 + (((sqrt(5) + 1) / 2) ^ n) / sqrt(5))
end sub</syntaxhighlight>
====Binet's formula====
Fibonacci sequence using the Binet formula
<syntaxhighlight lang="vbnet">sub fibonacciB(n)
local sq5, phi1, phi2, dn1, dn2, k
sq5 = sqrt(5)
phi1 = (1 + sq5) / 2
phi2 = (1 - sq5) / 2
dn1 = phi1: dn2 = phi2
for k = 0 to n
dn1 = dn1 * phi1
dn2 = dn2 * phi2
print int(((dn1 - dn2) / sq5) + .5);
next k
end sub</syntaxhighlight>
Line 3,397 ⟶ 3,524:
{true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}
}</syntaxhighlight>
=={{header|Bruijn}}==
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Math .
:import std/List .
# unary/Church fibonacci (moderately fast but very high space complexity)
fib-unary [0 [[[2 0 [2 (1 0)]]]] k i]
:test (fib-unary (+6u)) ((+8u))
# ternary fibonacci using infinite list iteration (very fast)
fib-list \index fibs
fibs head <$> (iterate &[[0 : (1 + 0)]] ((+0) : (+1)))
:test (fib-list (+6)) ((+8))
# recursive fib (very slow)
fib-rec y [[0 <? (+1) (+0) (0 <? (+2) (+1) rec)]]
rec (1 --0) + (1 --(--0))
:test (fib-rec (+6)) ((+8))
</syntaxhighlight>
Performance using <code>HigherOrder</code> reduction without optimizations:
<syntaxhighlight>
> :time fib-list (+1000)
0.9 seconds
> :time fib-unary (+50u)
1.7 seconds
> :time fib-rec (+25)
5.1 seconds
> :time fib-list (+50)
0.0006 seconds
</syntaxhighlight>
=={{header|Burlesque}}==
Line 3,602 ⟶ 3,766:
}
</syntaxhighlight>
=== Iterative ===
<syntaxhighlight lang="csharp">
using System; using System.Text; // FIBRUS.cs Russia
namespace Fibrus { class Program { static void Main()
{ long fi1=1; long fi2=1; long fi3=1; int da; int i; int d;
for (da=1; da<=78; da++) // rextester.com/MNGUV70257
{ d = 20-Convert.ToInt32((Convert.ToString(fi3)).Length);
for (i=1; i<d; i++) Console.Write(".");
Console.Write(fi3); Console.Write(" "); Console.WriteLine(da);
fi3 = fi2 + fi1;
fi1 = fi2;
fi2 = fi3;
}}}}
</syntaxhighlight>
{{out}}
<pre>
..................1 1
..................2 2
..................3 3
...
...5527939700884757 76
...8944394323791464 77
..14472334024676221 78
</pre>
=== Eager-Generative ===
Line 4,052 ⟶ 4,241:
Serves 1.</syntaxhighlight>
=={{header|Chez Scheme}}==
<syntaxhighlight lang="scheme">
(define fib (lambda (n) (cond ((> n 1) (+ (fib (- n 1)) (fib (- n 2))))
((= n 1) 1)
((= n 0) 0))))
</syntaxhighlight>
=={{header|Clio}}==
Line 4,609 ⟶ 4,805:
y: 1
temp: 0</syntaxhighlight>
=={{header|Coq}}==
<syntaxhighlight lang="coq">
Fixpoint rec_fib (m : nat) (a : nat) (b : nat) : nat :=
match m with
| 0 => a
| S k => rec_fib k b (a + b)
end.
Definition fib (n : nat) : nat :=
rec_fib n 0 1 .
</syntaxhighlight>
=={{header|Corescript}}==
Line 5,029 ⟶ 5,237:
<syntaxhighlight lang="dibol-11">
;
; are noot computed.
START ;First 15 Fibonacci NUmbers
Line 5,036 ⟶ 5,247:
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2,
RECORD HEADER
, A32, "First
RECORD OUTPUT
Line 5,052 ⟶ 5,263:
WRITES(8,HEADER)
; The First Two are given.
FIBOUT = 0
LOOPOUT = 1
WRITES(8,OUTPUT)
FIBOUT = 1
LOOPOUT = 2
WRITES(8,OUTPUT)
; The Rest are Computed.
LOOP,
FIBNEW = FIB1 + FIB2
Line 5,063 ⟶ 5,285:
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE.
CLOSE 8
END
</syntaxhighlight>
=={{header|DWScript}}==
Line 5,106 ⟶ 5,330:
<syntaxhighlight lang="text">
func fib n
if n < 2
.
prev = 0
val = 1
for
prev = val
val =
.
return val
.
</syntaxhighlight>
Recursive (inefficient):
<syntaxhighlight lang="text">
func
if
return n
.
.
=={{header|EchoLisp}}==
Line 5,305 ⟶ 5,527:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA
<syntaxhighlight lang="elena">import extensions;
Line 5,317 ⟶ 5,539:
else
{
for(int i := 2
{
int t := ac[1];
Line 5,330 ⟶ 5,552:
public program()
{
for(int i := 0
{
console.printLine(fibu(i))
Line 5,360 ⟶ 5,582:
long n_1 := 1l;
$yield
$yield
while(true)
Line 5,367 ⟶ 5,589:
long n := n_2 + n_1;
$yield
n_2 := n_1;
Line 5,379 ⟶ 5,601:
auto e := new FibonacciGenerator();
for(int i := 0
console.printLine(e.next())
};
Line 5,412 ⟶ 5,634:
=={{header|Elm}}==
Naïve recursive implementation.
<syntaxhighlight lang="haskell">fibonacci : Int -> Int
Line 5,418 ⟶ 5,641:
else
fibonacci(n - 2) + fibonacci(n - 1)</syntaxhighlight>
'''version 2'''
<syntaxhighlight lang=”elm">fib : Int -> number
fib n =
case n of
0 -> 0
1 -> 1
_ -> fib (n-1) + fib (n-2)
</syntaxhighlight>
{{out}}
<pre>
elm repl
> fib 40
102334155 : number
> List.map (\elem -> fib elem) (List.range 1 40)
[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,
4181,6765,10946,17711,28657,46368,75025,121393,196418,
317811,514229,832040,1346269,2178309,3524578,5702887,
9227465,14930352,24157817,39088169,63245986,102334155]
: List number
</pre>
=={{header|Emacs Lisp}}==
Line 6,570 ⟶ 6,817:
in a
</syntaxhighlight>
=={{header|FutureBasic}}==
=== Iterative ===
<syntaxhighlight lang="futurebasic">window 1, @"Fibonacci Sequence", (0,0,480,620)
local fn Fibonacci( n as long ) as long
static long s1
static long s2
long temp
if ( n < 2 )
s1 = n
exit fn
else
temp = s1 + s2
s2 = s1
s1 = temp
exit fn
end if
end fn = s1
long i
CFTimeInterval t
t = fn CACurrentMediaTime
for i = 0 to 40
print i;@".\t";fn Fibonacci(i)
next i
print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000
HandleEvents</syntaxhighlight>
Output:
<pre>
0. 0
1. 1
2. 1
3. 2
4. 3
5. 5
6. 8
7. 13
8. 21
9. 34
10. 55
11. 89
12. 144
13. 233
14. 377
15. 610
16. 987
17. 1597
18. 2584
19. 4181
20. 6765
21. 10946
22. 17711
23. 28657
24. 46368
25. 75025
26. 121393
27. 196418
28. 317811
29. 514229
30. 832040
31. 1346269
32. 2178309
33. 3524578
34. 5702887
35. 9227465
36. 14930352
37. 24157817
38. 39088169
39. 63245986
40. 102334155
Compute time: 2.143 ms</pre>
=== Recursive ===
Cost is a time penalty
<syntaxhighlight lang="futurebasic">
local fn Fibonacci( n as NSInteger ) as NSInteger
NSInteger result
if n < 2 then result = n : exit fn
result = fn Fibonacci( n-1 ) + fn Fibonacci( n-2 )
end fn = result
window 1
NSInteger i
CFTimeInterval t
t = fn CACurrentMediaTime
for i = 0 to 40
print i;@".\t";fn Fibonacci(i)
next
print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
0. 0
1. 1
2. 1
3. 2
4. 3
5. 5
6. 8
7. 13
8. 21
9. 34
10. 55
11. 89
12. 144
13. 233
14. 377
15. 610
16. 987
17. 1597
18. 2584
19. 4181
20. 6765
21. 10946
22. 17711
23. 28657
24. 46368
25. 75025
26. 121393
27. 196418
28. 317811
29. 514229
30. 832040
31. 1346269
32. 2178309
33. 3524578
34. 5702887
35. 9227465
36. 14930352
37. 24157817
38. 39088169
39. 63245986
40. 102334155
Compute time: 2844.217 ms
</pre>
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Fibonacci_numbers}}
=== Recursive ===
Recursive version is slow, it is O(2<sup>n</sup>), or of exponential order.
[[File:Fōrmulæ - Fibonacci sequence 01.png]]
[[File:Fōrmulæ - Fibonacci sequence 02.png]]
[[File:Fōrmulæ - Fibonacci sequence result.png]]
It is because it makes a lot of recursive calls.
To illustrate this, the following is a functions that makes a tree or the recursive calls:
[[File:Fōrmulæ - Fibonacci sequence 03.png]]
[[File:Fōrmulæ - Fibonacci sequence 04.png]]
[[File:Fōrmulæ - Fibonacci sequence 05.png]]
=== Iterative (3 variables) ===
It is O(n), or of linear order.
[[File:Fōrmulæ - Fibonacci sequence 06.png]]
[[File:Fōrmulæ - Fibonacci sequence 07.png]]
[[File:Fōrmulæ - Fibonacci sequence result.png]]
=== Iterative (2 variables) ===
It is O(n), or of linear order.
[[File:Fōrmulæ - Fibonacci sequence 08.png]]
[[File:Fōrmulæ - Fibonacci sequence 09.png]]
[[File:Fōrmulæ - Fibonacci sequence result.png]]
=== Iterative, using a list ===
It is O(n), or of linear order.
[[File:Fōrmulæ - Fibonacci sequence 10.png]]
[[File:Fōrmulæ - Fibonacci sequence 11.png]]
[[File:Fōrmulæ - Fibonacci sequence result.png]]
=== Using matrix multiplication ===
[[File:Fōrmulæ - Fibonacci sequence 12.png]]
[[File:Fōrmulæ - Fibonacci sequence 13.png]]
[[File:Fōrmulæ - Fibonacci sequence result.png]]
=== Divide and conquer ===
It is an optimized version of the matrix multiplication algorithm, with an order of O(lg(n))
[[File:Fōrmulæ - Fibonacci sequence 14.png]]
[[File:Fōrmulæ - Fibonacci sequence 15.png]]
[[File:Fōrmulæ - Fibonacci sequence result.png]]
=== Closed-form ===
It has an order of O(lg(n))
[[File:Fōrmulæ - Fibonacci sequence 16.png]]
[[File:Fōrmulæ - Fibonacci sequence 17.png]]
[[File:Fōrmulæ - Fibonacci sequence result.png]]
=={{header|GAP}}==
Line 6,676 ⟶ 7,145:
}
</syntaxhighlight>
=={{header|Grain}}==
=== Recursive ===
<syntaxhighlight lang="haskell">
import String from "string"
import File from "sys/file"
let rec fib = n => if (n < 2) {
n
} else {
fib(n - 1) + fib(n - 2)
}
for (let mut i = 0; i <= 20; i += 1) {
File.fdWrite(File.stdout, Pervasives.toString(fib(i)))
ignore(File.fdWrite(File.stdout, " "))
}
</syntaxhighlight>
=== Iterative ===
<syntaxhighlight lang="haskell">
import File from "sys/file"
let fib = j => {
let mut fnow = 0, fnext = 1
for (let mut n = 0; n <= j; n += 1) {
if (n == 0 || n == 1) {
let output1 = " " ++ toString(n)
ignore(File.fdWrite(File.stdout, output1))
} else {
let tempf = fnow + fnext
fnow = fnext
fnext = tempf
let output2 = " " ++ toString(fnext)
ignore(File.fdWrite(File.stdout, output2))
}
}
}
fib(20)
</syntaxhighlight>
{{out}}
=== Iterative with Buffer ===
<syntaxhighlight lang="haskell">
import Buffer from "buffer"
import String from "string"
let fib = j => {
// set-up minimal, growable buffer
let buf = Buffer.make(j * 2)
let mut fnow = 0, fnext = 1
for (let mut n = 0; n <= j; n += 1) {
if (n == 0 || n == 1) {
Buffer.addChar(' ', buf)
Buffer.addString(toString(n), buf)
} else {
let tempf = fnow + fnext
fnow = fnext
fnext = tempf
Buffer.addChar(' ', buf)
Buffer.addString(toString(fnext), buf)
}
}
// stringify buffer and return
Buffer.toString(buf)
}
let output = fib(20)
print(output)
</syntaxhighlight>
{{out}}<pre>
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
</pre>
=={{header|Groovy}}==
Line 7,156 ⟶ 7,691:
=={{header|J}}==
The [https://code.jsoftware.com/wiki/Essays/Fibonacci_Sequence Fibonacci Sequence essay] on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number.
This implementation is doubly recursive except that results are cached across function calls:
<syntaxhighlight lang="j">fibN=: (-&2 +&$: <:)^:(1&<) M."0</syntaxhighlight>
Iteration:
<syntaxhighlight lang="j">fibN=: [: {."1 +/\@|.@]^:[&0 1</syntaxhighlight>
'''Examples:'''
<syntaxhighlight lang="j"> fibN 12
Line 7,163 ⟶ 7,702:
fibN i.31
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</syntaxhighlight>
=={{header|Java}}==
Line 7,540 ⟶ 8,077:
=={{header|K}}==
{{works with|Kona}}
===Recursive===
Line 7,554 ⟶ 8,092:
===Sequence to n===
{{works with|Kona}} {{works with|ngn/k}}
<syntaxhighlight lang="k">{(x(|+\)\1 1)[;1]}</syntaxhighlight>
<syntaxhighlight lang="k">{x{x,+/-2#x}/!2}</syntaxhighlight>
Line 7,747 ⟶ 8,286:
{fib5 1000} -> 4.346655768693743e+208 (CPU ~ 1ms)
</syntaxhighlight>
=={{header|Lang}}==
===Iterative===
<syntaxhighlight lang="lang">
fp.fib = ($n) -> {
if($n < 2) {
return $n
}
$prev = 1
$cur = 1
$i = 2
while($i < $n) {
$tmp = $cur
$cur += $prev
$prev = $tmp
$i += 1
}
return $cur
}
</syntaxhighlight>
===Recursive===
<syntaxhighlight lang="lang">
fp.fib = ($n) -> {
if($n < 2) {
return $n
}
return parser.op(fp.fib($n - 1) + fp.fib($n - 2))
}
</syntaxhighlight>
Line 7,759 ⟶ 8,332:
=={{header|langur}}==
<syntaxhighlight lang="langur">val .fibonacci =
writeln map .fibonacci, series 2..20</syntaxhighlight>
Line 8,051 ⟶ 8,624:
=={{header|Logo}}==
<syntaxhighlight lang="logo">
to fib "loop
make "fib1 0
make "fib2 1
type [You requested\ ]
type :loop
print [\ Fibonacci Numbers]
type :fib1
type [\ ]
type :fib2
type [\ ]
make "loop :loop - 2
repeat :loop [ make "fibnew :fib1 + :fib2 type :fibnew type [\ ] make "fib1 :fib2 make "fib2 :fibnew ]
print [\ ]
end
</syntaxhighlight>
=={{header|LOLCODE}}==
Line 8,636 ⟶ 9,224:
=={{header|min}}==
{{works with|min|0.
<syntaxhighlight lang="min">(
(2 <)
(
unless
)
=={{header|MiniScript}}==
Line 9,529 ⟶ 10,117:
endif
endfunction</syntaxhighlight>
=={{header|Odin}}==
Fibinacci Sequence - Iterative Solution<br>
Odin Build: dev-2023-07-nightly:3072479c
<syntaxhighlight lang="odin">
package fib
import "core:fmt"
main :: proc() {
fmt.println("\nFibonacci Seq - starting n and n+1 from 0 and 1:")
fmt.println("------------------------------------------------")
for j: u128 = 0; j <= 20; j += 1 {
fmt.println("n:", j, "\tFib:", fibi(j))
}
}
fibi :: proc(n: u128) -> u128 {
if n < 2 {
return n
}
a, b: u128 = 0, 1
for _ in 2..=n {
a += b
a, b = b, a
}
return b
}
</syntaxhighlight>
{{out}}
<pre>
First 20 Fibonacci Numbers
Starting n and n+1 from 0 and 1
-------------------------------
n: 0 Fib: 0
n: 1 Fib: 1
n: 2 Fib: 1
n: 3 Fib: 2
n: 4 Fib: 3
n: 5 Fib: 5
n: 6 Fib: 8
n: 7 Fib: 13
n: 8 Fib: 21
n: 9 Fib: 34
n: 10 Fib: 55
n: 11 Fib: 89
n: 12 Fib: 144
n: 13 Fib: 233
n: 14 Fib: 377
n: 15 Fib: 610
n: 16 Fib: 987
n: 17 Fib: 1597
n: 18 Fib: 2584
n: 19 Fib: 4181
n: 20 Fib: 6765
-------------------------------
</pre>
=={{header|Oforth}}==
Line 9,535 ⟶ 10,179:
=={{header|Ol}}==
Same as [https://rosettacode.org/wiki/Fibonacci_sequence#Scheme Scheme] example(s).
=={{header|Onyx (wasm)}}==
<syntaxhighlight lang="C">
use core.iter
use core { printf }
// Procedural Simple For-Loop Style
fib_for_loop :: (n: i32) -> i32 {
a: i32 = 0;
b: i32 = 1;
for 0 .. n {
tmp := a;
a = b;
b = tmp + b;
}
return a;
}
FibState :: struct { a, b: u64 }
// Functional Folding Style
fib_by_fold :: (n: i32) => {
end_state :=
iter.counter()
|> iter.take(n)
|> iter.fold(
FibState.{ a = 0, b = 1 },
(_, state) => FibState.{
a = state.b,
b = state.a + state.b
}
);
return end_state.a;
}
// Custom Iterator Style
fib_iterator :: (n: i32) =>
iter.generator(
&.{ a = cast(u64) 0, b = cast(u64) 1, counter = n },
(state: & $Ctx) -> (u64, bool) {
if state.counter <= 0 {
return 0, false;
}
tmp := state.a;
state.a = state.b;
state.b = state.b + tmp;
state.counter -= 1;
return tmp, true;
}
);
main :: () {
printf("\nBy For Loop:\n");
for i in 0 .. 21 {
printf("{} ", fib_for_loop(i));
}
printf("\n\nBy Iterator:\n");
for i in 0 .. 21 {
printf("{} ", fib_by_fold(i));
}
printf("\n\nBy Fold:\n");
for value, index in fib_iterator(21) {
printf("{} ", value);
}
}
</syntaxhighlight>
{{out}}
<pre>
For-Loop:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Functional Fold:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Custom Iterator:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
</pre>
=={{header|OPL}}==
Line 9,801 ⟶ 10,524:
This code is purely for amusement and requires n > 1. It tests numbers in order to see if they are Fibonacci numbers, and waits until it has seen ''n'' of them.
<syntaxhighlight lang="parigp">fib(n)=my(k=0);while(n--,k++;while(!issquare(5*k^2+4)&&!issquare(5*k^2-4),k++));k</syntaxhighlight>
=={{header|ParaCL}}==
<syntaxhighlight lang="parasl">
fibbonachi = func(x) : fibb
{
res = 1;
if (x > 1)
res = fibb(x - 1) + fibb(x - 2);
res;
}
</syntaxhighlight>
=={{header|Pascal}}==
Line 9,887 ⟶ 10,621:
writeln(Fibo_BigInt(555))
>>>43516638122555047989641805373140394725407202037260729735885664398655775748034950972577909265605502785297675867877570
===Doubling (iterative)===
The Clojure solution gives a recursive version of the Fibonacci doubling algorithm. The code below is an iterative version, written in Free Pascal. The unsigned 64-bit integer type can hold Fibonacci numbers up to F[93].
<syntaxhighlight lang="pascal">
program Fibonacci_console;
{$mode objfpc}{$H+}
uses SysUtils;
function Fibonacci( n : word) : uint64;
{
Starts with the pair F[0],F[1]. At each iteration, uses the doubling formulae
to pass from F[k],F[k+1] to F[2k],F[2k+1]. If the current bit of n (starting
from the high end) is 1, there is a further step to F[2k+1],F[2k+2].
}
var
marker, half_n : word;
f, g : uint64; // pair of consecutive Fibonacci numbers
t, u : uint64; // -----"-----
begin
// The values of F[0], F[1], F[2] are assumed to be known
case n of
0 : result := 0;
1, 2 : result := 1;
else begin
half_n := n shr 1;
marker := 1;
while marker <= half_n do marker := marker shl 1;
// First time: current bit is 1 by construction,
// so go straight from F[0],F[1] to F[1],F[2].
f := 1; // = F[1]
g := 1; // = F[2]
marker := marker shr 1;
while marker > 1 do begin
t := f*(2*g - f);
u := f*f + g*g;
if (n and marker = 0) then begin
f := t;
g := u;
end
else begin
f := u;
g := t + u;
end;
marker := marker shr 1;
end;
// Last time: we need only one of the pair.
if (n and marker = 0) then
result := f*(2*g - f)
else
result := f*f + g*g;
end; // end else (i.e. n > 2)
end; // end case
end;
// Main program
var
n : word;
begin
for n := 0 to 93 do
WriteLn( SysUtils.Format( 'F[%2u] = %20u', [n, Fibonacci(n)]));
end.
</syntaxhighlight>
{{out}}
<pre>
F[ 0] = 0
F[ 1] = 1
F[ 2] = 1
F[ 3] = 2
F[ 4] = 3
F[ 5] = 5
F[ 6] = 8
F[ 7] = 13
[...]
F[90] = 2880067194370816120
F[91] = 4660046610375530309
F[92] = 7540113804746346429
F[93] = 12200160415121876738
</pre>
=={{header|PascalABC.NET}}==
Line 9,941 ⟶ 10,758:
use Math::Fibonacci qw/term/;
say term(10000);</syntaxhighlight>
===Array accumulation===
<p>This solution accumulates all Fibonacci numbers up to <i>n</i> into an array of <i>n</i>+1 elements (to account for the zeroth Fibonacci number). When the loop reaches <i>n</i>, the function returns the last element of the array, i.e. the <i>n</i>-th Fibonacci number. This function only works for positive integers, but it can be easily extended into negatives.</p>
<p>Note that, without the use of big integer libraries, pure Perl switches to floats in scientific notation above <i>n</i>=93 and treats any number as infinite above <i>n</i>=1476 (see output). This behaviour could vary across Perl implementations.</p>
<syntaxhighlight lang = "Perl>
sub fibonacci {
my $n = shift;
return 0 if $n < 1;
return 1 if $n == 1;
my @numbers = (0, 1);
push @numbers, $numbers[-1] + $numbers[-2] foreach 2 .. $n;
return $numbers[-1];
}
print "Fibonacci($_) -> ", (fibonacci $_), "\n"
foreach (0 .. 20, 50, 93, 94, 100, 200, 1000, 1476, 1477);
</syntaxhighlight>
{{out}}
<pre>
Fibonacci(0) -> 0
Fibonacci(1) -> 1
Fibonacci(2) -> 1
Fibonacci(3) -> 2
Fibonacci(4) -> 3
Fibonacci(5) -> 5
Fibonacci(6) -> 8
Fibonacci(7) -> 13
Fibonacci(8) -> 21
Fibonacci(9) -> 34
Fibonacci(10) -> 55
Fibonacci(11) -> 89
Fibonacci(12) -> 144
Fibonacci(13) -> 233
Fibonacci(14) -> 377
Fibonacci(15) -> 610
Fibonacci(16) -> 987
Fibonacci(17) -> 1597
Fibonacci(18) -> 2584
Fibonacci(19) -> 4181
Fibonacci(20) -> 6765
Fibonacci(50) -> 12586269025
Fibonacci(93) -> 12200160415121876738
Fibonacci(94) -> 1.97402742198682e+19
Fibonacci(100) -> 3.54224848179262e+20
Fibonacci(200) -> 2.8057117299251e+41
Fibonacci(1000) -> 4.34665576869374e+208
Fibonacci(1476) -> 1.3069892237634e+308
Fibonacci(1477) -> Inf
</pre>
=={{header|Phix}}==
Line 10,350 ⟶ 11,221:
i := i + 1
end;
! b
end.
</syntaxhighlight>
Line 11,494 ⟶ 12,365:
<syntaxhighlight lang="text">1&-:?v2\:2\01\--2\
>$.@</syntaxhighlight>
=={{header|RATFOR}}==
<syntaxhighlight lang="RATFOR">
program Fibonacci
#
integer*4 count, loop
integer*4 num1, num2, fib
1 format(A)
2 format(I4)
3 format(I6,' ')
4 format(' ')
write(6,1,advance='no')'How Many: '
read(5,2)count
num1 = 0
num2 = 1
write(6,3,advance='no')num1
write(6,3,advance='no')num2
for (loop = 3; loop<=count; loop=loop+1)
{
fib = num1 + num2
write(6,3,advance='no')fib
num1 = num2
num2 = fib
}
write(6,4)
end
</syntaxhighlight>
=={{header|Red}}==
(unnecessarily, but pleasantly palindromic)
<syntaxhighlight lang="red">
palindrome: [fn: fn-1 + fn-1: fn]
fibonacci: func [n][
fn-1: 0
Line 11,503 ⟶ 12,407:
loop n palindrome
]</syntaxhighlight>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout <Repeat 18 Fibonacci 1 1>>
} ;
Repeat {
0 s.F e.X = e.X;
s.N s.F e.X = <Repeat <- s.N 1> s.F <Mu s.F e.X>>;
};
Fibonacci {
e.X s.A s.B = e.X s.A s.B <+ s.A s.B>;
};</syntaxhighlight>
{{out}}
<pre>1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765</pre>
=={{header|Relation}}==
Line 11,773 ⟶ 12,693:
===Iterative===
≪ 0 1
0 4 ROLL '''START'''
OVER + SWAP
'''NEXT''' SWAP DROP
≫ '<span style="color:blue">→FIB</span>' STO
≪ { } 0 20 '''FOR''' j j <span style="color:blue">→FIB</span> + '''NEXT''' ≫ EVAL
===Recursive===
≪ '''IF''' DUP 2 > '''THEN'''
DUP 1 - <span style="color:blue">→FIB</span>
SWAP 2 - <span style="color:blue">→FIB</span> +
'''ELSE''' SIGN '''END'''
≫ '<span style="color:blue">→FIB</span>' STO
{{out}}
<pre>
Line 11,795 ⟶ 12,712:
</pre>
===Fast recursive===
A much better recursive approach, based on the formulas: <code>F(2k) =
≪ '''IF''' DUP 2 ≤ '''THEN''' SIGN '''ELSE'''
'''IF''' DUP 2 MOD
'''THEN''' 1 - 2 / DUP <span style="color:blue">→FIB</span> SQ SWAP 1 + <span style="color:blue">→FIB</span> SQ +
'''ELSE''' 2 / DUP <span style="color:blue">→FIB</span> DUP ROT 1 - <span style="color:blue">→FIB</span> 2 * + *
'''END END'''
≫ '<span style="color:blue">→FIB</span>' STO
=={{header|Ruby}}==
Line 13,311 ⟶ 14,225:
<pre>R/S -> 89</pre>
<pre>R/S -> 144</pre>
=={{header|TI-57}}==
{| class="wikitable"
! Step
! Function
! Comment
|-
| 00
| align="center" | <code>STO</code> <code> 0 </code>
| R0 = n
|-
| 01
|align="center" | <code>C.t</code>
| R7 = 0
|-
| 02
|align="center" | <code> 1 </code>
| Display = 1
|-
| 03
|align="center" | <code>INV</code> <code>SUM</code> <code> 1 </code>
| R0 -= 1
|-
| 04
|align="center" | <code>Lbl</code> <code> 1 </code>
| loop
|-
| 05
|align="center" | <code> + </code>
|
|-
| 06
|align="center" | <code>x⮂t</code>
| Swap Display with R7
|-
| 07
|align="center" | <code> = </code>
| Display += R7
|-
| 08
|align="center" | <code>Dsz</code>
| R0 -= 1
|-
| 09
|align="center" | <code>GTO</code> <code>1</code>
| until R0 == 0
|-
| 10
|align="center" | <code>R/S</code>
| Stop
|-
| 11
|align="center" | <code>RST</code>
| Go back to step 0
|-
|}
10 <code>RST</code> <code>R/S</code>
{{out}}
<pre>
55.
</pre>
=={{header|TSE SAL}}==
Line 13,429 ⟶ 14,404:
fibionacci 46=1836311903
</pre>
=={{header|Uiua}}==
{{works with|Uiua|0.10.0-dev.1}}
Simple recursive example with memoisation.
<syntaxhighlight lang="Uiua">
F ← |1 memo⟨+⊃(F-1)(F-2)|∘⟩<2.
F ⇡20
</syntaxhighlight>
=={{header|UNIX Shell}}==
Line 13,948 ⟶ 14,931:
=={{header|Wren}}==
<syntaxhighlight lang="
var fibItr = Fn.new { |n|
if (n < 2) return n
Line 14,165 ⟶ 15,148:
exx ; now in reg set
ret</syntaxhighlight>
=={{header|YAMLScript}}==
<syntaxhighlight lang="yaml">
!yamlscript/v0
defn main(n=10):
loop [a 0, b 1, i 1]:
say: a
if (i < n):
recur: b, (a + b), (i + 1)
</syntaxhighlight>
=={{header|zkl}}==
| |||