Category talk:Wren-long: Difference between revisions
m
→Source code: Now uses Wren S/H lexer.
(→Source code: Removed the previous limitation on the ULong.isPrime method.) |
m (→Source code: Now uses Wren S/H lexer.) |
||
| (7 intermediate revisions by the same user not shown) | |||
Line 48:
===Source code===
<syntaxhighlight lang="wren">/* Module "long.wren" */
import "./trait" for Comparable
Line 78 ⟶ 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 98 ⟶ 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 214 ⟶ 217:
static isInstance(n) { n is ULong }
// Private helper method
static
if (
} else {
}
return a
}
Line 241 ⟶ 245:
var next = false
while (d != 0) {
x = x.isShort ? (x * x) % n : x.modMul(x, n)
if (x.isOne) return false
if (x == nPrev) {
Line 422 ⟶ 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) ||
isDivisibleBy(ULong.seven)) return false
var a
if (this <
a = [2, 7, 61]
} else if (this < 1122004669633) {
Line 458 ⟶ 485:
// 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 468 ⟶ 507:
msb_ {
if (_hi == 0) return (_lo > 0) ? ULong.log2_(_lo).floor : 0
return ULong.log2_(_hi).floor + 32
}
Line 534 ⟶ 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 573 ⟶ 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 748 ⟶ 819:
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 768 ⟶ 845:
if (exp.isOdd) r = r.modMul(base, mod)
exp = exp >> 1
base = base.isShort ? base * base % mod : base.modMul(base, mod)
}
return r
Line 867 ⟶ 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 1,076 ⟶ 1,168:
var total = one
var power = two
while (n
total = total + power
power = power
n = n
}
var i = three
Line 1,103 ⟶ 1,195:
var count = 0
var prod = 1
while (n
count = count + 1
n = n
}
prod = prod * (1 + count)
Line 1,118 ⟶ 1,210:
i = i + 2
}
if (n > 2) prod = prod
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 1,130 ⟶ 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,344 ⟶ 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'.
Line 1,491 ⟶ 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,500 ⟶ 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>
| |||