Catalan numbers: Difference between revisions
→{{header|langur}}
Basicgames (talk | contribs) |
Langurmonkey (talk | contribs) |
||
| (18 intermediate revisions by 9 users not shown) | |||
Line 452:
14 2674440
15 9694845
==={{header|Applesoft BASIC}}===
{{works with|Chipmunk Basic}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">10 HOME : REM 10 CLS for Chipmunk Basic/QBasic
20 DIM c(15)
30 c(0) = 1
40 PRINT 0, c(0)
50 FOR n = 0 TO 14
60 c(n + 1) = 0
70 FOR i = 0 TO n
80 c(n + 1) = c(n + 1) + c(i) * c(n - i)
90 NEXT i
100 PRINT n + 1, c(n + 1)
110 NEXT n
120 END</syntaxhighlight>
==={{header|BASIC256}}===
Line 515 ⟶ 531:
742900
2674440</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">10 FOR i = 1 TO 15
20 PRINT i;" ";catalan(i)
30 NEXT
40 END
50 SUB catalan(n)
60 catalan = 1
70 IF n <> 0 THEN catalan = ((2*((2*n)-1))/(n+1))*catalan(n-1)
80 END SUB</syntaxhighlight>
==={{header|Craft Basic}}===
Line 535 ⟶ 563:
print n, " ", c[n]
next n</syntaxhighlight>
{{out| Output}}<pre>
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
</pre>
==={{header|FreeBASIC}}===
Line 2,266 ⟶ 2,310:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
func catalan n
if n = 0
return
.
for i = 0 to 14
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 2,930 ⟶ 2,953:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Catalan_numbers}}
'''Solution'''
'''Direct definition'''
[[File:Fōrmulæ - Catalan numbers 01.png]]
[[File:Fōrmulæ - Catalan numbers 02.png]]
'''Direct definition (alternative)'''
The expression <math>\frac{(2n)!}{(n+1)!\,n!}</math> turns out to be equals to <math>\prod_{k=2}^{n}\frac{n + k}{k}</math>
[[File:Fōrmulæ - Catalan numbers 03.png]]
(same result)
'''No directly defined'''
Recursive definitions are easy to write, but extremely inefficient (specially the first one).
Because a list is intended to be get, the list of previous values can be used as a form of memoization, avoiding recursion.
The next function make use of the "second" form of recursive definition (without recursion):
[[File:Fōrmulæ - Catalan numbers 04.png]]
[[File:Fōrmulæ - Catalan numbers 05.png]]
(same result)
=={{header|GAP}}==
<syntaxhighlight lang="gap">Catalan1 := n -> Binomial(2*n, n) - Binomial(2*n, n - 1);
Line 3,728 ⟶ 3,778:
=={{header|langur}}==
{{trans|Perl}}
<syntaxhighlight lang="langur">val .factorial =
val .catalan = fn(.n) { .factorial(2 x .n) / .factorial(.n+1) / .factorial(.n) }
for .i in 0..15 {
Line 3,786 ⟶ 3,837:
742900
2674440</pre>
=={{header|Logtalk}}==
For this task it is instructive to show a more general-purpose interface for sequences and an implementation of it for Catalan numbers.
First, <code>loader.lgt</code>:
<syntaxhighlight lang="logtalk">
:- initialization((
% libraries
logtalk_load(dates(loader)),
logtalk_load(meta(loader)),
logtalk_load(types(loader)),
% application
logtalk_load(seqp),
logtalk_load(catalan),
logtalk_load(catalan_test)
)).
</syntaxhighlight>
The interface is defined in <code>seqp.lgt</code> as a protocol:
<syntaxhighlight lang="logtalk">
:- protocol(seqp).
:- public(init/0). % reset to a beginning state if meaningful
:- public(nth/2). % get the nth value of the sequence
:- public(to_nth/2). % get from the start to the nth value of the sequence as a list
:- end_protocol.
</syntaxhighlight>
The implementation of a Catalan sequence generator is in <code>catalan.lgt</code>:
<syntaxhighlight lang="logtalk">
:- object(catalan, implements(seqp)).
:- private(catalan/2).
:- dynamic(catalan/2).
% Public interface.
init :- retractall(catalan(_,_)). % flush any memoized results
nth(N, V) :- \+ catalan(N, V), catalan_(N, V), !. % generate iff it's not been memoized
nth(N, V) :- catalan(N, V), !. % otherwise use the memoized version
to_nth(N, L) :-
integer::sequence(0, N, S), % generate a list of 0 to N
meta::map(nth, S, L). % map the nth/2 predicate to the list for all Catalan numbers up to N
% Local helper predicates.
catalan_(N, V) :-
N > 0, % calculate
N1 is N - 1,
N2 is N + 1,
catalan_(N1, V1), % via a recursive call
V is V1 * 2 * (2 * N - 1) // N2,
assertz(catalan(N, V)). % and memoize the result
catalan_(0, 1).
:- end_object.
</syntaxhighlight>
This is a memoizing implementation whose impact we will check in the test. The <code>init/0</code> predicate flushes any memoized results.
The test driver is a simple one that generates the first fifteen Catalan numbers four times, comparing times with and without memoization. From <code>catalan_test.lgt</code>:
<syntaxhighlight lang="logtalk">
:- object(catalan_test).
:- public(run/0).
run :-
% put the object into a known initial state
catalan::init,
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C1), D1),
% first 15 Catalan numbers again, twice, recording duration.
time_operation(catalan::to_nth(15, C2), D2),
time_operation(catalan::to_nth(15, C3), D3),
% reset the object again
catalan::init,
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C4), D4),
% ensure the results were the same each time
C1 = C2, C2 = C3, C3 = C4,
% write the results and durations of each run
write(C1), write(' '), write(D1), nl,
write(C2), write(' '), write(D2), nl,
write(C3), write(' '), write(D3), nl,
write(C4), write(' '), write(D4), nl.
% visual inspection should show all results the same
% first and final durations should be much larger
:- meta_predicate(time_operation(0, *)).
time_operation(Goal, Duration) :-
time::cpu_time(Before),
call(Goal),
time::cpu_time(After),
Duration is After - Before.
:- end_object.
</syntaxhighlight>
{{Out}}
The session at the top-level looks like this:
<pre>
?- {loader}.
% ... messages elided ...
% (0 warnings)
true.
?- catalan_test::run.
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001603
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.000306
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.00026
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001346
true.
</pre>
This test shows:
# The <code>nth/2</code> predicate works (since <code>to_nth/2</code> is implemented in terms of it).
# The <code>to_nth/2</code> predicate works.
# Memoization generates a speedup of between ~4.5× to ~6.2× over generating from scratch.
=={{header|Lua}}==
<syntaxhighlight lang="lua">-- recursive with memoization
Line 3,948 ⟶ 4,137:
/* both return [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440] */</syntaxhighlight>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map (show . catalan) [0..14]))]
catalan :: num->num
catalan 0 = 1
catalan n = (4*n - 2) * catalan (n - 1) div (n + 1)</syntaxhighlight>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE CatalanNumbers;
Line 4,014 ⟶ 4,227:
ReadChar
END CatalanNumbers.</syntaxhighlight>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math
Line 5,956 ⟶ 6,170:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="
import "./math" for Int
var catalan = Fn.new { |n|
Line 6,019 ⟶ 6,233:
15 9694845
</pre>
=={{header|XLISP}}==
<syntaxhighlight lang="lisp">(defun catalan (n)
| |||