Square form factorization: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (Added a comment) |
m (→{{header|Wren}}: Minor tidy) |
||
| (6 intermediate revisions by 5 users not shown) | |||
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}}==
Line 449 ⟶ 589:
for ( uint32_t i = 0; i < 20; ++i ) {
uint64_t test = distribution(random);
uint64_t factor = squfof(test);
if ( factor == 0 ) {
std::cout << test << "
} else {
std::cout << test << " = " << factor << " * " << test / factor << std::endl;
}
std::cout << std::endl;
Line 463 ⟶ 602:
{{ out }}
<pre>
</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight lang=easylang>
multiplier[] = [ 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 ]
func gcd a b .
while b <> 0
a = a mod b
swap a b
.
return a
.
func squfof N .
s = floor (sqrt N + 0.5)
if s * s = N
return s
.
for multiplier in multiplier[]
if N > 9007199254740992 / multiplier
print "Number " & N & " is too big"
break 1
.
D = multiplier * N
P = floor sqrt D
Po = P
Pprev = P
Qprev = 1
Q = D - Po * Po
L = 2 * floor sqrt (2 * s)
B = 3 * L
for i = 2 to B - 1
b = (Po + P) div Q
P = b * Q - P
q = Q
Q = Qprev + b * (Pprev - P)
r = floor (sqrt Q + 0.5)
if i mod 2 = 0 and r * r = Q
break 1
.
Qprev = q
Pprev = P
.
if i < B
b = (Po - P) div r
P = b * r + P
Pprev = P
Qprev = r
Q = (D - Pprev * Pprev) / Qprev
i = 0
repeat
b = (Po + P) div Q
Pprev = P
P = b * Q - P
q = Q
Q = Qprev + b * (Pprev - P)
Qprev = q
i += 1
until P = Pprev
.
r = gcd N Qprev
if r <> 1 and r <> N
return r
.
.
.
return 0
.
data[] = [ 2501 12851 13289 75301 120787 967009 997417 7091569 13290059 42854447 223553581 2027651281 11111111111 100895598169 1002742628021 60012462237239 287129523414791 9007199254740931 ]
for example in data[]
factor = squfof example
if factor = 0
print example & " was not factored."
else
quotient = example / factor
print example & " has factors " & factor & " " & quotient
.
.
</syntaxhighlight>
=={{header|FreeBASIC}}==
Line 1,201 ⟶ 1,418:
for ( long test : tests ) {
long factor = squfof(test);
if ( factor == 0 ) {
System.out.println(test + "
} else if ( factor == 1 ) {
System.out.println(test + " is a prime number");
} else {
System.out.println(test + " = " + factor + " * " + test / factor);
}
System.out.println();
Line 1,274 ⟶ 1,490:
}
private static class BQF { // Binary quadratic form
public BQF(long aA, long aB, long aC) {
Line 1,301 ⟶ 1,517:
{{ out }}
<pre>
</pre>
Line 1,749 ⟶ 1,965:
1537228672809128917 26675843 57626245319
4611686018427387877 343242169 13435662733</pre>
=={{header|Pascal}}==
{{works with|Free Pascal}}
A console program written in Free Pascal. The code is based on:
Jason E. Gower and Samuel S. Wagstaff, jr., "Square form factorization",
Mathematics of Computation Volume 77, Number 261, January 2008, Pages 551–588
S 0025-5718(07)02010-8
Article electronically published on May 14, 2007
I'm not sure whether this is the same as reference [1] in the task description; the words "a detailed analysis of SquFoF" appear in the abstract.
The Pascal program includes some small changes to the Gower-Wagstaff algorithm, as noted in the comments. The output shows the successful multiplier (if any) and whether the factor was found in the main or preliminary part of the algorithm.
Further to the advice (on the Discussion page) not to use the Wikipedia version of the algorithm, I tested the Gower-Wagstaff version for all odd composite numbers less than 10^9, and it found a factor in every case. The Wikipedia version failed in 790 cases.
<syntaxhighlight lang="pascal">
program SquFoF_console;
{$mode objfpc}{$H+}
uses SquFoF_utils;
type TResultKind =
(rkPrelim, // a factor was found by the preliminary routine
rkMain, // a factor was found by the main algorithm
rkFail); // no factor was found
type TAlgoResult = record
Kind : TResultKind;
Mult : word;
Factor : UInt64;
end;
// Preliminary to G-W algorithm. Returns D and S of the algorithm.
// Also returns a non-trivial factor if found, else returns factor = 1.
procedure GWPrelim( N : UInt64; // number to be factorized
m : word; // multiplier
out D, S, factor : UInt64);
var
sqflag : boolean;
begin
D := m*N;
sqflag := SquFoF_utils.IsSquare( D, S);
if m = 1 then
if sqflag then factor := S
else factor := 1
else
factor := GCD( N,m);
end;
// Tries to factorize N by applying Gower-Wagstaff alsorithm to m*N.
function GW_with_multiplier( N : UInt64;
m : word) : TAlgoResult;
var
D, S, P, P_prev, Q, L, B: Uint64;
r : UInt64;
i, j, k : integer;
f, g : UInt64;
sqrtD : double;
endCycle : boolean;
// Queue is not much used, so make it a simple array.
type TQueueItem = record
Left, Right : UInt64;
end;
const QUEUE_CAPACITY = 50; // as suggested by Gower & Wagstaff
var
queue : array [0..QUEUE_CAPACITY - 1] of TQueueItem;
queueCount : integer;
begin
result.Mult := m;
// Filter out special cases (differs from Gower & Wagstaff). Note:
// (1) multiplier m is assumed to be squarefree;
// (2) if we proceed to the main algorithm, mN must not be square
// (otherwise Q = 0 and division by Q causes an error).
GWPrelim( N, m, {out} D, S, f);
if f > 1 then begin
result.Kind := rkPrelim;
result.Factor := f;
exit;
end;
// Not special, proceed to main algorithm
result.Kind := rkMain;
result.Mult := m;
result.Factor := 1;
queueCount := 0; // Clear queue
P := S;
Q := 1;
i := -1; // keep i same as in G & W; algo fails if i > B
sqrtD := SquFoF_utils.FSqrt( D);
// L := Trunc( 2.0*Sqrt( 2.0*sqrtD));
L := Trunc( Sqrt( 2.0*sqrtD)); // as in Section 5.2 of G&W paper
B := 2*L;
// Start forward cycle
endCycle := false;
while not endCycle do begin
// We update Q here, P at the end of the loop
Q := (D - P*P) div Q;
if (not Odd(i)) and SquFoF_utils.IsSquare( Q, r) then begin
// Q is square for even i.
// Possibly (?probably?) ends the forward cycle,
// but we need to inspect the queue first.
endCycle := true;
j := queueCount; // working backwards down the queue
if r = 1 then begin // the method may fail
while (j > 0) and (result.Kind <> rkFail) do begin
dec( j);
if queue[j].Left = 1 then result.Kind := rkFail;
end;
if result.Kind = rkFail then exit;
end
else begin // if r > 1
while (j > 0) and (endCycle) do begin
dec( j);
if (queue[j].Left = r)
and ((P - queue[j].Right) mod r = 0) then begin
// Deleting up to the *last* item in the list that
// satisfies the condition, Should it be the *first* ?
// Delete queue items 0..j inclusive
inc(j); k := 0;
while j < queueCount do begin
queue[k] := queue[j];
inc(j); inc(k);
end;
queueCount := k;
endCycle := false;
end; // if
end;
end;
end; // if i even and Q square
if not endCycle then begin
g := Q div SquFoF_utils.GCD( Q, 2*m);
if g <= L then begin
if queueCount < QUEUE_CAPACITY then begin
with queue[queueCount] do begin
Left := g; Right := P mod g;
end;
inc( queueCount);
end
else begin // queue overflow, fail
result.Kind := rkFail;
exit;
end;
end;
inc(i);
if i > B then begin
result.Kind := rkFail;
exit;
end;
end;
P := S - ((S + P) mod Q);
end; // while not endCycle
Assert( (D - P*P) mod r = 0); // optional check
P := S - ((S + P) mod r);
Q := r;
// Start backward cycle
endCycle := false;
while not endCycle do begin
P_prev := P;
Q := (D - P*P) div Q;
P := S - ((S + P) mod q);
endCycle := (P = P_prev);
end; // while not endCycle
// Finished
result.Factor := Q div SquFoF_utils.GCD( Q, 2*m);
end;
const NR_RC_VALUES = 28;
RC_VALUES : array [0..NR_RC_VALUES - 1] of UInt64 =
( 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);
type TMultAndMaxN = record
Mult : word; // small multiplier
MaxN : UInt64; // maximum N for that multiplier (N*multiplier < 2^64)
end;
const NR_MULTIPLIERS = 16;
const MULTIPLIERS : array [0..NR_MULTIPLIERS - 1] of TMultAndMaxN =
((Mult: 1; MaxN: 18446744073709551615),
(Mult: 3; MaxN: 6148914691236517205),
(Mult: 5; MaxN: 3689348814741910323),
(Mult: 7; MaxN: 2635249153387078802),
(Mult: 11; MaxN: 1676976733973595601),
(Mult: 15; MaxN: 1229782938247303441),
(Mult: 21; MaxN: 878416384462359600),
(Mult: 33; MaxN: 558992244657865200),
(Mult: 35; MaxN: 527049830677415760),
(Mult: 55; MaxN: 335395346794719120),
(Mult: 77; MaxN: 239568104853370800),
(Mult: 105; MaxN: 175683276892471920),
(Mult: 165; MaxN: 111798448931573040),
(Mult: 231; MaxN: 79856034951123600),
(Mult: 385; MaxN: 47913620970674160),
(Mult: 1155; MaxN: 15971206990224720));
function GowerWagstaff( N : UInt64) : TAlgoResult;
var
j : integer;
begin
j := 0;
result.Kind := rkFail;
while (result.Kind = rkFail)
and (j < NR_MULTIPLIERS)
and (N <= MULTIPLIERS[j].MaxN) do
begin
result := GW_with_multiplier( N, MULTIPLIERS[j].Mult);
if result.Kind = rkFail then inc(j);
end;
end;
// Main program
var
j : integer;
ar : TAlgoResult;
kindStr : string;
N, cofactor : UInt64;
begin
WriteLn( ' Number Mult M/P Factorization');
for j := 0 to NR_RC_VALUES - 1 do begin
N := RC_VALUES[j];
ar := GowerWagstaff( N);
if ar.Kind = rkFail then
WriteLn( N:20, ' No factor found')
else begin
case ar.Kind of
rkPrelim: kindStr := 'Prelim';
rkMain : kindStr := 'Main ';
end;
cofactor := N div ar.Factor;
Assert( cofactor * ar.Factor = N); // check that all has gone well
WriteLn( N:20, ar.Mult:5, ' ',
kindStr:6, ' ', ar.Factor, ' * ', cofactor);
end;
end;
end.
unit SquFoF_utils;
{$mode objfpc}{$H+}
interface
// Returns floating-point square root of 64-bit unsigned integer.
function FSqrt( x : UInt64) : double;
// Returns whether a 64-bit unsigned integer is a perfect square.
// In either case, returns floor(sqrt(x)) in the out parameter.
function IsSquare( x : UInt64; out iroot : UInt64) : boolean;
// Returns g.c.d. of 64-bit and 16-bit unsigned integer.
function GCD( u : UInt64; x : word) : word;
implementation
function FSqrt( x : UInt64) : double;
// Both Free Pascal and Delphi 7 seem unreliable when casting
// a 64-bit integer to floating point. We use a workaround.
type TSplitUint64 = packed record case boolean of
true: (All : UInt64);
false: (Lo, Hi : longword); // longword is 32-bit unsigned
end;
var
temp : TSplitUInt64;
begin
temp.All := x;
result := Sqrt( 1.0*temp.Lo + 4294967296.0*temp.Hi);
end;
// Based on Rosetta Code ISqrt, solution for Modula-2.
// Trunc of the f.p. square root won't do, bacause of rounding errors..
function IsSquare( x : UInt64; out iroot : UInt64) : boolean;
var
Xdiv4, q, r, s, z : UInt64;
begin
Xdiv4 := X shr 2;
q := 1;
while q <= Xdiv4 do q := q shl 2;
z := x;
r := 0;
repeat
s := q + r;
r := r shr 1;
if z >= s then begin
z := z - s;
r := r + q;
end;
q := q shr 2;
until q = 0;
iroot := r;
result := (z = 0);
end;
function GCD( u : UInt64; x : word) : word;
var
y, t : word;
begin
y := u mod x;
while y <> 0 do begin
t := x mod y;
x := y;
y := t;
end;
result := x;
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Number Mult M/P Factorization
2501 3 Main 61 * 41
12851 1 Main 71 * 181
13289 1 Main 97 * 137
75301 3 Main 293 * 257
120787 1 Main 43 * 2809
967009 7 Main 1609 * 601
997417 1 Main 257 * 3881
7091569 1 Prelim 2663 * 2663
13290059 1 Main 3119 * 4261
42854447 3 Main 4423 * 9689
223553581 1 Main 11213 * 19937
2027651281 1 Main 44021 * 46061
11111111111 3 Main 21649 * 513239
100895598169 11 Main 898423 * 112303
1002742628021 No factor found
60012462237239 1 Main 6862753 * 8744663
287129523414791 5 Main 6059887 * 47381993
9007199254740931 1 Main 10624181 * 847801751
11111111111111111 1 Main 2071723 * 5363222357
314159265358979323 1 Main 317213509 * 990371647
384307168202281507 1 Main 415718707 * 924440401
419244183493398773 1 Main 48009977 * 8732438749
658812288346769681 1 Main 62222119 * 10588072199
922337203685477563 1 Main 110075821 * 8379108103
1000000000000000127 1 Main 111756107 * 8948056861
1152921505680588799 3 Main 139001459 * 8294312261
1537228672809128917 3 Main 26675843 * 57626245319
4611686018427387877 1 Main 343242169 * 13435662733
</pre>
=={{header|Perl}}==
Line 2,253 ⟶ 2,810:
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>
=={{header|Sidef}}==
{{trans|Perl}}
<syntaxhighlight lang="ruby">const multipliers = divisors(3*5*7*11).grep { _ > 1 }
func sff(N) {
N.is_prime && return 1 # n is prime
N.is_square && return N.isqrt # n is square
multipliers.each {|k|
var P0 = isqrt(k*N) # P[0]=floor(sqrt(N)
var Q0 = 1 # Q[0]=1
var Q = (k*N - P0*P0) # Q[1]=N-P[0]^2 & Q[i]
var P1 = P0 # P[i-1] = P[0]
var Q1 = Q0 # Q[i-1] = Q[0]
var P = 0 # P[i]
var Qn = 0 # P[i+1]
var b = 0 # b[i]
while (!Q.is_square) { # until Q[i] is a perfect square
b = idiv(isqrt(k*N) + P1, Q) # floor(floor(sqrt(N+P[i-1])/Q[i])
P = (b*Q - P1) # P[i]=b*Q[i]-P[i-1]
Qn = (Q1 + b*(P1 - P)) # Q[i+1]=Q[i-1]+b(P[i-1]-P[i])
(Q1, Q, P1) = (Q, Qn, P)
}
b = idiv(isqrt(k*N) + P, Q) # b=floor((floor(sqrt(N)+P[i])/Q[0])
P1 = (b*Q0 - P) # P[i-1]=b*Q[0]-P[i]
Q = (k*N - P1*P1)/Q0 # Q[1]=(N-P[0]^2)/Q[0] & Q[i]
Q1 = Q0 # Q[i-1] = Q[0]
loop {
b = idiv(isqrt(k*N) + P1, Q) # b=floor(floor(sqrt(N)+P[i-1])/Q[i])
P = (b*Q - P1) # P[i]=b*Q[i]-P[i-1]
Qn = (Q1 + b*(P1 - P)) # Q[i+1]=Q[i-1]+b(P[i-1]-P[i])
break if (P == P1) # until P[i+1]=P[i]
(Q1, Q, P1) = (Q, Qn, P)
}
with (gcd(N,P)) {|g|
return g if g.is_ntf(N)
}
}
return 0
}
[ 11111, 2501, 12851, 13289, 75301, 120787, 967009, 997417, 4558849, 7091569, 13290059,
42854447, 223553581, 2027651281, 11111111111, 100895598169, 1002742628021, 60012462237239,
287129523414791, 11111111111111111, 384307168202281507, 1000000000000000127, 9007199254740931,
922337203685477563, 314159265358979323, 1152921505680588799, 658812288346769681,
419244183493398773, 1537228672809128917
].each {|n|
var v = sff(n)
if (v == 0) { say "The number #{n} is not factored." }
elsif (v == 1) { say "The number #{n} is a prime." }
else { say "#{n} = #{[n/v, v].sort.join(' * ')}" }
}</syntaxhighlight>
{{out}}
<pre>
11111 = 41 * 271
2501 = 41 * 61
12851 = 71 * 181
13289 = 97 * 137
75301 = 257 * 293
120787 = 43 * 2809
967009 = 601 * 1609
997417 = 257 * 3881
4558849 = 383 * 11903
7091569 = 2663 * 2663
13290059 = 3119 * 4261
42854447 = 4423 * 9689
223553581 = 11213 * 19937
2027651281 = 44021 * 46061
11111111111 = 21649 * 513239
100895598169 = 112303 * 898423
The number 1002742628021 is a prime.
60012462237239 = 6862753 * 8744663
287129523414791 = 6059887 * 47381993
^C
</pre>
Line 2,266 ⟶ 2,906:
Even so, there are two examples which fail (1000000000000000127 and 1537228672809128917) because the code is unable to process enough 'multipliers' before an overflow situation is encountered. To deal with this, the program automatically switches to BigInt to process such cases.
<syntaxhighlight lang="
import "./big" for BigInt
import "./fmt" for Fmt
var multipliers = [
| |||