gizlang:natural

natural numbers of any size, for the integer and decimal types built on them (vm/bigint's Python int and JavaScript BigInt, db/decimal's wide NUMERIC). A natural is a Vec<u64> of 32-bit limbs, least significant first, with no zero limb on top: [] is 0. Each function takes and gives naturals in that form.

import * as Natural from "gizlang:natural";

Types

Division

type Division = { q: Vec<u64>; r: Vec<u64>; }

A quotient and a remainder.

• q: Vec<u64>
• r: Vec<u64>

Functions

trim

function trim(a: Vec<u64>): Vec<u64>

A without its zero limbs on top.

Effects: fail.

ofU64

function ofU64(x: u64): Vec<u64>

The natural of a u64.

Effects: fail.

compare

function compare(a: Vec<u64>, b: Vec<u64>): i64

-1, 0 or 1 as A is less than, equal to or greater than B.

Effects: fail.

add

function add(a: Vec<u64>, b: Vec<u64>): Vec<u64>

The sum of two natural numbers (little-endian 64-bit limbs).

Effects: fail.

sub

function sub(a: Vec<u64>, b: Vec<u64>): Vec<u64>

A - B for A >= B.

Effects: fail.

mul

function mul(a: Vec<u64>, b: Vec<u64>): Vec<u64>

The product of two natural numbers (little-endian 64-bit limbs).

Effects: fail.

mulAdd

function mulAdd(a: Vec<u64>, m: u64, add: u64): Vec<u64>

A * M + ADD for M and ADD below 2^32.

Effects: fail.

divSmall

function divSmall(a: Vec<u64>, d: u64): Division

A / D and A % D for 0 < D < 2^32.

Effects: fail.

divide

function divide(a: Vec<u64>, b: Vec<u64>): Division

A / B and A % B for B > 0, by Knuth's algorithm D.

Effects: fail.

shiftLeft

function shiftLeft(a: Vec<u64>, bits: i64): Vec<u64>

A * 2^BITS.

Effects: fail.

shiftRight

function shiftRight(a: Vec<u64>, bits: i64): Vec<u64>

A / 2^BITS, toward zero.

Effects: fail.

lowBitsSet

function lowBitsSet(a: Vec<u64>, bits: i64): bool

Whether any of the low BITS bits of A is set.

Effects: fail.

text

function text(a: Vec<u64>, radix: i64): string

A's digits in RADIX (2 to 36), lower case.

Effects: fail.