Catalan numbers: Difference between revisions
→{{header|langur}}
(Dialects of BASIC moved to the BASIC section.) |
Langurmonkey (talk | contribs) |
||
(25 intermediate revisions by 11 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}}===
<syntaxhighlight lang="basic">dim c[16]
let c[0] = 1
for n = 0 to 15
let p = n + 1
let c[p] = 0
for i = 0 to n
let q = n - i
let c[p] = c[p] + c[i] * c[q]
next i
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,243 ⟶ 2,310:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
func catalan n
if n = 0
return
.
for i = 0 to 14
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 2,907 ⟶ 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,288 ⟶ 3,361:
</pre>
=={{header|JavaScript}}==
===Procedural===
<syntaxhighlight lang="javascript"><html><head><title>Catalan</title></head>
<body><pre id='x'></pre><script type="application/javascript">
Line 3,335 ⟶ 3,410:
14 2674440 2674440 2674440
15 9694845 9694845 9694845</pre>
===Functional===
Defining an infinite list:
<syntaxhighlight lang="javascript">(() => {
"use strict";
// ----------------- CATALAN NUMBERS -----------------
// catalansDefinitionThree :: [Int]
const catalansDefinitionThree = () =>
// An infinite sequence of Catalan numbers.
scanlGen(
c => n => Math.floor(
(2 * c * pred(2 * n)) / succ(n)
)
)(1)(
enumFrom(1)
);
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () =>
take(15)(
catalansDefinitionThree()
);
// --------------------- GENERIC ---------------------
// enumFrom :: Enum a => a -> [a]
const enumFrom = function* (n) {
// An infinite sequence of integers,
// starting with n.
let v = n;
while (true) {
yield v;
v = 1 + v;
}
};
// pred :: Int -> Int
const pred = x =>
x - 1;
// scanlGen :: (b -> a -> b) -> b -> Gen [a] -> [b]
const scanlGen = f =>
// The series of interim values arising
// from a catamorphism over an infinite list.
startValue => function* (gen) {
let
a = startValue,
x = gen.next();
yield a;
while (!x.done) {
a = f(a)(x.value);
yield a;
x = gen.next();
}
};
// succ :: Int -> Int
const succ = x =>
1 + x;
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}).flat();
// MAIN ---
return JSON.stringify(main(), null, 2);
})();</syntaxhighlight>
{{Out}}
<pre>[
1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440
]</pre>
=={{header|jq}}==
{{ works with|jq|1.4 }}
Line 3,594 ⟶ 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,652 ⟶ 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,814 ⟶ 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 3,880 ⟶ 4,227:
ReadChar
END CatalanNumbers.</syntaxhighlight>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math
Line 4,491 ⟶ 4,839:
13 => 742900 742900 742900
14 => 2674440 2674440 2674440</pre>
=={{header|PL/0}}==
{{trans|Tiny BASIC}}
Integers are limited to 32767 so only the first ten Catalan numbers can be represented. To avoid internal overflow, the program subtracts something clever from <code>c</code> and then adds it back at the end.
<syntaxhighlight lang="pascal">
var n, c, i;
begin
n := 0; c := 1;
! c;
while n <= 9 do
begin
n := n + 1;
i := 0;
while c > 0 do
begin
c := c - (n + 1);
i := i + 1
end;
c := 2 * (2 * n - 1) * c / (n + 1);
c := c + 2 * i * (2 * n - 1);
! c
end;
end.
</syntaxhighlight>
{{out}}
<pre>
1
1
2
5
14
42
132
429
1430
4862
16796
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">catalan: procedure options (main); /* 23 February 2012 */
Line 5,783 ⟶ 6,170:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="
import "./math" for Int
var catalan = Fn.new { |n|
Line 5,846 ⟶ 6,233:
15 9694845
</pre>
=={{header|XLISP}}==
<syntaxhighlight lang="lisp">(defun catalan (n)
|