Anonymous user
Square form factorization: Difference between revisions
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
▲'queue size
type arg
Line 384:
type bqf
declare sub rho (
'reduce indefinite form
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 ulong rN, a, b, c
as integer vb
Line 402 ⟶ 401:
'return -1 if a proper square form is found
as
as
end type
Line 412 ⟶ 411:
dim shared flag as integer
'signal to end all threads
'quadratic residue tables
'------------------------------------------------
sub bqf.rho (
dim as ulong q, t
swap a, c
'residue
q = (rN + b) \ a
t = b: b = q * a - b
'pseudo-square
if sw then▼
c += q * (t
c += q * (t - b)▼
'initialize▼
c = (mN - culngint(b) * b) \ a▼
end sub
#macro rhoin(F)
F.rho : h = F.b
#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▼
for i = 0 to 31▼
q64(r and 63) =-1▼
q63(r mod 63) =-1▼
q55(r mod 55) =-1▼
next i▼
issqr = 0
if q64(c and 63) then
if q63(c mod 63) andalso q55(c mod 55) then
r =
if r * r =
end if
end if
Line 457 ⟶ 445:
sub bqf.qform (byref g as string, byval t as integer)
dim as longint
if t and 1 then
w = -w
Line 484 ⟶ 465:
sub queue.enq (byref P as bqf)
dim s as ulong
red(s, P.c)
if s < L then
'enqueue P.b, P.c
a(
a(
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
rp->f = 1
'multiplier
Line 539 ⟶ 520:
'check overflow m * N
if
h *= m▼
end if
▲r = int(sqr(h))
'float64 fix
if culngint(r) * r >
P.rN = r
A.rN = r
Line 556 ⟶ 535:
if P.vb then print "r = "; r
Q.
'Queue entry bounds
Q.L = int(sqr(r * 2))
Line 563 ⟶ 542:
'principal form
P.b = r: P.c = 1
P.qform("P", 1)
Line 572 ⟶ 551:
if P.c < L2 then Q.enq(P)
P.rho
if (i and 1) = 0 then
Line 583 ⟶ 562:
'inverse square root
A.b =-P.b: A.c = r
A.qform("A", j)
Line 589 ⟶ 568:
'search ambiguous cycle
t = A.b
A.rho
if A.b = t then
Line 650 ⟶ 629:
dim a(4) as arg
dim as ulongint f
dim
width 64, 30
cls
a(0).vb = 0
|