Partition function P: Difference between revisions
Content added Content deleted
(→{{header|REXX}}: added a faster 2nd version.) |
|||
Line 1,030: | Line 1,030: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Both REXX versions are recursive. |
|||
=== version 1 === |
|||
<lang rexx>/*REXX program calculates and displays a specific value (or a range of) partitionsP(N).*/ |
<lang rexx>/*REXX program calculates and displays a specific value (or a range of) partitionsP(N).*/ |
||
numeric digits 1000 /*able to handle some ginormous numbers*/ |
numeric digits 1000 /*able to handle some ginormous numbers*/ |
||
Line 1,037: | Line 1,038: | ||
if hi=='' | hi=="," then hi= lo /* " " " " " " */ |
if hi=='' | hi=="," then hi= lo /* " " " " " " */ |
||
@.= 0; @.0= 1; @.1= 1; @.2= 2; @.3= 3; @.4= 5 /*assign default value and low values. */ |
@.= 0; @.0= 1; @.1= 1; @.2= 2; @.3= 3; @.4= 5 /*assign default value and low values. */ |
||
!.= @.; !.1= 1; !.3= 1; !.5= 1; !.7= 1; !.9= 1 /*assign default value and even digits.*/ |
|||
w= length( commas(hi) ) /*W: is used for aligning the index. */ |
w= length( commas(hi) ) /*W: is used for aligning the index. */ |
||
Line 1,046: | Line 1,048: | ||
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? |
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
partP: procedure expose @.; parse arg n |
partP: procedure expose @. !.; parse arg n /*obtain number (index) for computation*/ |
||
if @.n\==0 then return @.n /*Is it already computed? Return it. */ |
if @.n\==0 then return @.n /*Is it already computed? Return it. */ |
||
#= 0 /*initialize part P number.*/ |
#= 0 /*initialize part P number.*/ |
||
do k=1 for n; z= n - (k*3 - 1) * k % 2 |
do k=1 for n; z= n - (k*3 - 1) * k % 2 /*compute the partition P num*/ |
||
if z<0 then leave /*Is Z negative? Then leave.*/ |
if z<0 then leave /*Is Z negative? Then leave.*/ |
||
if @.z==0 then x= partP(z) /*use recursion if not known.*/ |
if @.z==0 then x= partP(z) /*use recursion if not known.*/ |
||
Line 1,060: | Line 1,062: | ||
else #= # - (x + y) /*Even? " subtract " " " */ |
else #= # - (x + y) /*Even? " subtract " " " */ |
||
end /*k*/ |
end /*k*/ |
||
@.n= #; |
@.n= #; return # /*define and return partitionsP of N. */</lang> |
||
{{out|output|text= when using the input of: <tt> 6666 </tt>}} |
{{out|output|text= when using the input of: <tt> 6666 </tt>}} |
||
<pre> |
<pre> |
||
Line 1,069: | Line 1,071: | ||
66,666 931,283,431,869,095,717,238,416,063,534,148,471,363,928,685,651,267,074,563,360,050,977,549,251,436,058,076,515,262,033,789,845,457,356,081,278,451,246,751,375,974,038,318,319,810,923,102,769,109,446,980,055,567,090,089,060,954,748,065,131,666,952,830,623,286,286,824,837,240,058,805,177,319,865,230,913,417,587,625,830,803,675,380,262,765,598,632,742,903,192,085,254,824,621 |
66,666 931,283,431,869,095,717,238,416,063,534,148,471,363,928,685,651,267,074,563,360,050,977,549,251,436,058,076,515,262,033,789,845,457,356,081,278,451,246,751,375,974,038,318,319,810,923,102,769,109,446,980,055,567,090,089,060,954,748,065,131,666,952,830,623,286,286,824,837,240,058,805,177,319,865,230,913,417,587,625,830,803,675,380,262,765,598,632,742,903,192,085,254,824,621 |
||
</pre> |
</pre> |
||
=== version 2 === |
|||
This REXX version is about '''25%''' faster than REXX version 1. |
|||
The biggest part of the improvement was using the expression '''k+k+k''' instead of '''k*3'''. |
|||
<lang rexx>/*REXX program calculates and displays a specific value (or a range of) partitionsP(N).*/ |
|||
numeric digits 1000 /*able to handle some ginormous numbers*/ |
|||
parse arg lo hi . /*obtain optional arguments from the CL*/ |
|||
if lo=='' | lo=="," then lo= 0 /*Not specified? Then use the default.*/ |
|||
if hi=='' | hi=="," then hi= lo /* " " " " " " */ |
|||
@.= 0; @.0= 1; @.1= 1; @.2= 2; @.3= 3; @.4= 5 /*default values for some low numbers. */ |
|||
!.= @.; !.1= 1; !.3= 1; !.5= 1; !.7= 1; !.9= 1 /* " " " all the 1─digit #s*/ |
|||
w= length( commas(hi) ) /*W: is used for aligning the index. */ |
|||
do j=lo to hi /*compute a range of partitionsP. */ |
|||
say right( commas(j), w) ' ' commas( partP(j) ) |
|||
end /*j*/ |
|||
exit 0 /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
partP: procedure expose @. !.; parse arg n /*obtain number (index) for computation*/ |
|||
if @.n\==0 then return @.n /*Is it already computed? Return it. */ |
|||
#= 0 /*initialize part P number.*/ |
|||
do k=1 for n; z= n - (k+k+k - 1) * k % 2 /*compute the partition P num*/ |
|||
if z<0 then leave /*Is Z negative? Then leave.*/ |
|||
if @.z==0 then x= partP(z) /*use recursion if not known.*/ |
|||
else x= @.z /*use the pre─computed number*/ |
|||
z= z - k /*subtract index (K) from Z. */ |
|||
if z<0 then y= 0 /*Is Z negative? Then set Y=0*/ |
|||
else if @.z==0 then y= partP(z) /*use recursion if not known.*/ |
|||
else y= @.z /*use the pre─computed number*/ |
|||
parse var k '' -1 _ /*obtain K's last decimal dig*/ |
|||
if !._ then #= # + x + y /*Odd? Then sum X and Y.*/ |
|||
else #= # - (x + y) /*Even? " subtract " " " */ |
|||
end /*k*/ |
|||
@.n= #; return # /*define and return partitionsP of N. */</lang> |
|||
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br> |
|||
=={{header|Rust}}== |
=={{header|Rust}}== |