Square form factorization: Difference between revisions
Content added Content deleted
m (Minor code improvement) |
(Added Algol 68) |
||
Line 48: | Line 48: | ||
__TOC__ |
__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}}== |
=={{header|C}}== |