Rosetta Code

Category talk:Wren-long: Difference between revisions

Category Discussion

Category talk:Wren-long (view source)

Revision as of 12:13, 3 November 2023

12,985 bytes added ,  6 months ago
m
→‎Source code: Now uses Wren S/H lexer.
(→‎64-bit integer arithmetic: Revised preamble following introduction of Long class.)
m (→‎Source code: Now uses Wren S/H lexer.)
 
(15 intermediate revisions by the same user not shown)
Line 48:
 
===Source code===
 
<syntaxhighlight lang="ecmascript">/* Module "long.wren" */
<syntaxhighlight lang="wren">/* Module "long.wren" */
 
import "./trait" for Comparable
Line 64 ⟶ 65:
static four { lohi_( 4, 0) }
static five { lohi_( 5, 0) }
static six { lohi_( 6, 0) }
static seven { lohi_( 7, 0) }
static eight { lohi_( 8, 0) }
static nine { lohi_( 9, 0) }
static ten { lohi_(10, 0) }
 
Line 74 ⟶ 79:
// Returns the largest ULong = 2^64-1 = 18446744073709551615
static largest { lohi_(4294967295, 4294967295) }
 
// Returns the largest prime less than 2^64.
static largestPrime { ULong.new("18446744073709551557") }
 
// Returns the smallest ULong = 0
Line 94 ⟶ 102:
return String.fromCodePoint((c >= 65 && c <= 90) ? c + 32 : c)
}.join() }
 
 
// Private helper method to convert a lower case base string to a small integer.
Line 141 ⟶ 148:
if (!(b is ULong)) b = new(b)
return (a < b) ? a : b
}
 
// Returns the positive difference of two ULongs.
static dim(a, b) {
if (!(a is ULong)) a = new(a)
if (!(b is ULong)) b = new(b)
if (a >= b) return a - b
return zero
}
 
Line 170 ⟶ 185:
if (n < 2) return one
var fact = one
var i = two2
while (i <= n) {
fact = fact * i
Line 202 ⟶ 217:
static isInstance(n) { n is ULong }
 
// Private helper method tofor determinemodMul ifmethod a ULong is a basic primeto oravoid notoverflow.
static isBasicPrime_checkedAdd_(na, b, c) {
ifvar (!(nroom is= ULong))c n- =ULong.one - new(n)a
if (n.isOne)b return<= room) false{
if (n == two ||a n == three || n == five)a return+ trueb
} else {
if (n.isEven || n.isDivisibleBy(three) || n.isDivisibleBy(five)) return false
if (n < 49) returna true= b - room - ULong.one
}
return null // unknown if prime or not
return a
}
 
Line 229 ⟶ 245:
var next = false
while (d != 0) {
x = x.squareisShort ? (x * x) % n : x.modMul(x, n)
if (x.isOne) return false
if (x == nPrev) {
Line 410 ⟶ 426:
// Returns true if 'n' is a divisor of the current instance, false otherwise
isDivisibleBy(n) { (this % n).isZero }
 
// Private helper method for 'isPrime' method.
// Determines whether the current instance is prime using a wheel with basis [2, 3, 5].
// Should be faster than Miller-Rabin if the current instance is 'short' (below 2 ^ 32).
isShortPrime_ {
if (this < 2) return false
var n = this.copy()
if (n.isEven) return n == 2
if ((n%3).isZero) return n == 3
if ((n%5).isZero) return n == 5
var d = ULong.seven
while (d*d <= n) {
if ((n%d).isZero) return false
d = d + 4
if ((n%d).isZero) return false
d = d + 2
if ((n%d).isZero) return false
d = d + 4
if ((n%d).isZero) return false
d = d + 2
if ((n%d).isZero) return false
d = d + 4
if ((n%d).isZero) return false
d = d + 6
if ((n%d).isZero) return false
d = d + 2
if ((n%d).isZero) return false
d = d + 6
if ((n%d).isZero) return false
}
return true
}
 
// Returns true if the current instance is prime, false otherwise.
// Fails due to overflow on numbers > 9223372036854775807 unless divisible by 2,3 or 5.
isPrime {
varif isbp = ULong.isBasicPrime_(this.isShort) return isShortPrime_
if (isEven || isDivisibleBy(ULong.three) || isDivisibleBy(ULong.five) ||
if (isbp != null) return isbp
if (this > isDivisibleBy(ULong.largest/2seven) Fiber.abort("Cannot test %(this) forreturn primality.")false
var a
return ULong.millerRabinTest_(this, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])
if (this < 4759123141) {
a = [2, 7, 61]
} else if (this < 1122004669633) {
a = [2, 13, 23, 1662803]
} else if (this < 2152302898747) {
a = [2, 3, 5, 7, 11]
} else if (this < 3474749660383) {
a = [2, 3, 5, 7, 11, 13]
} else if (this < 341550071728321) {
a = [2, 3, 5, 7, 11, 13, 17]
} else if (this < ULong.new("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 ULong.millerRabinTest_(this, a)
}
 
// Returns the next prime number greater than the current instance.
nextPrime {
var n = isEven ?if (this +< ULong.One : thistwo) +return ULong.two
var n = isEven ? this + ULong.one : this + ULong.two
while (true) {
if (n.isPrime) return n
n = n + ULong.two
}
}
 
// Returns the previous prime number less than the current instance or null if there isn't one.
prevPrime {
if (this < ULong.three) return null
if (this == ULong.three) return ULong.two
var n = isEven ? this - ULong.one : this - ULong.two
while (true) {
if (n.isPrime) return n
n = n - ULong.two
}
}
Line 432 ⟶ 507:
msb_ {
if (_hi == 0) return (_lo > 0) ? ULong.log2_(_lo).floor : 0
 
return ULong.log2_(_hi).floor + 32
}
Line 498 ⟶ 574:
}
 
// Private helper method for 'divMod', '/' and '%' methods.
// Returns a list containing the quotient and the remainder after dividing
// Uses Num division to estimate the answer and refine it until the exact answer is found.
// the current instance by a ULong.
divModdivMod_(n) {
if (!(n is ULong)) n = ULong.new(n)
if (n.isZero) Fiber.abort("Cannot divide by zero.")
// if both operands are 'small' use Num division.
if (this.isSmall && n.isSmall) {
var a = this.toNum
var b = n.toNum
return [ULong.fromSmall_((a/b).floor), ULong.fromSmall_(a%b)]
}
if (this.isZero) return [ULong.zero, ULong.zero]
if (n.isOne) return [this.copy(), ULong.zero]
if (n > this) return [ULong.zero, this.copy()]
// use Num division to estimate the answer and refine it until the exact answer is found.
var div = ULong.zero
var rem = this.copy()
Line 537 ⟶ 601:
}
return [div, rem]
}
 
// Returns a list containing the quotient and the remainder after dividing
// the current instance by a ULong.
divMod(n) {
if (!(n is ULong)) n = ULong.new(n)
if (n.isZero) Fiber.abort("Cannot divide by zero.")
if (n > this) return [ULong.zero, this.copy()]
if (n == this) return [ULong.one, ULong.zero]
if (this.isZero) return [ULong.zero, ULong.zero]
if (n.isOne) return [this.copy(), ULong.zero]
// if both operands are 'small' use Num division.
if (this.isSmall && n.isSmall) {
var a = this.toNum
var b = n.toNum
return [ULong.fromSmall_((a/b).floor), ULong.fromSmall_(a%b)]
}
return divMod_(n)
}
 
// Divides the current instance by a ULong.
/ (n) { divMod(n)[0] }
if (!(n is ULong)) n = ULong.new(n)
if (n.isZero) Fiber.abort("Cannot divide by zero.")
if (n > this || this.isZero) return ULong.zero
if (n == this) return ULong.one
if (n.isOne) return this.copy()
// if this instance is 'small' use Num division.
if (this.isSmall) {
var a = this.toNum
var b = n.toNum
return ULong.fromSmall_((a/b).floor)
}
return divMod_(n)[0]
}
 
// Returns the remainder after dividing the current instance by a ULong.
% (n) { divMod(n)[1] }
if (!(n is ULong)) n = ULong.new(n)
if (n.isZero) Fiber.abort("Cannot divide by zero.")
if (n > this) return this.copy()
if (this.isZero || n.isOne || n == this) return ULong.zero
// if this instance is 'small' use Num division
if (this.isSmall) {
var a = this.toNum
var b = n.toNum
return ULong.fromSmall_(a%b)
}
return divMod_(n)[1]
}
 
//Returns the bitwise 'and' of the current instance and another ULong.
Line 645 ⟶ 752:
Fiber.abort("Argument must be a positive integer.")
}
if (n == 1) return this.copy()
var t = copy()
n = n - 1
Line 708 ⟶ 815:
// Returns the current instance multiplied by 'n' modulo 'mod'.
modMul(n, mod) {
if (!(n is ULong)) n = ULong.new(n)
if (!(mod is ULong)) mod = ULong.new(mod)
if (mod.isZero) Fiber.abort("Cannot take modMul with modulus 0.")
var x = ULong.zero
var y = this % mod
n = n % mod
if (n > y) {
var t = y
y = n
n = t
}
while (n > ULong.zero) {
if ((n & 1) == 1) x = ULong.checkedAdd_(x +, y) %, mod)
y = ULong.checkedAdd_(y, <<y, 1mod) % mod
n = n >> 1
}
Line 729 ⟶ 845:
if (exp.isOdd) r = r.modMul(base, mod)
exp = exp >> 1
base = base.isShort ? base * base % mod : base.modMul(base, mod)
}
return r
}
 
// Returns the multiplicative inverse of 'this' modulo 'n'.
// 'this' and 'n' must be coprme.
modInv(n) {
if (!(n is ULong)) n = ULong.new(n)
var r = n.copy()
var newR = this.copy()
var t = ULong.zero
var newT = ULong.one
while (!newR.isZero) {
var q = r / newR
var lastT = t.copy()
var lastR = r.copy()
t = newT
r = newR
newT = lastT - q * newT
newR = lastR - q * newR
}
if (!r.isOne) Fiber.abort("%(this) and %(n) are not co-prime.")
if (t < 0) t = t + n
return t
}
 
Line 806 ⟶ 944:
// Returns the string representation of the current instance in base 10.
toString { toBaseString_(10) }
 
// Creates and returns a range of ULongs from 'this' to 'n' with a step of 1.
// 'this' and 'n' must both be 'small' integers >= 0. 'n' can be a Num, a ULong or a Long.
..(n) { ULongs.range(this, n, 1, true) } // inclusive of 'n'
...(n) { ULongs.range(this, n, 1, false) } // exclusive of 'n'
 
// Return a list of the current instance's base 10 digits
digits { toString.map { |d| Num.fromString(d) }.toList }
 
// Returns the sum of the current instance's base 10 digits.
digitSum {
var sum = 0
for (d in toString.bytes) sum = sum + d - 48
return sum
}
 
/* Prime factorization methods. */
Line 964 ⟶ 1,117:
 
// 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 Num) n = ULong.zeronew(n) return []
var factorspf = ULong.primeFactors(n)
varif divs(pf.count == 0) return (n == 1) ? [ULong.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 987 ⟶ 1,160:
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
if (n is Num) n = ULong.new(n)
var total = one
var power = two
while (n.isEven) {
total = total + power
power = power << 1
n = n >> 1
}
var i = three
while (i * i <= n) {
var sum = one
power = i
while (n % i == 0) {
sum = sum + power
power = power * i
n = n / i
}
total = total * sum
i = i + 2
}
if (n > 1) total = total * (n + 1)
return total
}
 
// Returns the number of divisors of 'n' including 1 and 'n' itself.
static divisorCount(n) {
if (n < 1) return 0
if (n is Num) n = ULong.new(n)
var count = 0
var prod = 1
while (n.isEven) {
count = count + 1
n = n >> 1
}
prod = prod * (1 + count)
var i = three
while (i * i <= n) {
count = 0
while (n % i == 0) {
count = count + 1
n = n / i
}
prod = prod * (1 + count)
i = i + 2
}
if (n > 2) prod = prod << 1
return prod
}
}
 
/* ULongs contains various routines applicable to lists of unsigned 64-bit integers. */
and for creating and iterating though ranges of such numbers. */
class ULongs {
class ULongs is Sequence {
static sum(a) { a.reduce(ULong.zero) { |acc, x| acc + x } }
static mean(a) { sum(a)/a.count }
Line 997 ⟶ 1,223:
static max(a) { a.reduce { |acc, x| (x > acc) ? x : acc } }
static min(a) { a.reduce { |acc, x| (x < acc) ? x : acc } }
 
// Private helper method for creating ranges.
static checkValue_(v, name) {
if (v is ULong && v.isSmall) {
return v.toSmall
} else if (v is Long && v.isSmall && !v.isNegative) {
return v.toSmall
} else if (v is Num && v.isInteger && v >= 0 && v <= Num.maxSafeInteger) {
return v
} else {
Fiber.abort("Invalid value for '%(name)'.")
}
}
 
// Creates a range of 'small' ULongs analogous to the Range class but allowing for steps > 1.
// Use the 'ascending' parameter to check that the range's direction is as intended.
construct range(from, to, step, inclusive, ascending) {
from = ULongs.checkValue_(from, "from")
to = ULongs.checkValue_(to, "to")
step = ULongs.checkValue_(step, "step")
if (step < 1) Fiber.abort("'step' must be a positive integer.")
if (ascending && from > to) Fiber.abort("'from' cannot exceed 'to'.")
if (!ascending && from < to) Fiber.abort("'to' cannot exceed 'from'.")
_rng = inclusive ? from..to : from...to
_step = step
}
 
// Convenience versions of 'range' which use default values for some parameters.
static range(from, to, step, inclusive) { range(from, to, step, inclusive, from <= to) }
static range(from, to, step) { range(from, to, step, true, from <= to) }
static range(from, to) { range(from, to, 1, true, from <= to) }
 
// Self-explanatory read only properties.
from { _rng.from }
to { _rng.to }
step { _step }
min { from.min(to) }
max { from.max(to) }
isInclusive { _rng.isInclusive }
isAscending { from <= to }
 
// Iterator protocol methods.
iterate(iterator) {
if (!iterator || _step == 1) {
return _rng.iterate(iterator)
} else {
var count = _step
while (count > 0 && iterator) {
iterator = _rng.iterate(iterator)
count = count - 1
}
return iterator
}
}
 
iteratorValue(iterate) { ULong.fromSmall_(_rng.iteratorValue(iterate)) }
}
 
Line 1,013 ⟶ 1,295:
static four { sigma_( 1, ULong.four) }
static five { sigma_( 1, ULong.five) }
static six { sigma_( 1, ULong.six) }
static seven { sigma_( 1, ULong.seven) }
static eight { sigma_( 1, ULong.eight) }
static nine { sigma_( 1, ULong.nine) }
static ten { sigma_( 1, ULong.ten) }
 
Line 1,051 ⟶ 1,337:
if (!(b is Long)) b = new(b)
return (a < b) ? a : b
}
 
// Returns the positive difference of two Longs.
static dim(a, b) {
if (!(a is Long)) a = new(a)
if (!(b is Long)) b = new(b)
if (a >= b) return a - b
return zero
}
 
Line 1,199 ⟶ 1,493:
 
// Divides the current instance by a Long.
/ (n) { divMod(n)[0] }
if (!(n is Long)) n = Long.new(n)
if (n.isZero) Fiber.abort("Cannot divide by zero.")
var d = _mag / n.mag
return Long.sigma_(_sig / n.sign, d)
}
 
// Returns the remainder after dividing the current instance by a Long.
% (n) { divMod(n)[1] }
if (!(n is Long)) n = Long.new(n)
if (n.isZero) Fiber.abort("Cannot divide by zero.")
var m = _mag % n.mag
return Long.sigma_(_sig, m)
}
 
// Returns the absolute value of 'this'.
abs { isNegative ? -this : this.copy() }
 
// The inherited 'clone' method just returns 'this' as Long objects are immutable.
Line 1,295 ⟶ 1,599:
 
// Returns the current instance multiplied by 'n' modulo 'mod'.
modMul(n, mod) { Long.sigma_(_sig * n.sign , _mag.modMul(n.abs, mod.abs)) }
 
// Returns the current instance to the power 'exp' modulo 'mod'.
modPow(exp, mod) {
varif mag(!(exp is Long)) exp = _magLong.modPownew(exp, mod)
if (!(mod is Long)) mod = Long.new(mod)
var mag = _mag.modPow(exp.abs, mod.abs)
var sign
if (mag == ULong.zero) {
Line 1,310 ⟶ 1,616:
return Long.sigma_(sign, mag)
}
 
// Returns the multiplicative inverse of 'this' modulo 'n'.
// 'this' and 'n' must be co-prime.
modInv(n) { Long.sigma_(_sig, _mag.modInv(n.abs)) }
 
// Increments the current instance by one.
Line 1,340 ⟶ 1,650:
// Returns the string representation of the current instance in base 10.
toString { toBaseString(10) }
 
// Creates and returns a range of Longs from 'this' to 'n' with a step of 1.
// 'this' and 'n' must both be 'small' integers. 'n' can be a Num, a Long or a ULong.
..(n) { Longs.range(this, n, 1, true) } // inclusive of 'n'
...(n) { Longs.range(this, n, 1, false) } // exclusive of 'n'
}
 
/* Longs contains various routines applicable to lists of signed 64-bit integers. */
and for creating and iterating though ranges of such numbers. */
class Longs {
class Longs is Sequence {
static sum(a) { a.reduce(Long.zero) { |acc, x| acc + x } }
static mean(a) { sum(a)/a.count }
Line 1,349 ⟶ 1,665:
static max(a) { a.reduce { |acc, x| (x > acc) ? x : acc } }
static min(a) { a.reduce { |acc, x| (x < acc) ? x : acc } }
 
// Private helper method for creating ranges.
static checkValue_(v, name) {
if ((v is Long || v is ULong) && v.isSmall) {
return v.toSmall
} else if (v is Num && v.isInteger && v.abs <= Num.maxSafeInteger) {
return v
} else {
Fiber.abort("Invalid value for '%(name)'.")
}
}
 
// Creates a range of 'small' Longs analogous to the Range class but allowing for steps > 1.
// Use the 'ascending' parameter to check that the range's direction is as intended.
construct range(from, to, step, inclusive, ascending) {
from = Longs.checkValue_(from, "from")
to = Longs.checkValue_(to, "to")
step = Longs.checkValue_(step, "step")
if (step < 1) Fiber.abort("'step' must be a positive integer.")
if (ascending && from > to) Fiber.abort("'from' cannot exceed 'to'.")
if (!ascending && from < to) Fiber.abort("'to' cannot exceed 'from'.")
_rng = inclusive ? from..to : from...to
_step = step
}
 
// Convenience versions of 'range' which use default values for some parameters.
static range(from, to, step, inclusive) { range(from, to, step, inclusive, from <= to) }
static range(from, to, step) { range(from, to, step, true, from <= to) }
static range(from, to) { range(from, to, 1, true, from <= to) }
 
// Self-explanatory read only properties.
from { _rng.from }
to { _rng.to }
step { _step }
min { from.min(to) }
max { from.max(to) }
isInclusive { _rng.isInclusive }
isAscending { from <= to }
 
// Iterator protocol methods.
iterate(iterator) {
if (!iterator || _step == 1) {
return _rng.iterate(iterator)
} else {
var count = _step
while (count > 0 && iterator) {
iterator = _rng.iterate(iterator)
count = count - 1
}
return iterator
}
}
 
iteratorValue(iterate) { Long.fromSmall_(_rng.iteratorValue(iterate)) }
}</syntaxhighlight>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/331610...354609"