Square form factorization
A just for fun snail ..
References: Algorithm, C program example from the WP page and also the pseudocode from here.
# 20210325 Raku programming solution
my @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 );
sub circumfix:<⌊ ⌋>{ $^n.floor }; sub prefix:<√>{ $^n.sqrt }; # just for fun
sub SQUFOF ( \𝑁 ) {
return 1 if 𝑁.is-prime; # if n is prime return 1
return √𝑁 if √𝑁 == Int(√𝑁); # if n is a perfect square return √𝑁
for @multiplier -> \𝑘 {
my \Pₒ = $ = ⌊ √(𝑘*𝑁) ⌋; # P[0]=floor(√N)
my \Qₒ = $ = 1 ; # Q[0]=1
my \Q = $ = 𝑘*𝑁 - Pₒ²; # Q[1]=N-P[0]^2 & Q[i]
my \Pₚᵣₑᵥ = $ = Pₒ; # P[i-1] = P[0]
my \Qₚᵣₑᵥ = $ = Qₒ; # Q[i-1] = Q[0]
my \P = $ = 0; # P[i]
my \Qₙₑₓₜ = $ = 0; # P[i+1]
my \b = $ = 0; # b[i]
# i = 1
repeat until √Q == Int(√Q) { # until Q[i] is a perfect square
b = ⌊⌊ √(𝑘*𝑁) + Pₚᵣₑᵥ ⌋ / Q ⌋; # floor(floor(√N+P[i-1])/Q[i])
P = b*Q - Pₚᵣₑᵥ; # P[i]=b*Q[i]-P[i-1]
Qₙₑₓₜ = Qₚᵣₑᵥ + b*(Pₚᵣₑᵥ - P); # Q[i+1]=Q[i-1]+b(P[i-1]-P[i])
( Qₚᵣₑᵥ, Q, Pₚᵣₑᵥ ) = Q, Qₙₑₓₜ, P; # i++
}
b = ⌊ ⌊ √(𝑘*𝑁)+P ⌋ / Q ⌋; # b=floor((floor(√N)+P[i])/Q[0])
Pₚᵣₑᵥ = b*Qₒ - P; # P[i-1]=b*Q[0]-P[i]
Q = ( 𝑘*𝑁 - Pₚᵣₑᵥ² )/Qₒ; # Q[1]=(N-P[0]^2)/Q[0] & Q[i]
Qₚᵣₑᵥ = Qₒ; # Q[i-1] = Q[0]
# i = 1
loop { # repeat
b = ⌊ ⌊ √(𝑘*𝑁)+Pₚᵣₑᵥ ⌋ / Q ⌋; # b=floor(floor(√N)+P[i-1])/Q[i])
P = b*Q - Pₚᵣₑᵥ; # P[i]=b*Q[i]-P[i-1]
Qₙₑₓₜ = Qₚᵣₑᵥ + b*(Pₚᵣₑᵥ - P); # Q[i+1]=Q[i-1]+b(P[i-1]-P[i])
last if (P == Pₚᵣₑᵥ); # until P[i+1]=P[i]
( Qₚᵣₑᵥ, Q, Pₚᵣₑᵥ ) = Q, Qₙₑₓₜ, P; # i++
}
given 𝑁 gcd P { return $_ if $_ != 1|𝑁 }
} # gcd(N,P[i]) (if != 1 or N) is a factor of N, otherwise try next k
return 0 # give up
}
race for (
11111, # wikipedia.org/wiki/Shanks%27s_square_forms_factorization#Example
4558849, # example from talk page
# all of the rest are taken from the FreeBASIC entry
2501,12851,13289,75301,120787,967009,997417,7091569,13290059,
42854447,223553581,2027651281,11111111111,100895598169,1002742628021,
# time hoarders
60012462237239, # = 6862753 * 8744663 15s
287129523414791, # = 6059887 * 47381993 80s
11111111111111111, # = 2071723 * 5363222357 2m
384307168202281507, # = 415718707 * 924440401 5m
1000000000000000127, # = 111756107 * 8948056861 12m
9007199254740931, # = 10624181 * 847801751 17m
922337203685477563, # = 110075821 * 8379108103 41m
314159265358979323, # = 317213509 * 990371647 61m
1152921505680588799, # = 139001459 * 8294312261 93m
658812288346769681, # = 62222119 * 10588072199 112m
419244183493398773, # = 48009977 * 8732438749 135m
1537228672809128917, # = 26675843 * 57626245319 254m
# don't know how to handle this one
# for 1e-323, 1e-324 { my $*TOLERANCE = $_ ;
# say 4611686018427387877.sqrt ≅ 4611686018427387877.sqrt.Int }
# skip the perfect square check and start k with 3 to get the following
# 4611686018427387877, # = 343242169 * 13435662733 217m
) -> \data {
given data.&SQUFOF {
when 0 { say "The number ", data, " is not factored." }
when 1 { say "The number ", data, " is a prime." }
default { say data, " = ", $_, " * ", data div $_.Int }
}
}Output:
11111 = 41 * 271
4558849 = 383 * 11903
2501 = 61 * 41
12851 = 71 * 181
13289 = 97 * 137
75301 = 293 * 257
120787 = 43 * 2809
967009 = 601 * 1609
997417 = 257 * 3881
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
11111111111111111 = 2071723 * 5363222357
384307168202281507 = 415718707 * 924440401
1000000000000000127 = 111756107 * 8948056861
9007199254740931 = 10624181 * 847801751
922337203685477563 = 110075821 * 8379108103
314159265358979323 = 317213509 * 990371647
1152921505680588799 = 139001459 * 8294312261
658812288346769681 = 62222119 * 10588072199
419244183493398773 = 48009977 * 8732438749
1537228672809128917 = 26675843 * 57626245319 Use NativeCall
Use idea similar to the second approach from here, by compiling the C (Classical heuristic) entry to a shared library and then make use of the squfof routine.
squfof.raku
# 20210326 Raku programming solution
use NativeCall;
constant LIBSQUFOF = '/home/user/LibSQUFOF.so';
sub squfof(uint64 $n) returns uint64 is native(LIBSQUFOF) { * };
race for (
11111, # wikipedia.org/wiki/Shanks%27s_square_forms_factorization#Example
4558849, # example from talk page
# all of the rest are taken from the FreeBASIC entry
2501,12851,13289,75301,120787,967009,997417,7091569,13290059,
42854447,223553581,2027651281,11111111111,100895598169,1002742628021,
60012462237239, # = 6862753 * 8744663
287129523414791, # = 6059887 * 47381993
11111111111111111, # = 2071723 * 5363222357
384307168202281507, # = 415718707 * 924440401
1000000000000000127, # = 111756107 * 8948056861
9007199254740931, # = 10624181 * 847801751
922337203685477563, # = 110075821 * 8379108103
314159265358979323, # = 317213509 * 990371647
1152921505680588799, # = 139001459 * 8294312261
658812288346769681, # = 62222119 * 10588072199
419244183493398773, # = 48009977 * 8732438749
1537228672809128917, # = 26675843 * 57626245319
4611686018427387877, # = 343242169 * 13435662733
) -> \data {
given squfof(data) { say data, " = ", $_, " * ", data div $_ }
}Output:
gcc -Wall -fPIC -shared -o LibSQUFOF.so squfof.c
<p>file LibSQUFOF.so
LibSQUFOF.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=f7f9864e5508ba1de80cbc6e2f4d789f4ec448e9, not stripped
raku -c squfof.raku && time ./squfof.raku
Syntax OK
11111 = 41 * 271
4558849 = 383 * 11903
2501 = 61 * 41
12851 = 71 * 181
13289 = 97 * 137
75301 = 293 * 257
120787 = 43 * 2809
967009 = 1609 * 601
997417 = 257 * 3881
7091569 = 2663 * 2663
13290059 = 3119 * 4261
42854447 = 4423 * 9689
223553581 = 11213 * 19937
2027651281 = 44021 * 46061
11111111111 = 21649 * 513239
100895598169 = 112303 * 898423
1002742628021 = 1 * 1002742628021
60012462237239 = 6862753 * 8744663
287129523414791 = 6059887 * 47381993
11111111111111111 = 2071723 * 5363222357
384307168202281507 = 415718707 * 924440401
1000000000000000127 = 111756107 * 8948056861
9007199254740931 = 10624181 * 847801751
922337203685477563 = 110075821 * 8379108103
314159265358979323 = 317213509 * 990371647
1152921505680588799 = 139001459 * 8294312261
658812288346769681 = 62222119 * 10588072199
419244183493398773 = 48009977 * 8732438749
1537228672809128917 = 26675843 * 57626245319
4611686018427387877 = 343242169 * 13435662733
</p><p>real 0m0.784s
user 0m0.716s
sys 0m0.056s
</p>Last updated