Fibonacci sequence: Difference between revisions
m
PL/0: The last line of a "begin" compound statement must not be terminated with a semicolon. Unusual but true!
imported>Arakov |
m (PL/0: The last line of a "begin" compound statement must not be terminated with a semicolon. Unusual but true!) |
||
(13 intermediate revisions by 10 users not shown) | |||
Line 3,018:
150 END
</syntaxhighlight>
==={{header|True BASIC}}===
Line 3,309 ⟶ 3,287:
==={{header|Yabasic}}===
====Iterative====
<syntaxhighlight lang="vbnet">sub fibonacciI (n)
local n1, n2, k, sum
n1 = 0
n2 = 1
Line 3,317 ⟶ 3,298:
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,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 5,333 ⟶ 5,383:
<syntaxhighlight lang="dibol-11">
;
; are noot computed.
START ;First 15 Fibonacci NUmbers
Line 5,340 ⟶ 5,393:
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2,
RECORD HEADER
, A32, "First
RECORD OUTPUT
Line 5,356 ⟶ 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,367 ⟶ 5,431:
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE.
CLOSE 8
END
</syntaxhighlight>
=={{header|DWScript}}==
Line 8,265 ⟶ 8,331:
=={{header|langur}}==
<syntaxhighlight lang="langur">val .fibonacci =
writeln map .fibonacci, series 2..20</syntaxhighlight>
Line 8,557 ⟶ 8,623:
=={{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,097 ⟶ 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,363 ⟶ 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 11,049 ⟶ 11,220:
i := i + 1
end;
! b
end.
</syntaxhighlight>
Line 12,193 ⟶ 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,204 ⟶ 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,185 ⟶ 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,926 ⟶ 15,152:
!yamlscript/v0
defn main(n=10):
loop [a 0, b 1, i 1]:
recur: b, (a + b), (i + 1)
</syntaxhighlight>
|