Category talk:Wren-big: Difference between revisions
m
→Source code: Removed some surplus whitespace.
m (→Source code: Changed a program comment.) |
m (→Source code: Removed some surplus whitespace.) |
||
Line 1,036:
}
// Returns the integer n'th root of the current instance
// i.e. the precise n'th root truncated towards zero if not an integer.
// Throws an error if the current instance is negative and n is even.
Line 1,065:
// Returns the cube root of the current instance i.e. the largest integer 'r' such that
// r.cube <= this.
icbrt {
if (isSmall) return BigInt.small_(toSmall.cbrt.floor)
return iroot(3)
}
Line 1,333:
/* Prime factorization methods. */
// Private worker method for Pollard's Rho algorithm.
static pollardRho_(m, seed, c) {
Line 1,358:
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.
Line 1,365:
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]) {
Line 1,372:
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) {
Line 1,382:
var factors = []
var k = BigInt.new(37)
var i = 0
while (k * k <= n) {
if (n.isDivisibleBy(k)) {
Line 1,395:
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()]
Line 1,418:
break
}
if (n >= threshold) {
var d = pollardRho_(n, seed, c)
if (d != BigInt.zero) {
Line 1,435:
checkPrime = false
}
} else if (c < 101) {
c = c + 1
Line 1,443 ⟶ 1,442:
factors.addAll(primeFactorsWheel_(n))
break
}
} else {
factors.addAll(primeFactorsWheel_(n))
Line 1,452 ⟶ 1,451:
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 []
| |||