Rosetta Code

Square form factorization: Difference between revisions

Page Discussion

Square form factorization (view source)

Revision as of 17:27, 25 March 2021

227 bytes removed ,  3 years ago
Simplified FreeBasic, circular queue
(added Raku programming solution)
(Simplified FreeBasic, circular queue)
Line 369:
'tested : FreeBasic 1.07.1
 
 
const qx = 50▼
'queue size▼
 
'------------------------------------------------
const MxN = culngint(1) shl 62
'input maximum
 
▲const qx = 50(1 shl 5) - 1
▲'queue size
 
type arg
Line 384:
 
type bqf
declare sub rho (byval sw as integer)
'reduce indefinite form, set sw = 0 to initialize
declare function issqr (byref r as ulong) as integer
'return -1 if c is square, set r:= sqrt(c)
Line 391:
'print binary quadratic form #t (a, 2b, c)
 
as ulongint mN
as ulong rN, a, b, c
as integer vb
Line 402 ⟶ 401:
'return -1 if a proper square form is found
 
as integerulong ta(qx), L, m
as ulonginteger a(qx + 1), Lk, mt
end type
 
Line 412 ⟶ 411:
dim shared flag as integer
'signal to end all threads
 
staticdim shared as integer q64(63), q63(62), q55(54), sw = 0▼
'quadratic residue tables
 
 
'------------------------------------------------
sub bqf.rho (byval sw as integer)
dim as ulong q, t = b
swap a, c
'residue
q = (rN + b) \ a
t = b: b = q * a - b
'pseudo-square
if sw then▼
c += q * (t 'pseudo-square b)
c += q * (t - b)▼
else
'initialize▼
c = (mN - culngint(b) * b) \ a▼
end if
end sub
 
▲ 'initialize form
#macro rhoin(F)
F.rho : h = F.b
▲ F.c = (mN - culngint(b)h * bh) \ F.a
#endmacro
 
function bqf.issqr (byref r as ulong) as integer
▲static as integer q64(63), q63(62), q55(54), sw = 0
if sw = 0 then▼
sw = -1▼
'tabulate quadratic residues▼
dim i as ulong
for i = 0 to 31▼
r = i * i
q64(r and 63) =-1▼
q63(r mod 63) =-1▼
q55(r mod 55) =-1▼
next i▼
end if
issqr = 0
 
if q64(c and 63) then
if q63(c mod 63) andalso q55(c mod 55) then
if'>98% q55(cnon-squares mod 55) thenfiltered
r = '>98% non-squares filteredculng(sqr(c))
if r * r = culng(sqr(c)) then return -1
if c = r * r then return -1
end if
end if
end if
Line 457 ⟶ 445:
 
sub bqf.qform (byref g as string, byval t as integer)
▲if swvb = 0 then exit sub
dim as longint d, u = a, v = b, w = c
dim as longint ifu vb= a, v = 0b, thenw exit= subc
 
'{D/4 = mN}
d = v * v + u * w
if mN - d then
print "fail:"; d: exit sub
end if
 
if t and 1 then
w = -w
Line 484 ⟶ 465:
 
sub queue.enq (byref P as bqf)
if t = qx then exit sub
dim s as ulong
red(s, P.c)
if s < L then
t'circular += 2queue
▲ ck += q * (tk -+ b2) and qx
▲ if swk > t then t = k
'enqueue P.b, P.c
a(tk) = P.b mod s
a(tk + 1) = s
end if
end sub
Line 511 ⟶ 493:
dim as ulong L2, m, r, t, f = 1
dim as integer ix, i, j
dim as ulongint mN, h
'principal and ambiguous cycles
dim as bqf P, A
Line 528 ⟶ 510:
end if
 
h = N
rp->f = 1
'multiplier
Line 539 ⟶ 520:
 
'check overflow m * N
if hN > (MxN \ m) then exit sub
h *= m▼
end if
▲mN = hN *= m
 
r = int(sqr(hmN))▼
P.mN = h
A.mN = h
▲r = int(sqr(h))
'float64 fix
if culngint(r) * r > hmN then r -= 1
P.rN = r
A.rN = r
Line 556 ⟶ 535:
if P.vb then print "r = "; r
 
Q.tk = -2: Q.t = -1: Q.m = m
'Queue entry bounds
Q.L = int(sqr(r * 2))
Line 563 ⟶ 542:
'principal form
P.b = r: P.c = 1
P.rhorhoin(0P)
P.qform("P", 1)
 
Line 572 ⟶ 551:
if P.c < L2 then Q.enq(P)
 
P.rho(1)
if (i and 1) = 0 then
 
Line 583 ⟶ 562:
'inverse square root
A.b =-P.b: A.c = r
A.rhorhoin(0A): j = 1
A.qform("A", j)
 
Line 589 ⟶ 568:
'search ambiguous cycle
t = A.b
A.rho(1): j += 1
 
if A.b = t then
Line 650 ⟶ 629:
dim a(4) as arg
dim as ulongint f
dim t as integer s, t
 
width 64, 30
cls
 
▲ 'tabulate quadratic residues
▲ for it = 0 to 31
▲ sws = -1t * t
▲ q64(rs and 63) =-1
▲ q63(rs mod 63) =-1
▲ q55(rs mod 55) =-1
▲ next it
 
a(0).vb = 0
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/309048"