Square form factorization: Difference between revisions
Added Algol 68
m (Minor code improvement) |
(Added Algol 68) |
||
Line 48:
__TOC__
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Assumes LONG INT is long enough - this is true in ALGOL 68G versioins 2 and 3.
{{Trans|Wren|...but only using a single size of integer}}
<syntaxhighlight lang="algol68">
BEGIN # Daniel Shanks's Square Form Factorization (SquFoF) - based on the Wren sample #
MODE INTEGER = LONG INT; # large enough INT type #
PROC(LONG REAL)LONG REAL size sqrt = long sqrt; # sqrt for INTEGER values #
[]INTEGER multipliers = ( 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
);
PROC gcd = ( INTEGER x, y )INTEGER: # iterative gcd #
BEGIN
INTEGER a := x, b := y;
WHILE b /= 0 DO
INTEGER next a = b;
b := a MOD b;
a := next a
OD;
ABS a
END # gcd # ;
PROC squfof = ( INTEGER n )INTEGER:
IF INTEGER s = ENTIER ( size sqrt( n ) + 0.5 );
s * s = n
THEN s
ELSE INTEGER result := 0;
FOR multiplier FROM LWB multipliers TO UPB multipliers WHILE result = 0 DO
INTEGER d = n * multipliers[ multiplier ];
INTEGER pp := ENTIER size sqrt( d );
INTEGER p prev := pp;
INTEGER po = p prev;
INTEGER q prev := 1;
INTEGER qq := d - ( po * po );
INTEGER l = ENTIER size sqrt( s * 8 );
INTEGER bb = 3 * l;
INTEGER i := 2;
INTEGER b := 0;
INTEGER q := 0;
INTEGER r := 0;
BOOL again := TRUE;
WHILE i < bb AND again DO
b := ( po + pp ) OVER qq;
pp := ( b * qq ) - pp;
q := qq;
qq := q prev + ( b * ( p prev - pp ) );
r := ENTIER ( size sqrt( qq ) + 0.5 );
IF i MOD 2 = 0 THEN again := r * r /= qq FI;
IF again THEN
q prev := q;
p prev := pp;
i +:= 1
FI
OD;
IF i < bb THEN
b := ( po - pp ) OVER r;
p prev := pp := ( b * r ) + pp;
q prev := r;
qq := ( d - ( p prev * p prev ) ) OVER q prev;
i := 0;
WHILE
b := ( po + pp ) OVER qq;
p prev := pp;
pp := ( b * qq ) - pp;
q := qq;
qq := q prev + ( b * ( p prev - pp ) );
q prev := q;
i +:= 1;
pp /= p prev
DO SKIP OD
FI;
r := gcd( n, q prev );
IF r /= 1 AND r /=n THEN result := r FI
OD;
result
FI # squfof # ;
[]INTEGER examples = ( 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
);
print( ( "Integer Factor Quotient", newline ) );
print( ( "----------------------------------------", newline ) );
FOR example FROM LWB examples TO UPB examples DO
INTEGER n = examples[ example ];
INTEGER fact = squfof( n );
STRING quot = IF fact = 0 THEN "fail" ELSE whole( n OVER fact, 0 ) FI;
print( ( whole( n, -20 ), " ", whole( fact, -10 ), " ", quot, newline ) )
OD
END
</syntaxhighlight>
{{out}}
<pre>
Integer Factor Quotient
----------------------------------------
2501 61 41
12851 71 181
13289 137 97
75301 293 257
120787 43 2809
967009 1609 601
997417 257 3881
7091569 2663 2663
13290059 3119 4261
42854447 9689 4423
223553581 11213 19937
2027651281 46061 44021
11111111111 21649 513239
100895598169 112303 898423
1002742628021 0 fail
60012462237239 6862753 8744663
287129523414791 6059887 47381993
9007199254740931 10624181 847801751
11111111111111111 2071723 5363222357
314159265358979323 317213509 990371647
384307168202281507 415718707 924440401
419244183493398773 48009977 8732438749
658812288346769681 62222119 10588072199
922337203685477563 110075821 8379108103
1000000000000000127 111756107 8948056861
1152921505680588799 139001459 8294312261
1537228672809128917 26675843 57626245319
4611686018427387877 343242169 13435662733
</pre>
=={{header|C}}==
| |||