Category talk:Wren-big: Difference between revisions
→Source code: Added prime factorization plus 3 other utility methods.
(→Source code: Added BigInt.factorial method.) |
(→Source code: Added prime factorization plus 3 other utility methods.) |
||
Line 1,019:
}
return BigInt.big_(BigInt.square_(_value), false)
}
// Cube the current instance.
cube { square * this }
// Returns true if the current instance is a perfect square, false otherwise.
isSquare {
var root = isqrt
return root.square == this
}
// Returns true if the current instance is a perfect cube, false otherwise.
isCube {
var root = icbrt
return root.square * root == this
}
Line 1,314 ⟶ 1,329:
var sign = _signed ? "-" : ""
return sign + str
}
/* Prime factorization methods. */
// Private worker method for Pollard's Rho algorithm.
static pollardRho_(m, seed, c) {
var g = Fn.new { |x| (x*x + c) % m }
var x = BigInt.two
var y = BigInt.new(seed)
var z = BigInt.one
var d = BigInt.one
var count = 0
while (true) {
x = g.call(x)
y = g.call(g.call(y))
d = (x - y).abs % m
z = z * d
count = count + 1
if (count == 100) {
d = BigInt.gcd(z, m)
if (d != BigInt.one) break
z = BigInt.one
count = 0
}
}
if (d == m) return BigInt.zero
return d
}
// Returns a factor (BigInt) of 'm' (a BigInt or an integral Num) using the
// Pollard's Rho algorithm. Both the 'seed' and 'c' can be set to integers.
// Returns BigInt.zero in the event of failure.
static pollardRho(m, seed, c) {
if (m < 2) return BigInt.zero
if (m is Num) m = BigInt.new(m)
if (m.isProbablePrime(10)) return m.copy()
if (m.isSquare) return m.isqrt
for (p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]) {
if (m.isDivisibleBy(p)) return BigInt.new(p)
}
return pollardRho_(m, seed, c)
}
// Convenience version of the above method which uses a seed of 2 and a value for c of 1.
static pollardRho(m) { pollardRho(m, 2, 1) }
// Private method for factorizing smaller numbers (BigInt) using a wheel with basis [2, 3, 5].
static primeFactorsWheel_(m) {
var n = m.copy()
var inc = [4, 2, 4, 2, 4, 6, 2, 6]
var factors = []
var k = BigInt.new(37)
var i = 0
while (k * k <= n) {
if (n.isDivisibleBy(k)) {
factors.add(k.copy())
n = n / k
} else {
k = k + inc[i]
i = (i + 1) % 8
}
}
if (n > BigInt.one) factors.add(n)
return factors
}
// Private worker method (recursive) to obtain the prime factors of a number (BigInt).
static primeFactors_(m, trialDivs) {
if (m.isProbablePrime(10)) return [m.copy()]
var n = m.copy()
var factors = []
var seed = 2
var c = 1
var checkPrime = true
var threshold = 1e11 // from which using PR may be advantageous
if (trialDivs) {
for (p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]) {
while (n.isDivisibleBy(p)) {
factors.add(BigInt.new(p))
n = n / p
}
}
}
while (n > BigInt.one) {
if (checkPrime && n.isProbablePrime(10)) {
factors.add(n)
break
}
if (n >= threshold) {
var d = pollardRho_(n, seed, c)
if (d != BigInt.zero) {
factors.addAll(primeFactors_(d, false))
n = n / d
checkPrime = true
} else if (c == 1) {
if (n.isSquare) {
n = n.isqrt
var pf = primeFactors_(n, false)
factors.addAll(pf)
factors.addAll(pf)
break
} else {
c = 2
checkPrime = false
}
} else if (c < 101) {
c = c + 1
} else if (seed < 101) {
seed = seed + 1
} else {
factors.addAll(primeFactorsWheel_(n))
break
}
} else {
factors.addAll(primeFactorsWheel_(n))
break
}
}
factors.sort()
return factors
}
// Returns a list of the primes factors (BigInt) of 'm' (a Bigint or an integral Num)
// using the wheel based factorization and/or Pollard's Rho algorithm as appropriate.
static primeFactors(m) {
if (m < 2) return []
if (m is Num) m = BigInt.new(m)
return primeFactors_(m, true)
}
}
| |||