Rosetta Code

Fibonacci sequence: Difference between revisions

Page Discussion

Fibonacci sequence (view source)

Revision as of 03:59, 28 April 2024

9,025 bytes added ,  17 days ago
m
PL/0: The last line of a "begin" compound statement must not be terminated with a semicolon. Unusual but true!
m (PL/0: The last line of a "begin" compound statement must not be terminated with a semicolon. Unusual but true!)
(34 intermediate revisions by 20 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 2,989 ⟶ 3,018:
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,287:
 
==={{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,298:
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,670:
{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,387:
 
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,383:
<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,393:
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2, 13
 
RECORD HEADER
, A32, "First 1015 Fibonacci Numbers."
 
RECORD OUTPUT
Line 5,320 ⟶ 5,409:
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,431:
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE. 1015 GOTO LOOP
 
CLOSE 8
END
 
 
 
</syntaxhighlight>
 
=={{header|DWScript}}==
 
Line 5,571 ⟶ 5,673:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
Line 5,583 ⟶ 5,685:
else
{
for(int i := 2,; i <= n,; i+=1)
{
int t := ac[1];
Line 5,596 ⟶ 5,698:
public program()
{
for(int i := 0,; i <= 10,; i+=1)
{
console.printLine(fibu(i))
Line 5,626 ⟶ 5,728:
long n_1 := 1l;
 
$yield: n_2;
$yield: n_1;
 
while(true)
Line 5,633 ⟶ 5,735:
long n := n_2 + n_1;
 
$yield: n;
 
n_2 := n_1;
Line 5,645 ⟶ 5,747:
auto e := new FibonacciGenerator();
for(int i := 0,; i < 10,; i += 1) {
console.printLine(e.next())
};
Line 5,678 ⟶ 5,780:
 
=={{header|Elm}}==
 
Naïve recursive implementation.
<syntaxhighlight lang="haskell">fibonacci : Int -> Int
Line 5,684 ⟶ 5,787:
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 7,020 ⟶ 7,147:
=={{header|Grain}}==
=== Recursive ===
<syntaxhighlight lang="ocamlhaskell">
import String from "string"
import File from "sys/file"
Line 7,034 ⟶ 7,161:
</syntaxhighlight>
=== Iterative ===
<syntaxhighlight lang="ocamlhaskell">
import String from "string"
import File from "sys/file"
let fib = j => {
let mut fnow = 0, fnext = 1, tempf = 0
for (let mut n = 0; n <= j; n += 1) {
if (n == 0 || n == 1) {
let mut output1 = String.concat(" ", Pervasives.++ toString(n))
ignore(File.fdWrite(File.stdout, output1))
} else {
let tempf = fnow + fnext
fnow = fnext
fnext = tempf
let mut output2 = String.concat(" ", Pervasives.++ toString(fnext))
ignore(File.fdWrite(File.stdout, output2))
}
Line 7,055 ⟶ 7,181:
</syntaxhighlight>
{{out}}
=== Iterative with Buffer ===
<pre>
<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>
Line 7,538 ⟶ 7,690:
 
=={{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,545 ⟶ 7,701:
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,177 ⟶ 8,331:
 
=={{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,469 ⟶ 8,623:
 
=={{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 10,009 ⟶ 10,178:
=={{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,275 ⟶ 10,523:
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,361 ⟶ 10,620:
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,878 ⟶ 11,220:
i := i + 1
end;
! b;
end.
</syntaxhighlight>
Line 12,022 ⟶ 12,364:
<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 12,033 ⟶ 12,406:
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 14,014 ⟶ 14,403:
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,533 ⟶ 14,930:
 
=={{header|Wren}}==
<syntaxhighlight lang="ecmascriptwren">// iterative (quick)
var fibItr = Fn.new { |n|
if (n < 2) return n
Line 14,753 ⟶ 15,150:
=={{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>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/348892...364023"