Square form factorization: Difference between revisions

Line 942:

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~~ = [

var 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

]

var squfof = Fn.new { |N|

var s = N.~~isqrt~~

var s = ULong.new((N.toNum.sqrt + 0.5).floor)

if (s*s == N) return s

for (k in ~~0...multiplier.count~~) {

for (multiplier in multipliers) {

var T = ULong

var n = N

if (n > T.largest/multiplier~~[k]~~) {

if (n > ULong.largest/multiplier) {

T = BigInt

n = BigInt.new(n.toString)

}

var D = n * multiplier~~[k]~~

var D = n * multiplier

var P = D.isqrt

var Pprev = P

Line 968:

Line 966:

var Qprev = T.one

var Q = D - Po*Po

var L = ((s * 2).isqrt * 2).toSmall

var L = (s * 8).isqrt.toSmall

var B = 3 * L

var i = 2

Line 979:

Line 977:

q = Q

Q = Qprev + b * (Pprev - P)

r = Q.~~isqrt~~

r = T.new((Q.toNum.sqrt + 0.5).floor)

if ((i & 1) == 0 && r*r == Q) break

Qprev = q