Category talk:Wren-i64: Difference between revisions

Content added Content deleted
m (→‎Source code (Wren): Minor bug fix.)
(→‎Source code (Wren): Fixed some minor issues and improved U64.isPrime method.)
Line 63: Line 63:
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
static pow(x, n) {
static pow(x, n) {
if (!(x is I64)) x = from(x)
if (x is Num) x = from(x)
if (!(n is I64)) n = from(n)
if (n is Num) n = from(n)
if (n < 0) return zero
if (n < 0) return zero
if (n.isZero) return one
if (n.isZero) return one
Line 95: Line 95:
// Throws an error if 'x' is negative and 'n' is even.
// Throws an error if 'x' is negative and 'n' is even.
static root(x, n) {
static root(x, n) {
if (!(x is I64)) x = from(x)
if (x is Num) x = from(x)
if (!((n is Num) && n.isInteger && n > 0)) {
if (!((n is Num) && n.isInteger && n > 0)) {
Fiber.abort("'n' must be a positive integer.")
Fiber.abort("'n' must be a positive integer.")
Line 134: Line 134:
// The arguments can either be I64 objects or Nums but 'mod' must be non-zero.
// The arguments can either be I64 objects or Nums but 'mod' must be non-zero.
static modPow(x, exp, mod) {
static modPow(x, exp, mod) {
if (!(x is I64)) x = from(x)
if (x is Num) x = from(x)
exp = from(exp)
exp = from(exp)
if (!(mod is I64)) mod = from(mod)
if (mod is Num) mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
var r = one
var r = one
Line 156: Line 156:
// The arguments can either be I64 objects or Nums but must be co-prime.
// The arguments can either be I64 objects or Nums but must be co-prime.
static modInv(x, n) {
static modInv(x, n) {
if (!(x is I64)) x = from(x)
if (x is Num) x = from(x)
if (!(n is I64)) n = from(n)
if (n is Num) n = from(n)
var r = from(n)
var r = from(n)
var newR = from(x).abs
var newR = from(x).abs
Line 179: Line 179:
// Returns the smaller of two I64 objects.
// Returns the smaller of two I64 objects.
static min(x, y) {
static min(x, y) {
if (!(x is I64)) x = from(x)
if (x is Num) x = from(x)
if (!(y is I64)) y = from(y)
if (y is Num) y = from(y)
if (x < y) return x
if (x < y) return x
return y
return y
Line 187: Line 187:
// Returns the greater of two I64 objects.
// Returns the greater of two I64 objects.
static max(x, y) {
static max(x, y) {
if (!(x is I64)) x = from(x)
if (x is Num) x = from(x)
if (!(y is I64)) y = from(y)
if (y is Num) y = from(y)
if (x > y) return x
if (x > y) return x
return y
return y
Line 195: Line 195:
// Returns the positive difference of two I64 objects.
// Returns the positive difference of two I64 objects.
static dim(x, y) {
static dim(x, y) {
if (!(x is I64)) x = from(x)
if (x is Num) x = from(x)
if (!(y is I64)) y = from(y)
if (y is Num) y = from(y)
if (x >= y) return x - y
if (x >= y) return x - y
return zero
return zero
Line 412: Line 412:
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
static pow(x, n) {
static pow(x, n) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
if (!(n is U64)) n = from(n)
if (n is Num) n = from(n)
if (n.isZero) return one
if (n.isZero) return one
if (n.isOne) return x.copy()
if (n.isOne) return x.copy()
Line 439: Line 439:
// 'x' can either be a U64 object or a Num but 'n' must be a positive integer.
// 'x' can either be a U64 object or a Num but 'n' must be a positive integer.
static root(x, n) {
static root(x, n) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
if (!((n is Num) && n.isInteger && n > 0)) {
if (!((n is Num) && n.isInteger && n > 0)) {
Fiber.abort("'n' must be a positive integer.")
Fiber.abort("'n' must be a positive integer.")
Line 453: Line 453:
}
}
return s
return s
⚫
}

// Private helper method for modMul method to avoid overflow.
⚫
static checkedAdd_(a, b, c) {
⚫
var room = c - U64.one - a
⚫
if (b <= room) {
⚫
a.add(b)
⚫
} else {
⚫
a.set(b - room - U64.one)
}
}
}


Line 458: Line 468:
// The arguments can either be U64 objects or Nums.
// The arguments can either be U64 objects or Nums.
static modMul(x, n, mod) {
static modMul(x, n, mod) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
n = from(n)
n = from(n)
if (!(mod is U64)) mod = from(mod)
mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modMul with modulus 0.")
var z = zero
var z = zero
var y = x.copy()
var y = x % mod
n.rem(mod)
⚫
if (n > y) {
⚫
var t = y
⚫
y = n
⚫
n = t
}
while (n > zero) {
while (n > zero) {
if (n.isOdd) z.add(y).rem(mod)
if (n.isOdd) checkedAdd_(z, y, mod)
y.lsh(1).rem(mod)
checkedAdd_(y, y, mod)
n.rsh(1)
n.rsh(1)
}
}
Line 474: Line 491:
// The arguments can either be U64 objects or Nums but 'mod' must be non-zero.
// The arguments can either be U64 objects or Nums but 'mod' must be non-zero.
static modPow(x, exp, mod) {
static modPow(x, exp, mod) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
exp = from(exp)
exp = from(exp)
if (!(mod is U64)) mod = from(mod)
if (mod is Num) mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
var r = one
var r = one
Line 492: Line 509:
// The arguments can either be U64 objects or Nums but must be co-prime.
// The arguments can either be U64 objects or Nums but must be co-prime.
static modInv(x, n) {
static modInv(x, n) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
if (!(n is U64)) n = from(n)
if (n is Num) n = from(n)
return I64.modInv(x.toI64, n.toI64).toU64
return I64.modInv(x.toI64, n.toI64).toU64
}
}
Line 499: Line 516:
// Returns the smaller of two U64 objects.
// Returns the smaller of two U64 objects.
static min(x, y) {
static min(x, y) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
if (!(y is U64)) y = from(y)
if (y is Num) y = from(y)
if (x < y) return x
if (x < y) return x
return y
return y
Line 507: Line 524:
// Returns the greater of two U64 objects.
// Returns the greater of two U64 objects.
static max(x, y) {
static max(x, y) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
if (!(y is U64)) y = from(y)
if (y is Num) y = from(y)
if (x > y) return x
if (x > y) return x
return y
return y
Line 515: Line 532:
// Returns the positive difference of two U64 objects.
// Returns the positive difference of two U64 objects.
static dim(x, y) {
static dim(x, y) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
if (!(y is U64)) y = from(y)
if (y is Num) y = from(y)
if (x >= y) return x - y
if (x >= y) return x - y
return zero
return zero
Line 580: Line 597:
// Returns whether or not 'x' is an instance of U64.
// Returns whether or not 'x' is an instance of U64.
static isInstance(x) { x is U64 }
static isInstance(x) { x is U64 }

// Private method to determine if a U64 is a basic prime or not.
⚫
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
return null // unknown if prime or not
⚫
}


// Private method to apply the Miller-Rabin test.
// Private method to apply the Miller-Rabin test.
Line 618: Line 626:
}
}
}
}
}
⚫
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) {
⚫
if (x < 2) return false
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
⚫
while (d*d <= n) {
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(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
return true
Line 624: Line 664:
// Returns true if 'x' is prime, false otherwise.
// Returns true if 'x' is prime, false otherwise.
static isPrime(x) {
static isPrime(x) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
if (x < 137438953472) return isPrimeWheel_(x) // use wheel if below 2^37
⚫
var isbp = isBasicPrime_(x)
if (isbp != null) return isbp
if (x.isEven || x.isDivisible(three) || x.isDivisible(five) ||
⚫
x.isDivisible(seven)) return false
var a
var a
if (x < 2047) {
if (x < 1122004669633) {
⚫
a = [2]
⚫
} else if (x < 1373653) {
⚫
a = [2, 3]
⚫
} else if (x < 9080191) {
⚫
a = [31, 73]
⚫
} else if (x < 25326001) {
⚫
a = [2, 3, 5]
} else if (x < 3215031751) {
⚫
a = [2, 3, 5, 7]
} else if (x < 4759123141) {
⚫
a = [2, 7, 61]
} else if (x < 1122004669633) {
a = [2, 13, 23, 1662803]
a = [2, 13, 23, 1662803]
} else if (x < 2152302898747) {
} else if (x < 2152302898747) {
Line 648: Line 677:
} else if (x < 341550071728321) {
} else if (x < 341550071728321) {
a = [2, 3, 5, 7, 11, 13, 17]
a = [2, 3, 5, 7, 11, 13, 17]
} else if (x < from("3825123056546413051")) {
} else if (x < fromStr("3825123056546413051")) {
a = [2, 3, 5, 7, 11, 13, 17, 19, 23]
a = [2, 3, 5, 7, 11, 13, 17, 19, 23]
} else {
} else {
Line 658: Line 687:
// Returns the next prime number greater than 'x'.
// Returns the next prime number greater than 'x'.
static nextPrime(x) {
static nextPrime(x) {
if (!(x is U64)) x = from(x)
if (x is Num) x = from(x)
⚫
if (x < two) return two
var n = x.isEven ? x + one : x + two
var n = x.isEven ? x + one : x + two
while (true) {
while (true) {
Line 1,048: Line 1,076:
copy() { U64.from(this) } // copies 'this' to a new U64 object
copy() { U64.from(this) } // copies 'this' to a new U64 object


isOdd { this % U64.two == 1 } // true if 'this' is odd
isOdd { this % U64.two == 1 } // true if 'this' is odd
isEven { this % U64.two == 0 } // true if 'this' is even
isEven { this % U64.two == 0 } // true if 'this' is even
isZero { this == 0 } // true if 'this' is zero
isZero { this == 0 } // true if 'this' is zero
isOne { this == 1 } // true if 'this' is one
isOne { this == 1 } // true if 'this' is one
isSafe { this <= U64.maxSafe } // true if 'this' is safe
isSafe { this <= U64.maxSafe } // true if 'this' is safe


isDivisible(d) { this % d == U64.zero } // true if 'this' is divisible by d
isDivisible(d) { this % d == U64.zero } // true if 'this' is divisible by d
Retrieved from "https://rosettacode.org/wiki/Category_talk:Wren-i64"