Rosetta Code

Fibonacci sequence: Difference between revisions

Page Discussion

Fibonacci sequence (view source)

Revision as of 10:28, 2 May 2024

12,752 bytes added ,  15 days ago
m
FutureBasic entry moved out of the Basic group
m (→‎Iterative: Highlight syntax)
m (FutureBasic entry moved out of the Basic group)
(42 intermediate revisions by 24 users not shown)
Line 251:
;-------------------------------------------------------
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
;-------------------------------------------------------
; programmain code begins here
;-------------------------------------------------------
org 100h ; load point under CP/M
lxi h,0 ; save command processorCP/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,10 ; teststart bywith displaying first 20Fib(0)
mloop: push a ; save our count (putdec will trash)
call fib
call putdec
mvi a,space ; separate the numbers
call putchr
pop a ; get our count back
inr a ; increaseincrement it by one
cpi 20nterms+1 ; have we reached our limit?
jnz mloop ; not yet;no, dokeep anothergoing
lhld oldstk ; we'reall 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 ; initialDE value forholds Fib(n-2)
lxi h,1 ; intiialHL value forholds 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 holds= Fib(n), soon to be Fib(n-1)
pop d ; FormerDE Fib= old F(n-1), now Fib(n-2)
jmp fib2 ; loopready untilfor donenext pass
fib3: ret
;-------------------------------------------------------
; console output of char in A register
;-------------------------------------------------------
putchr: push h
push h
push d
push b
mov e,a
mvi c,conout
call bdos
pop b
Line 316 ⟶ 320:
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
Line 336 ⟶ 340:
ret
;-------------------------------------------------------
; message and data area
;-------------------------------------------------------
signon: db 'FirstFibonacci 20 Fibonaccinumber numberssequence:',cr,lf,'$'
oldstk: dw 0
stack equ $+128 ; 64-level stack
Line 346 ⟶ 350:
{{out}}
<pre>
Fibonacci number sequence:
First 20 Fibonacci numbers:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
</pre>
 
Line 1,726 ⟶ 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}}===
Line 1,936 ⟶ 1,965:
end</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|GFA Basic}}===
Line 2,989 ⟶ 2,872:
150 END
</syntaxhighlight>
 
==={{header|Tiny Craft Basic}}===
<syntaxhighlight lang="basic">10 cls
 
20 let a = 1
30 let b = 1
 
40 print "Fibonacci Sequence"
 
50 rem loop
 
60 let s = a + b
70 let a = b
80 let b = s
90 let i = i + 1
 
100 print s
 
120 if i < 20 then 50
 
130 shell "pause"
140 end</syntaxhighlight>
 
==={{header|True BASIC}}===
Line 3,280 ⟶ 3,141:
 
==={{header|Yabasic}}===
====Iterative====
<syntaxhighlight lang="yabasic">sub fibonacci (n)
<syntaxhighlight lang="vbnet">sub fibonacciI (n)
local n1, n2, k, sum
 
n1 = 0
n2 = 1
Line 3,288 ⟶ 3,152:
n2 = sum
next k
if n < 01 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>
 
Line 3,628 ⟶ 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 4,308 ⟶ 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 5,297 ⟶ 5,237:
<syntaxhighlight lang="dibol-11">
 
; START Redone ;Firstto include the first 10two Fibonaccivalues NUmbersthat
; are noot computed.
 
START ;First 15 Fibonacci NUmbers
 
 
Line 5,304 ⟶ 5,247:
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2, 13
 
RECORD HEADER
, A32, "First 1015 Fibonacci Numbers."
 
RECORD OUTPUT
Line 5,320 ⟶ 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,331 ⟶ 5,285:
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE. 1015 GOTO LOOP
 
CLOSE 8
END
 
 
 
</syntaxhighlight>
 
=={{header|DWScript}}==
 
Line 5,374 ⟶ 5,330:
 
<syntaxhighlight lang="text">
procfunc fib n . res .
if n < 2
res = return n
.
prev = 0
val = 1
for _i = 02 to n - 2
res h = prev + val
prev = val
val = resh
.
return val
.
callprint fib 36 r
print r
</syntaxhighlight>
 
Line 5,393 ⟶ 5,349:
 
<syntaxhighlight lang="text">
procfunc fib n . res .
if n < 2
res = return n
else .
callreturn fib (n - 12) a+ fib (n - 1)
call fib n - 2 b
res = a + b
.
.
callprint fib 36 r
print r
</syntaxhighlight>
 
Line 5,575 ⟶ 5,527:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
Line 5,587 ⟶ 5,539:
else
{
for(int i := 2,; i <= n,; i+=1)
{
int t := ac[1];
Line 5,600 ⟶ 5,552:
public program()
{
for(int i := 0,; i <= 10,; i+=1)
{
console.printLine(fibu(i))
Line 5,630 ⟶ 5,582:
long n_1 := 1l;
 
$yield: n_2;
$yield: n_1;
 
while(true)
Line 5,637 ⟶ 5,589:
long n := n_2 + n_1;
 
$yield: n;
 
n_2 := n_1;
Line 5,649 ⟶ 5,601:
auto e := new FibonacciGenerator();
for(int i := 0,; i < 10,; i += 1) {
console.printLine(e.next())
};
Line 5,682 ⟶ 5,634:
 
=={{header|Elm}}==
 
Naïve recursive implementation.
<syntaxhighlight lang="haskell">fibonacci : Int -> Int
Line 5,688 ⟶ 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,840 ⟶ 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,943 ⟶ 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,423 ⟶ 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. Here is one:
 
<syntaxhighlight lang="j"> fibN=: (-&2 +&$: -&1)^:(1&<) M."0</syntaxhighlight>
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,430 ⟶ 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>
 
(This implementation is doubly recursive except that results are cached across function calls.)
 
=={{header|Java}}==
Line 8,062 ⟶ 8,332:
 
=={{header|langur}}==
<syntaxhighlight lang="langur">val .fibonacci = ffn(.x) { if(.x < 2: .x ; self(.x - 1) + self(.x - 2)) }
 
writeln map .fibonacci, series 2..20</syntaxhighlight>
Line 8,354 ⟶ 8,624:
 
=={{header|Logo}}==
<syntaxhighlight lang="logo">to fib :n [:a 0] [:b 1]
to fib "loop
if :n < 1 [output :a]
make "fib1 0
output (fib :n-1 :b :a+:b)
make "fib2 1
end</syntaxhighlight>
 
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 9,894 ⟶ 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 10,160 ⟶ 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 10,246 ⟶ 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 10,763 ⟶ 11,221:
i := i + 1
end;
! b;
end.
</syntaxhighlight>
Line 11,907 ⟶ 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}}==
Line 11,918 ⟶ 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 13,720 ⟶ 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,838 ⟶ 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 14,357 ⟶ 14,931:
 
=={{header|Wren}}==
<syntaxhighlight lang="ecmascriptwren">// iterative (quick)
var fibItr = Fn.new { |n|
if (n < 2) return n
Line 14,577 ⟶ 15,151:
=={{header|YAMLScript}}==
<syntaxhighlight lang="yaml">
!yamlscript/v0
loop [a 0, b 1, i 1 ]:
 
say: a
defn main(i < n=10) ?:
loop [a ^^^:0, b, (a + b)1, (i + 1)]:
say: a
if (i < n):
recur: b, (a + b), (i + 1)
</syntaxhighlight>
 
Bernie
408

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/347401...364179"