Category talk:Wren-math: Difference between revisions
→Source code: Added squareFree, cubeFree and powerFree methods to Int class.
(→Source code: Added maxSafePrime and prevPrime methods and outlawed 'unsafe' arguments to several existing methods of the Int class.) |
(→Source code: Added squareFree, cubeFree and powerFree methods to Int class.) |
||
| (6 intermediate revisions by the same user not shown) | |||
Line 1:
===Source code===
<syntaxhighlight lang="
/* Math supplements the Num class with various other operations on numbers. */
Line 113:
return deriv
}
// Attempts to find a real root of a polynomial using Newton's method from
// an initial guess, a given tolerance, a maximum number of iterations
// and a given multiplicity (usually 1).
// If a root is found, it is returned otherwise 'null' is returned.
// If the root is near an integer checks if the integer is in fact the root.
static rootPoly(coefs, guess, tol, maxIter, mult) {
var deg = coefs.count - 1
if (deg == 0) return null
if (deg == 1) return -coefs[1]/coefs[0]
if (deg == 2 && coefs[1]*coefs[1] - 4*coefs[0]*coefs[2] < 0) return null
if (Math.evalPoly(coefs, 0) == 0) return 0
var eps = 0.001
var deriv = Math.diffPoly(coefs)
var x0 = guess
var iter = 1
while (true) {
var den = Math.evalPoly(deriv, x0)
if (den == 0) {
x0 = (x0 >= 0) ? x0 + eps : x0 - eps
} else {
var num = Math.evalPoly(coefs, x0)
var x1 = x0 - num/den * mult
if ((x1 - x0).abs <= tol) {
var r = x1.round
if ((r - x1).abs <= eps && Math.evalPoly(coefs, r) == 0) return r
return x1
}
x0 = x1
}
if (iter == maxIter) break
iter = iter + 1
}
x0 = x0.round
if (Math.evalPoly(coefs, x0) == 0) return x0
return null
}
// Convenience versions of 'rootPoly' which use defaults for some parameters.
static rootpoly(coefs, guess) { rootPoly(coefs, guess, 1e-15, 100, 1) }
static rootPoly(coefs) { rootPoly(coefs, 0.001, 1e-15, 100, 1) }
// Gamma function using Lanczos approximation.
Line 443 ⟶ 485:
n = n - 2
}
}
// Returns the 'n'th prime number. For the formula used, see:
// https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
static getPrime(n) {
if (n < 1 || !n.isInteger) Fiber.abort("Argument must be a positive integer.")
if (n < 8) return [2, 3, 5, 7, 11, 13, 17][n-1]
var l1 = n.log
var l2 = l1.log
var l3 = (l2 - 2) / l1
var l4 = (l2*l2 - 6*l2 + 11) / (2*l1*l1)
var p = ((l1 + l2 + l3 - l4 - 1) * n).floor
var g = p.log.round
var pc = Int.primeCount(p)
p = p + (n - pc) * g
if (p % 2 == 0) p = p - 1
pc = Int.primeCount(p)
if (pc < n) {
for (i in pc...n) p = Int.nextPrime(p)
} else if (Int.isPrime(p)) {
for (i in n...pc) p = Int.prevPrime(p)
} else {
for (i in n..pc) p = Int.prevPrime(p)
}
return p
}
Line 614 ⟶ 681:
}
return ans + 1
}
// Returns how many positive integers up to 'n' are relatively prime to 'n'.
static totient(n) {
if (n < 1) return 0
var tot = n
var i = 2
while (i*i <= n) {
if (n%i == 0) {
while (n%i == 0) n = (n/i).floor
tot = tot - (tot/i).floor
}
if (i == 2) i = 1
i = i + 2
}
if (n > 1) tot = tot - (tot/n).floor
return tot
}
Line 648 ⟶ 732:
return factors
}
// Returns a list of the distinct prime factors of 'n' in order.
static distinctPrimeFactors(n) {
var factors = primeFactors(n)
if (factors.count < 2) return factors
for (i in factors.count-1..1) {
if (factors[i] == factors[i-1]) factors.removeAt(i)
}
return factors
}
// Returns a list of the distinct prime factors of 'n' together with the number
// of times each such factor is repeated.
static primePowers(n) {
var factors = primeFactors(n)
if (factors.count == 0) return []
var prev = factors[0]
var res = [[prev, 1]]
for (f in factors.skip(1)) {
if (f == prev) {
res[-1][1] = res[-1][1] + 1
} else {
res.add([f, 1])
}
prev = f
}
return res
}
// Returns true if the prime factorization of 'n' does not contain any
// factors which are repeated 'm' (or more) times, or false otherwise.
static powerFree(m, n) { Int.primePowers(n).all { |pp| pp[1] < m } }
// Covenience versions of above method for squares and cubes.
static squareFree(n) { powerFree(2, n) }
static cubeFree(n) { powerFree(3, n) }
// Returns all the divisors of 'n' including 1 and 'n' itself.
| |||