Catalan numbers: Difference between revisions

Content added Content deleted
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: Line 2,790:
===version 1===
===version 1===
All methods use (independent) memoization for the computation of factorials.
All methods use (independent) memoization for the computation of factorials.
<lang rexx>/*REXX program calculates Catalan numbers using four different methods.*/
<lang rexx>/*REXX program calculates Catalan numbers using four different methods. */
parse arg bot top . /*get optional args from the C.L.*/
parse arg bot top . /*get optional arguments from the C.L. */
if bot=='' then do; top=15; bot=0; end /*No args? Use a range of 0──►15.*/
if bot=='' then do; top=15; bot=0; end /*No args? Use a range of 0 ───► 15. */
if top=='' then top=bot /*No top? Use the bottom for it.*/
if top=='' then top=bot /*No top? Use the bottom for default. */
numeric digits max(20, 5*top) /*allows gihugic Catalan numbers.*/
numeric digits max(20, 5*top) /*this allows gihugic Catalan numbers. */
call hdr '1a'; do j=bot to top; say $cat() catalan1a(j); end
@cat=' Catalan' /*a nice literal to have for the SAY. */
⚫
w=length(top) /*width of the largest number for SAY. */
⚫
call hdr '1b'; do j=bot to top; say $cat() catalan1b(j); end
call hdr 2 ; do j=bot to top; say $cat() catalan2(j) ; end
call hdr 1A; do j=bot to top; say @cat right(j,w)": " catalan1A(j); end
call hdr 3 ; do j=bot to top; say $cat() catalan3(j) ; end
call hdr 1B; do j=bot to top; say @cat right(j,w)": " catalan1B(j); end
⚫
call hdr 2 ; do j=bot to top; say @cat right(j,w)": " catalan2(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)
catalan1b: procedure expose !.; parse arg n; return !(n+n)%((n+1)*!(n)**2)
catalan1A: procedure expose !.; parse arg n; return comb(n+n, n) % (n+1)
comb: procedure; parse arg x,y; return pFact(x-y+1,x) % pFact(2,y)
catalan1B: procedure expose !.; parse arg n; return !(n+n) % ((n+1) * !(n)**2)
pFact: procedure; !=1; do k=arg(1) to arg(2); !=!*k; end; return !
comb: procedure; parse arg x,y; 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; do k=1 for x; !=!*k; end /*k*/; !.x=!; return !
hdr: !.=.; c.=.; c.0=1; 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; do k=0 to n-1
!: procedure expose !.; parse arg x; !=1; if !.x\==. then return !.x
s=s + catalan2(k) * catalan2(n-k-1) /*recursive invokes*/
do k=1 for x; !=!*k; end /*k*/
end /*k*/
!.x=!; return !
/*──────────────────────────────────Catalan method 2──────────────────────────*/
c.n=s; return s /*use REXX memoization technique.*/
⚫
catalan2: procedure expose c.; parse arg n; s=0; if c.n\==. then return c.n
/*──────────────────────────────────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) * catalan3(n-1) % (n+1); return c.n /*use memoization.*/
c.n=s; return s /*use a REXX memoization technique. */
/*──────────────────────────────────Catalan method 3──────────────────────────*/
/*──────────────────────────────────HDR subroutine──────────────────────*/
hdr: !.=.; c.=.; c.0=1; say /*set some variables; blank line.*/
catalan3: procedure expose c.; parse arg n; if c.n\==. then return c.n
say center(' Catalan numbers, method' left(arg(1),3), 79, '─'); return</lang>
c.n=(4*n-2) * catalan3(n-1) % (n+1); return c.n /*use memoization.*/</lang>
'''output''' when using the input of: &nbsp; <tt> 0 16 </tt>
'''output''' when using the input of: &nbsp; <tt> 0 16 </tt>
<pre>
<pre>
───────────────────────── Catalan numbers, method 1a ──────────────────────────
───────────────────────── Catalan numbers, method 1A ──────────────────────────
Catalan 0: 1
Catalan 0: 1
Catalan 1: 1
Catalan 1: 1
Line 2,841: Line 2,841:
Catalan 15: 9694845
Catalan 15: 9694845


───────────────────────── Catalan numbers, method 1b ──────────────────────────
───────────────────────── Catalan numbers, method 1B ──────────────────────────
··· (elided, same as first method) ···
··· (elided, same as first method) ···


Line 2,850: Line 2,850:
··· (elided, same as first method) ···
··· (elided, same as first method) ···
</pre>
</pre>
'''Timing notes''' of the four methods:
'''Timing notes''' &nbsp; of the four methods:


::* For Catalan numbers &nbsp; 1 ──► 200:
::* For Catalan numbers &nbsp; 1 ──► 200:
::::* method &nbsp; '''1a''' &nbsp; is about &nbsp; 50 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1A''' &nbsp; is about &nbsp; 50 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1b''' &nbsp; is about 100 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1B''' &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'''
::::* method &nbsp; '''2''' &nbsp; &nbsp; is about &nbsp; 85 times slower than method &nbsp; '''3'''


::* For Catalan numbers &nbsp; 1 ──► 300:
::* For Catalan numbers &nbsp; 1 ──► 300:
::::* method &nbsp; '''1a''' &nbsp; is about 100 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1A''' &nbsp; is about 100 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1b''' &nbsp; is about 200 times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1B''' &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; '''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.
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/Catalan_numbers"