Category talk:Wren-i64: Difference between revisions
→Source code (Wren): Fixed some minor issues and improved U64.isPrime method.
m (→Source code (Wren): Minor bug fix.) |
(→Source code (Wren): Fixed some minor issues and improved U64.isPrime method.) |
||
Line 63:
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
static pow(x, n) {
if
if
if (n < 0) return zero
if (n.isZero) return one
Line 95:
// Throws an error if 'x' is negative and 'n' is even.
static root(x, n) {
if
if (!((n is Num) && n.isInteger && n > 0)) {
Fiber.abort("'n' must be a positive integer.")
Line 134:
// The arguments can either be I64 objects or Nums but 'mod' must be non-zero.
static modPow(x, exp, mod) {
if
exp = from(exp)
if
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
var r = one
Line 156:
// The arguments can either be I64 objects or Nums but must be co-prime.
static modInv(x, n) {
if
if
var r = from(n)
var newR = from(x).abs
Line 179:
// Returns the smaller of two I64 objects.
static min(x, y) {
if
if
if (x < y) return x
return y
Line 187:
// Returns the greater of two I64 objects.
static max(x, y) {
if
if
if (x > y) return x
return y
Line 195:
// Returns the positive difference of two I64 objects.
static dim(x, y) {
if
if
if (x >= y) return x - y
return zero
Line 412:
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
static pow(x, n) {
if
if
if (n.isZero) return one
if (n.isOne) return x.copy()
Line 439:
// 'x' can either be a U64 object or a Num but 'n' must be a positive integer.
static root(x, n) {
if
if (!((n is Num) && n.isInteger && n > 0)) {
Fiber.abort("'n' must be a positive integer.")
Line 453:
}
return s
}▼
// Private helper method for modMul method to avoid overflow.
}
}
Line 458 ⟶ 468:
// The arguments can either be U64 objects or Nums.
static modMul(x, n, mod) {
if
n = from(n)
if (mod.isZero) Fiber.abort("Cannot take modMul with modulus 0.")
var z = zero
var y = x
n.rem(mod)
}
while (n > zero) {
if (n.isOdd) checkedAdd_(z
n.rsh(1)
}
Line 474 ⟶ 491:
// The arguments can either be U64 objects or Nums but 'mod' must be non-zero.
static modPow(x, exp, mod) {
if
exp = from(exp)
if
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
var r = one
Line 492 ⟶ 509:
// The arguments can either be U64 objects or Nums but must be co-prime.
static modInv(x, n) {
if
if
return I64.modInv(x.toI64, n.toI64).toU64
}
Line 499 ⟶ 516:
// Returns the smaller of two U64 objects.
static min(x, y) {
if
if
if (x < y) return x
return y
Line 507 ⟶ 524:
// Returns the greater of two U64 objects.
static max(x, y) {
if
if
if (x > y) return x
return y
Line 515 ⟶ 532:
// Returns the positive difference of two U64 objects.
static dim(x, y) {
if
if
if (x >= y) return x - y
return zero
Line 580 ⟶ 597:
// Returns whether or not 'x' is an instance of U64.
static isInstance(x) { x is U64 }
▲ static isBasicPrime_(n) {
if (n.isOne) return false▼
if (n.isEven || n.isDivisible(three) || n.isDivisible(five)) return false▼
▲ if (n < 49) return true
▲ }
// Private method to apply the Miller-Rabin test.
Line 618 ⟶ 626:
}
}
}
}
// Private helper method for 'isPrime' method.
// Determines whether 'x' is prime using a wheel with basis [2, 3, 5].
// Should be faster than Miller-Rabin if 'x' is below 2^37.
static isPrimeWheel_(x) {
var n = x.copy()
if (n.isEven) return n == 2
if ((n%3).isZero) return n == 3
if ((n%5).isZero) return n == 5
var d = U64.seven
if ((n%d).isZero) return false
if ((n%d).isZero) return false
d.add(2)
if ((n%d).isZero) return false
d.add(4)
if ((n%d).isZero) return false
d.add(2)
if ((n%d).isZero) return false
d.add(4)
if ((n%d).isZero) return false
d.add(6)
if ((n%d).isZero) return false
d.add(2)
if ((n%d).isZero) return false
d.add(6)
if ((n%d).isZero) return false
}
return true
Line 624 ⟶ 664:
// Returns true if 'x' is prime, false otherwise.
static isPrime(x) {
if
if (x < 137438953472) return isPrimeWheel_(x) // use wheel if below 2^37
▲ var isbp = isBasicPrime_(x)
if (
var a
if (x <
▲ a = [2]
▲ } else if (x < 1373653) {
▲ a = [2, 3]
▲ } else if (x < 9080191) {
▲ a = [31, 73]
▲ } else if (x < 25326001) {
▲ a = [2, 3, 5]
▲ a = [2, 3, 5, 7]
▲ a = [2, 7, 61]
a = [2, 13, 23, 1662803]
} else if (x < 2152302898747) {
Line 648 ⟶ 677:
} else if (x < 341550071728321) {
a = [2, 3, 5, 7, 11, 13, 17]
} else if (x <
a = [2, 3, 5, 7, 11, 13, 17, 19, 23]
} else {
Line 658 ⟶ 687:
// Returns the next prime number greater than 'x'.
static nextPrime(x) {
if
▲ if (x < two) return two
var n = x.isEven ? x + one : x + two
while (true) {
Line 1,048 ⟶ 1,076:
copy() { U64.from(this) } // copies 'this' to a new U64 object
isOdd { this % U64.two == 1 } // true if 'this' is odd
isEven { this % U64.two == 0 } // true if 'this' is even
isZero { this == 0 } // true if 'this' is zero
isOne { this == 1 } // true if 'this' is one
isSafe { this <= U64.maxSafe
isDivisible(d) { this % d == U64.zero } // true if 'this' is divisible by d
|