Rosetta Code

Category talk:Wren-i64: Difference between revisions

Category Discussion

Category talk:Wren-i64 (view source)

Revision as of 17:12, 11 March 2024

5,498 bytes added ,  2 months ago
→‎Source code (Wren): Bug fix
(Bug fix.)
 
(11 intermediate revisions by the same user not shown)
Line 28:
 
==Source code (Wren)==
<syntaxhighlight lang="ecmascriptwren">/* Module "i64.wren" */
 
import "./trait" for Comparable
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.
// Returns zero if the calculation would otherwise overflow or underflow.
static pow(x, n) {
if (!(x is I64)Num) x = from(x)
if (!(n is I64)Num) n = from(n)
if (n < 0) return zero
if (n.isZero) return one
Line 72 ⟶ 75:
value = value.pow(n.toNum)
if (value <= 9007199254740991) return neg ? from(-value) : from(value)
if (value >= 2.pow(63)) return zero
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.squaremul(x)
}
return y
Line 93 ⟶ 95:
// Throws an error if 'x' is negative and 'n' is even.
static root(x, n) {
if (!(x is I64)Num) x = from(x)
if (!((n is Num) && n.isInteger && n > 0)) {
Fiber.abort("'n' must be a positive integer.")
Line 101 ⟶ 103:
var neg = t < 0
if (neg) {
if (n % 2 == 0.isDivisible(two)) {
Fiber.abort("Cannot take the %(n)th root of a negative number.")
} else {
Line 115 ⟶ 117:
}
return (neg) ? -s : s
}
 
// Returns an I64 object equal in value to 'x' multiplied by 'n' modulo 'mod'.
// The arguments can either be I64 objects or Nums but 'mod' must be non-zero.
static modMul(x, n, mod) {
x = from(x)
n = from(n)
mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modMul with modulus 0.")
var sign = x.sign * n.sign
var mag = U64.modMul(x.abs, n.abs, mod.abs).toI64
return mag * sign
}
 
Line 120 ⟶ 134:
// The arguments can either be I64 objects or Nums but 'mod' must be non-zero.
static modPow(x, exp, mod) {
if (!(x is I64)Num) x = from(x)
if (!(exp is I64)) exp = from(exp)
if (!(mod is I64)Num) mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
var r = one
Line 132 ⟶ 146:
while (exp > 0) {
if (base.isZero) return zero
if (exp.isOdd) r.set(modMul(r *, base) %, mod))
exp.rsh(1)
base.square.remset(modMul(base, base, mod))
}
return r
Line 142 ⟶ 156:
// The arguments can either be I64 objects or Nums but must be co-prime.
static modInv(x, n) {
if (!(x is I64)Num) x = from(x)
if (!(n is I64)Num) n = from(n)
var r = from(n)
var newR = from(x).abs
Line 165 ⟶ 179:
// Returns the smaller of two I64 objects.
static min(x, y) {
if (x is Num) x = from(x)
if (y is Num) y = from(y)
if (x < y) return x
return y
Line 171 ⟶ 187:
// Returns the greater of two I64 objects.
static max(x, y) {
if (x is Num) x = from(x)
if (y is Num) y = from(y)
if (x > y) return x
return y
Line 177 ⟶ 195:
// Returns the positive difference of two I64 objects.
static dim(x, y) {
if (x is Num) x = from(x)
if (y is Num) y = from(y)
if (x >= y) return x - y
return zero
Line 183 ⟶ 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 = .set(x % y)
x = .set(t)
}
return x.abs
Line 193 ⟶ 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 322 ⟶ 346:
 
foreign cmpU64(op) // compare this to a U64 object
 
/* Miscellaneous methods. */
 
Line 328 ⟶ 352:
max(op) { (op > this) ? op : this } // returns the maximum of this and another I64 object
 
clamp(min, max) { // clamps this to the interval [min, max]
if (thismin <> minmax) setFiber.abort(min"Range cannot be decreasing.")
if (this < min) set(min) else if (this > max) set(max)
return this.copy()
}
 
copy() { I64.from(this) } // copies 'this' to a new I64 object
 
isOdd { this % I64.two =!= I64.onezero } // true if 'this' is odd
isEven { this % I64.two == I64.zero } // true if 'this' is even
isZero { this == I64.zero } // true if 'this' is zero
Line 341 ⟶ 366:
isSafe { this >= I64.minSafe && this <= I64.maxSafe } // true if 'this' is safe
 
isDivisible(d) { this % d == I64.zero } // true if 'this' is divisible by d
 
isRoot(n) { // true if 'this' is an exact nth root of another I64 object
var r = I64.root(this, n)
return I64.pow(r, n) == this
}
 
isSquare { isRoot(2) } // true if 'this' is an exact square root of another I64 object
isCube { isRoot(3) } // true if 'this' is an exact cube root of another I64 object
 
sign { // the sign of 'this'
if (this < I64.zero) return -1
if (this > I64.zero) return 1
Line 372 ⟶ 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 378 ⟶ 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'.
// The arguments can be either U64 objects or Nums.
// If 'n' is less than 0, returns zero. O.pow(0) returns one.
// Returns zero if the calculation would otherwise overflow.
static pow(x, n) {
if (!(x is U64)Num) x = from(x)
if (!(n is U64)Num) n = from(n)
if (n.isZero) return one
if (n.isOne) return x.copy()
Line 392 ⟶ 423:
var value = x.toNum.pow(n.toNum)
if (value <= 9007199254740991) return from(value)
if (value >= 2.pow(64)) return zero
x = x.copy()
var y = one
var z = n.copy()
while (true) {
if (z.isOdd) {
Line 403 ⟶ 433:
if (z.isZero) break
z.rsh(1)
x.squaremul(x)
}
return y
Line 412 ⟶ 442:
// 'x' can either be a U64 object or a Num but 'n' must be a positive integer.
static root(x, n) {
if (!(x is U64)Num) x = from(x)
if (!((n is Num) && n.isInteger && n > 0)) {
Fiber.abort("'n' must be a positive integer.")
Line 426 ⟶ 456:
}
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 431 ⟶ 471:
// The arguments can either be U64 objects or Nums.
static modMul(x, n, mod) {
if (!(x is U64)Num) x = from(x)
if (!(n is U64)) n = from(n) else n = n.copy()
if (!(mod is U64)) mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modMul with modulus 0.")
var z = zero
var y = x.copy() % mod
n.rem(mod)
if (n > y) {
var t = y
y = n
n = t
}
while (n > zero) {
if (n.isOdd) checkedAdd_(z.add(, y).rem(, mod)
y.lsh(1).remcheckedAdd_(y, y, mod)
n.rsh(1)
}
Line 447 ⟶ 494:
// The arguments can either be U64 objects or Nums but 'mod' must be non-zero.
static modPow(x, exp, mod) {
if (!(x is U64)Num) x = from(x)
if (!(exp is U64)) exp = from(exp) else exp = exp.copy()
if (!(mod is U64)Num) mod = from(mod)
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
var r = one
Line 460 ⟶ 507:
}
return r
}
 
// Returns the multiplicative inverse of 'x' modulo 'n'.
// The arguments can either be U64 objects or Nums but must be co-prime.
static modInv(x, n) {
if (x is Num) x = from(x)
if (n is Num) n = from(n)
return I64.modInv(x.toI64, n.toI64).toU64
}
 
// Returns the smaller of two U64 objects.
static min(x, y) {
if (x is Num) x = from(x)
if (y is Num) y = from(y)
if (x < y) return x
return y
Line 470 ⟶ 527:
// Returns the greater of two U64 objects.
static max(x, y) {
if (x is Num) x = from(x)
if (y is Num) y = from(y)
if (x > y) return x
return y
Line 476 ⟶ 535:
// Returns the positive difference of two U64 objects.
static dim(x, y) {
if (x is Num) x = from(x)
if (y is Num) y = from(y)
if (x >= y) return x - y
return zero
Line 482 ⟶ 543:
// 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 = .set(x % y)
x = .set(t)
}
return x
Line 492 ⟶ 555:
// 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 504 ⟶ 569:
if (n < 2) return one
var fact = one
var i = two2
while (i <= n) {
fact.mul(i)
i.inc = i + 1
}
return fact
Line 527 ⟶ 592:
if (e > 1) prod.mul(factorial(e))
}
return factorial(n)/.div(prod)
}
 
Line 535 ⟶ 600:
// Returns whether or not 'x' is an instance of 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.
Line 573 ⟶ 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) {
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
Line 578 ⟶ 666:
 
// Returns true if 'x' is prime, false otherwise.
// Fails due to overflow on numbers > 9223372036854775807 unless divisible by 2,3 or 5.
static isPrime(x) {
if (!(x is U64)Num) x = from(x)
if (x < 137438953472) return isPrimeWheel_(x) // use wheel if below 2^37
var isbp = isBasicPrime_(x)
if (isbpx.isEven !=|| nullx.isDivisible(three) return|| x.isDivisible(five) || isbp
if (x > largest/two) Fiberx.abortisDivisible("Cannot test %(xseven)) forreturn primality.")false
var a
return millerRabinTest_(x, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])
if (x < 1122004669633) {
a = [2, 13, 23, 1662803]
} else if (x < 2152302898747) {
a = [2, 3, 5, 7, 11]
} else if (x < 3474749660383) {
a = [2, 3, 5, 7, 11, 13]
} else if (x < 341550071728321) {
a = [2, 3, 5, 7, 11, 13, 17]
} else if (x < fromStr("3825123056546413051")) {
a = [2, 3, 5, 7, 11, 13, 17, 19, 23]
} else {
a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
}
return millerRabinTest_(x, a)
}
 
// Returns the next prime number greater than 'x'.
static nextPrime(x) {
if (!(x is U64)Num) x = from(x)
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
if (x == three) return U64.two
var n = x.isEven ? x - one : x - two
while (true) {
if (isPrime(n)) return n
n.sub(two)
}
}
Line 599 ⟶ 713:
// Private worker method for Pollard's Rho algorithm.
static pollardRho_(m, seed, c) {
var g = Fn.new { |x| x.copy(x * x).square.add(c).rem(m) }
var x = from(seed)
var y = from(seed)
Line 606 ⟶ 720:
var count = 0
while (true) {
x = .set(g.call(x))
y = .set(g.call(g.call(y)))
if (x >= y) d.sub(x, y).rem(m) else d.sub(y, x).rem(m)
z.mul(d)
Line 678 ⟶ 792:
while (n > one) {
if (checkPrime && isPrime(n)) {
factors.add(n.copy())
break
}
Line 752 ⟶ 866:
 
// As 'divisors' method but uses a different algorithm.
// Better for largelarger numbers with a small number of prime factors.
static divisors2(n) {
if (n <=is 0Num) returnn []= from(n)
var factorspf = primeFactors(n)
varif divs(pf.count == 0) return (n == 1) ? [one] : pf
forvar (parr in= factors) {[]
forif (ipf.count in== 0...divs.count1) divs.add(divs[i]*p){
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])
}
divs.sort()var divisors = []
var c = divs.countgenerateDivs
ifgenerateDivs (c= > 1)Fn.new { |currIndex, currDivisor|
forif (icurrIndex in== c-1arr..1count) {
if divisors.add(divs[i-1] == divs[i]) divscurrDivisor.removeAtcopy(i))
return
}
for (i in 0..arr[currIndex][1]) {
generateDivs.call(currIndex+1, currDivisor)
currDivisor = currDivisor * arr[currIndex][0]
}
}
returngenerateDivs.call(0, divsone)
return divisors.sort()
}
 
Line 775 ⟶ 909:
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.add(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 898 ⟶ 1,084:
max(op) { (op > this) ? op : this } // returns the maximum of this and another U64 object
 
clamp(min, max) { // clamps this to the interval [min, max]
if (thismin <> minmax) setFiber.abort(min"Range cannot be decreasing.")
if (this < min) set(min) else if (this > max) set(max)
return this.copy()
}
 
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 } // true if 'this' is safe
 
isDivisible(d) { this % d == U64.zero } // true if 'this' is divisible by d
 
isRoot(n) { // true if 'this' is an exact nth root of another U64 object
var r = U64.root(this, n)
return U64.pow(r, n) == this
}
 
isSquare { isRoot(2) } // true if 'this' is an exact square root of another U64 object
isCube { isRoot(3) } // true if 'this' is an exact cube root of another U64 object
 
sign { // the sign of 'this'
if (this > U64.zero) return 1
return 0
}
// Return a list of the current instance's base 10 digits
digits { toString.map { |d| Num.fromString(d) }.toList }
 
digits { toString.map { |d| Num.fromString(d) }.toList } // aReturns listthe sum of the current instance's base 10 digits.
digitSum {
digitSum { digits.reduce(0) { |acc, d| acc = acc + d } } // the sum of those digits
var sum = 0
for (d in toString.bytes) sum = sum + d - 48
return sum
}
}
 
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340225...361707"