Jump to content

Perfect numbers: Difference between revisions

Perfect numbers (view source)

Revision as of 06:13, 6 April 2016

535 bytes added ,  8 years ago
m
→‎Lucas-Lehmer method: added/changed comments and whitespace.
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 specifiedoptional arguments from number(s).CL*/
if high=='' & low=='' then high=34000000 /*if no argsarguments, then use a range. */
if low=='' then low=1 /*if no LOW, then assume unity. */
if low=low+low//2 then low=low+1 /*if LOW is odd, bump it by one. */
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# number*/
@.=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=_; @._=_▼
if isPerfect(i) end then say /*@.1*/ right(i,w) 'is a perfect /*uses memoization for formulanumber. */'
▲ end /*i*/
▲exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲isPerfect: procedure expose @.; parse arg x /*getobtain 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 end /*@.1*/ /*weuses knowmemoization for the followingformula. factors: */
 
/* 1 ('cause Mama said so.)*/▼
if @.x==0 then return 0 /*Didn't pass 2Lucas-Lehmer test? ('cause it's even.) */
s = 3 + x%2 /* x÷2 " /*we know "the following factors: " _*/
do j=3 while j*j<=x /*starting at 3,1 ('cause Mama said so.) find factors ≤√X*/
if x//j\==0 then iterate /*J divides2 X evenly, so('cause it's even...) */
s = s + j + x%j /*··· addx÷2 ( " " " ) it and the other factor___*/
if s>x then return 0 do j=3 while j*j<=x /*Sumstarting at 3, toofind big?the factors It≤√ ain'tX perfect.*/
end if x/*j*/j\==0 then iterate /*J divides X evenly, so ··· /*(above) is marginally faster. */
return s==x s=s + j + x%j /*if··· the sumadd matchesit X, perfect!and the other factor. */</lang>
if s>x then return 0 /*Is the sum too big? It ain't perfect*/
▲ end /*j*/ /*(above) 1is marginally faster. ('cause Mama said so.)*/
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).
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/80290"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information