Anonymous user
Catalan numbers: Difference between revisions
m
→version 1: added/changed whitespace and comments, eliminated the need for a function, optimized some functions.
PatGarrett (talk | contribs) 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
if bot=='' then do; top=15; bot=0; end /*No args? Use a range of
if top=='' then top=bot /*No top? Use the bottom for
numeric digits max(20, 5*top) /*this allows gihugic Catalan numbers. */
call hdr '1b'; do j=bot to top; say $cat() catalan1b(j); end▼
call hdr
call hdr
▲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
exit /*stick a fork in it, we're all done. */
/*────────────────────────────────────────────────────────────────────────────*/
catalan1a: procedure expose !.; parse arg n; return comb(n+n,n)%(n+1)▼
pFact: procedure; !=1; do k=arg(1) to arg(2); !=!*k; end; return !
/*────────────────────────────────────────────────────────────────────────────*/
say center(' Catalan numbers, method' left(arg(1),3), 79, '─'); return
/*────────────────────────────────────────────────────────────────────────────*/
!.x=!; return
/*──────────────────────────────────Catalan method 2──────────────────────────*/
▲
do k=0 to n-1; s=s+catalan2(k)*catalan2(n-k-1); end
c.n=
/*──────────────────────────────────Catalan method 3──────────────────────────*/
'''output''' when using the input of: <tt> 0 16 </tt>
<pre>
───────────────────────── Catalan numbers, method
Catalan 0: 1
Catalan 1: 1
Line 2,841:
Catalan 15: 9694845
───────────────────────── Catalan numbers, method
··· (elided, same as first method) ···
Line 2,850:
··· (elided, same as first method) ···
</pre>
'''Timing notes''' of the four methods:
::* For Catalan numbers 1 ──► 200:
::::* method '''
::::* method '''
::::* method '''2''' is about 85 times slower than method '''3'''
::* For Catalan numbers 1 ──► 300:
::::* method '''
::::* method '''
::::* method '''2''' is about 200 times slower than method '''3'''
Method '''3''' is really quite fast; even in the thousands range, computation time is still quite reasonable.
|