Square form factorization: Difference between revisions
Content deleted Content added
Added Wren |
|||
Line 685: | Line 685: | ||
1537228672809128917 0 fail |
1537228672809128917 0 fail |
||
4611686018427387877 343242169 13435662733 |
4611686018427387877 343242169 13435662733 |
||
</pre> |
|||
=={{header|Wren}}== |
|||
{{libheader|Wren-long}} |
|||
{{libheader|Wren-big}} |
|||
{{libheader|Wren-fmt}} |
|||
This is based on the C code in the Wikipedia article and the FreeBASIC entry examples. |
|||
'0' is not actually an example here but is used by FreeBASIC to mark the end of the 'data' statement list so I've ignored that. |
|||
As Wren doesn't natively support unsigned 64-bit arithmetic, I've used the ULong class in the first above named for this task. |
|||
Even so, there are two examples which fail (1000000000000000127 and 1537228672809128917) because the code is unable to process enough 'multipliers' before an overflow situation is encountered. To deal with this, the program automatically switches to BigInt to process such cases. |
|||
This is still 6 times faster than processing the whole lot using BigInt. |
|||
<lang ecmascript>import "/long" for ULong |
|||
import "/big" for BigInt |
|||
import "/fmt" for Fmt |
|||
var 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 |
|||
] |
|||
var squfof = Fn.new { |N| |
|||
var s = N.isqrt |
|||
if (s*s == N) return s |
|||
for (k in 0...multiplier.count) { |
|||
var T = ULong |
|||
var n = N |
|||
if (n > T.largest/multiplier[k]) { |
|||
T = BigInt |
|||
n = BigInt.new(n.toString) |
|||
} |
|||
var D = n * multiplier[k] |
|||
var P = D.isqrt |
|||
var Pprev = P |
|||
var Po = Pprev |
|||
var Qprev = T.one |
|||
var Q = D - Po*Po |
|||
var L = ((s * 2).isqrt * 2).toSmall |
|||
var B = 3 * L |
|||
var i = 2 |
|||
var b = T.zero |
|||
var q = T.zero |
|||
var r = T.zero |
|||
while (i < B) { |
|||
b = (Po + P) / Q |
|||
P = b * Q - P |
|||
q = Q |
|||
Q = Qprev + b * (Pprev - P) |
|||
r = Q.isqrt |
|||
if ((i & 1) == 0 && r*r == Q) break |
|||
Qprev = q |
|||
Pprev = P |
|||
i = i + 1 |
|||
} |
|||
if (i < B) { |
|||
b = (Po - P) / r |
|||
Pprev = P = b*r + P |
|||
Qprev = r |
|||
Q = (D - Pprev*Pprev) / Qprev |
|||
i = 0 |
|||
while (true) { |
|||
b = (Po + P) / Q |
|||
Pprev = P |
|||
P = b * Q - P |
|||
q = Q |
|||
Q = Qprev + b * (Pprev - P) |
|||
Qprev = q |
|||
i = i + 1 |
|||
if (P == Pprev) break |
|||
} |
|||
r = T.gcd(n, Qprev) |
|||
if (r != T.one && r != n) return (r is ULong) ? r : ULong.new(r.toString) |
|||
} |
|||
} |
|||
return ULong.zero |
|||
} |
|||
var 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" |
|||
] |
|||
System.print("Integer Factor Quotient") |
|||
System.print("------------------------------------------") |
|||
for (example in examples) { |
|||
var N = ULong.new(example) |
|||
var fact = squfof.call(N) |
|||
var quot = (fact.isZero) ? "fail" : (N / fact).toString |
|||
Fmt.print("$-20s $-10s $s", N, fact, quot) |
|||
}</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 |
|||
1002742628021 0 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> |
</pre> |