Category talk:Wren-long: Difference between revisions
m
→Source code: Now uses Wren S/H lexer.
(→Source code: Added support for signed 64 bit arithmetic (Long class).) |
m (→Source code: Now uses Wren S/H lexer.) |
||
| (16 intermediate revisions by the same user not shown) | |||
Line 7:
However, some tasks on RC only require integers within the 64-bit range and ''BigInt'' feels like overkill for such tasks.
This module aims to remedy that situation by providing
====ULong====
Internally, a 64-bit unsigned integer is represented by two unsigned 32-bit integral ''Num''s, a low and a high part, though this is generally invisible to the user.
The design of ''ULong'' follows closely that of the ''BigInt'' class though the implementation is generally much simpler and hopefully more performant for numbers within its range.
Line 28 ⟶ 30:
The most obvious way to perform division of larger numbers is to first obtain an estimate of the result by treating them as ''Num''s and then refine this result iteratively until the exact result is obtained. However, this is easier said than done because the accuracy of the initial estimate will depend on the magnitude of the numbers and one has to guard against overflow when performing the iterations. Consequently, this is quite a ''slow'' operation.
====Long====
Internally, a 64-bit signed integer is represented by a ULong (its ''magnitude'') and a sign (-1 for negative, 0 for zero and +1 for positive integers). This design has the following advantages:
1. Longs have double the range of ULongs and not one bit less as is usually the case for 64-bit signed integers where one bit is needed to represent the sign.
2. Apart from manipulation of the sign, most of the methods for the Long type can simply defer to the corresponding methods for the ULong type which makes the code for the Long class much shorter and simpler than it otherwise would have been.
3. There is no need to support bitwise operations and other stuff which is only really relevant to unsigned integers such as prime number routines. This again shortens and simplifies the code.
4. It is relatively easy to mix both Longs and ULongs in arithmetic expressions by performing the necessary conversions automatically.
However, a big disadvantage is that Longs use 50% more memory (3 Nums instead of two) and are slightly slower than ULongs which means that the latter should normally be preferred unless you know or suspect that you will need to deal with negative numbers.
A peculiarity of the design (though not necessarily a disadvantage) is that an overflow wraps around to zero rather than the opposite end of the range as is usual for 64-bit signed integers.
===Source code===
<syntaxhighlight lang="wren">/* Module "long.wren" */
import "./trait" for Comparable
Line 46 ⟶ 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 56 ⟶ 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 76 ⟶ 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 123 ⟶ 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 152 ⟶ 185:
if (n < 2) return one
var fact = one
var i =
while (i <= n) {
fact = fact * i
Line 184 ⟶ 217:
static isInstance(n) { n is ULong }
// Private helper method
static
if (
} else {
}
return a
}
Line 211 ⟶ 245:
var next = false
while (d != 0) {
x = x.
if (x.isOne) return false
if (x == nPrev) {
Line 392 ⟶ 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.
isPrime {
if (isEven || isDivisibleBy(ULong.three) || isDivisibleBy(ULong.five) ||
var a
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 ? 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 414 ⟶ 507:
msb_ {
if (_hi == 0) return (_lo > 0) ? ULong.log2_(_lo).floor : 0
return ULong.log2_(_hi).floor + 32
}
Line 480 ⟶ 574:
}
// Private helper method for 'divMod', '/' and '%' methods.
// Uses Num division to estimate the answer and refine it until the exact answer is found.
var div = ULong.zero
var rem = this.copy()
Line 519 ⟶ 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) {
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) {
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 627 ⟶ 752:
Fiber.abort("Argument must be a positive integer.")
}
if (n == 1) return this.copy()
var t = copy()
n = n - 1
Line 690 ⟶ 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 = ULong.checkedAdd_(y,
n = n >> 1
}
Line 711 ⟶ 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 788 ⟶ 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 946 ⟶ 1,117:
// As 'divisors' method but uses a different algorithm.
// Better for
static divisors2(n) {
if (n
var
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])
}
var
return
}
for (i in 0..arr[currIndex][1]) {
generateDivs.call(currIndex+1, currDivisor)
currDivisor = currDivisor * arr[currIndex][0]
}
}
return divisors.sort()
}
Line 969 ⟶ 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 is Sequence {
static sum(a) { a.reduce(ULong.zero) { |acc, x| acc + x } }
static mean(a) { sum(a)/a.count }
Line 979 ⟶ 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 995 ⟶ 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,033 ⟶ 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,181 ⟶ 1,493:
// Divides the current instance by a Long.
/ (n) {
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) {
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,277 ⟶ 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) {
if (!(mod is Long)) mod = Long.new(mod)
var mag = _mag.modPow(exp.abs, mod.abs)
var sign
if (mag == ULong.zero) {
Line 1,292 ⟶ 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,322 ⟶ 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 is Sequence {
static sum(a) { a.reduce(Long.zero) { |acc, x| acc + x } }
static mean(a) { sum(a)/a.count }
Line 1,331 ⟶ 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>
| |||