Perfect numbers: Difference between revisions
Content added Content deleted
m (→Lucas-Lehmer + other optimizations: changed indentations in the isPerfect function.) |
m (→{{header|REXX}}: added/changed comments and whitespace, changed comments in various header and output sections.) |
||
| Line 1,690: | Line 1,690: | ||
===Classic REXX version of PL/I=== |
===Classic REXX version of PL/I=== |
||
This version is a Classic REXX version of the PL/I program as of 14-Sep-2013, a REXX '''say''' statement |
This version is a Classic REXX version of the PL/I program as of 14-Sep-2013, a REXX '''say''' statement |
||
<br>was added to display the perfect numbers. Also, an epilog was written for the re-worked function. |
|||
<lang rexx>/*REXX version of the PL/I program (code was modified to run with Classic REXX). */ |
<lang rexx>/*REXX version of the PL/I program (code was modified to run with Classic REXX). */ |
||
parse arg low high . /*obtain the specified number(s).*/ |
parse arg low high . /*obtain the specified number(s).*/ |
||
| Line 1,714: | Line 1,715: | ||
===traditional method=== |
===traditional method=== |
||
Programming note: this traditional method takes advantage of a few shortcuts: |
Programming note: this traditional method takes advantage of a few shortcuts: |
||
:::* testing only goes up to the (integer) square root of '''X''' |
:::* testing only goes up to the (integer) square root of '''X''' |
||
:::* testing bypasses the test of the first and last factors |
:::* testing bypasses the test of the first and last factors |
||
:::* |
:::* the ''corresponding factor'' is used when a factor is found |
||
:::* testing is stopped if the sum of the factors exceeds '''X''' |
:::* testing is stopped if the sum of the factors exceeds '''X''' |
||
<lang rexx>/*REXX program tests if a number (or a range of numbers) is/are perfect. */ |
<lang rexx>/*REXX program tests if a number (or a range of numbers) is/are perfect. */ |
||
parse arg low high . /*obtain optional arguments from the CL*/ |
parse arg low high . /*obtain optional arguments from the CL*/ |
||
| Line 1,741: | Line 1,742: | ||
return s==x /*if the sum matches X, it's perfect! */</lang> |
return s==x /*if the sum matches X, it's perfect! */</lang> |
||
'''output''' when using the default inputs: |
'''output''' when using the default inputs: |
||
<pre> |
|||
6 is a perfect number. |
6 is a perfect number. |
||
28 is a perfect number. |
28 is a perfect number. |
||
| Line 1,747: | Line 1,749: | ||
33550336 is a perfect number. |
33550336 is a perfect number. |
||
</pre> |
</pre> |
||
For 10,000 numbers tested, this version is '''19.6''' times faster than the ooRexx program logic.<br> |
For 10,000 numbers tested, this version is '''19.6''' times faster than the ooRexx program logic.<br> |
||
For 10,000 numbers tested, this version is '''25.6''' times faster than the PL/I program logic. |
For 10,000 numbers tested, this version is '''25.6''' times faster than the PL/I program logic. |
||
<br><br>Note: For the above timings, only 10,000 numbers were tested. |
<br><br>Note: For the above timings, only 10,000 numbers were tested. |
||
===optimized using digital root=== |
===optimized using digital root=== |
||
This REXX version makes use of the fact that all ''known'' perfect numbers > 6 have a ''digital root'' of '''1'''. |
This REXX version makes use of the fact that all ''known'' perfect numbers > 6 have a ''digital root'' of '''1'''. |
||
<lang rexx>/*REXX program tests if a number (or a range of numbers) is/are perfect. */ |
<lang rexx>/*REXX program tests if a number (or a range of numbers) is/are perfect. */ |
||
parse arg low high . /*obtain the specified number(s). */ |
parse arg low high . /*obtain the specified number(s). */ |
||
| Line 1,782: | Line 1,784: | ||
end /*j*/ /*(above) is marginally faster. */ |
end /*j*/ /*(above) is marginally faster. */ |
||
return s==x /*if the sum matches X, it's perfect! */</lang> |
return s==x /*if the sum matches X, it's perfect! */</lang> |
||
'''output''' is the same as the traditional version and is about '''5.3''' times faster (testing 34,000,000 numbers). |
'''output''' is the same as the traditional version and is about '''5.3''' times faster (testing 34,000,000 numbers). |
||
===optimized using only even numbers=== |
===optimized using only even numbers=== |
||
| Line 1,816: | Line 1,818: | ||
end /*j*/ /*(above) is marginally faster. */ |
end /*j*/ /*(above) is marginally faster. */ |
||
return s==x /*if sum matches X, then it's perfect!*/</lang> |
return s==x /*if sum matches X, then it's perfect!*/</lang> |
||
'''output''' is the same as the traditional version and is about '''11.5''' times faster (testing 34,000,000 numbers). |
'''output''' is the same as the traditional version and is about '''11.5''' times faster (testing 34,000,000 numbers). |
||
===Lucas-Lehmer method=== |
===Lucas-Lehmer method=== |
||
This version uses memoization to implement a fast version of Lucas-Lehmer test, |
This version uses memoization to implement a fast version of the Lucas-Lehmer test, |
||
<br> |
<br>and it's faster than the traditional method by an order of magnitude. |
||
<lang rexx>/*REXX program tests if a number (or a range of numbers) is/are perfect. */ |
<lang rexx>/*REXX program tests if a number (or a range of numbers) is/are perfect. */ |
||
parse arg low high . /*obtain the optional arguments from CL*/ |
parse arg low high . /*obtain the optional arguments from CL*/ |
||
| Line 1,855: | Line 1,857: | ||
end /*j*/ /*(above) is marginally faster. */ |
end /*j*/ /*(above) is marginally faster. */ |
||
return s==x /*if the sum matches X, it's perfect!*/</lang> |
return s==x /*if the sum matches X, it's perfect!*/</lang> |
||
'''output''' is the same as the traditional version and is about '''75''' times faster (testing 34,000,000 numbers). |
'''output''' is the same as the traditional version and is about '''75''' times faster (testing 34,000,000 numbers). |
||
===Lucas-Lehmer + other optimizations=== |
===Lucas-Lehmer + other optimizations=== |
||