Evaluate binomial coefficients: Difference between revisions
Content added Content deleted
m (added whitespace before the TOC (table of contents), shown the formula with a bigger font to make it easier to read the italics.) |
m (→{{header|REXX}}: changed/added comments and whitespace, changed indentations.) |
||
Line 1,555: | Line 1,555: | ||
The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits. |
The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits. |
||
===idiomatic=== |
===idiomatic=== |
||
<lang rexx>/*REXX program calculates binomial coefficients ( |
<lang rexx>/*REXX program calculates binomial coefficients (also known as combinations). */ |
||
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
||
parse arg n k . /*obtain N and K from the C.L. */ |
parse arg n k . /*obtain N and K from the C.L. */ |
||
say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */ |
say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */ |
||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
comb: procedure; parse arg x,y; return !(x) % (!(x-y) * !(y)) |
comb: procedure; parse arg x,y; return !(x) % (!(x-y) * !(y)) |
||
⚫ | |||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
'''output''' when using the input of: <tt> 5 3 </tt> |
'''output''' when using the input of: <tt> 5 3 </tt> |
||
<pre> |
<pre> |
||
combinations(5,3)= 10 |
combinations(5,3)= 10 |
||
</pre> |
</pre> |
||
'''output''' when using the input of: <tt> 1200 120 </tt> |
'''output''' when using the input of: <tt> 1200 120 </tt> |
||
<pre> |
<pre> |
||
combinations(1200,120)= 1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600 |
combinations(1200,120)= 1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600 |
||
Line 1,576: | Line 1,575: | ||
This REXX version takes advantage of reducing the size (product) of the numerator, and also, |
This REXX version takes advantage of reducing the size (product) of the numerator, and also, |
||
<br>only two (factorial) products need be calculated. |
<br>only two (factorial) products need be calculated. |
||
<lang rexx>/*REXX program calculates binomial coefficients ( |
<lang rexx>/*REXX program calculates binomial coefficients (also known as combinations). */ |
||
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
||
parse arg n k . /*obtain N and K from the C.L. */ |
parse arg n k . /*obtain N and K from the C.L. */ |
||
say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */ |
say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */ |
||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
comb: procedure; parse arg x,y; return pfact(x-y+1,x) % pfact(2,y) |
comb: procedure; parse arg x,y; return pfact(x-y+1, x) % pfact(2, y) |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
pfact: procedure; !=1; |
pfact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end /*j*/; return !</lang> |
||
'''output''' is identical to the 1<sup>st</sup> version. |
'''output''' is identical to the 1<sup>st</sup> REXX version. |
||
It is (around average) about ten times faster than the 1<sup>st</sup> version for <code> 200,20 </code> and <code> 100,10</code>. |
It is (around average) about ten times faster than the 1<sup>st</sup> version for <code> 200,20 </code> and <code> 100,10</code>. |
||
<br>For <code>100,80 </code> it is about 30% faster. <br> |
<br>For <code>100,80 </code> it is about 30% faster. <br> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |