Fibonacci sequence: Difference between revisions
m
FutureBasic entry moved out of the Basic group
No edit summary |
m (FutureBasic entry moved out of the Basic group) |
||
| (29 intermediate revisions by 19 users not shown) | |||
Line 1,731:
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,941 ⟶ 1,965:
end</syntaxhighlight>
==={{header|GFA Basic}}===
Line 2,994 ⟶ 2,872:
150 END
</syntaxhighlight>
==={{header|True BASIC}}===
Line 3,285 ⟶ 3,141:
==={{header|Yabasic}}===
====Iterative====
<syntaxhighlight lang="vbnet">sub fibonacciI (n)
local n1, n2, k, sum
n1 = 0
n2 = 1
Line 3,293 ⟶ 3,152:
n2 = sum
next k
if n <
return n1 * ((-1) ^ ((-n) + 1))
else
return n1
end if
end sub</syntaxhighlight>
====Recursive====
Only positive numbers
<syntaxhighlight lang="vbnet">sub fibonacciR(n)
if n <= 1 then
return n
else
return fibonacciR(n-1) + fibonacciR(n-2)
end if
end sub</syntaxhighlight>
====Analytic====
Only positive numbers
<syntaxhighlight lang="vbnet">sub fibonacciA (n)
return int(0.5 + (((sqrt(5) + 1) / 2) ^ n) / sqrt(5))
end sub</syntaxhighlight>
====Binet's formula====
Fibonacci sequence using the Binet formula
<syntaxhighlight lang="vbnet">sub fibonacciB(n)
local sq5, phi1, phi2, dn1, dn2, k
sq5 = sqrt(5)
phi1 = (1 + sq5) / 2
phi2 = (1 - sq5) / 2
dn1 = phi1: dn2 = phi2
for k = 0 to n
dn1 = dn1 * phi1
dn2 = dn2 * phi2
print int(((dn1 - dn2) / sq5) + .5);
next k
end sub</syntaxhighlight>
Line 3,633 ⟶ 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,313 ⟶ 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,302 ⟶ 5,237:
<syntaxhighlight lang="dibol-11">
;
; are noot computed.
START ;First 15 Fibonacci NUmbers
Line 5,309 ⟶ 5,247:
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2,
RECORD HEADER
, A32, "First
RECORD OUTPUT
Line 5,325 ⟶ 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,336 ⟶ 5,285:
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE.
CLOSE 8
END
</syntaxhighlight>
=={{header|DWScript}}==
Line 5,576 ⟶ 5,527:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA
<syntaxhighlight lang="elena">import extensions;
Line 5,588 ⟶ 5,539:
else
{
for(int i := 2
{
int t := ac[1];
Line 5,601 ⟶ 5,552:
public program()
{
for(int i := 0
{
console.printLine(fibu(i))
Line 5,650 ⟶ 5,601:
auto e := new FibonacciGenerator();
for(int i := 0
console.printLine(e.next())
};
Line 5,683 ⟶ 5,634:
=={{header|Elm}}==
Naïve recursive implementation.
<syntaxhighlight lang="haskell">fibonacci : Int -> Int
Line 5,689 ⟶ 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,841 ⟶ 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æ}}==
Line 7,568 ⟶ 7,691:
=={{header|J}}==
The [https://code.jsoftware.com/wiki/Essays/Fibonacci_Sequence Fibonacci Sequence essay] on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number.
This implementation is doubly recursive except that results are cached across function calls:
<syntaxhighlight lang="j">fibN=: (-&2 +&$: <:)^:(1&<) M."0</syntaxhighlight>
Iteration:
<syntaxhighlight lang="j">fibN=: [: {."1 +/\@|.@]^:[&0 1</syntaxhighlight>
'''Examples:'''
<syntaxhighlight lang="j"> fibN 12
Line 7,575 ⟶ 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 8,207 ⟶ 8,332:
=={{header|langur}}==
<syntaxhighlight lang="langur">val .fibonacci =
writeln map .fibonacci, series 2..20</syntaxhighlight>
Line 8,499 ⟶ 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 10,039 ⟶ 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,305 ⟶ 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,391 ⟶ 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,908 ⟶ 11,221:
i := i + 1
end;
! b
end.
</syntaxhighlight>
Line 12,052 ⟶ 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 12,063 ⟶ 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 14,044 ⟶ 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,563 ⟶ 14,931:
=={{header|Wren}}==
<syntaxhighlight lang="
var fibItr = Fn.new { |n|
if (n < 2) return n
Line 14,783 ⟶ 15,151:
=={{header|YAMLScript}}==
<syntaxhighlight lang="yaml">
!yamlscript/v0
defn
loop [a
say: a
if (i < n):
recur: b, (a + b), (i + 1)
</syntaxhighlight>
| |||