packages /

num 0.1.0

Exact decimal arithmetic for money, prices, quantities and anything else that has to add up to the cent, plus integer helpers (gcd, lcm, pow_mod).

files / src/lib.auk 29.0 kB · 809 lines

/// Exact decimal arithmetic for money and other base-10 quantities (`Dec`), plus integer helpers
/// (`gcd`, `lcm`, `pow_mod`). Pure: no effects. A `Dec` is an arbitrary-precision integer
/// coefficient and a decimal scale, so `+ - *` are always exact and never overflow; only `/`
/// and `round` lose digits, and they do it in a rounding mode you choose.

/// A decimal number: `(-1 if neg) * coefficient / 10^scale`. The coefficient is stored as
/// little-endian base-10^9 limbs in `mag` (no leading zero limbs; zero is `[]` and never
/// negative), and `scale >= 0` counts the digits after the point. Make values with `dec`,
/// `from_int` or `scaled` rather than by hand.
///
/// The scale is kept: `dec("1.50")` shows as `1.50`, and `a + b` has the larger scale of the two.
/// `==` and `<` compare numerically (`1.5 == 1.50`). Because the derived hash still sees the
/// scale, `normalize` values before using them as map keys or in `unique`.
pub struct Dec { neg: bool, mag: [int], scale: int }

/// How `div` and `round` drop digits. `HalfEven` (banker's rounding) is the default for `/` and
/// for `round(d, places)`; it has no upward bias over many roundings.
pub enum Round {
  HalfEven,  // to nearest; a tie goes to the even neighbour (2.5 -> 2, 3.5 -> 4)
  HalfUp,    // to nearest; a tie goes away from zero (2.5 -> 3, -2.5 -> -3)
  HalfDown,  // to nearest; a tie goes toward zero (2.5 -> 2, -2.5 -> -2)
  Down,      // toward zero, i.e. truncate (2.9 -> 2, -2.9 -> -2)
  Up,        // away from zero (2.1 -> 3, -2.1 -> -3)
  Floor,     // toward negative infinity (2.9 -> 2, -2.1 -> -3)
  Ceiling,   // toward positive infinity (2.1 -> 3, -2.9 -> -2)
}

/// Why parsing or a conversion failed. `at` is a 0-based char index into the input.
pub enum NumErr {
  BadChar(at: int, c: char),  // not part of a number
  NoDigits,                   // "", "-", ".", "1e"
  ExpRange(at: int),          // an exponent beyond +-MAX_EXP
  Overflow,                   // `to_int` of a value outside the 64-bit range
}

/// A one-line description of an error, e.g. `bad char 'x' at 3`.
pub fn message(e: NumErr): str
fn message(BadChar(at, c)): str = "bad char '{c}' at {at}"
fn message(NoDigits): str = "no digits"
fn message(ExpRange(at)): str = "exponent out of range at {at} (limit {MAX_EXP})"
fn message(Overflow): str = "value does not fit in a 64-bit int"

/// The largest exponent magnitude `dec` accepts (`1e1000`, `1e-1000`). Arithmetic itself has no
/// limit; this only stops a short string from asking for a huge number.
pub let MAX_EXP = 1000

/// The number of fraction digits `a / b` computes before rounding (half-even).
pub let DIV_PLACES = 18

let BASE = 1_000_000_000  // limb base, 10^9: a limb product fits an int with room for carries
let POW10 = [1, 10, 100, 1000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000]

// ---- limb arithmetic on magnitudes (little-endian base 10^9, no leading zeros) ----

fn trim(xs: [int]): [int] {
  var n = xs.len()
  while n > 0 && xs[n - 1] == 0 { n -= 1 }
  if n == xs.len() { xs } else { xs.take(n) }
}

fn mag_cmp(a: [int], b: [int]): int {
  if a.len() != b.len() { return a.len() - b.len() }
  var i = a.len() - 1
  while i >= 0 {
    if a[i] != b[i] { return a[i] - b[i] }
    i -= 1
  }
  0
}

fn mag_add(a: [int], b: [int]): [int] {
  var out: [int] = []
  var carry = 0
  for i in 0..imax(a.len(), b.len()) {
    let s = (a.get(i) else 0) + (b.get(i) else 0) + carry
    out.push(s % BASE)
    carry = s / BASE
  }
  if carry > 0 { out.push(carry) }
  out
}

// a - b, for a >= b
fn mag_sub(a: [int], b: [int]): [int] {
  var out: [int] = []
  var borrow = 0
  for i in 0..a.len() {
    var s = a[i] - (b.get(i) else 0) - borrow
    borrow = 0
    if s < 0 {
      s += BASE
      borrow = 1
    }
    out.push(s)
  }
  trim(out)
}

// a * k for 0 <= k <= BASE
fn mag_mul_small(a: [int], k: int): [int] {
  if k == 0 { return [] }
  var out: [int] = []
  var carry = 0
  for x in a {
    let p = x * k + carry
    out.push(p % BASE)
    carry = p / BASE
  }
  while carry > 0 {
    out.push(carry % BASE)
    carry /= BASE
  }
  out
}

fn mag_mul(a: [int], b: [int]): [int] {
  if a.len() == 0 || b.len() == 0 { return [] }
  var out: [int] = []
  for _ in 0..a.len() + b.len() { out.push(0) }
  for i in 0..a.len() {
    var carry = 0
    let x = a[i]
    for j in 0..b.len() {
      let t = out[i + j] + x * b[j] + carry
      out[i + j] = t % BASE
      carry = t / BASE
    }
    var k = i + b.len()
    while carry > 0 {
      let t = out[k] + carry
      out[k] = t % BASE
      carry = t / BASE
      k += 1
    }
  }
  trim(out)
}

// a * 10^k, k >= 0
fn mag_shift(a: [int], k: int): [int] {
  if a.len() == 0 || k == 0 { return a }
  var out: [int] = []
  for _ in 0..k / 9 { out.push(0) }
  out + mag_mul_small(a, POW10[k % 9])
}

fn pow10(k: int): [int] = mag_shift([1], k)

// (a / b, a % b) for b != 0: schoolbook long division, one limb of quotient at a time, each
// found by binary search (b * q <= remainder).
fn mag_divmod(a: [int], b: [int]): ([int], [int]) {
  if mag_cmp(a, b) < 0 { return ([], a) }
  if b.len() == 1 { return mag_divmod_small(a, b[0]) }
  var q: [int] = []
  for _ in 0..a.len() { q.push(0) }
  var r: [int] = []
  var i = a.len() - 1
  while i >= 0 {
    r = trim([a[i]] + r)  // r = r * BASE + a[i]
    if mag_cmp(r, b) >= 0 {
      var lo = 1
      var hi = BASE - 1
      while lo < hi {
        let mid = (lo + hi + 1) / 2
        if mag_cmp(mag_mul_small(b, mid), r) <= 0 { lo = mid } else { hi = mid - 1 }
      }
      q[i] = lo
      r = mag_sub(r, mag_mul_small(b, lo))
    }
    i -= 1
  }
  (trim(q), r)
}

fn mag_divmod_small(a: [int], k: int): ([int], [int]) {
  var q: [int] = []
  for _ in 0..a.len() { q.push(0) }
  var rem = 0
  var i = a.len() - 1
  while i >= 0 {
    let cur = rem * BASE + a[i]  // < k * BASE <= 10^18
    q[i] = cur / k
    rem = cur % k
    i -= 1
  }
  (trim(q), trim([rem]))
}

fn imax(a: int, b: int): int = if a > b { a } else { b }

fn mag_is_odd(a: [int]): bool = a.len() > 0 && a[0] % 2 == 1

// The decimal digits of a magnitude ("0" for zero).
fn mag_str(a: [int]): str {
  if a.len() == 0 { return "0" }
  var parts = ["{a[a.len() - 1]}"]
  var i = a.len() - 2
  while i >= 0 {
    parts.push("{a[i]:09}")
    i -= 1
  }
  parts.join("")
}

// A magnitude from ASCII digits (already validated).
fn mag_of_digits(ds: [char]): [int] {
  var out: [int] = []
  var end = ds.len()
  while end > 0 {
    let start = imax(end - 9, 0)
    var v = 0
    for i in start..end { v = v * 10 + int(ds[i]) - int('0') }
    out.push(v)
    end = start
  }
  trim(out)
}

// ---- construction ----

fn make(neg: bool, mag: [int], scale: int): Dec = Dec { neg: neg && mag.len() > 0, mag, scale }

/// Zero (scale 0).
pub let ZERO = Dec { neg: false, mag: [], scale: 0 }

/// An integer as a `Dec` (scale 0). Every `int`, including the minimum, converts exactly.
pub fn from_int(n: int): Dec {
  var out: [int] = []
  var x = n
  while x != 0 {
    out.push((x % BASE).abs())  // `%` keeps the sign of `x`; `/` truncates toward 0
    x /= BASE
  }
  make(n < 0, out, 0)
}

/// `coef / 10^scale`, the natural way to load stored minor units: `scaled(1999, 2)` is `19.99`.
pub fn scaled(coef: int, scale: int): Dec
  requires scale >= 0
{
  Dec { scale, ..from_int(coef) }
}

/// Parses a decimal: an optional sign, digits with an optional `.` (`12`, `-0.50`, `.5`, `5.`),
/// and an optional exponent (`1.5e3`, `2E-4`). The scale is the number of fraction digits minus
/// the exponent (never below 0), so `dec("19.990")` keeps three places and `dec("1e3")` is
/// `1000`. No spaces, `_`, `,`, `inf` or `nan`.
pub fn dec(s: str): Dec!NumErr {
  let cs = s.chars()
  var i = 0
  var neg = false
  if i < cs.len() && (cs[i] == '-' || cs[i] == '+') {
    neg = cs[i] == '-'
    i += 1
  }
  var digits: [char] = []
  var frac = 0
  var seen_dot = false
  while i < cs.len() && (cs[i].is_digit() || (cs[i] == '.' && !seen_dot)) {
    if cs[i] == '.' {
      seen_dot = true
    } else {
      digits.push(cs[i])
      if seen_dot { frac += 1 }
    }
    i += 1
  }
  if digits.len() == 0 {
    if i < cs.len() { fail(BadChar(i, cs[i])) }
    fail(NoDigits)
  }
  var exp = 0
  if i < cs.len() && (cs[i] == 'e' || cs[i] == 'E') {
    i += 1
    let at = i
    var eneg = false
    if i < cs.len() && (cs[i] == '-' || cs[i] == '+') {
      eneg = cs[i] == '-'
      i += 1
    }
    if i >= cs.len() { fail(NoDigits) }
    while i < cs.len() && cs[i].is_digit() {
      exp = exp * 10 + int(cs[i]) - int('0')
      if exp > MAX_EXP { fail(ExpRange(at)) }
      i += 1
    }
    if eneg { exp = -exp }
  }
  if i < cs.len() { fail(BadChar(i, cs[i])) }
  let mag = mag_of_digits(digits)
  let scale = frac - exp
  if scale < 0 { make(neg, mag_shift(mag, -scale), 0) } else { make(neg, mag, scale) }
}

// ---- reading ----

/// The decimal text, keeping the scale: `19.99`, `-0.50`, `1000`, `0.000`. No exponent, no
/// grouping. `"{d}"` gives the same.
pub fn show(d: Dec): str {
  let ds = mag_str(d.mag)
  let sign = if d.neg { "-" } else { "" }
  if d.scale == 0 { return sign + ds }
  let padded = if ds.len() <= d.scale { "0".repeat(d.scale - ds.len() + 1) + ds } else { ds }
  let cut = padded.len() - d.scale
  "{sign}{padded[0..cut]}.{padded[cut..padded.len()]}"
}

/// The nearest `float` (through its decimal text, so `0.1` gives the float `0.1`).
pub fn to_float(d: Dec): float = float.parse(show(d))!

/// The integer part (truncated toward zero), or `Overflow` outside the 64-bit range.
pub fn to_int(d: Dec): int!NumErr {
  let m = mag_shift_down(d.mag, d.scale)
  var v = 0
  var i = m.len() - 1
  // accumulate negatively: the negative range is one larger
  while i >= 0 {
    if v < (-9_223_372_036_854_775_807 - 1 + m[i]) / BASE { fail(Overflow) }
    v = v * BASE - m[i]
    i -= 1
  }
  if d.neg { return v }
  if v == -9_223_372_036_854_775_807 - 1 { fail(Overflow) }
  -v
}

// a / 10^k, truncated
fn mag_shift_down(a: [int], k: int): [int] = if k == 0 { a } else { mag_divmod(a, pow10(k)).0 }

/// -1, 0 or 1.
pub fn sign(d: Dec): int = if d.mag.len() == 0 { 0 } else if d.neg { -1 } else { 1 }

pub fn is_zero(d: Dec): bool = d.mag.len() == 0

/// `-d` (unary minus can't be overloaded, so this is a function: `x.neg()`).
pub fn neg(d: Dec): Dec = make(!d.neg, d.mag, d.scale)

pub fn abs(d: Dec): Dec = Dec { neg: false, ..d }

/// The same value with trailing fraction zeros removed: `1.500` -> `1.5`, `2.00` -> `2`.
pub fn normalize(d: Dec): Dec {
  var m = d.mag
  var s = d.scale
  while s > 0 && m.len() > 0 && m[0] % 10 == 0 {
    m = mag_divmod_small(m, 10).0
    s -= 1
  }
  make(d.neg, m, if m.len() == 0 { 0 } else { s })
}

// ---- arithmetic ----

// Both coefficients at the larger scale.
fn align(a: Dec, b: Dec): ([int], [int], int) {
  let s = imax(a.scale, b.scale)
  (mag_shift(a.mag, s - a.scale), mag_shift(b.mag, s - b.scale), s)
}

/// `a + b`, exact; the result has the larger of the two scales.
pub fn add(a: Dec, b: Dec): Dec {
  let (x, y, s) = align(a, b)
  if a.neg == b.neg { return make(a.neg, mag_add(x, y), s) }
  let c = mag_cmp(x, y)
  if c >= 0 { make(a.neg, mag_sub(x, y), s) } else { make(b.neg, mag_sub(y, x), s) }
}

/// `a - b`, exact; the result has the larger of the two scales.
pub fn sub(a: Dec, b: Dec): Dec = add(a, neg(b))

/// `a * b`, exact; the scale is the sum of the scales (`1.5 * 2.25 == 3.375`). Use `round` to
/// bring it back to, say, cents.
pub fn mul(a: Dec, b: Dec): Dec = make(a.neg != b.neg, mag_mul(a.mag, b.mag), a.scale + b.scale)

/// `a / b`: computed to `DIV_PLACES` (18) fraction digits with `HalfEven`, then trailing zeros
/// are dropped down to the larger input scale, so an exact quotient stays short
/// (`10.00 / 4 == 2.50`, `1 / 8 == 0.125`, `1 / 3 == 0.333333333333333333`). For money, prefer
/// `div(a, b, places, mode)` and say what you want. Panics if `b` is zero, like `int` division.
pub fn div(a: Dec, b: Dec): Dec {
  let keep = imax(a.scale, b.scale)
  let q = div(a, b, imax(keep, DIV_PLACES), HalfEven)
  var m = q.mag
  var s = q.scale
  while s > keep && m.len() > 0 && m[0] % 10 == 0 {
    m = mag_divmod_small(m, 10).0
    s -= 1
  }
  make(q.neg, m, if m.len() == 0 { keep } else { s })
}

/// `a / b` rounded to exactly `places` fraction digits with `mode`:
/// `div(dec("10")?, dec("3")?, 2, HalfEven)` is `3.33`.
pub fn div(a: Dec, b: Dec, places: int, mode: Round): Dec
  requires !is_zero(b)
  requires places >= 0
{
  // a/b * 10^places = A * 10^(places + sb - sa) / B
  let e = places + b.scale - a.scale
  let n = if e >= 0 { mag_shift(a.mag, e) } else { a.mag }
  let d = if e >= 0 { b.mag } else { mag_shift(b.mag, -e) }
  let neg = a.neg != b.neg
  make(neg, round_quot(n, d, neg, mode), places)
}

/// The remainder of truncating division, with the sign of `a` (like `%` on `int`):
/// `dec("7.5")? % dec("2")? == dec("1.5")?`. Panics if `b` is zero.
pub fn mod(a: Dec, b: Dec): Dec
  requires !is_zero(b)
{
  let (x, y, s) = align(a, b)
  make(a.neg, mag_divmod(x, y).1, s)
}

/// `d` to the power `n` (n >= 0), exact: `pow(dec("1.1")?, 2) == dec("1.21")?`.
pub fn pow(d: Dec, n: int): Dec
  requires n >= 0
{
  var result = from_int(1)
  var base = d
  var k = n
  while k > 0 {
    if k % 2 == 1 { result = mul(result, base) }
    k /= 2
    if k > 0 { base = mul(base, base) }
  }
  result
}

/// `d` rounded to `places` fraction digits with banker's rounding (`HalfEven`):
/// `round(dec("2.345")?, 2) == dec("2.34")?`. Asking for more places than `d` has pads zeros.
pub fn round(d: Dec, places: int): Dec = round(d, places, HalfEven)

/// `d` with exactly `places` fraction digits, rounding with `mode` if digits are dropped.
pub fn round(d: Dec, places: int, mode: Round): Dec
  requires places >= 0
{
  if places >= d.scale { return make(d.neg, mag_shift(d.mag, places - d.scale), places) }
  make(d.neg, round_quot(d.mag, pow10(d.scale - places), d.neg, mode), places)
}

// n / d rounded to an integer magnitude; `neg` is the sign of the true quotient.
fn round_quot(n: [int], d: [int], neg: bool, mode: Round): [int] {
  let (q, r) = mag_divmod(n, d)
  if r.len() == 0 { return q }
  let half = mag_cmp(mag_add(r, r), d)  // compare the remainder with d / 2
  let bump = match mode {
    Down => false
    Up => true
    Floor => neg
    Ceiling => !neg
    HalfUp => half >= 0
    HalfDown => half > 0
    HalfEven => half > 0 || (half == 0 && mag_is_odd(q))
  }
  if bump { mag_add(q, [1]) } else { q }
}

/// Numeric order (negative, 0 or positive), ignoring scale, so `<`, `sort`, `min` and `max`
/// work: `dec("1.50")? == dec("1.5")?`.
pub fn cmp(a: Dec, b: Dec): int {
  let sa = sign(a)
  let sb = sign(b)
  if sa != sb { return sa - sb }
  let (x, y, _) = align(a, b)
  let c = mag_cmp(x, y)
  let unit = if c < 0 { -1 } else if c > 0 { 1 } else { 0 }
  if sa < 0 { -unit } else { unit }
}

/// Numeric equality, ignoring scale (`1.5 == 1.50`). This is what `==` uses.
pub fn eq(a: Dec, b: Dec): bool = cmp(a, b) == 0

/// The sum of a list (`ZERO` for an empty one). Core's `sum` covers only `int` and `float`.
pub fn sum(xs: [Dec]): Dec = xs.reduce(ZERO, (acc, x) => add(acc, x))

// ---- integers ----

/// The greatest common divisor, always >= 0; `gcd(0, 0) == 0`. Panics (overflow) only when the
/// answer is 2^63: `gcd(int.MIN, 0)` or `gcd(int.MIN, int.MIN)`.
pub fn gcd(a: int, b: int): int {
  var x = a
  var y = b
  while y != 0 {
    let t = x % y
    x = y
    y = t
  }
  x.abs()
}

/// The least common multiple, always >= 0; 0 if either is 0. Panics on overflow, like `*`.
pub fn lcm(a: int, b: int): int {
  if a == 0 || b == 0 { return 0 }
  (a / gcd(a, b) * b).abs()
}

/// `(a * b) mod m` in `0..m`, without overflowing for any `m > 0`.
pub fn mul_mod(a: int, b: int, m: int): int
  requires m > 0
{
  var x = norm_mod(a, m)
  var y = norm_mod(b, m)
  if m <= 3_037_000_499 { return x * y % m }  // both < m, so the product fits
  var r = 0
  while y > 0 {
    if y % 2 == 1 { r = add_mod(r, x, m) }
    x = add_mod(x, x, m)
    y /= 2
  }
  r
}

/// `base^exp mod m` in `0..m`, by square-and-multiply; never overflows. `exp >= 0`, `m > 0`;
/// a negative `base` is reduced first, and `pow_mod(b, 0, 1) == 0`.
pub fn pow_mod(base: int, exp: int, m: int): int
  requires exp >= 0 && m > 0
{
  var result = 1 % m
  var b = norm_mod(base, m)
  var e = exp
  while e > 0 {
    if e % 2 == 1 { result = mul_mod(result, b, m) }
    b = mul_mod(b, b, m)
    e /= 2
  }
  result
}

fn norm_mod(a: int, m: int): int {
  let r = a % m
  if r < 0 { r + m } else { r }
}

// (x + y) mod m for x, y in 0..m, without overflow
fn add_mod(x: int, y: int, m: int): int = if x >= m - y { x - (m - y) } else { x + y }

// ---- tests ----

fn d(s: str): Dec = dec(s)!

test "parse and show" {
  for s in [
    "0",
    "1",
    "-1",
    "19.99",
    "-0.50",
    "0.000",
    "1000",
    "123456789012345678901234567890.123",
  ] {
    assert show(d(s)) == s
  }
  assert "{d("+7")}" == "7"
  assert "{d(".5")}" == "0.5"
  assert "{d("5.")}" == "5"
  assert "{d("-0")}" == "0"  // no negative zero
  assert "{d("-0.00")}" == "0.00"
  assert "{d("007.10")}" == "7.10"
  assert "{d("1e3")}" == "1000"
  assert "{d("1.5E3")}" == "1500"
  assert "{d("1.5e1")}" == "15"
  assert "{d("2e-4")}" == "0.0002"
  assert "{d("12.5e-1")}" == "1.25"
  assert "{d("1e+2")}" == "100"
  assert "{d("0.000000000000000000000000000001")}" == "0.000000000000000000000000000001"
  assert d("19.99").scale == 2 && d("19.99").mag == [1999]
  assert d("1000000000").mag == [0, 1]
}

test "parse errors" {
  assert dec("") is err(NoDigits)
  assert dec("-") is err(NoDigits)
  assert dec(".") is err(NoDigits)
  assert dec("1e") is err(NoDigits)
  assert dec("1e-") is err(NoDigits)
  assert dec("abc") is err(BadChar(0, 'a'))
  assert dec("1.2.3") is err(BadChar(3, '.'))
  assert dec(" 1") is err(BadChar(0, ' '))
  assert dec("1 ") is err(BadChar(1, ' '))
  assert dec("1,000") is err(BadChar(1, ','))
  assert dec("--1") is err(BadChar(1, '-'))
  assert dec("1e5x") is err(BadChar(3, 'x'))
  assert dec("1e1001") is err(ExpRange(2))
  assert dec("1e-1001") is err(ExpRange(2))
  assert "{d("1e1000")}".len() == 1001
  assert message(BadChar(3, 'x')) == "bad char 'x' at 3"
  assert message(Overflow) == "value does not fit in a 64-bit int"
}

test "float traps are exact" {
  assert d("0.1") + d("0.2") == d("0.3")
  assert "{d("0.1") + d("0.2")}" == "0.3"
  assert 0.1 + 0.2 != 0.3  // the float version, for contrast
  var total = ZERO
  for _ in 0..10 { total = total + d("0.1") }
  assert total == from_int(1) && "{total}" == "1.0"
  assert d("1.1") * d("1.1") == d("1.21")
  assert d("3") * d("0.1") == d("0.3")
  assert d("1.0") - d("0.9") == d("0.1")
  assert d("100") - d("99.99") == d("0.01")
  assert sum([d("19.99"), d("5.01"), d("0.10")]) == d("25.10")
  assert "{sum([])}" == "0"
}

test "add, sub, mul: signs and scales" {
  assert "{d("1.5") + d("2.25")}" == "3.75"
  assert "{d("1.50") + d("2")}" == "3.50"  // the larger scale wins
  assert "{d("-1.5") + d("2.25")}" == "0.75"
  assert "{d("1.5") + d("-2.25")}" == "-0.75"
  assert "{d("-1.5") + d("-2.25")}" == "-3.75"
  assert "{d("2.25") - d("2.25")}" == "0.00"
  assert "{d("-3") - d("-5")}" == "2"
  assert "{d("1.5") * d("2.25")}" == "3.375"  // scales add
  assert "{d("-1.5") * d("2")}" == "-3.0"
  assert "{d("-1.5") * d("-2")}" == "3.0"
  assert "{d("0") * d("-2")}" == "0"
  assert "{neg(d("2.5"))} {neg(ZERO)} {abs(d("-2.5"))}" == "-2.5 0 2.5"
  assert "{pow(d("1.1"), 2)} {pow(d("2"), 0)} {pow(d("-0.5"), 3)}" == "1.21 1 -0.125"
  assert "{pow(d("2"), 100)}" == "1267650600228229401496703205376"
}

test "no overflow: big coefficients stay exact" {
  // one past int's maximum, and products far beyond 64 bits
  let big = from_int(9_223_372_036_854_775_807)
  assert "{big + from_int(1)}" == "9223372036854775808"
  assert "{big * big}" == "85070591730234615847396907784232501249"
  assert "{from_int(-9_223_372_036_854_775_807 - 1)}" == "-9223372036854775808"
  assert "{d("99999999999999999999.99") + d("0.01")}" == "100000000000000000000.00"
  assert d("12345678901234567890.123") * d("1000") - d("12345678901234567890123") == ZERO
  // limb boundaries
  assert "{d("999999999") + d("1")}" == "1000000000"
  assert "{d("1000000000") - d("1")}" == "999999999"
  assert "{d("999999999999999999") * d("999999999999999999")}" ==
    "999999999999999998000000000000000001"
  // conversion back to int is where the 64-bit range applies
  assert to_int(big) is ok(9_223_372_036_854_775_807)
  assert to_int(big + from_int(1)) is err(Overflow)
  assert to_int(neg(big) - from_int(1))? == -9_223_372_036_854_775_807 - 1
  assert to_int(neg(big) - from_int(2)) is err(Overflow)
  assert to_int(d("-12.99")) is ok(-12)
  assert to_int(d("0.5")) is ok(0)
  assert to_int(d("1e30")) is err(Overflow)
}

test "division with an explicit scale and mode" {
  assert "{div(d("10"), d("3"), 2, HalfEven)}" == "3.33"
  assert "{div(d("20"), d("3"), 2, HalfEven)}" == "6.67"
  assert "{div(d("-20"), d("3"), 2, HalfEven)}" == "-6.67"
  assert "{div(d("1"), d("8"), 2, HalfEven)}" == "0.12"  // 0.125: tie to even
  assert "{div(d("3"), d("8"), 2, HalfEven)}" == "0.38"  // 0.375: tie to even
  assert "{div(d("1"), d("8"), 2, HalfUp)}" == "0.13"
  assert "{div(d("-1"), d("8"), 2, HalfUp)}" == "-0.13"
  assert "{div(d("1"), d("8"), 2, HalfDown)}" == "0.12"
  assert "{div(d("2"), d("3"), 0, Down)}" == "0"
  assert "{div(d("2"), d("3"), 0, Up)}" == "1"
  assert "{div(d("-2"), d("3"), 0, Floor)}" == "-1"
  assert "{div(d("-2"), d("3"), 0, Ceiling)}" == "0"
  assert "{div(d("1.00"), d("0.03"), 4, HalfEven)}" == "33.3333"
  assert "{div(d("7"), d("0.5"), 0, Down)}" == "14"
  assert "{div(d("123.456"), d("1"), 1, HalfEven)}" == "123.5"  // fewer places than the input
  assert "{div(d("6"), d("2"), 3, Down)}" == "3.000"
  // a multi-limb divisor
  assert "{div(d("1"), d("12345678901234567890"), 30, HalfEven)}" ==
    "0.000000000000000000081000000729"
  assert "{div(d("152415787532388367504953515625"), d("123456789012345"), 0, Down)}" ==
    "1234567890123463"
}

test "the / and % operators" {
  assert "{d("10.00") / d("4")}" == "2.50"  // exact: trimmed to the input scale
  assert "{d("1") / d("8")}" == "0.125"
  assert "{d("1") / d("3")}" == "0.333333333333333333"
  assert "{d("2") / d("3")}" == "0.666666666666666667"
  assert "{d("-1") / d("3")}" == "-0.333333333333333333"
  assert "{d("6") / d("3")}" == "2"
  assert "{d("0") / d("3.0")}" == "0.0"
  assert d("1") / d("3") * d("3") != d("1")  // 18 places, not infinite precision
  assert "{d("7.5") % d("2")}" == "1.5"
  assert "{d("-7.5") % d("2")}" == "-1.5"
  assert "{d("7") % d("-2")}" == "1"
  assert "{d("0.3") % d("0.1")}" == "0.0"
}

test "cross-checked against Python's decimal module" {
  // "a b a+b a-b a*b places mode div(a,b,places,mode) a%b", from Python's `decimal` at 500 digits
  let rows = [
    "-750476357633517326.0 -9.08 -750476357633517335.08 -750476357633517316.92 6814325327312337320.080 0 HalfEven 82651581237171512 -6.12",
    "1754640288995955206917007.86091 0.9603082462 1754640288995955206917008.8212182462 1754640288995955206917006.9006017538 1684995538637566903648229.927862095636042 20 HalfUp 1827163617452184705520659.37357979130097362690 0.3587517542",
    "-750829545519.2199351819 730573909.86579 -750098971609.3541451819 -751560119429.0857251819 -548536476712730654891.652736728237201 4 Down -1027.7256 -530140087.0536051819",
    "-200980329511.3 -964199182854.5749118625 -1165179512365.8749118625 763218853343.2749118625 193785069484638667134815.40519779625 9 Floor 0.208442750 -200980329511.3000000000",
    "1501392826566174073872884 403728195825623183.97 1501393230294369899496067.97 1501392422837978248249700.03 606154617095094232759778757536576477126469.48 9 Up 3718820.835626379 337365930064861568.60",
    "4 4 8 0 16 9 Ceiling 1.000000000 0",
    "976614537807.50752917034236671276 -72118.46563 976614465689.04189917034236671276 976614609925.97315917034236671276 -70431941978629067.2984375583891070381424388 2 HalfDown -13541809.71 50872.98285917034236671276",
    "-86313.3 36953.02 -49360.28 -123266.32 -3189537101.166 4 HalfEven -2.3358 -12407.26",
    "990592406871355693.8 -0.86666 990592406871355692.93334 990592406871355694.66666 -858506815339129125.588708 9 HalfUp -1143000031005648920.914776268 0.79280",
    "0.1 1038737653782541257614155485942036841209.0 1038737653782541257614155485942036841209.1 -1038737653782541257614155485942036841208.9 103873765378254125761415548594203684120.90 20 Down 0.00000000000000000000 0.1",
    "9.01 -7043955674868288983041393.7 -7043955674868288983041384.69 7043955674868288983041402.71 -63466040630563283737202957.237 9 Floor -0.000000001 9.01",
    "-1069887743256727838472609534857252214411.54728 626235165620323557.0 -1069887743256727838471983299691631890854.54728 -1069887743256727838473235770022872537968.54728 -670001328093531165773704156984155185673396869685998870603.274960 4 Up -1708444051041017071909.9690 -606791927936554098.54728",
    "4.85253888539336338750 -211566542930.95755 -211566542926.10501111460663661250 211566542935.81008888539336338750 -1026634876420.7159136683173904867006250 0 Ceiling 0 4.85253888539336338750",
    "211211639.53799 8876190162784088033786916147316407719438.16372651676122202972 8876190162784088033786916147316618931077.70171651676122202972 -8876190162784088033786916147316196507798.62573651676122202972 1874754677132605582412633457527286944109540908808.4906019052924377508490628 20 HalfDown 0.00000000000000000000 211211639.53799000000000000000",
  ]
  for row in rows {
    let [a, b, sum, diff, prod, places, mode, quot, rem] = row.split(" ") else fail("bad row")
    let m = [HalfEven, HalfUp, HalfDown, Down, Up, Floor, Ceiling].find(x => "{x}" == mode)!
    assert "{d(a) + d(b)}" == sum
    assert "{d(a) - d(b)}" == diff
    assert "{d(a) * d(b)}" == prod
    assert "{div(d(a), d(b), int.parse(places)!, m)}" == quot
    assert "{d(a) % d(b)}" == rem
  }
}

test "banker's rounding" {
  let cases = [
    ("0.5", "0"),
    ("1.5", "2"),
    ("2.5", "2"),
    ("3.5", "4"),
    ("-0.5", "0"),
    ("-1.5", "-2"),
    ("-2.5", "-2"),
    ("2.51", "3"),
    ("2.49", "2"),
  ]
  for (x, want) in cases { assert "{round(d(x), 0)}" == want }
  assert "{round(d("2.345"), 2)}" == "2.34"
  assert "{round(d("2.355"), 2)}" == "2.36"
  assert "{round(d("2.3450001"), 2)}" == "2.35"  // not a tie
  // rounding many ties: half-even has no drift, half-up does
  let ties = ["0.005", "0.015", "0.025", "0.035", "0.045", "0.055", "0.065", "0.075"]
  let exact = sum(ties.map(s => d(s)))
  assert "{exact}" == "0.320"
  assert "{sum(ties.map(s => round(d(s), 2)))}" == "0.32"
  assert "{sum(ties.map(s => round(d(s), 2, HalfUp)))}" == "0.36"
}

test "round: every mode" {
  let modes = [HalfEven, HalfUp, HalfDown, Down, Up, Floor, Ceiling]
  let table = [
    ("2.5", ["2", "3", "2", "2", "3", "2", "3"]),
    ("-2.5", ["-2", "-3", "-2", "-2", "-3", "-3", "-2"]),
    ("2.1", ["2", "2", "2", "2", "3", "2", "3"]),
    ("-2.9", ["-3", "-3", "-3", "-2", "-3", "-3", "-2"]),
    ("2.0", ["2", "2", "2", "2", "2", "2", "2"]),
    ("-0.1", ["0", "0", "0", "0", "-1", "-1", "0"]),
  ]
  for (x, wants) in table {
    for i, m in modes { assert "{round(d(x), 0, m)}" == wants[i] }
  }
  assert "{round(d("1.5"), 3)}" == "1.500"  // more places pads
  assert "{round(d("-0.004"), 2)}" == "0.00"
  assert "{round(d("999.995"), 2, HalfUp)}" == "1000.00"
}

test "comparison and Ord" {
  assert d("1.5") == d("1.50") && d("1.5") != d("1.51")
  assert d("0") == d("-0.000")
  assert d("-1") < d("0") && d("0") < d("0.001") && d("-2") < d("-1.5")
  assert d("10") > d("9.99") && d("1.10") >= d("1.1") && d("1.1") <= d("1.10")
  let xs = [d("3"), d("-1.5"), d("0.25"), d("2.50"), d("-10")]
  assert xs.sort().map(x => "{x}") == ["-10", "-1.5", "0.25", "2.50", "3"]
  assert xs.max() == some(d("3")) && xs.min() == some(d("-10"))
  assert sign(d("-0.1")) == -1 && sign(ZERO) == 0 && sign(d("5")) == 1
  assert is_zero(d("0.00")) && !is_zero(d("0.01"))
}

test "normalize, scaled, from_int, to_float" {
  assert "{normalize(d("1.500"))} {normalize(d("2.00"))} {normalize(d("0.000"))}" == "1.5 2 0"
  assert "{normalize(d("100"))}" == "100"  // only fraction zeros go
  assert "{scaled(1999, 2)} {scaled(-5, 3)} {scaled(0, 2)}" == "19.99 -0.005 0.00"
  assert "{from_int(-42)} {from_int(0)}" == "-42 0"
  assert to_float(d("0.1")) == 0.1 && to_float(d("-2.5")) == -2.5
  // normalized values work as map keys
  var m: {Dec: int} = {}
  m[normalize(d("1.50"))] = 1
  assert m.get(normalize(d("1.5"))) == some(1)
}

test "Data round trip" {
  let x = d("-12.345")
  let back: Dec = from_value(to_value(x))?
  assert back == x && "{back}" == "-12.345"
}

test "gcd and lcm" {
  assert (gcd(12, 18), gcd(-12, 18), gcd(12, -18), gcd(0, 5), gcd(5, 0), gcd(0, 0)) ==
    (6, 6, 6, 5, 5, 0)
  assert gcd(17, 31) == 1
  assert gcd(-9_223_372_036_854_775_807 - 1, 6) == 2
  assert (lcm(4, 6), lcm(-4, 6), lcm(0, 6), lcm(7, 1)) == (12, 12, 0, 7)
  assert lcm(1 << 31, 1 << 30) == 1 << 31
}

test "pow_mod" {
  assert pow_mod(2, 10, 1000) == 24
  assert pow_mod(3, 0, 7) == 1
  assert pow_mod(5, 3, 1) == 0
  assert pow_mod(-2, 3, 5) == 2  // -8 mod 5
  assert pow_mod(0, 0, 7) == 1
  // Fermat: a^(p-1) = 1 mod p, with a modulus near 2^61 that would overflow a naive multiply
  let p = (1 << 61) - 1  // a Mersenne prime
  assert pow_mod(3, p - 1, p) == 1
  assert pow_mod(123_456_789, p - 1, p) == 1
  assert pow_mod(2, 61, p) == 1
  let big = 9_223_372_036_854_775_783  // the largest prime below 2^63
  assert pow_mod(2, big - 1, big) == 1
  assert mul_mod(big - 1, big - 1, big) == 1  // (-1)^2
  assert mul_mod(-1, 5, 7) == 2
}