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:
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.
<lang rexx>/*REXX program tests if a number (or a range of numbers) is/are perfect. */
parse arg low high . /*obtain the
if high=='' & low=='' then high=34000000 /*if no
if low=='' then low=1 /*if no LOW, then assume unity. */
if high=='' then high=low /*if no HIGH, then assume LOW. */
w=length(high) /*use W for formatting the output. */
numeric digits max(9,w+2) /*ensure enough digits to handle
@.=0; @.1=2 /*highest magic
do i=low to high by 2 /*process the single # or range. */▼
end /*i*/▼
exit /*stick a fork in it, we're done.*/▼
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) ] */▼
if @.0<x then do @.1=@.1 while @._<=x; _=(2**@.1-1)*2**(@.1-1); @.0=_; @._=_▼
if isPerfect(i)
▲exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲ /*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=_; @._=_
/* 1 ('cause Mama said so.)*/▼
if @.x==0 then return
s = 3 + x%2
if s>x then return 0 /*Is the sum too big? It ain't perfect*/
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).
|