Anonymous user
Square form factorization: Difference between revisions
→{{header|REXX}}: added the computer programming language REXX.
mNo edit summary |
(→{{header|REXX}}: added the computer programming language REXX.) |
||
Line 686:
1537228672809128917 0 fail
4611686018427387877 343242169 13435662733
</pre>
=={{header|REXX}}==
<lang rexx>/*REXX pgm factors an integer using Daniel Shanks' (1917-1996) square form factorization*/
numeric digits 100 /*ensure enough decimal digits.*/
call dMults 1,3,5,7,11,3*5,3*7,3*11,5*7,5*11,7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11
call dTests 2501, 12851, 13289, 75301, 120787, 967009, 997417, 7091569, 13290059, ,
42854447, 223553581, 2027651281, 11111111111, 100895598169, 1002742628021, ,
60012462237239, 287129523414791, 9007199254740931, 11111111111111111, ,
314159265358979323, 384307168202281507, 419244183493398773, ,
658812288346769681, 922337203685477563, 1000000000000000127, ,
1152921505680588799, 1537228672809128917, 4611686018427387877
w= length( commas(!.$) ) /*the max width of test numbers*/
do tests=1 for !.0; n= !.tests; nc= commas(n)
f= ssff(n); fc= commas(f); wf= length(fc); if f\==0 then nf= commas(n%f)
if f\==0 then do; nfc= commas(n%f); wnfc= length(nfc); end
if f ==0 then _= " (Shank's square form factor failed.)"
else _= ' factors are: ' right( fc, max(w%2 , wf ) ) " and " ,
right(nfc, max(w%2+4, wnfc) )
say right(nc, w+5) _
end /*tests*/
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 ?
dMults: @.$= 0; do j=1 for arg(); @.j= arg(j); @.$=max(@.$, @.j); end; @.0=j-1; return
dTests: !.$= 0; do j=1 for arg(); !.j= arg(j); !.$=max(!.$, !.j); end; !.0=j-1; return
gcd: procedure; parse arg x,y; do until _==0; _= x // y; x= y; y= _; end; return x
/*──────────────────────────────────────────────────────────────────────────────────────*/
iSqrt: procedure; parse arg x; r=0; q=1; do while q<=x; q=q*4; end
do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end
return r
/*──────────────────────────────────────────────────────────────────────────────────────*/
ssff: procedure expose @.; parse arg n; n= abs(n); er= '***error***'
s= iSqrt(n); if s**2==n then return s; big= 2**digits()
do #=1 for @.0; k= @.# /*get a # from the list of low factors*/
if n>big/k then do; say er 'number is too large: ' commas(k); exit 8; end
d= n * k
po= iSqrt(d); pprev= po
p= po; qprev= 1
QQ= d - po * po
BB= iSqrt(s+s) * 6
do i=2 while i<BB; b= (po + p) % QQ
p= b * QQ - p; q= QQ
QQ= qprev + b * (pprev - p)
r= iSqrt(QQ)
if i//2==0 & r*r==QQ then leave
qprev= q; pprev= p
end /*i*/
if i>=BB then iterate
b= (po - p) % r
p= b * r + p
pprev= p; qprev= r
QQ= (d - pprev*pprev) % qprev
do until p==pprev; pprev= p
b= (po + p) % QQ
p= b * QQ - p; q= QQ
QQ= qprev + b * (pprev - p)
qprev= q
end /*forever*/
r= gcd(n, qprev)
if r\==1 then if r\==n then return r
end /*#*/
return 0</lang>
{{out|output|text= when using the internal default input:}}
<pre>
2,501 factors are: 61 and 41
12,851 factors are: 71 and 181
13,289 factors are: 137 and 97
75,301 factors are: 293 and 257
120,787 factors are: 43 and 2,809
967,009 factors are: 1,609 and 601
997,417 factors are: 257 and 3,881
7,091,569 factors are: 2,663 and 2,663
13,290,059 factors are: 3,119 and 4,261
42,854,447 factors are: 9,689 and 4,423
223,553,581 factors are: 11,213 and 19,937
2,027,651,281 factors are: 46,061 and 44,021
11,111,111,111 factors are: 21,649 and 513,239
100,895,598,169 factors are: 112,303 and 898,423
1,002,742,628,021 (Shank's square form factor failed.)
60,012,462,237,239 factors are: 6,862,753 and 8,744,663
287,129,523,414,791 factors are: 6,059,887 and 47,381,993
9,007,199,254,740,931 factors are: 10,624,181 and 847,801,751
11,111,111,111,111,111 factors are: 2,071,723 and 5,363,222,357
314,159,265,358,979,323 factors are: 317,213,509 and 990,371,647
384,307,168,202,281,507 factors are: 415,718,707 and 924,440,401
419,244,183,493,398,773 factors are: 48,009,977 and 8,732,438,749
658,812,288,346,769,681 factors are: 62,222,119 and 10,588,072,199
922,337,203,685,477,563 factors are: 110,075,821 and 8,379,108,103
1,000,000,000,000,000,127 factors are: 111,756,107 and 8,948,056,861
1,152,921,505,680,588,799 factors are: 139,001,459 and 8,294,312,261
1,537,228,672,809,128,917 factors are: 26,675,843 and 57,626,245,319
4,611,686,018,427,387,877 factors are: 343,242,169 and 13,435,662,733
</pre>
| |||