Category talk:Wren-big: Difference between revisions

Content added Content deleted
m (→‎Source code: Changed a program comment.)
m (→‎Source code: Removed some surplus whitespace.)
Line 1,036: Line 1,036:
}
}


// Returns the integer n'th root of the current instance
// Returns the integer n'th root of the current instance
// i.e. the precise n'th root truncated towards zero if not an integer.
// 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.
// Throws an error if the current instance is negative and n is even.
Line 1,065: Line 1,065:
// Returns the cube root of the current instance i.e. the largest integer 'r' such that
// Returns the cube root of the current instance i.e. the largest integer 'r' such that
// r.cube <= this.
// r.cube <= this.
icbrt {
icbrt {
if (isSmall) return BigInt.small_(toSmall.cbrt.floor)
if (isSmall) return BigInt.small_(toSmall.cbrt.floor)
return iroot(3)
return iroot(3)
}
}


Line 1,333: Line 1,333:


/* Prime factorization methods. */
/* Prime factorization methods. */

// Private worker method for Pollard's Rho algorithm.
// Private worker method for Pollard's Rho algorithm.
static pollardRho_(m, seed, c) {
static pollardRho_(m, seed, c) {
Line 1,358: Line 1,358:
return d
return d
}
}

// Returns a factor (BigInt) of 'm' (a BigInt or an integral Num) using the
// 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.
// Pollard's Rho algorithm. Both the 'seed' and 'c' can be set to integers.
Line 1,365: Line 1,365:
if (m < 2) return BigInt.zero
if (m < 2) return BigInt.zero
if (m is Num) m = BigInt.new(m)
if (m is Num) m = BigInt.new(m)
if (m.isProbablePrime(10)) return m.copy()
if (m.isProbablePrime(10)) return m.copy()
if (m.isSquare) return m.isqrt
if (m.isSquare) return m.isqrt
for (p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]) {
for (p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]) {
Line 1,372: Line 1,372:
return pollardRho_(m, seed, c)
return pollardRho_(m, seed, c)
}
}

// Convenience version of the above method which uses a seed of 2 and a value for c of 1.
// 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) }
static pollardRho(m) { pollardRho(m, 2, 1) }

// Private method for factorizing smaller numbers (BigInt) using a wheel with basis [2, 3, 5].
// Private method for factorizing smaller numbers (BigInt) using a wheel with basis [2, 3, 5].
static primeFactorsWheel_(m) {
static primeFactorsWheel_(m) {
Line 1,382: Line 1,382:
var factors = []
var factors = []
var k = BigInt.new(37)
var k = BigInt.new(37)
var i = 0
var i = 0
while (k * k <= n) {
while (k * k <= n) {
if (n.isDivisibleBy(k)) {
if (n.isDivisibleBy(k)) {
Line 1,395: Line 1,395:
return factors
return factors
}
}

// Private worker method (recursive) to obtain the prime factors of a number (BigInt).
// Private worker method (recursive) to obtain the prime factors of a number (BigInt).
static primeFactors_(m, trialDivs) {
static primeFactors_(m, trialDivs) {
if (m.isProbablePrime(10)) return [m.copy()]
if (m.isProbablePrime(10)) return [m.copy()]
Line 1,418: Line 1,418:
break
break
}
}
if (n >= threshold) {
if (n >= threshold) {
var d = pollardRho_(n, seed, c)
var d = pollardRho_(n, seed, c)
if (d != BigInt.zero) {
if (d != BigInt.zero) {
Line 1,435: Line 1,435:
checkPrime = false
checkPrime = false
}
}
} else if (c < 101) {
} else if (c < 101) {
c = c + 1
c = c + 1
Line 1,443: Line 1,442:
factors.addAll(primeFactorsWheel_(n))
factors.addAll(primeFactorsWheel_(n))
break
break
}
}
} else {
} else {
factors.addAll(primeFactorsWheel_(n))
factors.addAll(primeFactorsWheel_(n))
Line 1,452: Line 1,451:
return factors
return factors
}
}

// Returns a list of the primes factors (BigInt) of 'm' (a Bigint or an integral Num)
// 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.
// using the wheel based factorization and/or Pollard's Rho algorithm as appropriate.
static primeFactors(m) {
static primeFactors(m) {
if (m < 2) return []
if (m < 2) return []
Retrieved from "https://rosettacode.org/wiki/Category_talk:Wren-big"