Perfect numbers: Difference between revisions

Content added Content deleted
m (→‎Classic REXX version of PL/I: changed a comment.)
m (→‎Lucas-Lehmer method: added/changed comments and whitespace.)
Line 1,828: Line 1,828:
This version uses memoization to implement a fast version of Lucas-Lehmer test,
This version uses memoization to implement a fast version of Lucas-Lehmer test,
<br>it is faster than the traditional method by an order of magnitude.
<br>it is 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 specified number(s).*/
parse arg low high . /*obtain the optional arguments from CL*/
if high=='' & low=='' then high=34000000 /*if no args, use a range.*/
if high=='' & low=='' then high=34000000 /*if no arguments, then use a range. */
if low=='' then low=1 /*if no LOW, then assume unity.*/
if low=='' then low=1 /*if no LOW, then assume unity. */
if low//2 then low=low+1 /*if LOW is odd, bump it by one.*/
low=low+low//2 /*if LOW is odd, bump it by one. */
if high=='' then high=low /*if no HIGH, then assume LOW. */
if high=='' then high=low /*if no HIGH, then assume LOW. */
w=length(high) /*use W for formatting output. */
w=length(high) /*use W for formatting the output. */
numeric digits max(9,w+2) /*ensure enough digits to handle#*/
numeric digits max(9,w+2) /*ensure enough digits to handle number*/
@.=0; @.1=2 /*highest magic # and its index.*/
@.=0; @.1=2 /*highest magic number and its index. */
⚫
do i=low to high by 2 /*process the single # or range. */
if isPerfect(i) then say right(i,w) 'is a perfect number.'
⚫
end /*i*/
⚫
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────ISPERFECT subroutine────────────────*/
⚫
isPerfect: procedure expose @.; parse arg x /*get the # to be tested.*/
⚫
/*Lucas-Lehmer know that perfect */
⚫
/* numbers can be expressed as: */
⚫
/* [2**n - 1] * [2** (n-1) ] */


⚫
do i=low to high by 2 /*process the single number or a range.*/
⚫
if @.0<x then do @.1=@.1 while @._<=x; _=(2**@.1-1)*2**(@.1-1); @.0=_; @._=_
end /*@.1*/ /*uses memoization for formula. */
if isPerfect(i) then say right(i,w) 'is a perfect number.'
⚫
end /*i*/
⚫
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
⚫
isPerfect: procedure expose @.; parse arg x /*obtain the number to be tested. */
⚫
/*Lucas-Lehmer know that perfect */
⚫
/* numbers can be expressed as: */
⚫
/* [2**n - 1] * [2** (n-1) ] */


⚫
if @.0<x then do @.1=@.1 while @._<=x; _=(2**@.1-1)*2**(@.1-1); @.0=_; @._=_
if @.x==0 then return 0 /*Didn't pass Lucas-Lehmer test? */
s = 3 + x%2 /*we know the following factors: */
end /*@.1*/ /*uses memoization for the formula. */

⚫
/* 1 ('cause Mama said so.)*/
/* 2 ('cause it's even.) */
if @.x==0 then return 0 /*Didn't pass Lucas-Lehmer test? */
/* x÷2 " " " _*/
s = 3 + x%2 /*we know the following factors: */
do j=3 while j*j<=x /*starting at 3, find factors ≤√X*/
/* 1 ('cause Mama said so.) */
if x//j\==0 then iterate /*J divides X evenly, so ... */
/* 2 ('cause it's even.) */
s = s + j + x%j /*··· add it and the other factor*/
/* x÷2 ( " " " ) ___*/
if s>x then return 0 /*Sum too big? It ain't perfect.*/
do j=3 while j*j<=x /*starting at 3, find the factors ≤√ X */
end /*j*/ /*(above) is marginally faster. */
if x//j\==0 then iterate /*J divides X evenly, so ··· */
return s==x /*if the sum matches X, perfect! */</lang>
s=s + j + x%j /*··· add it and the other factor. */
if s>x then return 0 /*Is the sum too big? It ain't perfect*/
⚫
end /*j*/ /*(above) is marginally faster. */
return s==x /*if the sum matches X, it's perfect!*/</lang>
'''output''' &nbsp; is the same as the traditional version &nbsp; and is about '''75''' times faster &nbsp; (testing 34,000,000 numbers).
'''output''' &nbsp; is the same as the traditional version &nbsp; and is about '''75''' times faster &nbsp; (testing 34,000,000 numbers).


Retrieved from "https://rosettacode.org/wiki/Perfect_numbers"