Rosetta Code

Catalan numbers: Difference between revisions

Page Discussion

Catalan numbers (view source)

Revision as of 22:04, 8 September 2015

352 bytes added ,  8 years ago
m
→‎version 1: added/changed whitespace and comments, eliminated the need for a function, optimized some functions.
m (→‎{{header|360 Assembly}}: Superfluous blanks suppressed)
m (→‎version 1: added/changed whitespace and comments, eliminated the need for a function, optimized some functions.)
Line 2,790:
===version 1===
All methods use (independent) memoization for the computation of factorials.
<lang rexx>/*REXX program calculates Catalan numbers using four different methods. */
parse arg bot top . /*get optional argsarguments from the C.L. */
if bot=='' then do; top=15; bot=0; end /*No args? Use a range of 0──►15 0 ───► 15. */
if top=='' then top=bot /*No top? Use the bottom for itdefault. */
numeric digits max(20, 5*top) /*this allows gihugic Catalan numbers. */
call@cat=' hdr Catalan'1a'; do j=bot to top; say $cat() catalan1a(j); /*a nice literal to have for the SAY. end*/
exit w=length(top) /*stickwidth aof forkthe inlargest it,number we'refor doneSAY. */▼
call hdr '1b'; do j=bot to top; say $cat() catalan1b(j); end▼
call hdr 2 1A; do j=bot to top; say @cat say $catright(j,w)": catalan2" catalan1A(j) ; end
call hdr 3 1B; do j=bot to top; say @cat say $catright(j,w)": catalan3" catalan1B(j) ; end
▲call hdr '1b'; 2 ; do j=bot to top; say $@cat right(j,w)": " catalan1bcatalan2(j); end
▲exit /*stick a fork in it, we're done.*/
call hdr 3 ; do j=bot to top; say @cat right(j,w)": " catalan3(j); end
/*──────────────────────────────────one─liner subroutines───────────────*/
exit /*stick a fork in it, we're all done. */
$cat: return ' Catalan' right(j,length(top))": "
/*────────────────────────────────────────────────────────────────────────────*/
catalan1a: procedure expose !.; parse arg n; return comb(n+n,n)%(n+1)▼
catalan1bcatalan1A: procedure expose !.; parse arg n; return !comb(n+n, n) %( (n+1)*!(n)**2)
combcatalan1B: procedure expose procedure!.; parse arg x,yn; return !(n+n) pFact% ((x-yn+1,x) %* pFact!(n)**2,y)
pFactcomb: procedure; !=1;parse arg x,y; do k=arg(1) to arg(2); !=!*k; end; return !pFact(x-y+1,x) % pFact(2,y)
pFact: procedure; !=1; do k=arg(1) to arg(2); !=!*k; end; return !
/*──────────────────────────────────! (factorial) function──────────────*/
/*────────────────────────────────────────────────────────────────────────────*/
!: procedure expose !.; parse arg x; if !.x\==. then return !.x
!=1;hdr: do k=1 for x; !.=!*k.; end /*k*/c.=.; !c.x0=!1; return !say
say center(' Catalan numbers, method' left(arg(1),3), 79, '─'); return
/*──────────────────────────────────catalan method 2────────────────────*/
/*────────────────────────────────────────────────────────────────────────────*/
catalan2: procedure expose c.; parse arg n; if c.n\==. then return c.n
s=0;!: procedure expose !.; do k=0parse arg tox; n-!=1; if !.x\==. then return !.x
s=s + catalan2(k) * catalan2(n- do k-=1) /for x; !=!*recursivek; invokes end /*k*/
!.x=!; return end /*k*/!
/*──────────────────────────────────Catalan method 2──────────────────────────*/
c.n=s; return s /*use REXX memoization technique.*/
▲catalan1acatalan2: procedure expose !c.; parse arg n; return comb(s=0; if c.n+n,n)%(\==. then return c.n+1)
/*──────────────────────────────────catalan method 3────────────────────*/
do k=0 to n-1; s=s+catalan2(k)*catalan2(n-k-1); end
catalan3: procedure expose c.; parse arg n; if c.n\==. then return c.n
c.n=(4*n-2)s; *return s catalan3(n-1) % (n+1); return c.n /*use a REXX memoization technique. */
/*──────────────────────────────────Catalan method 3──────────────────────────*/
/*──────────────────────────────────HDR subroutine──────────────────────*/
hdrcatalan3: procedure !.=expose c.; parse c.=.arg n; c.0=1; sayif c.n\==. /*set somethen variables;return blank linec.*/n
say centerc.n=('4*n-2) Catalan* numbers, method' left(argcatalan3(n-1),3), 79,% '─'(n+1); return c.n /*use memoization.*/</lang>
'''output''' when using the input of: &nbsp; <tt> 0 16 </tt>
<pre>
───────────────────────── Catalan numbers, method 1a1A ──────────────────────────
Catalan 0: 1
Catalan 1: 1
Line 2,841:
Catalan 15: 9694845
 
───────────────────────── Catalan numbers, method 1b1B ──────────────────────────
··· (elided, same as first method) ···
 
Line 2,850:
··· (elided, same as first method) ···
</pre>
'''Timing notes''' &nbsp; of the four methods:
 
::* For Catalan numbers &nbsp; 1 ──► 200:
::::* method &nbsp; '''1a1A''' &nbsp; is about &nbsp; 50 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1b1B''' &nbsp; is about 100 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''2''' &nbsp; &nbsp; is about &nbsp; 85 times slower than method &nbsp; '''3'''
 
::* For Catalan numbers &nbsp; 1 ──► 300:
::::* method &nbsp; '''1a1A''' &nbsp; is about 100 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1b1B''' &nbsp; is about 200 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''2''' &nbsp; &nbsp; is about 200 times slower than method &nbsp; '''3'''
Method &nbsp; '''3''' &nbsp; is really quite fast; &nbsp; even in the thousands range, computation time is still quite reasonable.
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/172200"