Category talk:Wren-long: Difference between revisions
Content added Content deleted
(Made modMul, modPow more robust.) |
(→Source code: Added modInv, improved isPrime.) |
||
Line 417: | Line 417: | ||
if (isbp != null) return isbp |
if (isbp != null) return isbp |
||
if (this > ULong.largest/2) Fiber.abort("Cannot test %(this) for primality.") |
if (this > ULong.largest/2) Fiber.abort("Cannot test %(this) for primality.") |
||
var a |
|||
⚫ | |||
if (this < 2047) { |
|||
a = [2] |
|||
} else if (this < 1373653) { |
|||
a = [2, 3] |
|||
} else if (this < 9080191) { |
|||
a = [31, 73] |
|||
} else if (this < 25326001) { |
|||
a = [2, 3, 5] |
|||
} else if (this < 3215031751) { |
|||
a = [2, 3, 5, 7] |
|||
} else if (this < 4759123141) { |
|||
a = [2, 7, 61] |
|||
} else if (this < 1122004669633) { |
|||
a = [2, 13, 23, 1662803] |
|||
} else if (this < 2152302898747) { |
|||
a = [2, 3, 5, 7, 11] |
|||
} else if (this < 3474749660383) { |
|||
a = [2, 3, 5, 7, 11, 13] |
|||
} else if (this < 341550071728321) { |
|||
a = [2, 3, 5, 7, 11, 13, 17] |
|||
} else if (this < ULong.new("3825123056546413051")) { |
|||
a = [2, 3, 5, 7, 11, 13, 17, 19, 23] |
|||
} else { |
|||
⚫ | |||
} |
|||
return ULong.millerRabinTest_(this, a) |
|||
} |
} |
||
Line 735: | Line 761: | ||
} |
} |
||
return r |
return r |
||
} |
|||
// Returns the multiplicative inverse of 'this' modulo 'n'. |
|||
// 'this' and 'n' must be coprme. |
|||
modInv(n) { |
|||
if (!(n is ULong)) n = ULong.new(n) |
|||
var r = n.copy() |
|||
var newR = this.copy() |
|||
var t = ULong.zero |
|||
var newT = ULong.one |
|||
while (!newR.isZero) { |
|||
var q = r / newR |
|||
var lastT = t.copy() |
|||
var lastR = r.copy() |
|||
t = newT |
|||
r = newR |
|||
newT = lastT - q * newT |
|||
newR = lastR - q * newR |
|||
} |
|||
if (!r.isOne) Fiber.abort("%(this) and %(n) are not co-prime.") |
|||
if (t < 0) t = t + n |
|||
return t |
|||
} |
} |
||
Line 1,298: | Line 1,346: | ||
// Returns the current instance multiplied by 'n' modulo 'mod'. |
// Returns the current instance multiplied by 'n' modulo 'mod'. |
||
modMul(n, mod) { Long.sigma_(_sig * n.sign , _mag.modMul(n.abs, mod.abs)) } |
modMul(n, mod) { Long.sigma_(_sig * n.sign , _mag.modMul(n.abs, mod.abs)) } |
||
// Returns the current instance to the power 'exp' modulo 'mod'. |
// Returns the current instance to the power 'exp' modulo 'mod'. |
||
Line 1,304: | Line 1,352: | ||
if (!(exp is Long)) exp = Long.new(exp) |
if (!(exp is Long)) exp = Long.new(exp) |
||
if (!(mod is Long)) mod = Long.new(mod) |
if (!(mod is Long)) mod = Long.new(mod) |
||
var mag = _mag.modPow(exp, mod) |
var mag = _mag.modPow(exp.abs, mod.abs) |
||
var sign |
var sign |
||
if (mag == ULong.zero) { |
if (mag == ULong.zero) { |
||
Line 1,315: | Line 1,363: | ||
return Long.sigma_(sign, mag) |
return Long.sigma_(sign, mag) |
||
} |
} |
||
// Returns the multiplicative inverse of 'this' modulo 'n'. |
|||
// 'this' and 'n' must be co-prime. |
|||
modInv(n) { Long.sigma_(_sig, _mag.modInv(n.abs)) } |
|||
// Increments the current instance by one. |
// Increments the current instance by one. |