Category talk:Wren-i64: Difference between revisions
→Source code (Wren): Complete overhaul including new constants, 'divisor' methods and several bug fixes.
(U64.isPrime method now uses a 'witness' list appropriate to the size of number.) |
(→Source code (Wren): Complete overhaul including new constants, 'divisor' methods and several bug fixes.) |
||
Line 47:
static four { from(4) }
static five { from(5) }
static six { from(6) }
static seven { from(7) }
static eight { from(8) }
static nine { from(9) }
static ten { from(10) }
Line 58 ⟶ 62:
// The arguments can be either I64 objects or Nums.
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
static pow(x, n) {
if (!(x is I64)) x = from(x)
Line 72 ⟶ 75:
value = value.pow(n.toNum)
if (value <= 9007199254740991) return neg ? from(-value) : from(value)
x = x.copy()
var y = one
var z = n.copy()
while (true) {
if (z.isOdd) {
Line 83 ⟶ 85:
if (z.isZero) break
z.rsh(1)
x.
}
return y
Line 101 ⟶ 103:
var neg = t < 0
if (neg) {
if (n
Fiber.abort("Cannot take the %(n)th root of a negative number.")
} else {
Line 120 ⟶ 122:
// The arguments can either be I64 objects or Nums but 'mod' must be non-zero.
static modMul(x, n, mod) {
if (mod.isZero) Fiber.abort("Cannot take modMul with modulus 0.")
var sign = x.sign * n.sign
Line 133 ⟶ 135:
static modPow(x, exp, mod) {
if (!(x is I64)) x = from(x)
if (!(mod is I64)) mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
Line 144 ⟶ 146:
while (exp > 0) {
if (base.isZero) return zero
if (exp.isOdd) r.set(modMul(r, base, mod))
exp.rsh(1)
base.set(modMul(base, base, mod))
Line 177 ⟶ 179:
// Returns the smaller of two I64 objects.
static min(x, y) {
if (!(x is I64)) x = from(x)
if (!(y is I64)) y = from(y)
if (x < y) return x
return y
Line 183 ⟶ 187:
// Returns the greater of two I64 objects.
static max(x, y) {
if (!(x is I64)) x = from(x)
if (!(y is I64)) y = from(y)
if (x > y) return x
return y
Line 189 ⟶ 195:
// Returns the positive difference of two I64 objects.
static dim(x, y) {
if (!(x is I64)) x = from(x)
if (!(y is I64)) y = from(y)
if (x >= y) return x - y
return zero
Line 195 ⟶ 203:
// Returns the greatest common divisor of two I64 objects.
static gcd(x, y) {
x = from(x)
y = from(y)
while (y != zero) {
var t = y
y
x
}
return x.abs
Line 205 ⟶ 215:
// Returns the least common multiple of two I64 objects.
static lcm(x, y) {
x = from(x)
y = from(y)
if (x.isZero && y.isZero) return zero
return (x*y).abs / gcd(x, y)
Line 334 ⟶ 346:
foreign cmpU64(op) // compare this to a U64 object
/* Miscellaneous methods. */
Line 340 ⟶ 352:
max(op) { (op > this) ? op : this } // returns the maximum of this and another I64 object
clamp(min, max) {
if (
if (this < min) set(min) else if (this > max) set(max)
return this.copy()
}
copy() { I64.from(this) }
isOdd { this % I64.two == I64.one } // true if 'this' is odd
Line 353 ⟶ 366:
isSafe { this >= I64.minSafe && this <= I64.maxSafe } // true if 'this' is safe
isDivisible(d) { this % d == I64.zero }
isRoot(n) {
var r = I64.root(this, n)
return I64.pow(r, n) == this
}
isSquare { isRoot(2) }
isCube { isRoot(3) }
sign {
if (this < I64.zero) return -1
if (this > I64.zero) return 1
Line 384 ⟶ 397:
static four { from(4) }
static five { from(5) }
static six { from(6) }
static seven { from(7) }
static eight { from(8) }
static nine { from(9) }
static ten { from(10) }
Line 394 ⟶ 411:
// The arguments can be either U64 objects or Nums.
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
static pow(x, n) {
if (!(x is U64)) x = from(x)
Line 404 ⟶ 420:
var value = x.toNum.pow(n.toNum)
if (value <= 9007199254740991) return from(value)
x = x.copy()
var y = one
var z = n.copy()
while (true) {
if (z.isOdd) {
Line 415 ⟶ 430:
if (z.isZero) break
z.rsh(1)
x.
}
return y
Line 444 ⟶ 459:
static modMul(x, n, mod) {
if (!(x is U64)) x = from(x)
if (!(mod is U64)) mod = from(mod)
var z = zero
Line 460 ⟶ 475:
static modPow(x, exp, mod) {
if (!(x is U64)) x = from(x)
if (!(mod is U64)) mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
Line 484 ⟶ 499:
// Returns the smaller of two U64 objects.
static min(x, y) {
if (!(x is U64)) x = from(x)
if (!(y is U64)) y = from(y)
if (x < y) return x
return y
Line 490 ⟶ 507:
// Returns the greater of two U64 objects.
static max(x, y) {
if (!(x is U64)) x = from(x)
if (!(y is U64)) y = from(y)
if (x > y) return x
return y
Line 496 ⟶ 515:
// Returns the positive difference of two U64 objects.
static dim(x, y) {
if (!(x is U64)) x = from(x)
if (!(y is U64)) y = from(y)
if (x >= y) return x - y
return zero
Line 502 ⟶ 523:
// Returns the greatest common divisor of two U64 objects.
static gcd(x, y) {
x = from(x)
y = from(y)
while (y != zero) {
var t = y
y
x
}
return x
Line 512 ⟶ 535:
// Returns the least common multiple of two U64 objects.
static lcm(x, y) {
x = from(x)
y = from(y)
if (x.isZero && y.isZero) return zero
return x * y / gcd(x, y)
Line 524 ⟶ 549:
if (n < 2) return one
var fact = one
var i =
while (i <= n) {
fact.mul(i)
i
}
return fact
Line 547 ⟶ 572:
if (e > 1) prod.mul(factorial(e))
}
return factorial(n)
}
Line 632 ⟶ 657:
return millerRabinTest_(x, a)
}
// Returns the next prime number greater than 'x'.
static nextPrime(x) {
Line 645 ⟶ 670:
// Private worker method for Pollard's Rho algorithm.
static pollardRho_(m, seed, c) {
var g = Fn.new { |x|
var x = from(seed)
var y = from(seed)
Line 652 ⟶ 677:
var count = 0
while (true) {
x
y
if (x >= y) d.sub(x, y).rem(m) else d.sub(y, x).rem(m)
z.mul(d)
Line 724 ⟶ 749:
while (n > one) {
if (checkPrime && isPrime(n)) {
factors.add(n.copy())
break
}
Line 798 ⟶ 823:
// As 'divisors' method but uses a different algorithm.
// Better for
static divisors2(n) {
if (n
var
arr.add([pf[0].copy(), 1])
} else {
var prevPrime = pf[0]
var count = 1
for (i in 1...pf.count) {
if (pf[i] == prevPrime) {
count = count + 1
} else {
arr.add([prevPrime.copy(), count])
prevPrime = pf[i]
count = 1
}
}
arr.add([prevPrime.copy(), count])
}
var
return
}
for (i in 0..arr[currIndex][1]) {
generateDivs.call(currIndex+1, currDivisor)
currDivisor = currDivisor * arr[currIndex][0]
}
}
return divisors.sort()
}
Line 821 ⟶ 866:
var c = d.count
return (c <= 1) ? [] : d[0..-2]
}
// Returns the sum of all the divisors of 'n' including 1 and 'n' itself.
static divisorSum(n) {
if (n < 1) return zero
n = from(n)
var total = one
var power = two
while (n.isDivisible(two)) {
total.add(power)
power.mul(2)
n.div(2)
}
var i = three
while (i * i <= n) {
var sum = one
power.set(i)
while (n.isDivisible(i)) {
sum.add(power)
power.mul(i)
n.div(i)
}
total.mul(sum)
i = i + 2
}
if (n > 1) total.mul(n + 1)
return total
}
// Returns the number of divisors of 'n' including 1 and 'n' itself.
static divisorCount(n) {
if (n < 1) return 0
n = from(n)
var count = 0
var prod = 1
while (n.isDivisible(two)) {
count = count + 1
n.div(2)
}
prod = prod * (1 + count)
var i = three
while (i * i <= n) {
count = 0
while (n.isDivisible(i)) {
count = count + 1
n.div(i)
}
prod = prod * (1 + count)
i.add(2)
}
if (n > 2) prod = prod * 2
return prod
}
Line 944 ⟶ 1,041:
max(op) { (op > this) ? op : this } // returns the maximum of this and another U64 object
clamp(min, max) {
if (
if (this < min) set(min) else if (this > max) set(max)
return this.copy()
}
copy() { U64.from(this) }
isOdd { this % U64.two == 1 } // true if 'this' is odd
Line 959 ⟶ 1,057:
isDivisible(d) { this % d == U64.zero } // true if 'this' is divisible by d
isRoot(n) {
var r = U64.root(this, n)
return U64.pow(r, n) == this
}
isSquare { isRoot(2) }
isCube { isRoot(3) }
sign {
if (this > U64.zero) return 1
return 0
| |||