Category talk:Wren-i64: Difference between revisions
→Source code (Wren): Bug fix
(→Source code (Wren): Removed the previous limitation on the U64.isPrime method.) |
(→Source code (Wren): Bug fix) |
||
| (5 intermediate revisions by the same user not shown) | |||
Line 28:
==Source code (Wren)==
<syntaxhighlight lang="
import "./trait" for Comparable
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 360:
copy() { I64.from(this) } // copies 'this' to a new I64 object
isOdd { this % I64.two
isEven { this % I64.two == I64.zero } // true if 'this' is even
isZero { this == I64.zero } // true if 'this' is zero
Line 407:
static maxSafe { from(9007199254740991) }
static maxU32 { from(4294967295) }
// Returns the largest prime less than 2^64.
static largestPrime { U64.fromStr("18446744073709551557") }
// Returns a U64 object equal in value to 'x' raised to the power of 'n'.
Line 412 ⟶ 415:
// 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 ⟶ 442:
// '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 ⟶ 456:
}
return s
}▼
// Private helper method for modMul method to avoid overflow.
}
}
Line 458 ⟶ 471:
// 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 ⟶ 494:
// 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 ⟶ 512:
// 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 ⟶ 519:
// Returns the smaller of two U64 objects.
static min(x, y) {
if
if
if (x < y) return x
return y
Line 507 ⟶ 527:
// Returns the greater of two U64 objects.
static max(x, y) {
if
if
if (x > y) return x
return y
Line 515 ⟶ 535:
// Returns the positive difference of two U64 objects.
static dim(x, y) {
if
if
if (x >= y) return x - y
return zero
Line 580 ⟶ 600:
// 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 == two || n == three || n == five) return true▼
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 ⟶ 629:
}
}
}
return true
}
// 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 ⟶ 667:
// 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 ⟶ 680:
} 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 ⟶ 690:
// Returns the next prime number greater than 'x'.
static nextPrime(x) {
if
if (x < two) return U64.two
var n = x.isEven ? x + one : x + two
while (true) {
if (isPrime(n)) return n
n.add(two)
}
}
// Returns the previous prime number less than 'x' or null if there isn't one.
static prevPrime(x) {
if (x is Num) x = from(x)
if (x < three) return null
var n = x.isEven ? x - one : x - two
while (true) {
if (isPrime(n)) return n
n.sub(two)
}
}
Line 1,047 ⟶ 1,092:
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
Line 1,067 ⟶ 1,112:
return 0
}
// Return a list of the current instance's base 10 digits
digits { toString.map { |d| Num.fromString(d) }.toList }
digitSum {
var sum = 0
for (d in toString.bytes) sum = sum + d - 48
return sum
}
}
| |||