Anonymous user
Square form factorization: Difference between revisions
trimmed FreeBasic
(→{{header|Raku}}: Additional solution) |
(trimmed FreeBasic) |
||
Line 205:
//reduce indefinite form
#define rho(a, b, c) {
q = (rN + b) / a;
b = q * a - b;
c += q * (t - b); }
//initialize
#define rhoin(a, b, c) {
rho(a, b, c) h = b;
c = (mN - h * h) / a; }
#define gcd(a, b) while (b) {
t = a % b; a = b; b = t; }
Line 234:
while (m[k]) {
if (k &&
//check overflow m * N
if (N > MxN / m[k]) break;
Line 386:
declare sub rho ()
'reduce indefinite form
declare function
'return -1 if c is square, set r:= sqrt(c)
declare sub qform (byref g as string, byval t as integer)
Line 412:
'signal to end all threads
dim shared as
'quadratic residue tables
Line 433:
#endmacro
function bqf.
issqr = 0▼
▲ if q63(c mod 63) andalso q55(c mod 55) then
▲ '>98% non-squares filtered
▲ r = culng(sqr(c))
▲ if r * r = c then return -1
end if▼
end if
end function
Line 552 ⟶ 550:
P.rho
if (i and 1) = 0 andalso P.issq(r) then
if
▲ 'square form found
A.b =-P.b: A.c = r
A.qform("A", j)
'
▲ A.qform("A", j)
'
red(f, A.
end
loop until
▲ if f = 1 then exit do
end if ' proper
end if▼
▲ end if ' square form
▲ end if ' even indices
if flag then exit for
Line 601 ⟶ 596:
data 7091569
data 13290059
data 23515517
data 42854447
data 223553581
Line 635 ⟶ 631:
'tabulate quadratic residues
for t = 0 to
s = t * t
next t
Line 663 ⟶ 658:
flag = 0
for t = 1 to tx + 1 step 2
h(t) = threadcreate(@squfof, @a(t))
▲ end if
▲ squfof(@a(0))
threadwait(h(t))▼
if f = 1 then f = a(t).f
if f > 1 then exit for
▲ f = a(0).f
▲ threadwait(h(t))
▲ if f = 1 then f = a(t).f
next t
Line 716 ⟶ 715:
N = 13290059
f = 3119 N/f = 4261
N = 23515517
f = 53 N/f = 443689
N = 42854447
Line 774 ⟶ 776:
f = 343242169 N/f = 13435662733
total time: 0.
</pre>
| |||