Fibonacci sequence: Difference between revisions
→{{header|PARI/GP}}: sinh
Wanderkind (talk | contribs) |
CRGreathouse (talk | contribs) (→{{header|PARI/GP}}: sinh) |
||
| (84 intermediate revisions by 40 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,582 ⟶ 1,704:
print n + chr(9) + c
</syntaxhighlight>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> PRINT FNfibonacci_r(1), FNfibonacci_i(1)
PRINT FNfibonacci_r(13), FNfibonacci_i(13)
PRINT FNfibonacci_r(26), FNfibonacci_i(26)
END
DEF FNfibonacci_r(N)
IF N < 2 THEN = N
= FNfibonacci_r(N-1) + FNfibonacci_r(N-2)
DEF FNfibonacci_i(N)
LOCAL F, I, P, T
IF N < 2 THEN = N
P = 1
FOR I = 1 TO N
T = F
F += P
P = T
NEXT
= F
</syntaxhighlight>
{{out}}
<pre> 1 1
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,609 ⟶ 1,820:
READY.</pre>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">let a = 1
let b = 1
print "Fibonacci Sequence"
for i = 0 to 20
let s = a + b
let a = b
let b = s
print s
next i</syntaxhighlight>
{{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}}===
Extended sequence coded big integer.
<syntaxhighlight lang="freebasic">'Fibonacci extended
'Freebasic version 24 Windows
Dim Shared ADDQmod(0 To 19) As Ubyte
Dim Shared ADDbool(0 To 19) As Ubyte
For z As Integer=0 To 19
ADDQmod(z)=(z Mod 10+48)
ADDbool(z)=(-(10<=z))
Next z
Function plusINT(NUM1 As String,NUM2 As String) As String
Dim As Byte flag
#macro finish()
three=Ltrim(three,"0")
If three="" Then Return "0"
If flag=1 Then Swap NUM2,NUM1
Return three
Exit Function
#endmacro
var lenf=Len(NUM1)
var lens=Len(NUM2)
If lens>lenf Then
Swap NUM2,NUM1
Swap lens,lenf
flag=1
End If
var diff=lenf-lens-Sgn(lenf-lens)
var three="0"+NUM1
var two=String(lenf-lens,"0")+NUM2
Dim As Integer n2
Dim As Ubyte addup,addcarry
addcarry=0
For n2=lenf-1 To diff Step -1
addup=two[n2]+NUM1[n2]-96
three[n2+1]=addQmod(addup+addcarry)
addcarry=addbool(addup+addcarry)
Next n2
If addcarry=0 Then
finish()
End If
If n2=-1 Then
three[0]=addcarry+48
finish()
End If
For n2=n2 To 0 Step -1
addup=two[n2]+NUM1[n2]-96
three[n2+1]=addQmod(addup+addcarry)
addcarry=addbool(addup+addcarry)
Next n2
three[0]=addcarry+48
finish()
End Function
Function fibonacci(n As Integer) As String
Dim As String sl,l,term
sl="0": l="1"
If n=1 Then Return "0"
If n=2 Then Return "1"
n=n-2
For x As Integer= 1 To n
term=plusINT(l,sl)
sl=l
l=term
Next x
Function =term
End Function
'============== EXAMPLE ===============
print "THE SEQUENCE TO 10:"
print
For n As Integer=1 To 10
Print "term";n;": "; fibonacci(n)
Next n
print
print "Selected Fibonacci number"
print "Fibonacci 500"
print
print fibonacci(500)
Sleep</syntaxhighlight>
{{out}}
<pre>THE SEQUENCE TO 10:
term 1: 0
term 2: 1
term 3: 1
term 4: 2
term 5: 3
term 6: 5
term 7: 8
term 8: 13
term 9: 21
term 10: 34
Selected Fibonacci number
Fibonacci 500
86168291600238450732788312165664788095941068326060883324529903470149056115823592
713458328176574447204501</pre>
==={{header|FTCBASIC}}===
<syntaxhighlight lang="basic">define a = 1, b = 1, s = 0, i = 0
cls
print "Fibonacci Sequence"
do
let s = a + b
let a = b
let b = s
+1 i
print s
loop i < 20
pause
end</syntaxhighlight>
==={{header|GFA Basic}}===
<syntaxhighlight lang="text">
'
' Compute nth Fibonacci number
'
' open a window for display
OPENW 1
CLEARW 1
' Display some fibonacci numbers
' Fib(46) is the largest number GFA Basic can reach
' (long integers are 4 bytes)
FOR i%=0 TO 46
PRINT "fib(";i%;")=";@fib(i%)
NEXT i%
' wait for a key press and tidy up
~INP(2)
CLOSEW 1
'
' Function to compute nth fibonacci number
' n must be in range 0 to 46, inclusive
'
FUNCTION fib(n%)
LOCAL n0%,n1%,nn%,i%
n0%=0
n1%=1
SELECT n%
CASE 0
RETURN n0%
CASE 1
RETURN n1%
DEFAULT
FOR i%=2 TO n%
nn%=n0%+n1%
n0%=n1%
n1%=nn%
NEXT i%
RETURN nn%
ENDSELECT
ENDFUNC
</syntaxhighlight>
==={{header|GW-BASIC}}===
{{works with|BASICA}}
====Iterative====
<syntaxhighlight lang="gwbasic">
10 ' SAVE"FIBONA", A
20 ' Secuencia de Fibonacci
30 ' Var
40 DEFDBL D
50 IMAXFIBO% = 76
60 DNUM1 = 1: DNUM2 = DNUM1
70 CLS
80 PRINT "Este programa calcula la serie de Fibonacci."
90 PRINT DNUM1; DNUM2;
100 FOR I% = 1 TO IMAXFIBO%
110 DNUM3 = DNUM1 + DNUM2
120 PRINT DNUM3;
130 DNUM1 = DNUM2: DNUM2 = DNUM3
140 NEXT I%
150 PRINT
160 PRINT "Fin de la ejecución del programa."
170 END
</syntaxhighlight>
{{out}}
<pre>
Este programa calcula la serie de Fibonacci.
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 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 190392490709135
308061521170129 498454011879264 806515533049393 1304969544928657
2111485077978050 3416454622906707 5527939700884757 8944394323791464
Fin de la ejecución del programa.
Ok
</pre>
====Binet formula====
<syntaxhighlight lang="gwbasic">
10 ' SAVE"FIBINF", A
20 ' Secuencia de Fibonacci mediante la fórmula de Binet
30 ' Var
40 DEFDBL D
50 IMAXFIBO% = 77
60 DSQR5 = SQR(5)
70 DPIV1 = (1 + DSQR5) / 2
80 DPIV2 = (1 - DSQR5) / 2
90 DNUM1 = DPIV1: DNUM2 = DPIV2
100 CLS
110 PRINT "Este programa calcula la serie de Fibonacci."
120 FOR I% = 1 TO IMAXFIBO%
130 DNUM1 = DNUM1 * DPIV1
140 DNUM2 = DNUM2 * DPIV2
150 PRINT FIX(((DNUM1 - DNUM2) / DSQR5)+.5);
160 NEXT I%
170 PRINT
180 PRINT "Fin de la ejecución del programa."
190 END
</syntaxhighlight>
{{out}}
<pre>
Este programa calcula la serie de Fibonacci.
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 2178310 3524579 5702889 9227468 14930357 24157826
39088183 63246010 102334195 165580207 267914406 433494620 701409036
1134903671 1836312733 2971216446 4807529247 7778745802 12586275225
20365021312 32951296999 53316319058 86267617266 139583938281 225851558714
365435502118 591287069122 956722584654 1548009675479 2504732295250
4052742027550 6557474414738 10610216591046 17167691246479 27777908226979
44945600103607 72723509350188 117669111103547 190392623123089
308061738545741 498454368657289 806516118510594 1304970505463907
2111486653578091 3416457206941612 5527943938022908 8944401270367342
Fin de la ejecución del programa.
Ok
</pre>
==={{header|Integer BASIC}}===
Line 1,636 ⟶ 2,113:
200 LET FIB=A
210 END DEF</syntaxhighlight>
==={{header|Liberty BASIC}}===
====Iterative/Recursive====
{{works with|Just BASIC}}
<syntaxhighlight lang="lb">
for i = 0 to 15
print fiboR(i),fiboI(i)
next i
function fiboR(n)
if n <= 1 then
fiboR = n
else
fiboR = fiboR(n-1) + fiboR(n-2)
end if
end function
function fiboI(n)
a = 0
b = 1
for i = 1 to n
temp = a + b
a = b
b = temp
next i
fiboI = a
end function
</syntaxhighlight>
{{out}}
<pre>
0 0
1 1
1 1
2 2
3 3
5 5
8 8
13 13
21 21
34 34
55 55
89 89
144 144
233 233
377 377
610 610
</pre>
====Iterative/Negative====
{{works with|Just BASIC}}
<syntaxhighlight lang="lb">
print "Rosetta Code - Fibonacci sequence": print
print " n Fn"
for x=-12 to 12 '68 max
print using("### ", x); using("##############", FibonacciTerm(x))
next x
print
[start]
input "Enter a term#: "; n$
n$=lower$(trim$(n$))
if n$="" then print "Program complete.": end
print FibonacciTerm(val(n$))
goto [start]
function FibonacciTerm(n)
n=int(n)
FTa=0: FTb=1: FTc=-1
select case
case n=0 : FibonacciTerm=0 : exit function
case n=1 : FibonacciTerm=1 : exit function
case n=-1 : FibonacciTerm=-1 : exit function
case n>1
for x=2 to n
FibonacciTerm=FTa+FTb
FTa=FTb: FTb=FibonacciTerm
next x
exit function
case n<-1
for x=-2 to n step -1
FibonacciTerm=FTa+FTc
FTa=FTc: FTc=FibonacciTerm
next x
exit function
end select
end function
</syntaxhighlight>
{{out}}
<pre>
Rosetta Code - Fibonacci sequence
n Fn
-12 -144
-11 -89
-10 -55
-9 -34
-8 -21
-7 -13
-6 -8
-5 -5
-4 -3
-3 -2
-2 -1
-1 -1
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
Enter a term#: 12
144
Enter a term#:
Program complete.
</pre>
==={{header|Microsoft Small Basic}}===
====Iterative====
<syntaxhighlight lang="smallbasic">' Fibonacci sequence - 31/07/2018
n = 139
f1 = 0
f2 = 1
TextWindow.WriteLine("fibo(0)="+f1)
TextWindow.WriteLine("fibo(1)="+f2)
For i = 2 To n
f3 = f1 + f2
TextWindow.WriteLine("fibo("+i+")="+f3)
f1 = f2
f2 = f3
EndFor</syntaxhighlight>
{{out}}
<pre>
fibo(139)=50095301248058391139327916261
</pre>
====Binet's Formula====
<syntaxhighlight lang="smallbasic">' Fibonacci sequence - Binet's Formula - 31/07/2018
n = 69
sq5=Math.SquareRoot(5)
phi1=(1+sq5)/2
phi2=(1-sq5)/2
phi1n=phi1
phi2n=phi2
For i = 2 To n
phi1n=phi1n*phi1
phi2n=phi2n*phi2
TextWindow.Write(Math.Floor((phi1n-phi2n)/sq5)+" ")
EndFor</syntaxhighlight>
{{out}}
<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>
==={{header|PowerBASIC}}===
{{trans|BASIC}}
There seems to be a limitation (dare I say, bug?) in PowerBASIC regarding how large numbers are stored. 10E17 and larger get rounded to the nearest 10. For F(n), where ABS(n) > 87, is affected like this:
actual: displayed:
F(88) 1100087778366101931 1100087778366101930
F(89) 1779979416004714189 1779979416004714190
F(90) 2880067194370816120 2880067194370816120
F(91) 4660046610375530309 4660046610375530310
F(92) 7540113804746346429 7540113804746346430
<syntaxhighlight lang="powerbasic">FUNCTION fibonacci (n AS LONG) AS QUAD
DIM u AS LONG, a AS LONG, L0 AS LONG, outP AS QUAD
STATIC fibNum() AS QUAD
u = UBOUND(fibNum)
a = ABS(n)
IF u < 1 THEN
REDIM fibNum(1)
fibNum(1) = 1
u = 1
END IF
SELECT CASE a
CASE 0 TO 92
IF a > u THEN
REDIM PRESERVE fibNum(a)
FOR L0 = u + 1 TO a
fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
IF 88 = L0 THEN fibNum(88) = fibNum(88) + 1
NEXT
END IF
IF n < 0 THEN
fibonacci = fibNum(a) * ((-1)^(a+1))
ELSE
fibonacci = fibNum(a)
END IF
CASE ELSE
'Even without the above-mentioned bug, we're still limited to
'F(+/-92), due to data type limits. (F(93) = &hA94F AD42 221F 2702)
ERROR 6
END SELECT
END FUNCTION
FUNCTION PBMAIN () AS LONG
DIM n AS LONG
#IF NOT %DEF(%PB_CC32)
OPEN "out.txt" FOR OUTPUT AS 1
#ENDIF
FOR n = -92 TO 92
#IF %DEF(%PB_CC32)
PRINT STR$(n); ": "; FORMAT$(fibonacci(n), "#")
#ELSE
PRINT #1, STR$(n) & ": " & FORMAT$(fibonacci(n), "#")
#ENDIF
NEXT
CLOSE
END FUNCTION</syntaxhighlight>
==={{header|PureBasic}}===
====Macro based calculation====
<syntaxhighlight lang="purebasic">Macro Fibonacci (n)
Int((Pow(((1+Sqr(5))/2),n)-Pow(((1-Sqr(5))/2),n))/Sqr(5))
EndMacro</syntaxhighlight>
====Recursive====
<syntaxhighlight lang="purebasic">Procedure FibonacciReq(n)
If n<2
ProcedureReturn n
Else
ProcedureReturn FibonacciReq(n-1)+FibonacciReq(n-2)
EndIf
EndProcedure</syntaxhighlight>
====Recursive & optimized with a static hash table====
This will be much faster on larger n's, this as it uses a table to store known parts instead of recalculating them.
On my machine the speedup compares to above code is
Fib(n) Speedup
20 2
25 23
30 217
40 25847
46 1156741
<syntaxhighlight lang="purebasic">Procedure Fibonacci(n)
Static NewMap Fib.i()
Protected FirstRecursion
If MapSize(Fib())= 0 ; Init the hash table the first run
Fib("0")=0: Fib("1")=1
FirstRecursion = #True
EndIf
If n >= 2
Protected.s s=Str(n)
If Not FindMapElement(Fib(),s) ; Calculate only needed parts
Fib(s)= Fibonacci(n-1)+Fibonacci(n-2)
EndIf
n = Fib(s)
EndIf
If FirstRecursion ; Free the memory when finalizing the first call
ClearMap(Fib())
EndIf
ProcedureReturn n
EndProcedure</syntaxhighlight>
'''Example'''
Fibonacci(0)= 0
Fibonacci(1)= 1
Fibonacci(2)= 1
Fibonacci(3)= 2
Fibonacci(4)= 3
Fibonacci(5)= 5
FibonacciReq(0)= 0
FibonacciReq(1)= 1
FibonacciReq(2)= 1
FibonacciReq(3)= 2
FibonacciReq(4)= 3
FibonacciReq(5)= 5
==={{header|QB64}}===
''CBTJD'': 2020/03/13
<syntaxhighlight lang="qbasic">_DEFINE F AS _UNSIGNED _INTEGER64
CLS
PRINT
PRINT "Enter 40 to more easily see the difference in calculation speeds."
PRINT
INPUT "Enter n for Fibonacci(n): ", n
PRINT
PRINT " Analytic Method (Fastest): F("; LTRIM$(STR$(n)); ") ="; fA(n)
PRINT "Iterative Method (Fast): F("; LTRIM$(STR$(n)); ") ="; fI(n)
PRINT "Recursive Method (Slow): F("; LTRIM$(STR$(n)); ") ="; fR(n)
END
' === Analytic Fibonacci Function (Fastest)
FUNCTION fA (n)
fA = INT(0.5 + (((SQR(5) + 1) / 2) ^ n) / SQR(5))
END FUNCTION
' === Iterative Fibonacci Function (Fast)
FUNCTION fI (n)
FOR i = 1 TO n
IF i < 3 THEN a = 1: b = 1
t = fI + b: fI = b: b = t
NEXT
END FUNCTION
' === Recursive Fibonacci function (Slow)
FUNCTION fR (n)
IF n <= 1 THEN
fR = n
ELSE
fR = fR(n - 1) + fR(n - 2)
END IF
END FUNCTION
</syntaxhighlight>
Fibonacci from Russia
<syntaxhighlight lang="qbasic">DIM F(80) AS DOUBLE 'FibRus.bas DANILIN
F(1) = 0: F(2) = 1
'OPEN "FibRus.txt" FOR OUTPUT AS #1
FOR i = 3 TO 80
F(i) = F(i-1)+F(i-2)
NEXT i
FOR i = 1 TO 80
f$ = STR$(F(i)): LF = 22 - LEN(f$)
n$ = ""
FOR j = 1 TO LF: n$ = " " + n$: NEXT
f$ = n$ + f$
PRINT i, f$: ' PRINT #1, i, f$
NEXT i</syntaxhighlight>
{{out}}
<pre>1 0
2 1
3 1
4 2
5 3
6 5
7 8
8 13
9 21
...
24 28657
25 46368
26 75025
...
36 9227465
37 14930352
38 24157817
...
48 2971215073
49 4807526976
50 7778742049
...
60 956722026041
61 1548008755920
62 2504730781961
...
76 2111485077978050
77 3416454622906707
78 5527939700884757
79 8944394323791464
80 1.447233402467622D+16</pre>
==={{header|QBasic}}===
Line 1,706 ⟶ 2,603:
====Recursive====
This example can't handle n < 0.
<syntaxhighlight lang="qbasic">FUNCTION recFib (n)
IF (n < 2) THEN
Line 1,716 ⟶ 2,612:
====Array (Table) Lookup====
This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.)
Line 1,741 ⟶ 2,636:
'*****sample inputs*****</syntaxhighlight>
<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}}===
<syntaxhighlight lang="runbasic">for i = 0 to 10
print i;" ";fibR(i);" ";fibI(i)
next i
end
function fibR(n)
if n < 2 then fibR = n else fibR = fibR(n-1) + fibR(n-2)
end function
function fibI(n)
b = 1
for i = 1 to n
t = a + b
a = b
b = t
next i
fibI = a
end function</syntaxhighlight>
==={{header|S-BASIC}}===
Note that the 23rd Fibonacci number (=28657) is the largest that can be generated without overflowing S-BASIC's integer data type.
<syntaxhighlight lang="basic">
rem - iterative function to calculate nth fibonacci number
function fibonacci(n = integer) = integer
var f, i, p1, p2 = integer
p1 = 0
p2 = 1
if n = 0 then
f = 0
else
for i = 1 to n
f = p1 + p2
p2 = p1
p1 = f
next i
end = f
rem - exercise the function
var i = integer
for i = 0
print fibonacci(i);
next i
end
</syntaxhighlight>
{{out}}
<pre>
</pre>
==={{header|Sinclair ZX81 BASIC}}===
Line 1,822 ⟶ 2,730:
120 GOSUB 70
130 RETURN</syntaxhighlight>
==={{header|smart BASIC}}===
The Iterative method is slow (relatively) and the Recursive method doubly so since it references the recursion function twice.
The N-th Term (fibN) function is much faster as it utilizes Binet's Formula.
<ul>
<li>fibR: Fibonacci Recursive</li>
<li>fibI: Fibonacci Iterative</li>
<li>fibN: Fibonacci N-th Term</li>
</ul>
<syntaxhighlight lang="qbasic">FOR i = 0 TO 15
PRINT fibR(i),fibI(i),fibN(i)
NEXT i
/* Recursive Method */
DEF fibR(n)
IF n <= 1 THEN
fibR = n
ELSE
fibR = fibR(n-1) + fibR(n-2)
ENDIF
END DEF
/* Iterative Method */
DEF fibI(n)
a = 0
b = 1
FOR i = 1 TO n
temp = a + b
a = b
b = temp
NEXT i
fibI = a
END DEF
/* N-th Term Method */
DEF fibN(n)
uphi = .5 + SQR(5)/2
lphi = .5 - SQR(5)/2
fibN = (uphi^n-lphi^n)/SQR(5)
END DEF</syntaxhighlight>
==={{header|Softbridge BASIC}}===
====Iterative====
<syntaxhighlight lang="basic">
Function Fibonacci(n)
x = 0
y = 1
i = 0
n = ABS(n)
If n < 2 Then
Fibonacci = n
Else
Do Until (i = n)
sum = x+y
x=y
y=sum
i=i+1
Loop
Fibonacci = x
End If
End Function
</syntaxhighlight>
==={{header|TI-83 BASIC}}===
==== Sequence table ====
<syntaxhighlight lang="ti83b">[Y=]
nMin=0
u(n)=u(n-1)+u(n-2)
u(nMin)={1,0}
[TABLE]
n u(n)
------- -------
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 </syntaxhighlight>
==== Iterative ====
<syntaxhighlight lang="ti83b">{0,1
While 1
Disp Ans(1
{Ans(2),sum(Ans
End</syntaxhighlight>
==== Binet's formula ====
<syntaxhighlight lang="ti83b">Prompt N
.5(1+√(5 //golden ratio
(Ans^N–(-Ans)^-N)/√(5</syntaxhighlight>
==={{header|TI-89 BASIC}}===
====Recursive====
Optimized implementation (too slow to be usable for ''n'' higher than about 12).
<syntaxhighlight lang="ti89b">fib(n)
when(n<2, n, fib(n-1) + fib(n-2))</syntaxhighlight>
====Iterative====
Unoptimized implementation (I think the for loop can be eliminated, but I'm not sure).
<syntaxhighlight lang="ti89b">fib(n)
Func
Local a,b,c,i
0→a
1→b
For i,1,n
a→c
b→a
c+b→b
EndFor
a
EndFunc</syntaxhighlight>
==={{header|Tiny BASIC}}===
{{works with|TinyBasic}}
<syntaxhighlight lang="basic">10 LET A = 0
20 LET B = 1
30 PRINT "Which F_n do you want?"
40 INPUT N
50 IF N = 0 THEN GOTO 140
60 IF N = 1 THEN GOTO 120
70 LET C = B + A
80 LET A = B
90 LET B = C
100 LET N = N - 1
110 GOTO 60
120 PRINT B
130 END
140 PRINT 0
150 END
</syntaxhighlight>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION fibonacci (n)
LET n1 = 0
LET n2 = 1
FOR k = 1 TO ABS(n)
LET sum = n1 + n2
LET n1 = n2
LET n2 = sum
NEXT k
IF n < 0 THEN
LET fibonacci = n1 * ((-1) ^ ((-n) + 1))
ELSE
LET fibonacci = n1
END IF
END FUNCTION
PRINT fibonacci(0) ! 0
PRINT fibonacci(13) ! 233
PRINT fibonacci(-42) !-267914296
PRINT fibonacci(47) ! 2971215073
END</syntaxhighlight>
==={{header|VBA}}===
Like Visual Basic .NET, but with keyword "Public" and type Variant (subtype Currency) instead of Decimal:
<syntaxhighlight lang="vb">Public Function Fib(ByVal n As Integer) As Variant
Dim fib0 As Variant, fib1 As Variant, sum As Variant
Dim i As Integer
fib0 = 0
fib1 = 1
For i = 1 To n
sum = fib0 + fib1
fib0 = fib1
fib1 = sum
Next i
Fib = fib0
End Function </syntaxhighlight>
With Currency type, maximum value is fibo(73).
The (slow) recursive version:
<syntaxhighlight lang="vba">
Public Function RFib(Term As Integer) As Long
If Term < 2 Then RFib = Term Else RFib = RFib(Term - 1) + RFib(Term - 2)
End Function
</syntaxhighlight>
With Long type, maximum value is fibo(46).
==={{header|VBScript}}===
====Non-recursive, object oriented, generator====
Defines a generator class, with a default Get property. Uses Currency for larger-than-Long values. Tests for overflow and switches to Double. Overflow information also available from class.
=====Class Definition:=====
<syntaxhighlight lang="vb">class generator
dim t1
dim t2
dim tn
dim cur_overflow
Private Sub Class_Initialize
cur_overflow = false
t1 = ccur(0)
t2 = ccur(1)
tn = ccur(t1 + t2)
end sub
public default property get generated
on error resume next
generated = ccur(tn)
if err.number <> 0 then
generated = cdbl(tn)
cur_overflow = true
end if
t1 = ccur(t2)
if err.number <> 0 then
t1 = cdbl(t2)
cur_overflow = true
end if
t2 = ccur(tn)
if err.number <> 0 then
t2 = cdbl(tn)
cur_overflow = true
end if
tn = ccur(t1+ t2)
if err.number <> 0 then
tn = cdbl(t1) + cdbl(t2)
cur_overflow = true
end if
on error goto 0
end property
public property get overflow
overflow = cur_overflow
end property
end class</syntaxhighlight>
=====Invocation:=====
<syntaxhighlight lang="vb">dim fib
set fib = new generator
dim i
for i = 1 to 100
wscript.stdout.write " " & fib
if fib.overflow then
wscript.echo
exit for
end if
next</syntaxhighlight>
{{out}}
<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 190392490709135 308061521170129 498454011879264 806515533049393</pre>
==={{header|Visual Basic}}===
{{works with|Visual Basic|VB6 Standard}}
Maximum integer value (7*10^28) can be obtained by using decimal type, but decimal type is only a sub type of the variant type.
<syntaxhighlight lang="vb">Sub fibonacci()
Const n = 139
Dim i As Integer
Dim f1 As Variant, f2 As Variant, f3 As Variant 'for Decimal
f1 = CDec(0): f2 = CDec(1) 'for Decimal setting
Debug.Print "fibo("; 0; ")="; f1
Debug.Print "fibo("; 1; ")="; f2
For i = 2 To n
f3 = f1 + f2
Debug.Print "fibo("; i; ")="; f3
f1 = f2
f2 = f3
Next i
End Sub 'fibonacci</syntaxhighlight>
{{Out}}
<pre>fibo( 0 )= 0
fibo( 1 )= 1
fibo( 2 )= 1
...
fibo( 137 )= 19134702400093278081449423917
fibo( 138 )= 30960598847965113057878492344
fibo( 139 )= 50095301248058391139327916261 </pre>
==={{header|Visual Basic .NET}}===
'''Platform:''' [[.NET]]
====Iterative====
{{works with|Visual Basic .NET|9.0+}}
With Decimal type, maximum value is fibo(139).
<syntaxhighlight lang="vbnet">Function Fib(ByVal n As Integer) As Decimal
Dim fib0, fib1, sum As Decimal
Dim i As Integer
fib0 = 0
fib1 = 1
For i = 1 To n
sum = fib0 + fib1
fib0 = fib1
fib1 = sum
Next
Fib = fib0
End Function</syntaxhighlight>
====Recursive====
{{works with|Visual Basic .NET|9.0+}}
<syntaxhighlight lang="vbnet">Function Seq(ByVal Term As Integer)
If Term < 2 Then Return Term
Return Seq(Term - 1) + Seq(Term - 2)
End Function</syntaxhighlight>
====BigInteger====
There is no real maximum value of BigInterger class, except the memory to store the number.
Within a minute, fibo(2000000) is a number with 417975 digits.
<syntaxhighlight lang="vbnet"> Function FiboBig(ByVal n As Integer) As BigInteger
' Fibonacci sequence with BigInteger
Dim fibn2, fibn1, fibn As BigInteger
Dim i As Integer
fibn = 0
fibn2 = 0
fibn1 = 1
If n = 0 Then
Return fibn2
ElseIf n = 1 Then
Return fibn1
ElseIf n >= 2 Then
For i = 2 To n
fibn = fibn2 + fibn1
fibn2 = fibn1
fibn1 = fibn
Next i
Return fibn
End If
Return 0
End Function 'FiboBig
Sub fibotest()
Dim i As Integer, s As String
i = 2000000 ' 2 millions
s = FiboBig(i).ToString
Console.WriteLine("fibo(" & i & ")=" & s & " - length=" & Len(s))
End Sub 'fibotest</syntaxhighlight>
====BigInteger, speedier method====
{{Libheader|System.Numerics}}
This method doesn't need to iterate the entire list, and is much faster. The 2000000 (two millionth) Fibonacci number can be found in a fraction of a second.<br/>Algorithm from [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html here, see section 3, ''Finding Fibonacci Numbers Fully''.]
<syntaxhighlight lang="vbnet">Imports System
Imports System.Collections.Generic
Imports BI = System.Numerics.BigInteger
Module Module1
' A sparse array of values calculated along the way
Dim sl As SortedList(Of Integer, BI) = New SortedList(Of Integer, BI)()
' Square a BigInteger
Function sqr(ByVal n As BI) As BI
Return n * n
End Function
' Helper routine for Fsl(). It adds an entry to the sorted list when necessary
Sub IfNec(n As Integer)
If Not sl.ContainsKey(n) Then sl.Add(n, Fsl(n))
End Sub
' This routine is semi-recursive, but doesn't need to evaluate every number up to n.
' Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
Function Fsl(ByVal n As Integer) As BI
If n < 2 Then Return n
Dim n2 As Integer = n >> 1, pm As Integer = n2 + ((n And 1) << 1) - 1 : IfNec(n2) : IfNec(pm)
Return If(n2 > pm, (2 * sl(pm) + sl(n2)) * sl(n2), sqr(sl(n2)) + sqr(sl(pm)))
End Function
' Conventional iteration method (not used here)
Function Fm(ByVal n As BI) As BI
If n < 2 Then Return n
Dim cur As BI = 0, pre As BI = 1
For i As Integer = 0 To n - 1
Dim sum As BI = cur + pre : pre = cur : cur = sum : Next : Return cur
End Function
Sub Main()
Dim vlen As Integer, num As Integer = 2_000_000, digs As Integer = 35
Dim sw As System.Diagnostics.Stopwatch = System.Diagnostics.Stopwatch.StartNew()
Dim v As BI = Fsl(num) : sw.[Stop]()
Console.Write("{0:n3} ms to calculate the {1:n0}th Fibonacci number, ", sw.Elapsed.TotalMilliseconds, num)
vlen = CInt(Math.Ceiling(BI.Log10(v))) : Console.WriteLine("number of digits is {0}", vlen)
If vlen < 10000 Then
sw.Restart() : Console.WriteLine(v) : sw.[Stop]()
Console.WriteLine("{0:n3} ms to write it to the console.", sw.Elapsed.TotalMilliseconds)
Else
Console.Write("partial: {0}...{1}", v / BI.Pow(10, vlen - digs), v Mod BI.Pow(10, digs))
End If
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>120.374 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975
partial: 85312949175076415430516606545038251...91799493108960825129188777803453125</pre>
==={{header|Xojo}}===
Pass n to this function where n is the desired number of iterations. This example uses the UInt64 datatype which is as unsigned 64 bit integer. As such, it overflows after the 93rd iteration.
<syntaxhighlight lang="vb">Function fibo(n As Integer) As UInt64
Dim noOne As UInt64 = 1
Dim noTwo As UInt64 = 1
Dim sum As UInt64
For i As Integer = 3 To n
sum = noOne + noTwo
noTwo = noOne
noOne = sum
Next
Return noOne
End Function</syntaxhighlight>
==={{header|Yabasic}}===
====Iterative====
<syntaxhighlight lang="vbnet">sub fibonacciI (n)
local n1, n2, k, sum
n1 = 0
n2 = 1
for k = 1 to abs(n)
sum = n1 + n2
n1 = n2
n2 = sum
next k
if n < 1 then
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>
==={{header|ZX Spectrum Basic}}===
====Iterative====
<syntaxhighlight lang="zxbasic">10 REM Only positive numbers
20 LET n=10
30 LET n1=0: LET n2=1
40 FOR k=1 TO n
50 LET sum=n1+n2
60 LET n1=n2
70 LET n2=sum
80 NEXT k
90 PRINT n1</syntaxhighlight>
====Analytic====
<syntaxhighlight lang="zxbasic">10 DEF FN f(x)=INT (0.5+(((SQR 5+1)/2)^x)/SQR 5)</syntaxhighlight>
=={{header|Batch File}}==
Line 1,911 ⟶ 3,294:
// vim: set syntax=c ts=4 sw=4 et:
</syntaxhighlight>
=={{header|bc}}==
Line 2,167 ⟶ 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 2,372 ⟶ 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 2,822 ⟶ 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 3,379 ⟶ 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 3,423 ⟶ 4,861:
<pre>0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181</pre>
=={{header|Crystal}}==
===Recursive===
<syntaxhighlight lang="ruby">def fib(n)
Line 3,817 ⟶ 5,237:
<syntaxhighlight lang="dibol-11">
;
; are noot computed.
START ;First 15 Fibonacci NUmbers
Line 3,824 ⟶ 5,247:
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2,
RECORD HEADER
, A32, "First
RECORD OUTPUT
Line 3,840 ⟶ 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 3,851 ⟶ 5,285:
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE.
CLOSE 8
END
</syntaxhighlight>
=={{header|DWScript}}==
Line 3,894 ⟶ 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 4,093 ⟶ 5,527:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA
<syntaxhighlight lang="elena">import extensions;
Line 4,105 ⟶ 5,539:
else
{
for(int i := 2
{
int t := ac[1];
Line 4,118 ⟶ 5,552:
public program()
{
for(int i := 0
{
console.printLine(fibu(i))
Line 4,148 ⟶ 5,582:
long n_1 := 1l;
$yield
$yield
while(true)
Line 4,155 ⟶ 5,589:
long n := n_2 + n_1;
$yield
n_2 := n_1;
Line 4,167 ⟶ 5,601:
auto e := new FibonacciGenerator();
for(int i := 0
console.printLine(e.next())
};
Line 4,200 ⟶ 5,634:
=={{header|Elm}}==
Naïve recursive implementation.
<syntaxhighlight lang="haskell">fibonacci : Int -> Int
Line 4,206 ⟶ 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 4,885 ⟶ 6,344:
}
}
</syntaxhighlight>
=={{header|Fe}}==
Recursive:
<syntaxhighlight lang="clojure">
(= fib (fn (n)
(if (< n 2) n
(+ (fib (- n 1)) (fib (- n 2))))))
</syntaxhighlight>
Iterative:
<syntaxhighlight lang="clojure">
(= fib (fn (n)
(let p0 0)
(let p1 1)
(while (< 0 n)
(= n (- n 1))
(let tmp (+ p0 p1))
(= p0 p1)
(= p1 tmp))
p0))
</syntaxhighlight>
Line 5,201 ⟶ 6,680:
fibonacci := f[previous];
end;</syntaxhighlight>
=={{header|Frink}}==
Line 5,349 ⟶ 6,723:
RET</syntaxhighlight>
=={{header|FunL}}==
Line 5,614 ⟶ 6,967:
=={{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 5,632 ⟶ 7,059:
<syntaxhighlight lang="gecho">0 1 dup wover + dup wover + dup wover + dup wover +</syntaxhighlight>
Prints the first several fibonacci numbers...
=={{header|GML}}==
<syntaxhighlight lang="gml">///fibonacci(n)
//Returns the nth fibonacci number
Line 5,761 ⟶ 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 6,241 ⟶ 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 6,248 ⟶ 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 6,625 ⟶ 8,077:
=={{header|K}}==
{{works with|Kona}}
===Recursive===
Line 6,639 ⟶ 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 6,746 ⟶ 8,200:
{{VI solution|LabVIEW_Fibonacci_sequence.png}}
=={{header|
<syntaxhighlight lang="scheme">
Line 6,832 ⟶ 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 6,844 ⟶ 8,332:
=={{header|langur}}==
<syntaxhighlight lang="langur">val .fibonacci =
writeln map .fibonacci, series 2..20</syntaxhighlight>
Line 6,987 ⟶ 8,475:
</syntaxhighlight>
=={{header|Lingo}}==
===Recursive===
<syntaxhighlight lang="lingo">on fib (n)
if n<2 then return n
Line 7,116 ⟶ 8,484:
===Iterative===
<syntaxhighlight lang="lingo">on fib (n)
if n<2 then return n
Line 7,130 ⟶ 8,497:
===Analytic===
<syntaxhighlight lang="lingo">on fib (n)
sqrt5 = sqrt(5.0)
Line 7,258 ⟶ 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 7,841 ⟶ 9,222:
end</syntaxhighlight>
=={{header|min}}==
{{works with|min|0.
<syntaxhighlight lang="min">(
(2 <)
(
unless
)
=={{header|MiniScript}}==
Line 8,771 ⟶ 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 8,777 ⟶ 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 8,911 ⟶ 10,392:
=={{header|PARI/GP}}==
===Built-in===
<syntaxhighlight lang="parigp">
===Matrix===
Line 8,937 ⟶ 10,418:
===Binary powering===
This is an efficient method (similar to the one used internally by <code>fibonacci()</code>), although running it without compilation won't give competitive speed.
<syntaxhighlight lang="parigp">fib(n)={
if(n<=0,
Line 9,010 ⟶ 10,492:
a
};</syntaxhighlight>
===Trigonometric===
This solution uses the complex hyperbolic sine.
<syntaxhighlight lang="parigp">fib(n)=real(2/sqrt(5)/I^n*sinh(n*log(I*(1+sqrt(5))/2)))\/1;</syntaxhighlight>
===Chebyshev===
Line 9,043 ⟶ 10,529:
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,129 ⟶ 10,626:
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,183 ⟶ 10,763:
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 9,578 ⟶ 11,212:
end
.end</syntaxhighlight>
=={{header|PL/0}}==
The program waits for ''n''. Then it displays ''n''<sup>th</sup> Fibonacci number.
<syntaxhighlight lang="pascal">
var n, a, b, i, tmp;
begin
? n;
a := 0; b := 1;
i := 2;
while i <= n do
begin
tmp := b; b := a + b; a := tmp;
i := i + 1
end;
! b
end.
</syntaxhighlight>
4 runs.
{{in}}
<pre>5</pre>
{{out}}
<pre> 5</pre>
{{in}}
<pre>9</pre>
{{out}}
<pre> 34</pre>
{{in}}
<pre>13</pre>
{{out}}
<pre> 233</pre>
{{in}}
<pre>20</pre>
{{out}}
<pre> 6765</pre>
=={{header|PL/I}}==
Line 9,818 ⟶ 11,486:
.
.</syntaxhighlight>
=={{header|PowerShell}}==
Line 10,211 ⟶ 11,819:
loop a b n = if n==0 then a else loop b (a+b) (n-1);
end;</syntaxhighlight>
=={{header|Purity}}==
Line 10,593 ⟶ 12,140:
.. 679891637638612258
. 1100087778366101931</pre>
=={{header|Qi}}==
Line 10,860 ⟶ 12,370:
<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 10,869 ⟶ 12,412:
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,019 ⟶ 12,578:
=={{header|Rhovas}}==
Solutions support arbitrarily large numbers as Rhovas's <code>Integer</code> type is arbitrary-precision (Java <code>BigInteger</code>). Additional notes:
* <code>require num >= 0;</code> asserts input range preconditions, throwing on negative numbers
===Iterative===
* <code>range(1, num, :incl)</code> creates an inclusive range (<code>1 <= i <= num</code>) for iteration.
** The loop uses <code>_</code> as the variable name since the value is unused.
<syntaxhighlight lang="scala">
func
require
var previous = 1;
var current = 0;
for (val _ in range(1, num, :incl)) {
val next = current + previous;
previous = current;
current = next;
}
return current;
}
</syntaxhighlight>
===Recursive===
Standard recursive solution using a pattern matching approach:
* <code>match</code> without arguments is a ''conditional match'', which works like <code>if/else</code> chains.
* Rhovas doesn't perform tail-call optimization yet, hence why this solution isn't tail recursive.
<syntaxhighlight lang="scala">
func fibonacci(num: Integer): Integer {
match {
num == 0: return 0;
num == 1: return 1;
else: return fibonacci(num - 1) + fibonacci(num - 2);
}
}
</syntaxhighlight>
===Negatives===
Standard solution using a pattern matching approach, delegating to an existing <code>positiveFibonacci</code> solution (as shown above). For negative fibonacci numbers, odd inputs return positive results while evens return negatives.
<syntaxhighlight lang="scala">
func fibonacci(num: Integer): Integer {
match {
num >= 0: return positiveFibonacci(num);
num.mod(2) != 0: return positiveFibonacci(-num);
else: return -positiveFibonacci(-num);
}
}
Line 11,113 ⟶ 12,698:
===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>
1: { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 }
</pre>
===Fast recursive===
A much better recursive approach, based on the formulas: <code>F(2k) = [2*F(k-1) + F(k)]*F(k)</code> and <code>F(2k+1) = F(k)² + F(k+1)²</code>
≪ '''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 11,280 ⟶ 12,870:
=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
</pre>
=={{header|Rust}}==
Line 11,403 ⟶ 12,973:
}</syntaxhighlight>
=={{header|SAS}}==
=== Iterative ===
This code builds a table <code>fib</code> holding the first few values of the Fibonacci sequence.
<syntaxhighlight lang="sas">data fib;
a=0;
Line 11,452 ⟶ 12,990:
=== Naive recursive ===
This code provides a simple example of defining a function and using it recursively. One of the members of the sequence is written to the log.
Line 12,020 ⟶ 13,557:
2000000 fib (builtin): 229ms (827461038 cycles)
10000000 fib (builtin): 2.769s (9970686190 cycles)</pre>
=={{header|SNOBOL4}}==
===Recursive===
<syntaxhighlight lang="snobol"> define("fib(a)") :(fib_end)
Line 12,130 ⟶ 13,622:
| #+==/ fib(n-2)|+fib(n-1)|
\=====recursion======/!========/</syntaxhighlight>
=={{header|Spin}}==
Line 12,653 ⟶ 14,122:
}</syntaxhighlight>
=={{header|TI
{| class="wikitable"
|+ Texas Instruments SR-56 Program Listing for "Fibonacci Sequence"
|-
! Display !! Key !! Display !! Key !! Display !! Key !! Display !! Key
|-
| 00 33 || STO || 25 || || 50 || || 75 ||
|-
| 01 00 || 0 || 26 || || 51 || || 76 ||
|-
| 02 01 || 1 || 27 || || 52 || || 77 ||
|-
| 03 33 || STO || 28 || || 53 || || 78 ||
|-
| 04 01 || 1 || 29 || || 54 || || 79 ||
|-
| 05 00 || 0 || 30 || || 55 || || 80 ||
|-
| 06 84 || + || 31 || || 56 || || 81 ||
|-
| 07 39 || *EXC || 32 || || 57 || || 82 ||
|-
| 08 01 || 1 || 33 || || 58 || || 83 ||
|-
| 09 94 || = || 34 || || 59 || || 84 ||
|-
| 10 27 || *dsz || 35 || || 60 || || 85 ||
|-
| 11 00 || 0 || 36 || || 61 || || 86 ||
|-
| 12 06 || 6 || 37 || || 62 || || 87 ||
|-
| 13 41 || R/S || 38 || || 63 || || 88 ||
|-
| 14 22 || GTO || 39 || || 64 || || 89 ||
|-
| 15 00 || 0 || 40 || || 65 || || 90 ||
|-
| 16 06 || 6 || 41 || || 66 || || 91 ||
|-
| 17 || || 42 || || 67 || || 92 ||
|-
| 18 || || 43 || || 68 || || 93 ||
|-
| 19 || || 44 || || 69 || || 94 ||
|-
| 20 || || 45 || || 70 || || 95 ||
|-
| 21 || || 46 || || 71 || || 96 ||
|-
| 22 || || 47 || || 72 || || 97 ||
|-
| 23 || || 48 || || 73 || || 98 ||
|-
| 24 || || 49 || || 74 || || 99 ||
|}
Asterisk denotes 2nd function key.
{| class="wikitable"
|+ Register allocation
|-
| 0: Nth term requested || 1: Last term || 2: Unused || 3: Unused || 4: Unused
|-
| 5: Unused || 6: Unused || 7: Unused || 8: Unused || 9: Unused
|}
Annotated listing:
<syntaxhighlight lang="text">
STO 0 // Nth term requested := User input
1 STO 1 // Last term := 1
0 // Initial value: 0
+ *EXC 1 = // Calculate next term.
*dsz 0 6 // Loop while R0 positive
R/S // Done, show answer
GTO 0 6 // If user hits R/S calculate next term
</syntaxhighlight>
'''Usage:'''
At the keypad enter a number N, then press RST R/S to calculate and display the Nth Fibonacci number. R/S for the following numbers.
{{in}}
<pre>1 RST R/S</pre>
{{out}}
<pre>1</pre>
{{in}}
<pre>2 RST R/S</pre>
{{out}}
<pre>1</pre>
{{in}}
<pre>3 RST R/S</pre>
{{out}}
<pre>2</pre>
{{in}}
<pre>10 RST R/S</pre>
{{out}}
<pre>55</pre>
<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}}==
<syntaxhighlight lang="tse sal">
// library: math: get: series: fibonacci <description></description> <version control></version control> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=getmasfi.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 22:04:02]
INTEGER PROC FNMathGetSeriesFibonacciI( INTEGER nI )
Line 12,822 ⟶ 14,338:
UNTIL FALSE
END
</syntaxhighlight>
Line 12,894 ⟶ 14,409:
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,069 ⟶ 14,592:
$
</syntaxhighlight>
=={{header|Vedit macro language}}==
===Iterative===
Calculate fibonacci(#1). Negative values return 0.
<syntaxhighlight lang="vedit">:FIBONACCI:
Line 13,241 ⟶ 14,672:
{{out}}
<pre>fibonacci(1000) = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875</pre>
=={{header|V (Vlang)}}==
Line 13,643 ⟶ 14,936:
=={{header|Wren}}==
<syntaxhighlight lang="
var fibItr = Fn.new { |n|
if (n < 2) return n
Line 13,762 ⟶ 15,055:
x
(fib 1 1 x) ) )</syntaxhighlight>
=={{header|XPL0}}==
Line 13,817 ⟶ 15,093:
else local:fib($n - 1) + local:fib($n - 2)
};</syntaxhighlight>
=={{header|Z80 Assembly}}==
Line 13,894 ⟶ 15,153:
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}}==
Line 13,905 ⟶ 15,175:
610,987,1597,2584,4181,
</pre>
[[Category:Arithmetic]]
| |||