Category talk:Wren-long: Difference between revisions
→Source code: Added modInv, improved isPrime.
(Made modMul, modPow more robust.) |
(→Source code: Added modInv, improved isPrime.) |
||
Line 417:
if (isbp != null) return isbp
if (this > ULong.largest/2) Fiber.abort("Cannot test %(this) for primality.")
var a
return ULong.millerRabinTest_(this, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])▼
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 ⟶ 761:
}
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 ⟶ 1,346:
// Returns the current instance multiplied by 'n' modulo 'mod'.
modMul(n, mod) { Long.sigma_(_sig * n.sign , _mag.modMul(n.abs, mod.abs)) }
// Returns the current instance to the power 'exp' modulo 'mod'.
Line 1,304 ⟶ 1,352:
if (!(exp is Long)) exp = Long.new(exp)
if (!(mod is Long)) mod = Long.new(mod)
var mag = _mag.modPow(exp.abs, mod.abs)
var sign
if (mag == ULong.zero) {
Line 1,315 ⟶ 1,363:
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.
| |||