Catalan numbers: Difference between revisions
Content deleted Content added
Langurmonkey (talk | contribs) |
Crystal code |
||
Line 1,233:
(format t "~%Method ~d:~%" i)
(dotimes (i 16) (format t "C(~2d) = ~d~%" i (funcall f i))))</lang>
=={{header|Crystal}}==
{{trans|Ruby}}
<lang ruby>require "big"
require "benchmark"
def factorial(n : BigInt) : BigInt
(1..n).reduce(1.to_big_i) { |acc, i| acc * i }
end
def factorial(n : Int32 | Int64)
factorial n.to_big_i
end
# direct
def catalan_direct(n)
factorial(2*n) / (factorial(n + 1) * factorial(n))
end
# recursive
def catalan_rec1(n)
return 1 if n == 0
(0...n).reduce(0) do |sum, i|
sum + catalan_rec1(i) * catalan_rec1(n - 1 - i)
end
end
def catalan_rec2(n)
return 1 if n == 0
2*(2*n - 1) * catalan_rec2(n - 1) / (n + 1)
end
# performance and results
Benchmark.bm do |b|
b.report("catalan_direct") { 16.times { |n| catalan_direct(n) } }
b.report("catalan_rec1") { 16.times { |n| catalan_rec1(n) } }
b.report("catalan_rec2") { 16.times { |n| catalan_rec2(n) } }
end
puts "\n direct rec1 rec2"
16.times { |n| puts "%2d :%9d%9d%9d" % [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)] }
</lang>
{{out}}
<pre>
# with --release flag
user system total real
catalan_direct 0.000000 0.000000 0.000000 ( 0.000350)
catalan_rec1 0.109375 0.000000 0.109375 ( 0.122726)
catalan_rec2 0.000000 0.000000 0.000000 ( 0.000010)
direct rec1 rec2
0 : 1 1 1
1 : 1 1 1
2 : 2 2 2
3 : 5 5 5
4 : 14 14 14
5 : 42 42 42
6 : 132 132 132
7 : 429 429 429
8 : 1430 1430 1430
9 : 4862 4862 4862
10 : 16796 16796 16796
11 : 58786 58786 58786
12 : 208012 208012 208012
13 : 742900 742900 742900
14 : 2674440 2674440 2674440
15 : 9694845 9694845 9694845
</pre>
=={{header|D}}==
| |||