Square form factorization: Difference between revisions
→{{header|jq}}
Thundergnat (talk | contribs) m (Thundergnat moved page Square Form Factorization to Square form factorization: Standardize capitalization) |
|||
Line 943:
1537228672809128917 0 fail
4611686018427387877 343242169 13435662733
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with gojq, the Go implementation of jq'''
gojq has support for unbounded-precision
integer arithmetic and accordingly the output shown below is from a run thereof;
the C implementation of jq produces correct results up to and including
[287129523414791,6059887,47381993].
'''Preliminaries'''
<lang jq>def gcd(a; b):
# subfunction expects [a,b] as input
# i.e. a ~ .[0] and b ~ .[1]
def rgcd: if .[1] == 0 then .[0]
else [.[1], .[0] % .[1]] | rgcd
end;
[a,b] | rgcd;
# for infinite precision integer-arithmetic
def idivide($p; $q): ($p - ($p % $q)) / $q ;
def idivide($q): (. - (. % $q)) / $q ;
def isqrt:
def irt:
. as $x
| 1 | until(. > $x; . * 4) as $q
| {$q, $x, r: 0}
| until( .q <= 1;
.q |= idivide(4)
| .t = .x - .r - .q
| .r |= idivide(2)
| if .t >= 0
then .x = .t
| .r += .q
else .
end)
| .r ;
if type == "number" and (isinfinite|not) and (isnan|not) and . >= 0
then irt
else "isqrt requires a non-negative integer for accuracy" | error
end ;</lang>
'''The Tasks'''
<lang jq>def 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
];
# input should be a number
def squfof:
def toi : floor | tostring | tonumber;
. as $N
| (($N|sqrt + 0.5)|toi) as $s
| if ($s*$s == $N) then $s
else label $out
| {}
| multipliers[] as $multiplier
| ($N * $multiplier) as $D
| .P = ($D|isqrt)
| .Pprev = .P
| .Pprev as $Po
| .Qprev = 1
| .Q = $D - $Po*$Po
| (($s * 8)|isqrt) as $L
| (3 * $L) as $B
| .i = 2
| .b = 0
| .q = 0
| .r = 0
| .stop = false
| until( (.i >= $B) or .stop;
.b = idivide($Po + .P; .Q)
| .P = .b * .Q - .P
| .q = .Q
| .Q = .Qprev + .b * (.Pprev - .P)
| .r = (((.Q|isqrt) + 0.5)|toi)
| if ((.i % 2) == 0 and (.r*.r) == .Q) then .stop = true
else
.Qprev = .q
| .Pprev = .P
| .i += 1
end )
| if .i < $B
then
.b = idivide($Po - .P; .r)
| .P = .b*.r + .P
| .Pprev = .P
| .Qprev = .r
| .Q = idivide($D - .Pprev*.Pprev; .Qprev)
| .i = 0
| .stop = false
| until (.stop;
.b = idivide($Po + .P; .Q)
| .Pprev = .P
| .P = .b * .Q - .P
| .q = .Q
| .Q = .Qprev + .b * (.Pprev - .P)
| .Qprev = .q
| .i += 1
| if (.P == .Pprev) then .stop = true else . end )
| .r = gcd($N; .Qprev)
| if .r != 1 and .r != $N then .r, break $out else empty end
else empty
end
end
// 0 ;
def 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"
];
"[Integer, Factor, Quotient]"
"---------------------------",
(examples[] as $example
| ($example|tonumber) as $N
| ($N | squfof) as $fact
| if $fact == 0 then "fail"
else idivide($N; $fact) as $quot
| [$N, $fact, $quot]
end
)</lang>
{{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]
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>
| |||