Category talk:Wren-big: Difference between revisions
m
→Source code: Now uses Wren S/H lexer.
(→Source code: Added BigDec and BigDecs classes.) |
m (→Source code: Now uses Wren S/H lexer.) |
||
| (8 intermediate revisions by the same user not shown) | |||
Line 5:
Wren is unable to deal natively and precisely with integers outside a 53-bit range and so either has to limit such tasks to integers which it can deal with or is unable to offer a realistic solution at all.
This module aims to remedy that situation by providing classes for arbitrary precision arithmetic (integers, rational and
;BigInt class
Line 29:
There are also separate methods to enable you to to generate a BigRat from a Rat object, from a string in rational form (i.e. "n/d"), from a mixed string (e.g. "1_2/3") from a decimal string or value (e.g. "1.234") or from a Num.
;BigDec class
As rational numbers can easily be created from or displayed as decimal numbers, at first glance there seems little point in adding a BigDec class to the module as well.
However, a problem with BigRat is that it always works to maximum precision which uses a lot of memory and can be very slow in certain circumstances.
BigDec aims to fix this problem by working to a user defined precision, where precision is measured in digits after the decimal point. One can therefore limit precision having regard to the accuracy needed for a particular task though, to dove-tail with the maximum accuracy of ordinary Nums, a minimum (and default) precision of 16 is imposed.
Otherwise, BigDec is simply a thin wrapper over BigRat and defers to it for the implementation of most of its methods. Where all you need is decimal numbers, it is also somewhat easier to use than BigRat as the user never has to deal with the latter directly.
;General observations
The original Javascript libraries and this module are easy to use as they try to mimic native arithmetic by always producing immutable objects and by implicitly converting suitable operands into BigInts, BigRats or
Of course, such a system inevitably keeps the garbage collector busy and is not going to be as fast and efficient as systems where BigInts, BigRats or
===Source code===
<syntaxhighlight lang="
import "./trait" for Comparable
Line 1,388 ⟶ 1,396:
return sign + str
}
// Creates and returns a range of BigInts from 'this' to 'n' with a step of 1.
// 'this' and 'n' must both be 'small' integers. 'n' can be a Num or a BigInt.
..(n) { BigInts.range(this, n, 1, true) } // inclusive of 'n'
...(n) { BigInts.range(this, n, 1, false) } // exclusive of 'n'
/* Prime factorization methods. */
Line 1,644 ⟶ 1,657:
}
/* BigInts contains various routines applicable to lists of big integers
and for creating and iterating though ranges of such numbers. */
class BigInts is Sequence {
static sum(a) { a.reduce(BigInt.zero) { |acc, x| acc + x } }
static prod(a) { a.reduce(BigInt.one) { |acc, x| acc * x } }
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 BigInt && 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' BigInts 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 = BigInts.checkValue_(from, "from")
to = BigInts.checkValue_(to, "to")
step = BigInts.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) { BigInt.small_(_rng.iteratorValue(iterate)) }
}
Line 1,876 ⟶ 1,944:
pow(i) {
if (!((i is Num) && i.isInteger)) Fiber.abort("Argument must be an integer.")
if (i == 0) return
if (i == 1) return this.copy()
if (i == -1) return this.inverse
var np = _n.pow(i.abs)
var dp = _d.pow(i.abs)
Line 1,944 ⟶ 2,014:
// Converts the current instance to a Num where possible.
// Will probably lose accuracy if the numerator and/or denominator are not 'small'.
toFloat {
// Converts the current instance to an integer where possible with any fractional part truncated.
Line 2,002 ⟶ 2,072:
// Returns a string represenation of this instance in the form "i_n/d" where 'i' is an integer.
toMixedString {
var
var
return sign + q.toString + "_" + r.toString + "/" + _d.toString
}
Line 2,064 ⟶ 2,135:
static phi { new("1.6180339887498948482045868343656381177203091798057628621354486227", 64) }
static sqrt2 { new("1.4142135623730950488016887242096980785696718753769480731766797380", 64) }
// Returns 'pi' to a given precision using the Almqvest Berndt AGM method.
// See https://rosettacode.org/wiki/Arithmetic-geometric_mean/Calculate_Pi for details.
static pi(prec) {
if (prec < 16) prec = 16
var an = BigRat.one
var bn = BigRat.half.sqrt(prec)
var tn = BigRat.half.square
var pn = BigRat.one
while (pn <= prec) {
var prevAn = an
an = (bn + an) * BigRat.half
bn = (bn * prevAn).sqrt(prec)
prevAn = prevAn - an
tn = tn - (prevAn.square * pn)
pn = pn + pn
}
var res = (an + bn).square / (tn * 4)
return BigDec.fromBigRat(res, prec)
}
// Returns the greater of two BigDec objects.
Line 2,179 ⟶ 2,270:
copy() { BigDec.new_(_br.copy(), _prec) }
// Compares this BigDec with
compare(other) { (other is BigDec) ? _br.compare(other.br_) : _br.compare(other) }
// As above but compares
compareAbs(other) { (other is BigDec) ? _br.compareAbs(other.br_) : _br.compareAbs(other) }
// Returns this BigDec expressed as a BigInt with any fractional part truncated.
Line 2,193 ⟶ 2,284:
// Converts the current instance to a Num where possible.
// Will probably lose accuracy for larger numbers.
toFloat {
// Converts the current instance to an integer where possible with any fractional part truncated.
Line 2,211 ⟶ 2,302:
toString { toString(_prec, true, false) } // precision digits, always rounded
toDefaultString { toString(16, true, false) } // 16 digits, always rounded
// Private worker method for exponentiation using Taylor series.
exp_ {
var y = _br
var x = _br
var z = _br
var res = x + BigRat.one
var eps = BigRat.new(BigInt.one, BigInt.ten.pow(_prec))
var k = 2
var fact = BigRat.two
while (x.abs > eps) {
z = z * y
x = z / fact
res = res + x.round(_prec+2)
k = k + 1
fact = fact * k
}
return BigDec.fromBigRat(res, _prec)
}
// Returns the exponential of this instance (e ^ this) to the same precision.
exp {
if (_br.isInteger) return exp_
return (truncate/2).exp_.square * fraction.exp_
}
// Private worker method for natural logarithm using Taylor series.
log_ {
var y = _br
var x = (y - BigRat.one) / (y + BigRat.one)
var z = x * x
var res = BigRat.zero
var eps = BigRat.new(BigInt.one, BigInt.ten.pow(_prec))
var k = 1
while (x.abs > eps) {
res = res + (BigRat.two * x / k).round(_prec+2)
x = (x * z).round(_prec+2)
k = k + 2
}
return BigDec.new_(res, _prec)
}
// Returns the natural logarithm of this instance to the same precision.
log {
if (sign <= 0) Fiber.abort("Instance must be positive.")
if (this < BigDec.two) return log_
var d = this.copy()
var pow = 0
var two = BigDec.new(2, _prec)
while (d >= two) {
d = d / 2
pow = pow + 1
}
return d.log_ + two.log_ * pow
}
// Returns this ^ f where f may be fractional.
powf(f) {
if ((f is Num) && f.isInteger) return pow(f)
return (log * f).exp
}
}
| |||