Fibonacci sequence: Difference between revisions
m
FutureBasic entry moved out of the Basic group
imported>Polarit (Output the last number of the range and the list of all numbers of the range) |
m (FutureBasic entry moved out of the Basic group) |
||
(20 intermediate revisions by 13 users not shown) | |||
Line 1,965:
end</syntaxhighlight>
==={{header|GFA Basic}}===
Line 3,018 ⟶ 2,872:
150 END
</syntaxhighlight>
==={{header|True BASIC}}===
Line 3,309 ⟶ 3,141:
==={{header|Yabasic}}===
====Iterative====
<syntaxhighlight lang="vbnet">sub fibonacciI (n)
local n1, n2, k, sum
n1 = 0
n2 = 1
Line 3,317 ⟶ 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,657 ⟶ 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 5,333 ⟶ 5,237:
<syntaxhighlight lang="dibol-11">
;
; are noot computed.
START ;First 15 Fibonacci NUmbers
Line 5,340 ⟶ 5,247:
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2,
RECORD HEADER
, A32, "First
RECORD OUTPUT
Line 5,356 ⟶ 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,367 ⟶ 5,285:
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE.
CLOSE 8
END
</syntaxhighlight>
=={{header|DWScript}}==
Line 5,607 ⟶ 5,527:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA
<syntaxhighlight lang="elena">import extensions;
Line 5,619 ⟶ 5,539:
else
{
for(int i := 2
{
int t := ac[1];
Line 5,632 ⟶ 5,552:
public program()
{
for(int i := 0
{
console.printLine(fibu(i))
Line 5,681 ⟶ 5,601:
auto e := new FibonacciGenerator();
for(int i := 0
console.printLine(e.next())
};
Line 5,714 ⟶ 5,634:
=={{header|Elm}}==
Naïve recursive implementation.
<syntaxhighlight lang="haskell">fibonacci : Int -> Int
Line 5,722 ⟶ 5,643:
'''version 2'''
<syntaxhighlight lang=”elm">fib : Int -> number
fib n =
case n of
Line 5,745 ⟶ 5,665:
: List number
</pre>
=={{header|Emacs Lisp}}==
Line 6,898 ⟶ 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 8,266 ⟶ 8,332:
=={{header|langur}}==
<syntaxhighlight lang="langur">val .fibonacci =
writeln map .fibonacci, series 2..20</syntaxhighlight>
Line 8,558 ⟶ 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,098 ⟶ 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,364 ⟶ 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 11,050 ⟶ 11,221:
i := i + 1
end;
! b
end.
</syntaxhighlight>
Line 12,194 ⟶ 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,205 ⟶ 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,186 ⟶ 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,927 ⟶ 15,153:
!yamlscript/v0
defn main(n=10):
loop [a 0, b 1, i 1]:
recur: b, (a + b), (i + 1)
</syntaxhighlight>
|