Merge pull request #5192 from ziglang/stage2-tests

add ZIR compare output test case to test suite

4 files changed, 3167 insertions, 2508 deletions

diff --git a/lib/std/math/big.zig b/lib/std/math/big.zig
index 8105beb506..ab651c05c6 100644
--- a/lib/std/math/big.zig
+++ b/lib/std/math/big.zig
@@ -1,7 +1,24 @@
-pub usingnamespace @import("big/int.zig");
-pub usingnamespace @import("big/rational.zig");
+const std = @import("../std.zig");
+const assert = std.debug.assert;
 
-test "math.big" {
-    _ = @import("big/int.zig");
-    _ = @import("big/rational.zig");
+pub const Rational = @import("big/rational.zig").Rational;
+pub const int = @import("big/int.zig");
+pub const Limb = usize;
+pub const DoubleLimb = std.meta.IntType(false, 2 * Limb.bit_count);
+pub const SignedDoubleLimb = std.meta.IntType(true, DoubleLimb.bit_count);
+pub const Log2Limb = std.math.Log2Int(Limb);
+
+comptime {
+    assert(std.math.floorPowerOfTwo(usize, Limb.bit_count) == Limb.bit_count);
+    assert(Limb.bit_count <= 64); // u128 set is unsupported
+    assert(Limb.is_signed == false);
+}
+
+test "" {
+    _ = int;
+    _ = Rational;
+    _ = Limb;
+    _ = DoubleLimb;
+    _ = SignedDoubleLimb;
+    _ = Log2Limb;
 }
diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig
index f5d65a6866..8ee1474275 100644
--- a/lib/std/math/big/int.zig
+++ b/lib/std/math/big/int.zig
@@ -1,293 +1,196 @@
 const std = @import("../../std.zig");
-const debug = std.debug;
-const testing = std.testing;
 const math = std.math;
+const Limb = std.math.big.Limb;
+const DoubleLimb = std.math.big.DoubleLimb;
+const SignedDoubleLimb = std.math.big.SignedDoubleLimb;
+const Log2Limb = std.math.big.Log2Limb;
+const Allocator = std.mem.Allocator;
 const mem = std.mem;
-const Allocator = mem.Allocator;
-const ArrayList = std.ArrayList;
 const maxInt = std.math.maxInt;
 const minInt = std.math.minInt;
+const assert = std.debug.assert;
 
-pub const Limb = usize;
-pub const DoubleLimb = std.meta.Int(false, 2 * Limb.bit_count);
-pub const SignedDoubleLimb = std.meta.Int(true, DoubleLimb.bit_count);
-pub const Log2Limb = math.Log2Int(Limb);
+/// Returns the number of limbs needed to store `scalar`, which must be a
+/// primitive integer value.
+pub fn calcLimbLen(scalar: var) usize {
+    const T = @TypeOf(scalar);
+    switch (@typeInfo(T)) {
+        .Int => |info| {
+            const UT = if (info.is_signed) std.meta.Int(false, info.bits - 1) else T;
+            return @sizeOf(UT) / @sizeOf(Limb);
+        },
+        .ComptimeInt => {
+            const w_value = if (scalar < 0) -scalar else scalar;
+            return @divFloor(math.log2(w_value), Limb.bit_count) + 1;
+        },
+        else => @compileError("parameter must be a primitive integer type"),
+    }
+}
 
-comptime {
-    debug.assert(math.floorPowerOfTwo(usize, Limb.bit_count) == Limb.bit_count);
-    debug.assert(Limb.bit_count <= 64); // u128 set is unsupported
-    debug.assert(Limb.is_signed == false);
+pub fn calcToStringLimbsBufferLen(a_len: usize, base: u8) usize {
+    if (math.isPowerOfTwo(base))
+        return 0;
+    return a_len + 2 + a_len + calcDivLimbsBufferLen(a_len, 1);
 }
 
-/// An arbitrary-precision big integer.
-///
-/// Memory is allocated by an Int as needed to ensure operations never overflow. The range of an
-/// Int is bounded only by available memory.
-pub const Int = struct {
-    const sign_bit: usize = 1 << (usize.bit_count - 1);
+pub fn calcDivLimbsBufferLen(a_len: usize, b_len: usize) usize {
+    return calcMulLimbsBufferLen(a_len, b_len, 2) * 4;
+}
 
-    /// Default number of limbs to allocate on creation of an Int.
-    pub const default_capacity = 4;
+pub fn calcMulLimbsBufferLen(a_len: usize, b_len: usize, aliases: usize) usize {
+    return aliases * math.max(a_len, b_len);
+}
+
+pub fn calcSetStringLimbsBufferLen(base: u8, string_len: usize) usize {
+    const limb_count = calcSetStringLimbCount(base, string_len);
+    return calcMulLimbsBufferLen(limb_count, limb_count, 2);
+}
+
+pub fn calcSetStringLimbCount(base: u8, string_len: usize) usize {
+    return (string_len + (Limb.bit_count / base - 1)) / (Limb.bit_count / base);
+}
 
-    /// Allocator used by the Int when requesting memory.
-    allocator: ?*Allocator,
+/// a + b * c + *carry, sets carry to the overflow bits
+pub fn addMulLimbWithCarry(a: Limb, b: Limb, c: Limb, carry: *Limb) Limb {
+    @setRuntimeSafety(false);
+    var r1: Limb = undefined;
 
+    // r1 = a + *carry
+    const c1: Limb = @boolToInt(@addWithOverflow(Limb, a, carry.*, &r1));
+
+    // r2 = b * c
+    const bc = @as(DoubleLimb, math.mulWide(Limb, b, c));
+    const r2 = @truncate(Limb, bc);
+    const c2 = @truncate(Limb, bc >> Limb.bit_count);
+
+    // r1 = r1 + r2
+    const c3: Limb = @boolToInt(@addWithOverflow(Limb, r1, r2, &r1));
+
+    // This never overflows, c1, c3 are either 0 or 1 and if both are 1 then
+    // c2 is at least <= maxInt(Limb) - 2.
+    carry.* = c1 + c2 + c3;
+
+    return r1;
+}
+
+/// A arbitrary-precision big integer, with a fixed set of mutable limbs.
+pub const Mutable = struct {
     /// Raw digits. These are:
     ///
     /// * Little-endian ordered
     /// * limbs.len >= 1
-    /// * Zero is represent as Int.len() == 1 with limbs[0] == 0.
+    /// * Zero is represented as limbs.len == 1 with limbs[0] == 0.
     ///
     /// Accessing limbs directly should be avoided.
+    /// These are allocated limbs; the `len` field tells the valid range.
     limbs: []Limb,
+    len: usize,
+    positive: bool,
 
-    /// High bit is the sign bit. If set, Int is negative, else Int is positive.
-    /// The remaining bits represent the number of limbs used by Int.
-    metadata: usize,
-
-    /// Creates a new Int. default_capacity limbs will be allocated immediately.
-    /// Int will be zeroed.
-    pub fn init(allocator: *Allocator) !Int {
-        return try Int.initCapacity(allocator, default_capacity);
-    }
-
-    /// Creates a new Int. Int will be set to `value`.
-    ///
-    /// This is identical to an `init`, followed by a `set`.
-    pub fn initSet(allocator: *Allocator, value: var) !Int {
-        var s = try Int.init(allocator);
-        try s.set(value);
-        return s;
+    pub fn toConst(self: Mutable) Const {
+        return .{
+            .limbs = self.limbs[0..self.len],
+            .positive = self.positive,
+        };
     }
 
-    /// Creates a new Int with a specific capacity. If capacity < default_capacity then the
-    /// default capacity will be used instead.
-    pub fn initCapacity(allocator: *Allocator, capacity: usize) !Int {
-        return Int{
+    /// Asserts that the allocator owns the limbs memory. If this is not the case,
+    /// use `toConst().toManaged()`.
+    pub fn toManaged(self: Mutable, allocator: *Allocator) Managed {
+        return .{
             .allocator = allocator,
-            .metadata = 1,
-            .limbs = block: {
-                var limbs = try allocator.alloc(Limb, math.max(default_capacity, capacity));
-                limbs[0] = 0;
-                break :block limbs;
-            },
+            .limbs = limbs,
+            .metadata = if (self.positive)
+                self.len & ~Managed.sign_bit
+            else
+                self.len | Managed.sign_bit,
         };
     }
 
-    /// Returns the number of limbs currently in use.
-    pub fn len(self: Int) usize {
-        return self.metadata & ~sign_bit;
-    }
-
-    /// Returns whether an Int is positive.
-    pub fn isPositive(self: Int) bool {
-        return self.metadata & sign_bit == 0;
-    }
-
-    /// Sets the sign of an Int.
-    pub fn setSign(self: *Int, positive: bool) void {
-        if (positive) {
-            self.metadata &= ~sign_bit;
-        } else {
-            self.metadata |= sign_bit;
-        }
-    }
-
-    /// Sets the length of an Int.
-    ///
-    /// If setLen is used, then the Int must be normalized to suit.
-    pub fn setLen(self: *Int, new_len: usize) void {
-        self.metadata &= sign_bit;
-        self.metadata |= new_len;
-    }
-
-    /// Returns an Int backed by a fixed set of limb values.
-    /// This is read-only and cannot be used as a result argument. If the Int tries to allocate
-    /// memory a runtime panic will occur.
-    pub fn initFixed(limbs: []const Limb) Int {
-        var self = Int{
-            .allocator = null,
-            .metadata = limbs.len,
-            // Cast away the const, invalid use to pass as a pointer argument.
-            .limbs = @intToPtr([*]Limb, @ptrToInt(limbs.ptr))[0..limbs.len],
+    /// `value` is a primitive integer type.
+    /// Asserts the value fits within the provided `limbs_buffer`.
+    /// Note: `calcLimbLen` can be used to figure out how big an array to allocate for `limbs_buffer`.
+    pub fn init(limbs_buffer: []Limb, value: var) Mutable {
+        limbs_buffer[0] = 0;
+        var self: Mutable = .{
+            .limbs = limbs_buffer,
+            .len = 1,
+            .positive = true,
         };
-
-        self.normalize(limbs.len);
+        self.set(value);
         return self;
     }
 
-    /// Ensures an Int has enough space allocated for capacity limbs. If the Int does not have
-    /// sufficient capacity, the exact amount will be allocated. This occurs even if the requested
-    /// capacity is only greater than the current capacity by one limb.
-    pub fn ensureCapacity(self: *Int, capacity: usize) !void {
-        self.assertWritable();
-        if (capacity <= self.limbs.len) {
-            return;
-        }
-
-        self.limbs = try self.allocator.?.realloc(self.limbs, capacity);
-    }
-
-    fn assertWritable(self: Int) void {
-        if (self.allocator == null) {
-            @panic("provided Int value is read-only but must be writable");
+    /// Copies the value of a Const to an existing Mutable so that they both have the same value.
+    /// Asserts the value fits in the limbs buffer.
+    pub fn copy(self: *Mutable, other: Const) void {
+        if (self.limbs.ptr != other.limbs.ptr) {
+            mem.copy(Limb, self.limbs[0..], other.limbs[0..other.limbs.len]);
         }
+        self.positive = other.positive;
+        self.len = other.limbs.len;
     }
 
-    /// Frees all memory associated with an Int.
-    pub fn deinit(self: Int) void {
-        self.assertWritable();
-        self.allocator.?.free(self.limbs);
-    }
-
-    /// Clones an Int and returns a new Int with the same value. The new Int is a deep copy and
-    /// can be modified separately from the original.
-    pub fn clone(other: Int) !Int {
-        return other.clone2(other.allocator.?);
-    }
-
-    pub fn clone2(other: Int, allocator: *Allocator) !Int {
-        return Int{
-            .allocator = allocator,
-            .metadata = other.metadata,
-            .limbs = block: {
-                var limbs = try allocator.alloc(Limb, other.len());
-                mem.copy(Limb, limbs[0..], other.limbs[0..other.len()]);
-                break :block limbs;
-            },
-        };
-    }
-
-    /// Copies the value of an Int to an existing Int so that they both have the same value.
-    /// Extra memory will be allocated if the receiver does not have enough capacity.
-    pub fn copy(self: *Int, other: Int) !void {
-        self.assertWritable();
-        if (self.limbs.ptr == other.limbs.ptr) {
-            return;
-        }
-
-        try self.ensureCapacity(other.len());
-        mem.copy(Limb, self.limbs[0..], other.limbs[0..other.len()]);
-        self.metadata = other.metadata;
-    }
-
-    /// Efficiently swap an Int with another. This swaps the limb pointers and a full copy is not
+    /// Efficiently swap an Mutable with another. This swaps the limb pointers and a full copy is not
     /// performed. The address of the limbs field will not be the same after this function.
-    pub fn swap(self: *Int, other: *Int) void {
-        self.assertWritable();
-        mem.swap(Int, self, other);
+    pub fn swap(self: *Mutable, other: *Mutable) void {
+        mem.swap(Mutable, self, other);
     }
 
-    pub fn dump(self: Int) void {
-        for (self.limbs) |limb| {
-            debug.warn("{x} ", .{limb});
+    pub fn dump(self: Mutable) void {
+        for (self.limbs[0..self.len]) |limb| {
+            std.debug.warn("{x} ", .{limb});
         }
-        debug.warn("\n", .{});
-    }
-
-    /// Negate the sign of an Int.
-    pub fn negate(self: *Int) void {
-        self.metadata ^= sign_bit;
-    }
-
-    /// Make an Int positive.
-    pub fn abs(self: *Int) void {
-        self.metadata &= ~sign_bit;
-    }
-
-    /// Returns true if an Int is odd.
-    pub fn isOdd(self: Int) bool {
-        return self.limbs[0] & 1 != 0;
-    }
-
-    /// Returns true if an Int is even.
-    pub fn isEven(self: Int) bool {
-        return !self.isOdd();
-    }
-
-    /// Returns the number of bits required to represent the absolute value an Int.
-    fn bitCountAbs(self: Int) usize {
-        return (self.len() - 1) * Limb.bit_count + (Limb.bit_count - @clz(Limb, self.limbs[self.len() - 1]));
+        std.debug.warn("capacity={} positive={}\n", .{ self.limbs.len, self.positive });
     }
 
-    /// Returns the number of bits required to represent the integer in twos-complement form.
-    ///
-    /// If the integer is negative the value returned is the number of bits needed by a signed
-    /// integer to represent the value. If positive the value is the number of bits for an
-    /// unsigned integer. Any unsigned integer will fit in the signed integer with bitcount
-    /// one greater than the returned value.
-    ///
-    /// e.g. -127 returns 8 as it will fit in an i8. 127 returns 7 since it fits in a u7.
-    fn bitCountTwosComp(self: Int) usize {
-        var bits = self.bitCountAbs();
-
-        // If the entire value has only one bit set (e.g. 0b100000000) then the negation in twos
-        // complement requires one less bit.
-        if (!self.isPositive()) block: {
-            bits += 1;
-
-            if (@popCount(Limb, self.limbs[self.len() - 1]) == 1) {
-                for (self.limbs[0 .. self.len() - 1]) |limb| {
-                    if (@popCount(Limb, limb) != 0) {
-                        break :block;
-                    }
-                }
-
-                bits -= 1;
-            }
-        }
-
-        return bits;
-    }
-
-    pub fn fitsInTwosComp(self: Int, is_signed: bool, bit_count: usize) bool {
-        if (self.eqZero()) {
-            return true;
-        }
-        if (!is_signed and !self.isPositive()) {
-            return false;
-        }
-
-        const req_bits = self.bitCountTwosComp() + @boolToInt(self.isPositive() and is_signed);
-        return bit_count >= req_bits;
+    /// Clones an Mutable and returns a new Mutable with the same value. The new Mutable is a deep copy and
+    /// can be modified separately from the original.
+    /// Asserts that limbs is big enough to store the value.
+    pub fn clone(other: Mutable, limbs: []Limb) Mutable {
+        mem.copy(Limb, limbs, other.limbs[0..other.len]);
+        return .{
+            .limbs = limbs,
+            .len = other.len,
+            .positive = other.positive,
+        };
     }
 
-    /// Returns whether self can fit into an integer of the requested type.
-    pub fn fits(self: Int, comptime T: type) bool {
-        return self.fitsInTwosComp(T.is_signed, T.bit_count);
+    pub fn negate(self: *Mutable) void {
+        self.positive = !self.positive;
     }
 
-    /// Returns the approximate size of the integer in the given base. Negative values accommodate for
-    /// the minus sign. This is used for determining the number of characters needed to print the
-    /// value. It is inexact and may exceed the given value by ~1-2 bytes.
-    pub fn sizeInBase(self: Int, base: usize) usize {
-        const bit_count = @as(usize, @boolToInt(!self.isPositive())) + self.bitCountAbs();
-        return (bit_count / math.log2(base)) + 1;
+    /// Modify to become the absolute value
+    pub fn abs(self: *Mutable) void {
+        self.positive = true;
     }
 
-    /// Sets an Int to value. Value must be an primitive integer type.
-    pub fn set(self: *Int, value: var) Allocator.Error!void {
-        self.assertWritable();
+    /// Sets the Mutable to value. Value must be an primitive integer type.
+    /// Asserts the value fits within the limbs buffer.
+    /// Note: `calcLimbLen` can be used to figure out how big the limbs buffer
+    /// needs to be to store a specific value.
+    pub fn set(self: *Mutable, value: var) void {
         const T = @TypeOf(value);
 
         switch (@typeInfo(T)) {
             .Int => |info| {
                 const UT = if (T.is_signed) std.meta.Int(false, T.bit_count - 1) else T;
 
-                try self.ensureCapacity(@sizeOf(UT) / @sizeOf(Limb));
-                self.metadata = 0;
-                self.setSign(value >= 0);
+                const needed_limbs = @sizeOf(UT) / @sizeOf(Limb);
+                assert(needed_limbs <= self.limbs.len); // value too big
+                self.len = 0;
+                self.positive = value >= 0;
 
                 var w_value: UT = if (value < 0) @intCast(UT, -value) else @intCast(UT, value);
 
                 if (info.bits <= Limb.bit_count) {
                     self.limbs[0] = @as(Limb, w_value);
-                    self.metadata += 1;
+                    self.len += 1;
                 } else {
                     var i: usize = 0;
                     while (w_value != 0) : (i += 1) {
                         self.limbs[i] = @truncate(Limb, w_value);
-                        self.metadata += 1;
+                        self.len += 1;
 
                         // TODO: shift == 64 at compile-time fails. Fails on u128 limbs.
                         w_value >>= Limb.bit_count / 2;
@@ -299,10 +202,10 @@ pub const Int = struct {
                 comptime var w_value = if (value < 0) -value else value;
 
                 const req_limbs = @divFloor(math.log2(w_value), Limb.bit_count) + 1;
-                try self.ensureCapacity(req_limbs);
+                assert(req_limbs <= self.limbs.len); // value too big
 
-                self.metadata = req_limbs;
-                self.setSign(value >= 0);
+                self.len = req_limbs;
+                self.positive = value >= 0;
 
                 if (w_value <= maxInt(Limb)) {
                     self.limbs[0] = w_value;
@@ -318,83 +221,8 @@ pub const Int = struct {
                     }
                 }
             },
-            else => {
-                @compileError("cannot set Int using type " ++ @typeName(T));
-            },
-        }
-    }
-
-    pub const ConvertError = error{
-        NegativeIntoUnsigned,
-        TargetTooSmall,
-    };
-
-    /// Convert self to type T.
-    ///
-    /// Returns an error if self cannot be narrowed into the requested type without truncation.
-    pub fn to(self: Int, comptime T: type) ConvertError!T {
-        switch (@typeInfo(T)) {
-            .Int => {
-                const UT = std.meta.Int(false, T.bit_count);
-
-                if (self.bitCountTwosComp() > T.bit_count) {
-                    return error.TargetTooSmall;
-                }
-
-                var r: UT = 0;
-
-                if (@sizeOf(UT) <= @sizeOf(Limb)) {
-                    r = @intCast(UT, self.limbs[0]);
-                } else {
-                    for (self.limbs[0..self.len()]) |_, ri| {
-                        const limb = self.limbs[self.len() - ri - 1];
-                        r <<= Limb.bit_count;
-                        r |= limb;
-                    }
-                }
-
-                if (!T.is_signed) {
-                    return if (self.isPositive()) @intCast(T, r) else error.NegativeIntoUnsigned;
-                } else {
-                    if (self.isPositive()) {
-                        return @intCast(T, r);
-                    } else {
-                        if (math.cast(T, r)) |ok| {
-                            return -ok;
-                        } else |_| {
-                            return minInt(T);
-                        }
-                    }
-                }
-            },
-            else => {
-                @compileError("cannot convert Int to type " ++ @typeName(T));
-            },
-        }
-    }
-
-    fn charToDigit(ch: u8, base: u8) !u8 {
-        const d = switch (ch) {
-            '0'...'9' => ch - '0',
-            'a'...'f' => (ch - 'a') + 0xa,
-            'A'...'F' => (ch - 'A') + 0xa,
-            else => return error.InvalidCharForDigit,
-        };
-
-        return if (d < base) d else return error.DigitTooLargeForBase;
-    }
-
-    fn digitToChar(d: u8, base: u8, uppercase: bool) !u8 {
-        if (d >= base) {
-            return error.DigitTooLargeForBase;
+            else => @compileError("cannot set Mutable using type " ++ @typeName(T)),
         }
-
-        const a: u8 = if (uppercase) 'A' else 'a';
-        return switch (d) {
-            0...9 => '0' + d,
-            0xa...0xf => (a - 0xa) + d,
-            else => unreachable,
-        };
     }
 
     /// Set self from the string representation `value`.
@@ -403,13 +231,25 @@ pub const Int = struct {
     /// not allowed (e.g. 0x43 should simply be 43).  Underscores in the input string are
     /// ignored and can be used as digit separators.
     ///
-    /// Returns an error if memory could not be allocated or `value` has invalid digits for the
-    /// requested base.
-    pub fn setString(self: *Int, base: u8, value: []const u8) !void {
-        self.assertWritable();
-        if (base < 2 or base > 16) {
-            return error.InvalidBase;
-        }
+    /// Asserts there is enough memory for the value in `self.limbs`. An upper bound on number of limbs can
+    /// be determined with `calcSetStringLimbCount`.
+    /// Asserts the base is in the range [2, 16].
+    ///
+    /// Returns an error if the value has invalid digits for the requested base.
+    ///
+    /// `limbs_buffer` is used for temporary storage. The size required can be found with
+    /// `calcSetStringLimbsBufferLen`.
+    ///
+    /// If `allocator` is provided, it will be used for temporary storage to improve
+    /// multiplication performance. `error.OutOfMemory` is handled with a fallback algorithm.
+    pub fn setString(
+        self: *Mutable,
+        base: u8,
+        value: []const u8,
+        limbs_buffer: []Limb,
+        allocator: ?*Allocator,
+    ) error{InvalidCharacter}!void {
+        assert(base >= 2 and base <= 16);
 
         var i: usize = 0;
         var positive = true;
@@ -418,633 +258,451 @@ pub const Int = struct {
             i += 1;
         }
 
-        const ap_base = Int.initFixed(([_]Limb{base})[0..]);
-        try self.set(0);
+        const ap_base: Const = .{ .limbs = &[_]Limb{base}, .positive = true };
+        self.set(0);
 
         for (value[i..]) |ch| {
             if (ch == '_') {
                 continue;
             }
-            const d = try charToDigit(ch, base);
-
-            const ap_d = Int.initFixed(([_]Limb{d})[0..]);
-
-            try self.mul(self.*, ap_base);
-            try self.add(self.*, ap_d);
-        }
-        self.setSign(positive);
-    }
-
-    /// Converts self to a string in the requested base. Memory is allocated from the provided
-    /// allocator and not the one present in self.
-    /// TODO make this call format instead of the other way around
-    pub fn toString(self: Int, allocator: *Allocator, base: u8, uppercase: bool) ![]const u8 {
-        if (base < 2 or base > 16) {
-            return error.InvalidBase;
-        }
+            const d = try std.fmt.charToDigit(ch, base);
+            const ap_d: Const = .{ .limbs = &[_]Limb{d}, .positive = true };
 
-        var digits = ArrayList(u8).init(allocator);
-        try digits.ensureCapacity(self.sizeInBase(base) + 1);
-        defer digits.deinit();
-
-        if (self.eqZero()) {
-            try digits.append('0');
-            return digits.toOwnedSlice();
+            self.mul(self.toConst(), ap_base, limbs_buffer, allocator);
+            self.add(self.toConst(), ap_d);
         }
-
-        // Power of two: can do a single pass and use masks to extract digits.
-        if (math.isPowerOfTwo(base)) {
-            const base_shift = math.log2_int(Limb, base);
-
-            for (self.limbs[0..self.len()]) |limb| {
-                var shift: usize = 0;
-                while (shift < Limb.bit_count) : (shift += base_shift) {
-                    const r = @intCast(u8, (limb >> @intCast(Log2Limb, shift)) & @as(Limb, base - 1));
-                    const ch = try digitToChar(r, base, uppercase);
-                    try digits.append(ch);
-                }
-            }
-
-            while (true) {
-                // always will have a non-zero digit somewhere
-                const c = digits.pop();
-                if (c != '0') {
-                    digits.append(c) catch unreachable;
-                    break;
-                }
-            }
-        } else {
-            // Non power-of-two: batch divisions per word size.
-            const digits_per_limb = math.log(Limb, base, maxInt(Limb));
-            var limb_base: Limb = 1;
-            var j: usize = 0;
-            while (j < digits_per_limb) : (j += 1) {
-                limb_base *= base;
-            }
-
-            var q = try self.clone2(allocator);
-            defer q.deinit();
-            q.abs();
-            var r = try Int.init(allocator);
-            defer r.deinit();
-            var b = try Int.initSet(allocator, limb_base);
-            defer b.deinit();
-
-            while (q.len() >= 2) {
-                try Int.divTrunc(&q, &r, q, b);
-
-                var r_word = r.limbs[0];
-                var i: usize = 0;
-                while (i < digits_per_limb) : (i += 1) {
-                    const ch = try digitToChar(@intCast(u8, r_word % base), base, uppercase);
-                    r_word /= base;
-                    try digits.append(ch);
-                }
-            }
-
-            {
-                debug.assert(q.len() == 1);
-
-                var r_word = q.limbs[0];
-                while (r_word != 0) {
-                    const ch = try digitToChar(@intCast(u8, r_word % base), base, uppercase);
-                    r_word /= base;
-                    try digits.append(ch);
-                }
-            }
-        }
-
-        if (!self.isPositive()) {
-            try digits.append('-');
-        }
-
-        var s = digits.toOwnedSlice();
-        mem.reverse(u8, s);
-        return s;
-    }
-
-    /// To allow `std.fmt.printf` to work with Int.
-    /// TODO make this non-allocating
-    /// TODO support read-only fixed integers
-    pub fn format(
-        self: Int,
-        comptime fmt: []const u8,
-        options: std.fmt.FormatOptions,
-        out_stream: var,
-    ) !void {
-        comptime var radix = 10;
-        comptime var uppercase = false;
-
-        if (fmt.len == 0 or comptime std.mem.eql(u8, fmt, "d")) {
-            radix = 10;
-            uppercase = false;
-        } else if (comptime std.mem.eql(u8, fmt, "b")) {
-            radix = 2;
-            uppercase = false;
-        } else if (comptime std.mem.eql(u8, fmt, "x")) {
-            radix = 16;
-            uppercase = false;
-        } else if (comptime std.mem.eql(u8, fmt, "X")) {
-            radix = 16;
-            uppercase = true;
-        } else {
-            @compileError("Unknown format string: '" ++ fmt ++ "'");
-        }
-
-        var buf: [4096]u8 = undefined;
-        var fba = std.heap.FixedBufferAllocator.init(&buf);
-        const str = self.toString(&fba.allocator, radix, uppercase) catch @panic("TODO make this non allocating");
-        return out_stream.writeAll(str);
-    }
-
-    /// Returns math.Order.lt, math.Order.eq, math.Order.gt if |a| < |b|, |a| ==
-    /// |b| or |a| > |b| respectively.
-    pub fn cmpAbs(a: Int, b: Int) math.Order {
-        if (a.len() < b.len()) {
-            return .lt;
-        }
-        if (a.len() > b.len()) {
-            return .gt;
-        }
-
-        var i: usize = a.len() - 1;
-        while (i != 0) : (i -= 1) {
-            if (a.limbs[i] != b.limbs[i]) {
-                break;
-            }
-        }
-
-        if (a.limbs[i] < b.limbs[i]) {
-            return .lt;
-        } else if (a.limbs[i] > b.limbs[i]) {
-            return .gt;
-        } else {
-            return .eq;
-        }
-    }
-
-    /// Returns math.Order.lt, math.Order.eq, math.Order.gt if a < b, a == b or a
-    /// > b respectively.
-    pub fn cmp(a: Int, b: Int) math.Order {
-        if (a.isPositive() != b.isPositive()) {
-            return if (a.isPositive()) .gt else .lt;
-        } else {
-            const r = cmpAbs(a, b);
-            return if (a.isPositive()) r else switch (r) {
-                .lt => math.Order.gt,
-                .eq => math.Order.eq,
-                .gt => math.Order.lt,
-            };
-        }
-    }
-
-    /// Returns true if a == 0.
-    pub fn eqZero(a: Int) bool {
-        return a.len() == 1 and a.limbs[0] == 0;
-    }
-
-    /// Returns true if |a| == |b|.
-    pub fn eqAbs(a: Int, b: Int) bool {
-        return cmpAbs(a, b) == .eq;
-    }
-
-    /// Returns true if a == b.
-    pub fn eq(a: Int, b: Int) bool {
-        return cmp(a, b) == .eq;
+        self.positive = positive;
     }
 
-    // Normalize a possible sequence of leading zeros.
-    //
-    // [1, 2, 3, 4, 0] -> [1, 2, 3, 4]
-    // [1, 2, 0, 0, 0] -> [1, 2]
-    // [0, 0, 0, 0, 0] -> [0]
-    fn normalize(r: *Int, length: usize) void {
-        debug.assert(length > 0);
-        debug.assert(length <= r.limbs.len);
-
-        var j = length;
-        while (j > 0) : (j -= 1) {
-            if (r.limbs[j - 1] != 0) {
-                break;
-            }
-        }
-
-        // Handle zero
-        r.setLen(if (j != 0) j else 1);
-    }
-
-    // Cannot be used as a result argument to any function.
-    fn readOnlyPositive(a: Int) Int {
-        return Int{
-            .allocator = null,
-            .metadata = a.len(),
-            .limbs = a.limbs,
-        };
+    /// r = a + scalar
+    ///
+    /// r and a may be aliases.
+    /// scalar is a primitive integer type.
+    ///
+    /// Asserts the result fits in `r`. An upper bound on the number of limbs needed by
+    /// r is `math.max(a.limbs.len, calcLimbLen(scalar)) + 1`.
+    pub fn addScalar(r: *Mutable, a: Const, scalar: var) void {
+        var limbs: [calcLimbLen(scalar)]Limb = undefined;
+        const operand = init(&limbs, scalar).toConst();
+        return add(r, a, operand);
     }
 
     /// r = a + b
     ///
     /// r, a and b may be aliases.
     ///
-    /// Returns an error if memory could not be allocated.
-    pub fn add(r: *Int, a: Int, b: Int) Allocator.Error!void {
-        r.assertWritable();
+    /// Asserts the result fits in `r`. An upper bound on the number of limbs needed by
+    /// r is `math.max(a.limbs.len, b.limbs.len) + 1`.
+    pub fn add(r: *Mutable, a: Const, b: Const) void {
         if (a.eqZero()) {
-            try r.copy(b);
+            r.copy(b);
             return;
         } else if (b.eqZero()) {
-            try r.copy(a);
+            r.copy(a);
             return;
         }
 
-        if (a.isPositive() != b.isPositive()) {
-            if (a.isPositive()) {
+        if (a.limbs.len == 1 and b.limbs.len == 1 and a.positive == b.positive) {
+            if (!@addWithOverflow(Limb, a.limbs[0], b.limbs[0], &r.limbs[0])) {
+                r.len = 1;
+                r.positive = a.positive;
+                return;
+            }
+        }
+
+        if (a.positive != b.positive) {
+            if (a.positive) {
                 // (a) + (-b) => a - b
-                try r.sub(a, readOnlyPositive(b));
+                r.sub(a, b.abs());
             } else {
                 // (-a) + (b) => b - a
-                try r.sub(b, readOnlyPositive(a));
+                r.sub(b, a.abs());
             }
         } else {
-            if (a.len() >= b.len()) {
-                try r.ensureCapacity(a.len() + 1);
-                lladd(r.limbs[0..], a.limbs[0..a.len()], b.limbs[0..b.len()]);
-                r.normalize(a.len() + 1);
+            if (a.limbs.len >= b.limbs.len) {
+                lladd(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]);
+                r.normalize(a.limbs.len + 1);
             } else {
-                try r.ensureCapacity(b.len() + 1);
-                lladd(r.limbs[0..], b.limbs[0..b.len()], a.limbs[0..a.len()]);
-                r.normalize(b.len() + 1);
+                lladd(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]);
+                r.normalize(b.limbs.len + 1);
             }
 
-            r.setSign(a.isPositive());
+            r.positive = a.positive;
         }
     }
 
-    // Knuth 4.3.1, Algorithm A.
-    fn lladd(r: []Limb, a: []const Limb, b: []const Limb) void {
-        @setRuntimeSafety(false);
-        debug.assert(a.len != 0 and b.len != 0);
-        debug.assert(a.len >= b.len);
-        debug.assert(r.len >= a.len + 1);
-
-        var i: usize = 0;
-        var carry: Limb = 0;
-
-        while (i < b.len) : (i += 1) {
-            var c: Limb = 0;
-            c += @boolToInt(@addWithOverflow(Limb, a[i], b[i], &r[i]));
-            c += @boolToInt(@addWithOverflow(Limb, r[i], carry, &r[i]));
-            carry = c;
-        }
-
-        while (i < a.len) : (i += 1) {
-            carry = @boolToInt(@addWithOverflow(Limb, a[i], carry, &r[i]));
-        }
-
-        r[i] = carry;
-    }
-
     /// r = a - b
     ///
     /// r, a and b may be aliases.
     ///
-    /// Returns an error if memory could not be allocated.
-    pub fn sub(r: *Int, a: Int, b: Int) !void {
-        r.assertWritable();
-        if (a.isPositive() != b.isPositive()) {
-            if (a.isPositive()) {
+    /// Asserts the result fits in `r`. An upper bound on the number of limbs needed by
+    /// r is `math.max(a.limbs.len, b.limbs.len) + 1`. The +1 is not needed if both operands are positive.
+    pub fn sub(r: *Mutable, a: Const, b: Const) void {
+        if (a.positive != b.positive) {
+            if (a.positive) {
                 // (a) - (-b) => a + b
-                try r.add(a, readOnlyPositive(b));
+                r.add(a, b.abs());
             } else {
                 // (-a) - (b) => -(a + b)
-                try r.add(readOnlyPositive(a), b);
-                r.setSign(false);
+                r.add(a.abs(), b);
+                r.positive = false;
             }
         } else {
-            if (a.isPositive()) {
+            if (a.positive) {
                 // (a) - (b) => a - b
-                if (a.cmp(b) != .lt) {
-                    try r.ensureCapacity(a.len() + 1);
-                    llsub(r.limbs[0..], a.limbs[0..a.len()], b.limbs[0..b.len()]);
-                    r.normalize(a.len());
-                    r.setSign(true);
+                if (a.order(b) != .lt) {
+                    llsub(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]);
+                    r.normalize(a.limbs.len);
+                    r.positive = true;
                 } else {
-                    try r.ensureCapacity(b.len() + 1);
-                    llsub(r.limbs[0..], b.limbs[0..b.len()], a.limbs[0..a.len()]);
-                    r.normalize(b.len());
-                    r.setSign(false);
+                    llsub(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]);
+                    r.normalize(b.limbs.len);
+                    r.positive = false;
                 }
             } else {
                 // (-a) - (-b) => -(a - b)
-                if (a.cmp(b) == .lt) {
-                    try r.ensureCapacity(a.len() + 1);
-                    llsub(r.limbs[0..], a.limbs[0..a.len()], b.limbs[0..b.len()]);
-                    r.normalize(a.len());
-                    r.setSign(false);
+                if (a.order(b) == .lt) {
+                    llsub(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]);
+                    r.normalize(a.limbs.len);
+                    r.positive = false;
                 } else {
-                    try r.ensureCapacity(b.len() + 1);
-                    llsub(r.limbs[0..], b.limbs[0..b.len()], a.limbs[0..a.len()]);
-                    r.normalize(b.len());
-                    r.setSign(true);
+                    llsub(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]);
+                    r.normalize(b.limbs.len);
+                    r.positive = true;
                 }
             }
         }
     }
 
-    // Knuth 4.3.1, Algorithm S.
-    fn llsub(r: []Limb, a: []const Limb, b: []const Limb) void {
-        @setRuntimeSafety(false);
-        debug.assert(a.len != 0 and b.len != 0);
-        debug.assert(a.len > b.len or (a.len == b.len and a[a.len - 1] >= b[b.len - 1]));
-        debug.assert(r.len >= a.len);
-
-        var i: usize = 0;
-        var borrow: Limb = 0;
+    /// rma = a * b
+    ///
+    /// `rma` may alias with `a` or `b`.
+    /// `a` and `b` may alias with each other.
+    ///
+    /// Asserts the result fits in `rma`. An upper bound on the number of limbs needed by
+    /// rma is given by `a.limbs.len + b.limbs.len + 1`.
+    ///
+    /// `limbs_buffer` is used for temporary storage. The amount required is given by `calcMulLimbsBufferLen`.
+    pub fn mul(rma: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, allocator: ?*Allocator) void {
+        var buf_index: usize = 0;
 
-        while (i < b.len) : (i += 1) {
-            var c: Limb = 0;
-            c += @boolToInt(@subWithOverflow(Limb, a[i], b[i], &r[i]));
-            c += @boolToInt(@subWithOverflow(Limb, r[i], borrow, &r[i]));
-            borrow = c;
-        }
+        const a_copy = if (rma.limbs.ptr == a.limbs.ptr) blk: {
+            const start = buf_index;
+            mem.copy(Limb, limbs_buffer[buf_index..], a.limbs);
+            buf_index += a.limbs.len;
+            break :blk a.toMutable(limbs_buffer[start..buf_index]).toConst();
+        } else a;
 
-        while (i < a.len) : (i += 1) {
-            borrow = @boolToInt(@subWithOverflow(Limb, a[i], borrow, &r[i]));
-        }
+        const b_copy = if (rma.limbs.ptr == b.limbs.ptr) blk: {
+            const start = buf_index;
+            mem.copy(Limb, limbs_buffer[buf_index..], b.limbs);
+            buf_index += b.limbs.len;
+            break :blk b.toMutable(limbs_buffer[start..buf_index]).toConst();
+        } else b;
 
-        debug.assert(borrow == 0);
+        return rma.mulNoAlias(a_copy, b_copy, allocator);
     }
 
     /// rma = a * b
     ///
-    /// rma, a and b may be aliases. However, it is more efficient if rma does not alias a or b.
+    /// `rma` may not alias with `a` or `b`.
+    /// `a` and `b` may alias with each other.
     ///
-    /// Returns an error if memory could not be allocated.
-    pub fn mul(rma: *Int, a: Int, b: Int) !void {
-        rma.assertWritable();
-
-        var r = rma;
-        var aliased = rma.limbs.ptr == a.limbs.ptr or rma.limbs.ptr == b.limbs.ptr;
-
-        var sr: Int = undefined;
-        if (aliased) {
-            sr = try Int.initCapacity(rma.allocator.?, a.len() + b.len());
-            r = &sr;
-            aliased = true;
+    /// Asserts the result fits in `rma`. An upper bound on the number of limbs needed by
+    /// rma is given by `a.limbs.len + b.limbs.len + 1`.
+    ///
+    /// If `allocator` is provided, it will be used for temporary storage to improve
+    /// multiplication performance. `error.OutOfMemory` is handled with a fallback algorithm.
+    pub fn mulNoAlias(rma: *Mutable, a: Const, b: Const, allocator: ?*Allocator) void {
+        assert(rma.limbs.ptr != a.limbs.ptr); // illegal aliasing
+        assert(rma.limbs.ptr != b.limbs.ptr); // illegal aliasing
+
+        if (a.limbs.len == 1 and b.limbs.len == 1) {
+            if (!@mulWithOverflow(Limb, a.limbs[0], b.limbs[0], &rma.limbs[0])) {
+                rma.len = 1;
+                rma.positive = (a.positive == b.positive);
+                return;
+            }
         }
-        defer if (aliased) {
-            rma.swap(r);
-            r.deinit();
-        };
-
-        try r.ensureCapacity(a.len() + b.len() + 1);
 
-        mem.set(Limb, r.limbs[0 .. a.len() + b.len() + 1], 0);
+        mem.set(Limb, rma.limbs[0 .. a.limbs.len + b.limbs.len + 1], 0);
 
-        try llmulacc(rma.allocator.?, r.limbs, a.limbs[0..a.len()], b.limbs[0..b.len()]);
+        llmulacc(allocator, rma.limbs, a.limbs, b.limbs);
 
-        r.normalize(a.len() + b.len());
-        r.setSign(a.isPositive() == b.isPositive());
+        rma.normalize(a.limbs.len + b.limbs.len);
+        rma.positive = (a.positive == b.positive);
     }
 
-    // a + b * c + *carry, sets carry to the overflow bits
-    pub fn addMulLimbWithCarry(a: Limb, b: Limb, c: Limb, carry: *Limb) Limb {
-        @setRuntimeSafety(false);
-        var r1: Limb = undefined;
-
-        // r1 = a + *carry
-        const c1: Limb = @boolToInt(@addWithOverflow(Limb, a, carry.*, &r1));
-
-        // r2 = b * c
-        const bc = @as(DoubleLimb, math.mulWide(Limb, b, c));
-        const r2 = @truncate(Limb, bc);
-        const c2 = @truncate(Limb, bc >> Limb.bit_count);
+    /// q = a / b (rem r)
+    ///
+    /// a / b are floored (rounded towards 0).
+    /// q may alias with a or b.
+    ///
+    /// Asserts there is enough memory to store q and r.
+    /// The upper bound for r limb count is a.limbs.len.
+    /// The upper bound for q limb count is given by `a.limbs.len + b.limbs.len + 1`.
+    ///
+    /// If `allocator` is provided, it will be used for temporary storage to improve
+    /// multiplication performance. `error.OutOfMemory` is handled with a fallback algorithm.
+    ///
+    /// `limbs_buffer` is used for temporary storage. The amount required is given by `calcDivLimbsBufferLen`.
+    pub fn divFloor(
+        q: *Mutable,
+        r: *Mutable,
+        a: Const,
+        b: Const,
+        limbs_buffer: []Limb,
+        allocator: ?*Allocator,
+    ) void {
+        div(q, r, a, b, limbs_buffer, allocator);
 
-        // r1 = r1 + r2
-        const c3: Limb = @boolToInt(@addWithOverflow(Limb, r1, r2, &r1));
+        // Trunc -> Floor.
+        if (!q.positive) {
+            const one: Const = .{ .limbs = &[_]Limb{1}, .positive = true };
+            q.sub(q.toConst(), one);
+            r.add(q.toConst(), one);
+        }
+        r.positive = b.positive;
+    }
 
-        // This never overflows, c1, c3 are either 0 or 1 and if both are 1 then
-        // c2 is at least <= maxInt(Limb) - 2.
-        carry.* = c1 + c2 + c3;
+    /// q = a / b (rem r)
+    ///
+    /// a / b are truncated (rounded towards -inf).
+    /// q may alias with a or b.
+    ///
+    /// Asserts there is enough memory to store q and r.
+    /// The upper bound for r limb count is a.limbs.len.
+    /// The upper bound for q limb count is given by `calcQuotientLimbLen`. This accounts
+    /// for temporary space used by the division algorithm.
+    ///
+    /// If `allocator` is provided, it will be used for temporary storage to improve
+    /// multiplication performance. `error.OutOfMemory` is handled with a fallback algorithm.
+    ///
+    /// `limbs_buffer` is used for temporary storage. The amount required is given by `calcDivLimbsBufferLen`.
+    pub fn divTrunc(
+        q: *Mutable,
+        r: *Mutable,
+        a: Const,
+        b: Const,
+        limbs_buffer: []Limb,
+        allocator: ?*Allocator,
+    ) void {
+        div(q, r, a, b, limbs_buffer, allocator);
+        r.positive = a.positive;
+    }
 
-        return r1;
+    /// r = a << shift, in other words, r = a * 2^shift
+    ///
+    /// r and a may alias.
+    ///
+    /// Asserts there is enough memory to fit the result. The upper bound Limb count is
+    /// `a.limbs.len + (shift / (@sizeOf(Limb) * 8))`.
+    pub fn shiftLeft(r: *Mutable, a: Const, shift: usize) void {
+        llshl(r.limbs[0..], a.limbs[0..a.limbs.len], shift);
+        r.normalize(a.limbs.len + (shift / Limb.bit_count) + 1);
+        r.positive = a.positive;
     }
 
-    fn llmulDigit(acc: []Limb, y: []const Limb, xi: Limb) void {
-        @setRuntimeSafety(false);
-        if (xi == 0) {
+    /// r = a >> shift
+    /// r and a may alias.
+    ///
+    /// Asserts there is enough memory to fit the result. The upper bound Limb count is
+    /// `a.limbs.len - (shift / (@sizeOf(Limb) * 8))`.
+    pub fn shiftRight(r: *Mutable, a: Const, shift: usize) void {
+        if (a.limbs.len <= shift / Limb.bit_count) {
+            r.len = 1;
+            r.positive = true;
+            r.limbs[0] = 0;
             return;
         }
 
-        var carry: usize = 0;
-        var a_lo = acc[0..y.len];
-        var a_hi = acc[y.len..];
-
-        var j: usize = 0;
-        while (j < a_lo.len) : (j += 1) {
-            a_lo[j] = @call(.{ .modifier = .always_inline }, addMulLimbWithCarry, .{ a_lo[j], y[j], xi, &carry });
-        }
+        const r_len = llshr(r.limbs[0..], a.limbs[0..a.limbs.len], shift);
+        r.len = a.limbs.len - (shift / Limb.bit_count);
+        r.positive = a.positive;
+    }
 
-        j = 0;
-        while ((carry != 0) and (j < a_hi.len)) : (j += 1) {
-            carry = @boolToInt(@addWithOverflow(Limb, a_hi[j], carry, &a_hi[j]));
+    /// r = a | b
+    /// r may alias with a or b.
+    ///
+    /// a and b are zero-extended to the longer of a or b.
+    ///
+    /// Asserts that r has enough limbs to store the result. Upper bound is `math.max(a.limbs.len, b.limbs.len)`.
+    pub fn bitOr(r: *Mutable, a: Const, b: Const) void {
+        if (a.limbs.len > b.limbs.len) {
+            llor(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]);
+            r.len = a.limbs.len;
+        } else {
+            llor(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]);
+            r.len = b.limbs.len;
         }
     }
 
-    // Knuth 4.3.1, Algorithm M.
-    //
-    // r MUST NOT alias any of a or b.
-    fn llmulacc(allocator: *Allocator, r: []Limb, a: []const Limb, b: []const Limb) error{OutOfMemory}!void {
-        @setRuntimeSafety(false);
-
-        const a_norm = a[0..llnormalize(a)];
-        const b_norm = b[0..llnormalize(b)];
-        var x = a_norm;
-        var y = b_norm;
-        if (a_norm.len > b_norm.len) {
-            x = b_norm;
-            y = a_norm;
+    /// r = a & b
+    /// r may alias with a or b.
+    ///
+    /// Asserts that r has enough limbs to store the result. Upper bound is `math.min(a.limbs.len, b.limbs.len)`.
+    pub fn bitAnd(r: *Mutable, a: Const, b: Const) void {
+        if (a.limbs.len > b.limbs.len) {
+            lland(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]);
+            r.normalize(b.limbs.len);
+        } else {
+            lland(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]);
+            r.normalize(a.limbs.len);
         }
+    }
 
-        debug.assert(r.len >= x.len + y.len + 1);
-
-        // 48 is a pretty abitrary size chosen based on performance of a factorial program.
-        if (x.len <= 48) {
-            // Basecase multiplication
-            var i: usize = 0;
-            while (i < x.len) : (i += 1) {
-                llmulDigit(r[i..], y, x[i]);
-            }
+    /// r = a ^ b
+    /// r may alias with a or b.
+    ///
+    /// Asserts that r has enough limbs to store the result. Upper bound is `math.max(a.limbs.len, b.limbs.len)`.
+    pub fn bitXor(r: *Mutable, a: Const, b: Const) void {
+        if (a.limbs.len > b.limbs.len) {
+            llxor(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]);
+            r.normalize(a.limbs.len);
         } else {
-            // Karatsuba multiplication
-            const split = @divFloor(x.len, 2);
-            var x0 = x[0..split];
-            var x1 = x[split..x.len];
-            var y0 = y[0..split];
-            var y1 = y[split..y.len];
+            llxor(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]);
+            r.normalize(b.limbs.len);
+        }
+    }
 
-            var tmp = try allocator.alloc(Limb, x1.len + y1.len + 1);
-            defer allocator.free(tmp);
-            mem.set(Limb, tmp, 0);
+    /// rma may alias x or y.
+    /// x and y may alias each other.
+    /// Asserts that `rma` has enough limbs to store the result. Upper bound is
+    /// `math.min(x.limbs.len, y.limbs.len)`.
+    ///
+    /// `limbs_buffer` is used for temporary storage during the operation. When this function returns,
+    /// it will have the same length as it had when the function was called.
+    pub fn gcd(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.ArrayList(Limb)) !void {
+        const prev_len = limbs_buffer.items.len;
+        defer limbs_buffer.shrink(prev_len);
+        const x_copy = if (rma.limbs.ptr == x.limbs.ptr) blk: {
+            const start = limbs_buffer.items.len;
+            try limbs_buffer.appendSlice(x.limbs);
+            break :blk x.toMutable(limbs_buffer.items[start..]).toConst();
+        } else x;
+        const y_copy = if (rma.limbs.ptr == y.limbs.ptr) blk: {
+            const start = limbs_buffer.items.len;
+            try limbs_buffer.appendSlice(y.limbs);
+            break :blk y.toMutable(limbs_buffer.items[start..]).toConst();
+        } else y;
+
+        return gcdLehmer(rma, x_copy, y_copy, limbs_buffer);
+    }
+
+    /// rma may not alias x or y.
+    /// x and y may alias each other.
+    /// Asserts that `rma` has enough limbs to store the result. Upper bound is given by `calcGcdNoAliasLimbLen`.
+    ///
+    /// `limbs_buffer` is used for temporary storage during the operation.
+    pub fn gcdNoAlias(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.ArrayList(Limb)) !void {
+        assert(rma.limbs.ptr != x.limbs.ptr); // illegal aliasing
+        assert(rma.limbs.ptr != y.limbs.ptr); // illegal aliasing
+        return gcdLehmer(rma, x, y, allocator);
+    }
 
-            try llmulacc(allocator, tmp, x1, y1);
+    fn gcdLehmer(result: *Mutable, xa: Const, ya: Const, limbs_buffer: *std.ArrayList(Limb)) !void {
+        var x = try xa.toManaged(limbs_buffer.allocator);
+        defer x.deinit();
+        x.abs();
 
-            var length = llnormalize(tmp);
-            _ = llaccum(r[split..], tmp[0..length]);
-            _ = llaccum(r[split * 2 ..], tmp[0..length]);
+        var y = try ya.toManaged(limbs_buffer.allocator);
+        defer y.deinit();
+        y.abs();
 
-            mem.set(Limb, tmp[0..length], 0);
+        if (x.toConst().order(y.toConst()) == .lt) {
+            x.swap(&y);
+        }
 
-            try llmulacc(allocator, tmp, x0, y0);
+        var t_big = try Managed.init(limbs_buffer.allocator);
+        defer t_big.deinit();
 
-            length = llnormalize(tmp);
-            _ = llaccum(r[0..], tmp[0..length]);
-            _ = llaccum(r[split..], tmp[0..length]);
+        var r = try Managed.init(limbs_buffer.allocator);
+        defer r.deinit();
 
-            const x_cmp = llcmp(x1, x0);
-            const y_cmp = llcmp(y1, y0);
-            if (x_cmp * y_cmp == 0) {
-                return;
-            }
-            const x0_len = llnormalize(x0);
-            const x1_len = llnormalize(x1);
-            var j0 = try allocator.alloc(Limb, math.max(x0_len, x1_len));
-            defer allocator.free(j0);
-            if (x_cmp == 1) {
-                llsub(j0, x1[0..x1_len], x0[0..x0_len]);
-            } else {
-                llsub(j0, x0[0..x0_len], x1[0..x1_len]);
-            }
+        while (y.len() > 1) {
+            assert(x.isPositive() and y.isPositive());
+            assert(x.len() >= y.len());
 
-            const y0_len = llnormalize(y0);
-            const y1_len = llnormalize(y1);
-            var j1 = try allocator.alloc(Limb, math.max(y0_len, y1_len));
-            defer allocator.free(j1);
-            if (y_cmp == 1) {
-                llsub(j1, y1[0..y1_len], y0[0..y0_len]);
-            } else {
-                llsub(j1, y0[0..y0_len], y1[0..y1_len]);
-            }
-            const j0_len = llnormalize(j0);
-            const j1_len = llnormalize(j1);
-            if (x_cmp == y_cmp) {
-                mem.set(Limb, tmp[0..length], 0);
-                try llmulacc(allocator, tmp, j0, j1);
-
-                length = Int.llnormalize(tmp);
-                llsub(r[split..], r[split..], tmp[0..length]);
-            } else {
-                try llmulacc(allocator, r[split..], j0, j1);
-            }
-        }
-    }
+            var xh: SignedDoubleLimb = x.limbs[x.len() - 1];
+            var yh: SignedDoubleLimb = if (x.len() > y.len()) 0 else y.limbs[x.len() - 1];
 
-    // r = r + a
-    fn llaccum(r: []Limb, a: []const Limb) Limb {
-        @setRuntimeSafety(false);
-        debug.assert(r.len != 0 and a.len != 0);
-        debug.assert(r.len >= a.len);
+            var A: SignedDoubleLimb = 1;
+            var B: SignedDoubleLimb = 0;
+            var C: SignedDoubleLimb = 0;
+            var D: SignedDoubleLimb = 1;
 
-        var i: usize = 0;
-        var carry: Limb = 0;
+            while (yh + C != 0 and yh + D != 0) {
+                const q = @divFloor(xh + A, yh + C);
+                const qp = @divFloor(xh + B, yh + D);
+                if (q != qp) {
+                    break;
+                }
 
-        while (i < a.len) : (i += 1) {
-            var c: Limb = 0;
-            c += @boolToInt(@addWithOverflow(Limb, r[i], a[i], &r[i]));
-            c += @boolToInt(@addWithOverflow(Limb, r[i], carry, &r[i]));
-            carry = c;
-        }
+                var t = A - q * C;
+                A = C;
+                C = t;
+                t = B - q * D;
+                B = D;
+                D = t;
 
-        while ((carry != 0) and i < r.len) : (i += 1) {
-            carry = @boolToInt(@addWithOverflow(Limb, r[i], carry, &r[i]));
-        }
+                t = xh - q * yh;
+                xh = yh;
+                yh = t;
+            }
 
-        return carry;
-    }
+            if (B == 0) {
+                // t_big = x % y, r is unused
+                try r.divTrunc(&t_big, x.toConst(), y.toConst());
+                assert(t_big.isPositive());
 
-    /// Returns -1, 0, 1 if |a| < |b|, |a| == |b| or |a| > |b| respectively for limbs.
-    pub fn llcmp(a: []const Limb, b: []const Limb) i8 {
-        @setRuntimeSafety(false);
-        const a_len = llnormalize(a);
-        const b_len = llnormalize(b);
-        if (a_len < b_len) {
-            return -1;
-        }
-        if (a_len > b_len) {
-            return 1;
-        }
+                x.swap(&y);
+                y.swap(&t_big);
+            } else {
+                var storage: [8]Limb = undefined;
+                const Ap = fixedIntFromSignedDoubleLimb(A, storage[0..2]).toConst();
+                const Bp = fixedIntFromSignedDoubleLimb(B, storage[2..4]).toConst();
+                const Cp = fixedIntFromSignedDoubleLimb(C, storage[4..6]).toConst();
+                const Dp = fixedIntFromSignedDoubleLimb(D, storage[6..8]).toConst();
 
-        var i: usize = a_len - 1;
-        while (i != 0) : (i -= 1) {
-            if (a[i] != b[i]) {
-                break;
-            }
-        }
+                // t_big = Ax + By
+                try r.mul(x.toConst(), Ap);
+                try t_big.mul(y.toConst(), Bp);
+                try t_big.add(r.toConst(), t_big.toConst());
 
-        if (a[i] < b[i]) {
-            return -1;
-        } else if (a[i] > b[i]) {
-            return 1;
-        } else {
-            return 0;
-        }
-    }
+                // u = Cx + Dy, r as u
+                try x.mul(x.toConst(), Cp);
+                try r.mul(y.toConst(), Dp);
+                try r.add(x.toConst(), r.toConst());
 
-    // returns the min length the limb could be.
-    fn llnormalize(a: []const Limb) usize {
-        @setRuntimeSafety(false);
-        var j = a.len;
-        while (j > 0) : (j -= 1) {
-            if (a[j - 1] != 0) {
-                break;
+                x.swap(&t_big);
+                y.swap(&r);
             }
         }
 
-        // Handle zero
-        return if (j != 0) j else 1;
-    }
-
-    /// q = a / b (rem r)
-    ///
-    /// a / b are floored (rounded towards 0).
-    pub fn divFloor(q: *Int, r: *Int, a: Int, b: Int) !void {
-        try div(q, r, a, b);
+        // euclidean algorithm
+        assert(x.toConst().order(y.toConst()) != .lt);
 
-        // Trunc -> Floor.
-        if (!q.isPositive()) {
-            const one = Int.initFixed(([_]Limb{1})[0..]);
-            try q.sub(q.*, one);
-            try r.add(q.*, one);
+        while (!y.toConst().eqZero()) {
+            try t_big.divTrunc(&r, x.toConst(), y.toConst());
+            x.swap(&y);
+            y.swap(&r);
         }
-        r.setSign(b.isPositive());
-    }
 
-    /// q = a / b (rem r)
-    ///
-    /// a / b are truncated (rounded towards -inf).
-    pub fn divTrunc(q: *Int, r: *Int, a: Int, b: Int) !void {
-        try div(q, r, a, b);
-        r.setSign(a.isPositive());
+        result.copy(x.toConst());
     }
 
-    // Truncates by default.
-    fn div(quo: *Int, rem: *Int, a: Int, b: Int) !void {
-        quo.assertWritable();
-        rem.assertWritable();
-
-        if (b.eqZero()) {
-            @panic("division by zero");
-        }
-        if (quo == rem) {
-            @panic("quo and rem cannot be same variable");
-        }
+    /// Truncates by default.
+    fn div(quo: *Mutable, rem: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, allocator: ?*Allocator) void {
+        assert(!b.eqZero()); // division by zero
+        assert(quo != rem); // illegal aliasing
 
-        if (a.cmpAbs(b) == .lt) {
+        if (a.orderAbs(b) == .lt) {
             // quo may alias a so handle rem first
-            try rem.copy(a);
-            rem.setSign(a.isPositive() == b.isPositive());
+            rem.copy(a);
+            rem.positive = a.positive == b.positive;
 
-            quo.metadata = 1;
+            quo.positive = true;
+            quo.len = 1;
             quo.limbs[0] = 0;
             return;
         }
@@ -1053,118 +711,108 @@ pub const Int = struct {
         // algorithms.
         const a_zero_limb_count = blk: {
             var i: usize = 0;
-            while (i < a.len()) : (i += 1) {
+            while (i < a.limbs.len) : (i += 1) {
                 if (a.limbs[i] != 0) break;
             }
             break :blk i;
         };
         const b_zero_limb_count = blk: {
             var i: usize = 0;
-            while (i < b.len()) : (i += 1) {
+            while (i < b.limbs.len) : (i += 1) {
                 if (b.limbs[i] != 0) break;
             }
             break :blk i;
         };
 
-        const ab_zero_limb_count = std.math.min(a_zero_limb_count, b_zero_limb_count);
-
-        if (b.len() - ab_zero_limb_count == 1) {
-            try quo.ensureCapacity(a.len());
+        const ab_zero_limb_count = math.min(a_zero_limb_count, b_zero_limb_count);
 
-            lldiv1(quo.limbs[0..], &rem.limbs[0], a.limbs[ab_zero_limb_count..a.len()], b.limbs[b.len() - 1]);
-            quo.normalize(a.len() - ab_zero_limb_count);
-            quo.setSign(a.isPositive() == b.isPositive());
+        if (b.limbs.len - ab_zero_limb_count == 1) {
+            lldiv1(quo.limbs[0..], &rem.limbs[0], a.limbs[ab_zero_limb_count..a.limbs.len], b.limbs[b.limbs.len - 1]);
+            quo.normalize(a.limbs.len - ab_zero_limb_count);
+            quo.positive = (a.positive == b.positive);
 
-            rem.metadata = 1;
+            rem.len = 1;
+            rem.positive = true;
         } else {
             // x and y are modified during division
-            var x = try Int.initCapacity(quo.allocator.?, a.len());
-            defer x.deinit();
-            try x.copy(a);
-
-            var y = try Int.initCapacity(quo.allocator.?, b.len());
-            defer y.deinit();
-            try y.copy(b);
-
-            // x may grow one limb during normalization
-            try quo.ensureCapacity(a.len() + y.len());
+            const sep_len = calcMulLimbsBufferLen(a.limbs.len, b.limbs.len, 2);
+            const x_limbs = limbs_buffer[0 * sep_len ..][0..sep_len];
+            const y_limbs = limbs_buffer[1 * sep_len ..][0..sep_len];
+            const t_limbs = limbs_buffer[2 * sep_len ..][0..sep_len];
+            const mul_limbs_buf = limbs_buffer[3 * sep_len ..][0..sep_len];
+
+            var x: Mutable = .{
+                .limbs = x_limbs,
+                .positive = a.positive,
+                .len = a.limbs.len - ab_zero_limb_count,
+            };
+            var y: Mutable = .{
+                .limbs = y_limbs,
+                .positive = b.positive,
+                .len = b.limbs.len - ab_zero_limb_count,
+            };
 
             // Shrink x, y such that the trailing zero limbs shared between are removed.
-            if (ab_zero_limb_count != 0) {
-                std.mem.copy(Limb, x.limbs[0..], x.limbs[ab_zero_limb_count..]);
-                std.mem.copy(Limb, y.limbs[0..], y.limbs[ab_zero_limb_count..]);
-                x.metadata -= ab_zero_limb_count;
-                y.metadata -= ab_zero_limb_count;
-            }
+            mem.copy(Limb, x.limbs, a.limbs[ab_zero_limb_count..a.limbs.len]);
+            mem.copy(Limb, y.limbs, b.limbs[ab_zero_limb_count..b.limbs.len]);
 
-            try divN(quo.allocator.?, quo, rem, &x, &y);
-            quo.setSign(a.isPositive() == b.isPositive());
+            divN(quo, rem, &x, &y, t_limbs, mul_limbs_buf, allocator);
+            quo.positive = (a.positive == b.positive);
         }
 
         if (ab_zero_limb_count != 0) {
-            try rem.shiftLeft(rem.*, ab_zero_limb_count * Limb.bit_count);
-        }
-    }
-
-    // Knuth 4.3.1, Exercise 16.
-    fn lldiv1(quo: []Limb, rem: *Limb, a: []const Limb, b: Limb) void {
-        @setRuntimeSafety(false);
-        debug.assert(a.len > 1 or a[0] >= b);
-        debug.assert(quo.len >= a.len);
-
-        rem.* = 0;
-        for (a) |_, ri| {
-            const i = a.len - ri - 1;
-            const pdiv = ((@as(DoubleLimb, rem.*) << Limb.bit_count) | a[i]);
-
-            if (pdiv == 0) {
-                quo[i] = 0;
-                rem.* = 0;
-            } else if (pdiv < b) {
-                quo[i] = 0;
-                rem.* = @truncate(Limb, pdiv);
-            } else if (pdiv == b) {
-                quo[i] = 1;
-                rem.* = 0;
-            } else {
-                quo[i] = @truncate(Limb, @divTrunc(pdiv, b));
-                rem.* = @truncate(Limb, pdiv - (quo[i] *% b));
-            }
+            rem.shiftLeft(rem.toConst(), ab_zero_limb_count * Limb.bit_count);
         }
     }
 
-    // Handbook of Applied Cryptography, 14.20
-    //
-    // x = qy + r where 0 <= r < y
-    fn divN(allocator: *Allocator, q: *Int, r: *Int, x: *Int, y: *Int) !void {
-        debug.assert(y.len() >= 2);
-        debug.assert(x.len() >= y.len());
-        debug.assert(q.limbs.len >= x.len() + y.len() - 1);
-        debug.assert(default_capacity >= 3); // see 3.2
-
-        var tmp = try Int.init(allocator);
-        defer tmp.deinit();
+    /// Handbook of Applied Cryptography, 14.20
+    ///
+    /// x = qy + r where 0 <= r < y
+    fn divN(
+        q: *Mutable,
+        r: *Mutable,
+        x: *Mutable,
+        y: *Mutable,
+        tmp_limbs: []Limb,
+        mul_limb_buf: []Limb,
+        allocator: ?*Allocator,
+    ) void {
+        assert(y.len >= 2);
+        assert(x.len >= y.len);
+        assert(q.limbs.len >= x.len + y.len - 1);
+
+        // See 3.2
+        var backup_tmp_limbs: [3]Limb = undefined;
+        const t_limbs = if (tmp_limbs.len < 3) &backup_tmp_limbs else tmp_limbs;
+
+        var tmp: Mutable = .{
+            .limbs = t_limbs,
+            .len = 1,
+            .positive = true,
+        };
+        tmp.limbs[0] = 0;
 
         // Normalize so y > Limb.bit_count / 2 (i.e. leading bit is set) and even
-        var norm_shift = @clz(Limb, y.limbs[y.len() - 1]);
-        if (norm_shift == 0 and y.isOdd()) {
+        var norm_shift = @clz(Limb, y.limbs[y.len - 1]);
+        if (norm_shift == 0 and y.toConst().isOdd()) {
             norm_shift = Limb.bit_count;
         }
-        try x.shiftLeft(x.*, norm_shift);
-        try y.shiftLeft(y.*, norm_shift);
+        x.shiftLeft(x.toConst(), norm_shift);
+        y.shiftLeft(y.toConst(), norm_shift);
 
-        const n = x.len() - 1;
-        const t = y.len() - 1;
+        const n = x.len - 1;
+        const t = y.len - 1;
 
         // 1.
-        q.metadata = n - t + 1;
-        mem.set(Limb, q.limbs[0..q.len()], 0);
+        q.len = n - t + 1;
+        q.positive = true;
+        mem.set(Limb, q.limbs[0..q.len], 0);
 
         // 2.
-        try tmp.shiftLeft(y.*, Limb.bit_count * (n - t));
-        while (x.cmp(tmp) != .lt) {
+        tmp.shiftLeft(y.toConst(), Limb.bit_count * (n - t));
+        while (x.toConst().order(tmp.toConst()) != .lt) {
             q.limbs[n - t] += 1;
-            try x.sub(x.*, tmp);
+            x.sub(x.toConst(), tmp.toConst());
         }
 
         // 3.
@@ -1193,7 +841,7 @@ pub const Int = struct {
                 r.limbs[2] = carry;
                 r.normalize(3);
 
-                if (r.cmpAbs(tmp) != .gt) {
+                if (r.toConst().orderAbs(tmp.toConst()) != .gt) {
                     break;
                 }
 
@@ -1201,1748 +849,1284 @@ pub const Int = struct {
             }
 
             // 3.3
-            try tmp.set(q.limbs[i - t - 1]);
-            try tmp.mul(tmp, y.*);
-            try tmp.shiftLeft(tmp, Limb.bit_count * (i - t - 1));
-            try x.sub(x.*, tmp);
-
-            if (!x.isPositive()) {
-                try tmp.shiftLeft(y.*, Limb.bit_count * (i - t - 1));
-                try x.add(x.*, tmp);
+            tmp.set(q.limbs[i - t - 1]);
+            tmp.mul(tmp.toConst(), y.toConst(), mul_limb_buf, allocator);
+            tmp.shiftLeft(tmp.toConst(), Limb.bit_count * (i - t - 1));
+            x.sub(x.toConst(), tmp.toConst());
+
+            if (!x.positive) {
+                tmp.shiftLeft(y.toConst(), Limb.bit_count * (i - t - 1));
+                x.add(x.toConst(), tmp.toConst());
                 q.limbs[i - t - 1] -= 1;
             }
         }
 
         // Denormalize
-        q.normalize(q.len());
+        q.normalize(q.len);
 
-        try r.shiftRight(x.*, norm_shift);
-        r.normalize(r.len());
+        r.shiftRight(x.toConst(), norm_shift);
+        r.normalize(r.len);
     }
 
-    /// r = a << shift, in other words, r = a * 2^shift
-    pub fn shiftLeft(r: *Int, a: Int, shift: usize) !void {
-        r.assertWritable();
-
-        try r.ensureCapacity(a.len() + (shift / Limb.bit_count) + 1);
-        llshl(r.limbs[0..], a.limbs[0..a.len()], shift);
-        r.normalize(a.len() + (shift / Limb.bit_count) + 1);
-        r.setSign(a.isPositive());
-    }
-
-    fn llshl(r: []Limb, a: []const Limb, shift: usize) void {
-        @setRuntimeSafety(false);
-        debug.assert(a.len >= 1);
-        debug.assert(r.len >= a.len + (shift / Limb.bit_count) + 1);
-
-        const limb_shift = shift / Limb.bit_count + 1;
-        const interior_limb_shift = @intCast(Log2Limb, shift % Limb.bit_count);
-
-        var carry: Limb = 0;
-        var i: usize = 0;
-        while (i < a.len) : (i += 1) {
-            const src_i = a.len - i - 1;
-            const dst_i = src_i + limb_shift;
-
-            const src_digit = a[src_i];
-            r[dst_i] = carry | @call(.{ .modifier = .always_inline }, math.shr, .{
-                Limb,
-                src_digit,
-                Limb.bit_count - @intCast(Limb, interior_limb_shift),
-            });
-            carry = (src_digit << interior_limb_shift);
-        }
-
-        r[limb_shift - 1] = carry;
-        mem.set(Limb, r[0 .. limb_shift - 1], 0);
-    }
-
-    /// r = a >> shift
-    pub fn shiftRight(r: *Int, a: Int, shift: usize) !void {
-        r.assertWritable();
-
-        if (a.len() <= shift / Limb.bit_count) {
-            r.metadata = 1;
-            r.limbs[0] = 0;
-            return;
-        }
-
-        try r.ensureCapacity(a.len() - (shift / Limb.bit_count));
-        const r_len = llshr(r.limbs[0..], a.limbs[0..a.len()], shift);
-        r.metadata = a.len() - (shift / Limb.bit_count);
-        r.setSign(a.isPositive());
-    }
-
-    fn llshr(r: []Limb, a: []const Limb, shift: usize) void {
-        @setRuntimeSafety(false);
-        debug.assert(a.len >= 1);
-        debug.assert(r.len >= a.len - (shift / Limb.bit_count));
-
-        const limb_shift = shift / Limb.bit_count;
-        const interior_limb_shift = @intCast(Log2Limb, shift % Limb.bit_count);
-
-        var carry: Limb = 0;
-        var i: usize = 0;
-        while (i < a.len - limb_shift) : (i += 1) {
-            const src_i = a.len - i - 1;
-            const dst_i = src_i - limb_shift;
-
-            const src_digit = a[src_i];
-            r[dst_i] = carry | (src_digit >> interior_limb_shift);
-            carry = @call(.{ .modifier = .always_inline }, math.shl, .{
-                Limb,
-                src_digit,
-                Limb.bit_count - @intCast(Limb, interior_limb_shift),
-            });
-        }
+    /// Normalize a possible sequence of leading zeros.
+    ///
+    /// [1, 2, 3, 4, 0] -> [1, 2, 3, 4]
+    /// [1, 2, 0, 0, 0] -> [1, 2]
+    /// [0, 0, 0, 0, 0] -> [0]
+    fn normalize(r: *Mutable, length: usize) void {
+        r.len = llnormalize(r.limbs[0..length]);
     }
+};
 
-    /// r = a | b
+/// A arbitrary-precision big integer, with a fixed set of immutable limbs.
+pub const Const = struct {
+    /// Raw digits. These are:
     ///
-    /// a and b are zero-extended to the longer of a or b.
-    pub fn bitOr(r: *Int, a: Int, b: Int) !void {
-        r.assertWritable();
-
-        if (a.len() > b.len()) {
-            try r.ensureCapacity(a.len());
-            llor(r.limbs[0..], a.limbs[0..a.len()], b.limbs[0..b.len()]);
-            r.setLen(a.len());
-        } else {
-            try r.ensureCapacity(b.len());
-            llor(r.limbs[0..], b.limbs[0..b.len()], a.limbs[0..a.len()]);
-            r.setLen(b.len());
-        }
+    /// * Little-endian ordered
+    /// * limbs.len >= 1
+    /// * Zero is represented as limbs.len == 1 with limbs[0] == 0.
+    ///
+    /// Accessing limbs directly should be avoided.
+    limbs: []const Limb,
+    positive: bool,
+
+    /// The result is an independent resource which is managed by the caller.
+    pub fn toManaged(self: Const, allocator: *Allocator) Allocator.Error!Managed {
+        const limbs = try allocator.alloc(Limb, math.max(Managed.default_capacity, self.limbs.len));
+        mem.copy(Limb, limbs, self.limbs);
+        return Managed{
+            .allocator = allocator,
+            .limbs = limbs,
+            .metadata = if (self.positive)
+                self.limbs.len & ~Managed.sign_bit
+            else
+                self.limbs.len | Managed.sign_bit,
+        };
     }
 
-    fn llor(r: []Limb, a: []const Limb, b: []const Limb) void {
-        @setRuntimeSafety(false);
-        debug.assert(r.len >= a.len);
-        debug.assert(a.len >= b.len);
-
-        var i: usize = 0;
-        while (i < b.len) : (i += 1) {
-            r[i] = a[i] | b[i];
-        }
-        while (i < a.len) : (i += 1) {
-            r[i] = a[i];
-        }
+    /// Asserts `limbs` is big enough to store the value.
+    pub fn toMutable(self: Const, limbs: []Limb) Mutable {
+        mem.copy(Limb, limbs, self.limbs[0..self.limbs.len]);
+        return .{
+            .limbs = limbs,
+            .positive = self.positive,
+            .len = self.limbs.len,
+        };
     }
 
-    /// r = a & b
-    pub fn bitAnd(r: *Int, a: Int, b: Int) !void {
-        r.assertWritable();
-
-        if (a.len() > b.len()) {
-            try r.ensureCapacity(b.len());
-            lland(r.limbs[0..], a.limbs[0..a.len()], b.limbs[0..b.len()]);
-            r.normalize(b.len());
-        } else {
-            try r.ensureCapacity(a.len());
-            lland(r.limbs[0..], b.limbs[0..b.len()], a.limbs[0..a.len()]);
-            r.normalize(a.len());
+    pub fn dump(self: Const) void {
+        for (self.limbs[0..self.limbs.len]) |limb| {
+            std.debug.warn("{x} ", .{limb});
         }
+        std.debug.warn("positive={}\n", .{self.positive});
     }
 
-    fn lland(r: []Limb, a: []const Limb, b: []const Limb) void {
-        @setRuntimeSafety(false);
-        debug.assert(r.len >= b.len);
-        debug.assert(a.len >= b.len);
-
-        var i: usize = 0;
-        while (i < b.len) : (i += 1) {
-            r[i] = a[i] & b[i];
-        }
+    pub fn abs(self: Const) Const {
+        return .{
+            .limbs = self.limbs,
+            .positive = true,
+        };
     }
 
-    /// r = a ^ b
-    pub fn bitXor(r: *Int, a: Int, b: Int) !void {
-        r.assertWritable();
-
-        if (a.len() > b.len()) {
-            try r.ensureCapacity(a.len());
-            llxor(r.limbs[0..], a.limbs[0..a.len()], b.limbs[0..b.len()]);
-            r.normalize(a.len());
-        } else {
-            try r.ensureCapacity(b.len());
-            llxor(r.limbs[0..], b.limbs[0..b.len()], a.limbs[0..a.len()]);
-            r.normalize(b.len());
-        }
+    pub fn isOdd(self: Const) bool {
+        return self.limbs[0] & 1 != 0;
     }
 
-    fn llxor(r: []Limb, a: []const Limb, b: []const Limb) void {
-        @setRuntimeSafety(false);
-        debug.assert(r.len >= a.len);
-        debug.assert(a.len >= b.len);
-
-        var i: usize = 0;
-        while (i < b.len) : (i += 1) {
-            r[i] = a[i] ^ b[i];
-        }
-        while (i < a.len) : (i += 1) {
-            r[i] = a[i];
-        }
+    pub fn isEven(self: Const) bool {
+        return !self.isOdd();
     }
 
-    pub fn gcd(rma: *Int, x: Int, y: Int) !void {
-        rma.assertWritable();
-        var r = rma;
-        var aliased = rma.limbs.ptr == x.limbs.ptr or rma.limbs.ptr == y.limbs.ptr;
-
-        var sr: Int = undefined;
-        if (aliased) {
-            sr = try Int.initCapacity(rma.allocator.?, math.max(x.len(), y.len()));
-            r = &sr;
-            aliased = true;
-        }
-        defer if (aliased) {
-            rma.swap(r);
-            r.deinit();
-        };
-
-        try gcdLehmer(r, x, y);
+    /// Returns the number of bits required to represent the absolute value of an integer.
+    pub fn bitCountAbs(self: Const) usize {
+        return (self.limbs.len - 1) * Limb.bit_count + (Limb.bit_count - @clz(Limb, self.limbs[self.limbs.len - 1]));
     }
 
-    fn gcdLehmer(r: *Int, xa: Int, ya: Int) !void {
-        var x = try xa.clone();
-        x.abs();
-        defer x.deinit();
-
-        var y = try ya.clone();
-        y.abs();
-        defer y.deinit();
-
-        if (x.cmp(y) == .lt) {
-            x.swap(&y);
-        }
-
-        var T = try Int.init(r.allocator.?);
-        defer T.deinit();
-
-        while (y.len() > 1) {
-            debug.assert(x.isPositive() and y.isPositive());
-            debug.assert(x.len() >= y.len());
-
-            var xh: SignedDoubleLimb = x.limbs[x.len() - 1];
-            var yh: SignedDoubleLimb = if (x.len() > y.len()) 0 else y.limbs[x.len() - 1];
+    /// Returns the number of bits required to represent the integer in twos-complement form.
+    ///
+    /// If the integer is negative the value returned is the number of bits needed by a signed
+    /// integer to represent the value. If positive the value is the number of bits for an
+    /// unsigned integer. Any unsigned integer will fit in the signed integer with bitcount
+    /// one greater than the returned value.
+    ///
+    /// e.g. -127 returns 8 as it will fit in an i8. 127 returns 7 since it fits in a u7.
+    pub fn bitCountTwosComp(self: Const) usize {
+        var bits = self.bitCountAbs();
 
-            var A: SignedDoubleLimb = 1;
-            var B: SignedDoubleLimb = 0;
-            var C: SignedDoubleLimb = 0;
-            var D: SignedDoubleLimb = 1;
+        // If the entire value has only one bit set (e.g. 0b100000000) then the negation in twos
+        // complement requires one less bit.
+        if (!self.positive) block: {
+            bits += 1;
 
-            while (yh + C != 0 and yh + D != 0) {
-                const q = @divFloor(xh + A, yh + C);
-                const qp = @divFloor(xh + B, yh + D);
-                if (q != qp) {
-                    break;
+            if (@popCount(Limb, self.limbs[self.limbs.len - 1]) == 1) {
+                for (self.limbs[0 .. self.limbs.len - 1]) |limb| {
+                    if (@popCount(Limb, limb) != 0) {
+                        break :block;
+                    }
                 }
 
-                var t = A - q * C;
-                A = C;
-                C = t;
-                t = B - q * D;
-                B = D;
-                D = t;
-
-                t = xh - q * yh;
-                xh = yh;
-                yh = t;
-            }
-
-            if (B == 0) {
-                // T = x % y, r is unused
-                try Int.divTrunc(r, &T, x, y);
-                debug.assert(T.isPositive());
-
-                x.swap(&y);
-                y.swap(&T);
-            } else {
-                var storage: [8]Limb = undefined;
-                const Ap = FixedIntFromSignedDoubleLimb(A, storage[0..2]);
-                const Bp = FixedIntFromSignedDoubleLimb(B, storage[2..4]);
-                const Cp = FixedIntFromSignedDoubleLimb(C, storage[4..6]);
-                const Dp = FixedIntFromSignedDoubleLimb(D, storage[6..8]);
-
-                // T = Ax + By
-                try r.mul(x, Ap);
-                try T.mul(y, Bp);
-                try T.add(r.*, T);
-
-                // u = Cx + Dy, r as u
-                try x.mul(x, Cp);
-                try r.mul(y, Dp);
-                try r.add(x, r.*);
-
-                x.swap(&T);
-                y.swap(r);
+                bits -= 1;
             }
         }
 
-        // euclidean algorithm
-        debug.assert(x.cmp(y) != .lt);
+        return bits;
+    }
 
-        while (!y.eqZero()) {
-            try Int.divTrunc(&T, r, x, y);
-            x.swap(&y);
-            y.swap(r);
+    pub fn fitsInTwosComp(self: Const, is_signed: bool, bit_count: usize) bool {
+        if (self.eqZero()) {
+            return true;
+        }
+        if (!is_signed and !self.positive) {
+            return false;
         }
 
-        r.swap(&x);
+        const req_bits = self.bitCountTwosComp() + @boolToInt(self.positive and is_signed);
+        return bit_count >= req_bits;
     }
-};
-
-// Storage must live for the lifetime of the returned value
-fn FixedIntFromSignedDoubleLimb(A: SignedDoubleLimb, storage: []Limb) Int {
-    std.debug.assert(storage.len >= 2);
-
-    var A_is_positive = A >= 0;
-    const Au = @intCast(DoubleLimb, if (A < 0) -A else A);
-    storage[0] = @truncate(Limb, Au);
-    storage[1] = @truncate(Limb, Au >> Limb.bit_count);
-    var Ap = Int.initFixed(storage[0..2]);
-    Ap.setSign(A_is_positive);
-    return Ap;
-}
 
-// NOTE: All the following tests assume the max machine-word will be 64-bit.
-//
-// They will still run on larger than this and should pass, but the multi-limb code-paths
-// may be untested in some cases.
-
-test "big.int comptime_int set" {
-    comptime var s = 0xefffffff00000001eeeeeeefaaaaaaab;
-    var a = try Int.initSet(testing.allocator, s);
-    defer a.deinit();
-
-    const s_limb_count = 128 / Limb.bit_count;
-
-    comptime var i: usize = 0;
-    inline while (i < s_limb_count) : (i += 1) {
-        const result = @as(Limb, s & maxInt(Limb));
-        s >>= Limb.bit_count / 2;
-        s >>= Limb.bit_count / 2;
-        testing.expect(a.limbs[i] == result);
+    /// Returns whether self can fit into an integer of the requested type.
+    pub fn fits(self: Const, comptime T: type) bool {
+        const info = @typeInfo(T).Int;
+        return self.fitsInTwosComp(info.is_signed, info.bits);
     }
-}
-
-test "big.int comptime_int set negative" {
-    var a = try Int.initSet(testing.allocator, -10);
-    defer a.deinit();
-
-    testing.expect(a.limbs[0] == 10);
-    testing.expect(a.isPositive() == false);
-}
-
-test "big.int int set unaligned small" {
-    var a = try Int.initSet(testing.allocator, @as(u7, 45));
-    defer a.deinit();
-
-    testing.expect(a.limbs[0] == 45);
-    testing.expect(a.isPositive() == true);
-}
-
-test "big.int comptime_int to" {
-    const a = try Int.initSet(testing.allocator, 0xefffffff00000001eeeeeeefaaaaaaab);
-    defer a.deinit();
-
-    testing.expect((try a.to(u128)) == 0xefffffff00000001eeeeeeefaaaaaaab);
-}
-
-test "big.int sub-limb to" {
-    const a = try Int.initSet(testing.allocator, 10);
-    defer a.deinit();
-
-    testing.expect((try a.to(u8)) == 10);
-}
-
-test "big.int to target too small error" {
-    const a = try Int.initSet(testing.allocator, 0xffffffff);
-    defer a.deinit();
-
-    testing.expectError(error.TargetTooSmall, a.to(u8));
-}
-
-test "big.int normalize" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-    try a.ensureCapacity(8);
-
-    a.limbs[0] = 1;
-    a.limbs[1] = 2;
-    a.limbs[2] = 3;
-    a.limbs[3] = 0;
-    a.normalize(4);
-    testing.expect(a.len() == 3);
-
-    a.limbs[0] = 1;
-    a.limbs[1] = 2;
-    a.limbs[2] = 3;
-    a.normalize(3);
-    testing.expect(a.len() == 3);
-
-    a.limbs[0] = 0;
-    a.limbs[1] = 0;
-    a.normalize(2);
-    testing.expect(a.len() == 1);
-
-    a.limbs[0] = 0;
-    a.normalize(1);
-    testing.expect(a.len() == 1);
-}
-
-test "big.int normalize multi" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-    try a.ensureCapacity(8);
-
-    a.limbs[0] = 1;
-    a.limbs[1] = 2;
-    a.limbs[2] = 0;
-    a.limbs[3] = 0;
-    a.normalize(4);
-    testing.expect(a.len() == 2);
-
-    a.limbs[0] = 1;
-    a.limbs[1] = 2;
-    a.limbs[2] = 3;
-    a.normalize(3);
-    testing.expect(a.len() == 3);
-
-    a.limbs[0] = 0;
-    a.limbs[1] = 0;
-    a.limbs[2] = 0;
-    a.limbs[3] = 0;
-    a.normalize(4);
-    testing.expect(a.len() == 1);
-
-    a.limbs[0] = 0;
-    a.normalize(1);
-    testing.expect(a.len() == 1);
-}
-
-test "big.int parity" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.set(0);
-    testing.expect(a.isEven());
-    testing.expect(!a.isOdd());
-
-    try a.set(7);
-    testing.expect(!a.isEven());
-    testing.expect(a.isOdd());
-}
-
-test "big.int bitcount + sizeInBase" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.set(0b100);
-    testing.expect(a.bitCountAbs() == 3);
-    testing.expect(a.sizeInBase(2) >= 3);
-    testing.expect(a.sizeInBase(10) >= 1);
-
-    a.negate();
-    testing.expect(a.bitCountAbs() == 3);
-    testing.expect(a.sizeInBase(2) >= 4);
-    testing.expect(a.sizeInBase(10) >= 2);
-
-    try a.set(0xffffffff);
-    testing.expect(a.bitCountAbs() == 32);
-    testing.expect(a.sizeInBase(2) >= 32);
-    testing.expect(a.sizeInBase(10) >= 10);
-
-    try a.shiftLeft(a, 5000);
-    testing.expect(a.bitCountAbs() == 5032);
-    testing.expect(a.sizeInBase(2) >= 5032);
-    a.setSign(false);
-
-    testing.expect(a.bitCountAbs() == 5032);
-    testing.expect(a.sizeInBase(2) >= 5033);
-}
-
-test "big.int bitcount/to" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.set(0);
-    testing.expect(a.bitCountTwosComp() == 0);
-
-    testing.expect((try a.to(u0)) == 0);
-    testing.expect((try a.to(i0)) == 0);
-
-    try a.set(-1);
-    testing.expect(a.bitCountTwosComp() == 1);
-    testing.expect((try a.to(i1)) == -1);
-
-    try a.set(-8);
-    testing.expect(a.bitCountTwosComp() == 4);
-    testing.expect((try a.to(i4)) == -8);
-
-    try a.set(127);
-    testing.expect(a.bitCountTwosComp() == 7);
-    testing.expect((try a.to(u7)) == 127);
-
-    try a.set(-128);
-    testing.expect(a.bitCountTwosComp() == 8);
-    testing.expect((try a.to(i8)) == -128);
-
-    try a.set(-129);
-    testing.expect(a.bitCountTwosComp() == 9);
-    testing.expect((try a.to(i9)) == -129);
-}
-
-test "big.int fits" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.set(0);
-    testing.expect(a.fits(u0));
-    testing.expect(a.fits(i0));
-
-    try a.set(255);
-    testing.expect(!a.fits(u0));
-    testing.expect(!a.fits(u1));
-    testing.expect(!a.fits(i8));
-    testing.expect(a.fits(u8));
-    testing.expect(a.fits(u9));
-    testing.expect(a.fits(i9));
-
-    try a.set(-128);
-    testing.expect(!a.fits(i7));
-    testing.expect(a.fits(i8));
-    testing.expect(a.fits(i9));
-    testing.expect(!a.fits(u9));
-
-    try a.set(0x1ffffffffeeeeeeee);
-    testing.expect(!a.fits(u32));
-    testing.expect(!a.fits(u64));
-    testing.expect(a.fits(u65));
-}
-
-test "big.int string set" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.setString(10, "120317241209124781241290847124");
-    testing.expect((try a.to(u128)) == 120317241209124781241290847124);
-}
-
-test "big.int string negative" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.setString(10, "-1023");
-    testing.expect((try a.to(i32)) == -1023);
-}
-
-test "big.int string set number with underscores" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.setString(10, "__1_2_0_3_1_7_2_4_1_2_0_____9_1__2__4_7_8_1_2_4_1_2_9_0_8_4_7_1_2_4___");
-    testing.expect((try a.to(u128)) == 120317241209124781241290847124);
-}
-
-test "big.int string set case insensitive number" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.setString(16, "aB_cD_eF");
-    testing.expect((try a.to(u32)) == 0xabcdef);
-}
-
-test "big.int string set bad char error" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-    testing.expectError(error.InvalidCharForDigit, a.setString(10, "x"));
-}
-
-test "big.int string set bad base error" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-    testing.expectError(error.InvalidBase, a.setString(45, "10"));
-}
-
-test "big.int string to" {
-    const a = try Int.initSet(testing.allocator, 120317241209124781241290847124);
-    defer a.deinit();
-
-    const as = try a.toString(testing.allocator, 10, false);
-    defer testing.allocator.free(as);
-    const es = "120317241209124781241290847124";
-
-    testing.expect(mem.eql(u8, as, es));
-}
-
-test "big.int string to base base error" {
-    const a = try Int.initSet(testing.allocator, 0xffffffff);
-    defer a.deinit();
-
-    testing.expectError(error.InvalidBase, a.toString(testing.allocator, 45, false));
-}
-
-test "big.int string to base 2" {
-    const a = try Int.initSet(testing.allocator, -0b1011);
-    defer a.deinit();
-
-    const as = try a.toString(testing.allocator, 2, false);
-    defer testing.allocator.free(as);
-    const es = "-1011";
-
-    testing.expect(mem.eql(u8, as, es));
-}
-
-test "big.int string to base 16" {
-    const a = try Int.initSet(testing.allocator, 0xefffffff00000001eeeeeeefaaaaaaab);
-    defer a.deinit();
-
-    const as = try a.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(as);
-    const es = "efffffff00000001eeeeeeefaaaaaaab";
-
-    testing.expect(mem.eql(u8, as, es));
-}
-
-test "big.int neg string to" {
-    const a = try Int.initSet(testing.allocator, -123907434);
-    defer a.deinit();
-
-    const as = try a.toString(testing.allocator, 10, false);
-    defer testing.allocator.free(as);
-    const es = "-123907434";
-
-    testing.expect(mem.eql(u8, as, es));
-}
-
-test "big.int zero string to" {
-    const a = try Int.initSet(testing.allocator, 0);
-    defer a.deinit();
-
-    const as = try a.toString(testing.allocator, 10, false);
-    defer testing.allocator.free(as);
-    const es = "0";
-
-    testing.expect(mem.eql(u8, as, es));
-}
-
-test "big.int clone" {
-    var a = try Int.initSet(testing.allocator, 1234);
-    defer a.deinit();
-    const b = try a.clone();
-    defer b.deinit();
-
-    testing.expect((try a.to(u32)) == 1234);
-    testing.expect((try b.to(u32)) == 1234);
-
-    try a.set(77);
-    testing.expect((try a.to(u32)) == 77);
-    testing.expect((try b.to(u32)) == 1234);
-}
-
-test "big.int swap" {
-    var a = try Int.initSet(testing.allocator, 1234);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 5678);
-    defer b.deinit();
-
-    testing.expect((try a.to(u32)) == 1234);
-    testing.expect((try b.to(u32)) == 5678);
-
-    a.swap(&b);
-
-    testing.expect((try a.to(u32)) == 5678);
-    testing.expect((try b.to(u32)) == 1234);
-}
-
-test "big.int to negative" {
-    var a = try Int.initSet(testing.allocator, -10);
-    defer a.deinit();
-
-    testing.expect((try a.to(i32)) == -10);
-}
-
-test "big.int compare" {
-    var a = try Int.initSet(testing.allocator, -11);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 10);
-    defer b.deinit();
-
-    testing.expect(a.cmpAbs(b) == .gt);
-    testing.expect(a.cmp(b) == .lt);
-}
-
-test "big.int compare similar" {
-    var a = try Int.initSet(testing.allocator, 0xffffffffeeeeeeeeffffffffeeeeeeee);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0xffffffffeeeeeeeeffffffffeeeeeeef);
-    defer b.deinit();
-
-    testing.expect(a.cmpAbs(b) == .lt);
-    testing.expect(b.cmpAbs(a) == .gt);
-}
-
-test "big.int compare different limb size" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb) + 1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 1);
-    defer b.deinit();
-
-    testing.expect(a.cmpAbs(b) == .gt);
-    testing.expect(b.cmpAbs(a) == .lt);
-}
-
-test "big.int compare multi-limb" {
-    var a = try Int.initSet(testing.allocator, -0x7777777799999999ffffeeeeffffeeeeffffeeeef);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x7777777799999999ffffeeeeffffeeeeffffeeeee);
-    defer b.deinit();
-
-    testing.expect(a.cmpAbs(b) == .gt);
-    testing.expect(a.cmp(b) == .lt);
-}
-
-test "big.int equality" {
-    var a = try Int.initSet(testing.allocator, 0xffffffff1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, -0xffffffff1);
-    defer b.deinit();
-
-    testing.expect(a.eqAbs(b));
-    testing.expect(!a.eq(b));
-}
-
-test "big.int abs" {
-    var a = try Int.initSet(testing.allocator, -5);
-    defer a.deinit();
-
-    a.abs();
-    testing.expect((try a.to(u32)) == 5);
-
-    a.abs();
-    testing.expect((try a.to(u32)) == 5);
-}
-
-test "big.int negate" {
-    var a = try Int.initSet(testing.allocator, 5);
-    defer a.deinit();
-
-    a.negate();
-    testing.expect((try a.to(i32)) == -5);
-
-    a.negate();
-    testing.expect((try a.to(i32)) == 5);
-}
-
-test "big.int add single-single" {
-    var a = try Int.initSet(testing.allocator, 50);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 5);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.add(a, b);
-
-    testing.expect((try c.to(u32)) == 55);
-}
-
-test "big.int add multi-single" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb) + 1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 1);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-
-    try c.add(a, b);
-    testing.expect((try c.to(DoubleLimb)) == maxInt(Limb) + 2);
-
-    try c.add(b, a);
-    testing.expect((try c.to(DoubleLimb)) == maxInt(Limb) + 2);
-}
-
-test "big.int add multi-multi" {
-    const op1 = 0xefefefef7f7f7f7f;
-    const op2 = 0xfefefefe9f9f9f9f;
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, op2);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.add(a, b);
-
-    testing.expect((try c.to(u128)) == op1 + op2);
-}
-
-test "big.int add zero-zero" {
-    var a = try Int.initSet(testing.allocator, 0);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.add(a, b);
 
-    testing.expect((try c.to(u32)) == 0);
-}
-
-test "big.int add alias multi-limb nonzero-zero" {
-    const op1 = 0xffffffff777777771;
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0);
-    defer b.deinit();
-
-    try a.add(a, b);
-
-    testing.expect((try a.to(u128)) == op1);
-}
-
-test "big.int add sign" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    const one = try Int.initSet(testing.allocator, 1);
-    defer one.deinit();
-    const two = try Int.initSet(testing.allocator, 2);
-    defer two.deinit();
-    const neg_one = try Int.initSet(testing.allocator, -1);
-    defer neg_one.deinit();
-    const neg_two = try Int.initSet(testing.allocator, -2);
-    defer neg_two.deinit();
-
-    try a.add(one, two);
-    testing.expect((try a.to(i32)) == 3);
-
-    try a.add(neg_one, two);
-    testing.expect((try a.to(i32)) == 1);
-
-    try a.add(one, neg_two);
-    testing.expect((try a.to(i32)) == -1);
-
-    try a.add(neg_one, neg_two);
-    testing.expect((try a.to(i32)) == -3);
-}
-
-test "big.int sub single-single" {
-    var a = try Int.initSet(testing.allocator, 50);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 5);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.sub(a, b);
-
-    testing.expect((try c.to(u32)) == 45);
-}
-
-test "big.int sub multi-single" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb) + 1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 1);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.sub(a, b);
-
-    testing.expect((try c.to(Limb)) == maxInt(Limb));
-}
-
-test "big.int sub multi-multi" {
-    const op1 = 0xefefefefefefefefefefefef;
-    const op2 = 0xabababababababababababab;
-
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, op2);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.sub(a, b);
-
-    testing.expect((try c.to(u128)) == op1 - op2);
-}
-
-test "big.int sub equal" {
-    var a = try Int.initSet(testing.allocator, 0x11efefefefefefefefefefefef);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x11efefefefefefefefefefefef);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.sub(a, b);
-
-    testing.expect((try c.to(u32)) == 0);
-}
-
-test "big.int sub sign" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    const one = try Int.initSet(testing.allocator, 1);
-    defer one.deinit();
-    const two = try Int.initSet(testing.allocator, 2);
-    defer two.deinit();
-    const neg_one = try Int.initSet(testing.allocator, -1);
-    defer neg_one.deinit();
-    const neg_two = try Int.initSet(testing.allocator, -2);
-    defer neg_two.deinit();
-
-    try a.sub(one, two);
-    testing.expect((try a.to(i32)) == -1);
-
-    try a.sub(neg_one, two);
-    testing.expect((try a.to(i32)) == -3);
-
-    try a.sub(one, neg_two);
-    testing.expect((try a.to(i32)) == 3);
-
-    try a.sub(neg_one, neg_two);
-    testing.expect((try a.to(i32)) == 1);
-
-    try a.sub(neg_two, neg_one);
-    testing.expect((try a.to(i32)) == -1);
-}
-
-test "big.int mul single-single" {
-    var a = try Int.initSet(testing.allocator, 50);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 5);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.mul(a, b);
-
-    testing.expect((try c.to(u64)) == 250);
-}
-
-test "big.int mul multi-single" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb));
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 2);
-    defer b.deinit();
-
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.mul(a, b);
-
-    testing.expect((try c.to(DoubleLimb)) == 2 * maxInt(Limb));
-}
+    /// Returns the approximate size of the integer in the given base. Negative values accommodate for
+    /// the minus sign. This is used for determining the number of characters needed to print the
+    /// value. It is inexact and may exceed the given value by ~1-2 bytes.
+    /// TODO See if we can make this exact.
+    pub fn sizeInBaseUpperBound(self: Const, base: usize) usize {
+        const bit_count = @as(usize, @boolToInt(!self.positive)) + self.bitCountAbs();
+        return (bit_count / math.log2(base)) + 2;
+    }
 
-test "big.int mul multi-multi" {
-    const op1 = 0x998888efefefefefefefef;
-    const op2 = 0x333000abababababababab;
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, op2);
-    defer b.deinit();
+    pub const ConvertError = error{
+        NegativeIntoUnsigned,
+        TargetTooSmall,
+    };
 
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.mul(a, b);
+    /// Convert self to type T.
+    ///
+    /// Returns an error if self cannot be narrowed into the requested type without truncation.
+    pub fn to(self: Const, comptime T: type) ConvertError!T {
+        switch (@typeInfo(T)) {
+            .Int => {
+                const UT = std.meta.Int(false, T.bit_count);
 
-    testing.expect((try c.to(u256)) == op1 * op2);
-}
+                if (self.bitCountTwosComp() > T.bit_count) {
+                    return error.TargetTooSmall;
+                }
 
-test "big.int mul alias r with a" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb));
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 2);
-    defer b.deinit();
+                var r: UT = 0;
 
-    try a.mul(a, b);
+                if (@sizeOf(UT) <= @sizeOf(Limb)) {
+                    r = @intCast(UT, self.limbs[0]);
+                } else {
+                    for (self.limbs[0..self.limbs.len]) |_, ri| {
+                        const limb = self.limbs[self.limbs.len - ri - 1];
+                        r <<= Limb.bit_count;
+                        r |= limb;
+                    }
+                }
 
-    testing.expect((try a.to(DoubleLimb)) == 2 * maxInt(Limb));
-}
+                if (!T.is_signed) {
+                    return if (self.positive) @intCast(T, r) else error.NegativeIntoUnsigned;
+                } else {
+                    if (self.positive) {
+                        return @intCast(T, r);
+                    } else {
+                        if (math.cast(T, r)) |ok| {
+                            return -ok;
+                        } else |_| {
+                            return minInt(T);
+                        }
+                    }
+                }
+            },
+            else => @compileError("cannot convert Const to type " ++ @typeName(T)),
+        }
+    }
 
-test "big.int mul alias r with b" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb));
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 2);
-    defer b.deinit();
+    /// To allow `std.fmt.format` to work with this type.
+    /// If the integer is larger than `pow(2, 64 * @sizeOf(usize) * 8), this function will fail
+    /// to print the string, printing "(BigInt)" instead of a number.
+    /// This is because the rendering algorithm requires reversing a string, which requires O(N) memory.
+    /// See `toString` and `toStringAlloc` for a way to print big integers without failure.
+    pub fn format(
+        self: Const,
+        comptime fmt: []const u8,
+        options: std.fmt.FormatOptions,
+        out_stream: var,
+    ) !void {
+        comptime var radix = 10;
+        comptime var uppercase = false;
 
-    try a.mul(b, a);
+        if (fmt.len == 0 or comptime mem.eql(u8, fmt, "d")) {
+            radix = 10;
+            uppercase = false;
+        } else if (comptime mem.eql(u8, fmt, "b")) {
+            radix = 2;
+            uppercase = false;
+        } else if (comptime mem.eql(u8, fmt, "x")) {
+            radix = 16;
+            uppercase = false;
+        } else if (comptime mem.eql(u8, fmt, "X")) {
+            radix = 16;
+            uppercase = true;
+        } else {
+            @compileError("Unknown format string: '" ++ fmt ++ "'");
+        }
 
-    testing.expect((try a.to(DoubleLimb)) == 2 * maxInt(Limb));
-}
+        var limbs: [128]Limb = undefined;
+        const needed_limbs = calcDivLimbsBufferLen(self.limbs.len, 1);
+        if (needed_limbs > limbs.len)
+            return out_stream.writeAll("(BigInt)");
 
-test "big.int mul alias r with a and b" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb));
-    defer a.deinit();
+        // This is the inverse of calcDivLimbsBufferLen
+        const available_len = (limbs.len / 3) - 2;
 
-    try a.mul(a, a);
+        const biggest: Const = .{
+            .limbs = &([1]Limb{math.maxInt(Limb)} ** available_len),
+            .positive = false,
+        };
+        var buf: [biggest.sizeInBaseUpperBound(radix)]u8 = undefined;
+        const len = self.toString(&buf, radix, uppercase, &limbs);
+        return out_stream.writeAll(buf[0..len]);
+    }
 
-    testing.expect((try a.to(DoubleLimb)) == maxInt(Limb) * maxInt(Limb));
-}
+    /// Converts self to a string in the requested base.
+    /// Caller owns returned memory.
+    /// Asserts that `base` is in the range [2, 16].
+    /// See also `toString`, a lower level function than this.
+    pub fn toStringAlloc(self: Const, allocator: *Allocator, base: u8, uppercase: bool) Allocator.Error![]u8 {
+        assert(base >= 2);
+        assert(base <= 16);
 
-test "big.int mul a*0" {
-    var a = try Int.initSet(testing.allocator, 0xefefefefefefefef);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0);
-    defer b.deinit();
+        if (self.eqZero()) {
+            return mem.dupe(allocator, u8, "0");
+        }
+        const string = try allocator.alloc(u8, self.sizeInBaseUpperBound(base));
+        errdefer allocator.free(string);
 
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.mul(a, b);
+        const limbs = try allocator.alloc(Limb, calcToStringLimbsBufferLen(self.limbs.len, base));
+        defer allocator.free(limbs);
 
-    testing.expect((try c.to(u32)) == 0);
-}
+        return allocator.shrink(string, self.toString(string, base, uppercase, limbs));
+    }
 
-test "big.int mul 0*0" {
-    var a = try Int.initSet(testing.allocator, 0);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0);
-    defer b.deinit();
+    /// Converts self to a string in the requested base.
+    /// Asserts that `base` is in the range [2, 16].
+    /// `string` is a caller-provided slice of at least `sizeInBaseUpperBound` bytes,
+    /// where the result is written to.
+    /// Returns the length of the string.
+    /// `limbs_buffer` is caller-provided memory for `toString` to use as a working area. It must have
+    /// length of at least `calcToStringLimbsBufferLen`.
+    /// In the case of power-of-two base, `limbs_buffer` is ignored.
+    /// See also `toStringAlloc`, a higher level function than this.
+    pub fn toString(self: Const, string: []u8, base: u8, uppercase: bool, limbs_buffer: []Limb) usize {
+        assert(base >= 2);
+        assert(base <= 16);
 
-    var c = try Int.init(testing.allocator);
-    defer c.deinit();
-    try c.mul(a, b);
+        if (self.eqZero()) {
+            string[0] = '0';
+            return 1;
+        }
 
-    testing.expect((try c.to(u32)) == 0);
-}
+        var digits_len: usize = 0;
 
-test "big.int div single-single no rem" {
-    var a = try Int.initSet(testing.allocator, 50);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 5);
-    defer b.deinit();
+        // Power of two: can do a single pass and use masks to extract digits.
+        if (math.isPowerOfTwo(base)) {
+            const base_shift = math.log2_int(Limb, base);
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+            outer: for (self.limbs[0..self.limbs.len]) |limb| {
+                var shift: usize = 0;
+                while (shift < Limb.bit_count) : (shift += base_shift) {
+                    const r = @intCast(u8, (limb >> @intCast(Log2Limb, shift)) & @as(Limb, base - 1));
+                    const ch = std.fmt.digitToChar(r, uppercase);
+                    string[digits_len] = ch;
+                    digits_len += 1;
+                    // If we hit the end, it must be all zeroes from here.
+                    if (digits_len == string.len) break :outer;
+                }
+            }
 
-    testing.expect((try q.to(u32)) == 10);
-    testing.expect((try r.to(u32)) == 0);
-}
+            // Always will have a non-zero digit somewhere.
+            while (string[digits_len - 1] == '0') {
+                digits_len -= 1;
+            }
+        } else {
+            // Non power-of-two: batch divisions per word size.
+            const digits_per_limb = math.log(Limb, base, maxInt(Limb));
+            var limb_base: Limb = 1;
+            var j: usize = 0;
+            while (j < digits_per_limb) : (j += 1) {
+                limb_base *= base;
+            }
+            const b: Const = .{ .limbs = &[_]Limb{limb_base}, .positive = true };
 
-test "big.int div single-single with rem" {
-    var a = try Int.initSet(testing.allocator, 49);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 5);
-    defer b.deinit();
+            var q: Mutable = .{
+                .limbs = limbs_buffer[0 .. self.limbs.len + 2],
+                .positive = true, // Make absolute by ignoring self.positive.
+                .len = self.limbs.len,
+            };
+            mem.copy(Limb, q.limbs, self.limbs);
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+            var r: Mutable = .{
+                .limbs = limbs_buffer[q.limbs.len..][0..self.limbs.len],
+                .positive = true,
+                .len = 1,
+            };
+            r.limbs[0] = 0;
 
-    testing.expect((try q.to(u32)) == 9);
-    testing.expect((try r.to(u32)) == 4);
-}
+            const rest_of_the_limbs_buf = limbs_buffer[q.limbs.len + r.limbs.len ..];
 
-test "big.int div multi-single no rem" {
-    const op1 = 0xffffeeeeddddcccc;
-    const op2 = 34;
+            while (q.len >= 2) {
+                // Passing an allocator here would not be helpful since this division is destroying
+                // information, not creating it. [TODO citation needed]
+                q.divTrunc(&r, q.toConst(), b, rest_of_the_limbs_buf, null);
 
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, op2);
-    defer b.deinit();
+                var r_word = r.limbs[0];
+                var i: usize = 0;
+                while (i < digits_per_limb) : (i += 1) {
+                    const ch = std.fmt.digitToChar(@intCast(u8, r_word % base), uppercase);
+                    r_word /= base;
+                    string[digits_len] = ch;
+                    digits_len += 1;
+                }
+            }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+            {
+                assert(q.len == 1);
 
-    testing.expect((try q.to(u64)) == op1 / op2);
-    testing.expect((try r.to(u64)) == 0);
-}
+                var r_word = q.limbs[0];
+                while (r_word != 0) {
+                    const ch = std.fmt.digitToChar(@intCast(u8, r_word % base), uppercase);
+                    r_word /= base;
+                    string[digits_len] = ch;
+                    digits_len += 1;
+                }
+            }
+        }
 
-test "big.int div multi-single with rem" {
-    const op1 = 0xffffeeeeddddcccf;
-    const op2 = 34;
+        if (!self.positive) {
+            string[digits_len] = '-';
+            digits_len += 1;
+        }
 
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, op2);
-    defer b.deinit();
+        const s = string[0..digits_len];
+        mem.reverse(u8, s);
+        return s.len;
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// Returns `math.Order.lt`, `math.Order.eq`, `math.Order.gt` if
+    /// `|a| < |b|`, `|a| == |b|`, or `|a| > |b|` respectively.
+    pub fn orderAbs(a: Const, b: Const) math.Order {
+        if (a.limbs.len < b.limbs.len) {
+            return .lt;
+        }
+        if (a.limbs.len > b.limbs.len) {
+            return .gt;
+        }
 
-    testing.expect((try q.to(u64)) == op1 / op2);
-    testing.expect((try r.to(u64)) == 3);
-}
+        var i: usize = a.limbs.len - 1;
+        while (i != 0) : (i -= 1) {
+            if (a.limbs[i] != b.limbs[i]) {
+                break;
+            }
+        }
 
-test "big.int div multi>2-single" {
-    const op1 = 0xfefefefefefefefefefefefefefefefe;
-    const op2 = 0xefab8;
+        if (a.limbs[i] < b.limbs[i]) {
+            return .lt;
+        } else if (a.limbs[i] > b.limbs[i]) {
+            return .gt;
+        } else {
+            return .eq;
+        }
+    }
 
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, op2);
-    defer b.deinit();
+    /// Returns `math.Order.lt`, `math.Order.eq`, `math.Order.gt` if `a < b`, `a == b` or `a > b` respectively.
+    pub fn order(a: Const, b: Const) math.Order {
+        if (a.positive != b.positive) {
+            return if (a.positive) .gt else .lt;
+        } else {
+            const r = orderAbs(a, b);
+            return if (a.positive) r else switch (r) {
+                .lt => math.Order.gt,
+                .eq => math.Order.eq,
+                .gt => math.Order.lt,
+            };
+        }
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// Same as `order` but the right-hand operand is a primitive integer.
+    pub fn orderAgainstScalar(lhs: Const, scalar: var) math.Order {
+        var limbs: [calcLimbLen(scalar)]Limb = undefined;
+        const rhs = Mutable.init(&limbs, scalar);
+        return order(lhs, rhs.toConst());
+    }
 
-    testing.expect((try q.to(u128)) == op1 / op2);
-    testing.expect((try r.to(u32)) == 0x3e4e);
-}
+    /// Returns true if `a == 0`.
+    pub fn eqZero(a: Const) bool {
+        return a.limbs.len == 1 and a.limbs[0] == 0;
+    }
 
-test "big.int div single-single q < r" {
-    var a = try Int.initSet(testing.allocator, 0x0078f432);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x01000000);
-    defer b.deinit();
+    /// Returns true if `|a| == |b|`.
+    pub fn eqAbs(a: Const, b: Const) bool {
+        return orderAbs(a, b) == .eq;
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// Returns true if `a == b`.
+    pub fn eq(a: Const, b: Const) bool {
+        return order(a, b) == .eq;
+    }
+};
 
-    testing.expect((try q.to(u64)) == 0);
-    testing.expect((try r.to(u64)) == 0x0078f432);
-}
+/// An arbitrary-precision big integer along with an allocator which manages the memory.
+///
+/// Memory is allocated as needed to ensure operations never overflow. The range
+/// is bounded only by available memory.
+pub const Managed = struct {
+    pub const sign_bit: usize = 1 << (usize.bit_count - 1);
 
-test "big.int div single-single q == r" {
-    var a = try Int.initSet(testing.allocator, 10);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 10);
-    defer b.deinit();
+    /// Default number of limbs to allocate on creation of a `Managed`.
+    pub const default_capacity = 4;
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// Allocator used by the Managed when requesting memory.
+    allocator: *Allocator,
 
-    testing.expect((try q.to(u64)) == 1);
-    testing.expect((try r.to(u64)) == 0);
-}
+    /// Raw digits. These are:
+    ///
+    /// * Little-endian ordered
+    /// * limbs.len >= 1
+    /// * Zero is represent as Managed.len() == 1 with limbs[0] == 0.
+    ///
+    /// Accessing limbs directly should be avoided.
+    limbs: []Limb,
 
-test "big.int div q=0 alias" {
-    var a = try Int.initSet(testing.allocator, 3);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 10);
-    defer b.deinit();
+    /// High bit is the sign bit. If set, Managed is negative, else Managed is positive.
+    /// The remaining bits represent the number of limbs used by Managed.
+    metadata: usize,
 
-    try Int.divTrunc(&a, &b, a, b);
+    /// Creates a new `Managed`. `default_capacity` limbs will be allocated immediately.
+    /// The integer value after initializing is `0`.
+    pub fn init(allocator: *Allocator) !Managed {
+        return initCapacity(allocator, default_capacity);
+    }
 
-    testing.expect((try a.to(u64)) == 0);
-    testing.expect((try b.to(u64)) == 3);
-}
+    pub fn toMutable(self: Managed) Mutable {
+        return .{
+            .limbs = self.limbs,
+            .positive = self.isPositive(),
+            .len = self.len(),
+        };
+    }
 
-test "big.int div multi-multi q < r" {
-    const op1 = 0x1ffffffff0078f432;
-    const op2 = 0x1ffffffff01000000;
-    var a = try Int.initSet(testing.allocator, op1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, op2);
-    defer b.deinit();
-
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
-
-    testing.expect((try q.to(u128)) == 0);
-    testing.expect((try r.to(u128)) == op1);
-}
+    pub fn toConst(self: Managed) Const {
+        return .{
+            .limbs = self.limbs[0..self.len()],
+            .positive = self.isPositive(),
+        };
+    }
 
-test "big.int div trunc single-single +/+" {
-    const u: i32 = 5;
-    const v: i32 = 3;
+    /// Creates a new `Managed` with value `value`.
+    ///
+    /// This is identical to an `init`, followed by a `set`.
+    pub fn initSet(allocator: *Allocator, value: var) !Managed {
+        var s = try Managed.init(allocator);
+        try s.set(value);
+        return s;
+    }
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+    /// Creates a new Managed with a specific capacity. If capacity < default_capacity then the
+    /// default capacity will be used instead.
+    /// The integer value after initializing is `0`.
+    pub fn initCapacity(allocator: *Allocator, capacity: usize) !Managed {
+        return Managed{
+            .allocator = allocator,
+            .metadata = 1,
+            .limbs = block: {
+                const limbs = try allocator.alloc(Limb, math.max(default_capacity, capacity));
+                limbs[0] = 0;
+                break :block limbs;
+            },
+        };
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// Returns the number of limbs currently in use.
+    pub fn len(self: Managed) usize {
+        return self.metadata & ~sign_bit;
+    }
 
-    // n = q * d + r
-    // 5 = 1 * 3 + 2
-    const eq = @divTrunc(u, v);
-    const er = @mod(u, v);
+    /// Returns whether an Managed is positive.
+    pub fn isPositive(self: Managed) bool {
+        return self.metadata & sign_bit == 0;
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// Sets the sign of an Managed.
+    pub fn setSign(self: *Managed, positive: bool) void {
+        if (positive) {
+            self.metadata &= ~sign_bit;
+        } else {
+            self.metadata |= sign_bit;
+        }
+    }
 
-test "big.int div trunc single-single -/+" {
-    const u: i32 = -5;
-    const v: i32 = 3;
+    /// Sets the length of an Managed.
+    ///
+    /// If setLen is used, then the Managed must be normalized to suit.
+    pub fn setLen(self: *Managed, new_len: usize) void {
+        self.metadata &= sign_bit;
+        self.metadata |= new_len;
+    }
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+    pub fn setMetadata(self: *Managed, positive: bool, length: usize) void {
+        self.metadata = if (positive) length & ~sign_bit else length | sign_bit;
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// Ensures an Managed has enough space allocated for capacity limbs. If the Managed does not have
+    /// sufficient capacity, the exact amount will be allocated. This occurs even if the requested
+    /// capacity is only greater than the current capacity by one limb.
+    pub fn ensureCapacity(self: *Managed, capacity: usize) !void {
+        if (capacity <= self.limbs.len) {
+            return;
+        }
+        self.limbs = try self.allocator.realloc(self.limbs, capacity);
+    }
 
-    //  n = q *  d + r
-    // -5 = 1 * -3 - 2
-    const eq = -1;
-    const er = -2;
+    /// Frees all associated memory.
+    pub fn deinit(self: *Managed) void {
+        self.allocator.free(self.limbs);
+        self.* = undefined;
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// Returns a `Managed` with the same value. The returned `Managed` is a deep copy and
+    /// can be modified separately from the original, and its resources are managed
+    /// separately from the original.
+    pub fn clone(other: Managed) !Managed {
+        return other.cloneWithDifferentAllocator(other.allocator);
+    }
 
-test "big.int div trunc single-single +/-" {
-    const u: i32 = 5;
-    const v: i32 = -3;
+    pub fn cloneWithDifferentAllocator(other: Managed, allocator: *Allocator) !Managed {
+        return Managed{
+            .allocator = allocator,
+            .metadata = other.metadata,
+            .limbs = block: {
+                var limbs = try allocator.alloc(Limb, other.len());
+                mem.copy(Limb, limbs[0..], other.limbs[0..other.len()]);
+                break :block limbs;
+            },
+        };
+    }
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+    /// Copies the value of the integer to an existing `Managed` so that they both have the same value.
+    /// Extra memory will be allocated if the receiver does not have enough capacity.
+    pub fn copy(self: *Managed, other: Const) !void {
+        if (self.limbs.ptr == other.limbs.ptr) return;
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+        try self.ensureCapacity(other.limbs.len);
+        mem.copy(Limb, self.limbs[0..], other.limbs[0..other.limbs.len]);
+        self.setMetadata(other.positive, other.limbs.len);
+    }
 
-    // n =  q *  d + r
-    // 5 = -1 * -3 + 2
-    const eq = -1;
-    const er = 2;
+    /// Efficiently swap a `Managed` with another. This swaps the limb pointers and a full copy is not
+    /// performed. The address of the limbs field will not be the same after this function.
+    pub fn swap(self: *Managed, other: *Managed) void {
+        mem.swap(Managed, self, other);
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// Debugging tool: prints the state to stderr.
+    pub fn dump(self: Managed) void {
+        for (self.limbs[0..self.len()]) |limb| {
+            std.debug.warn("{x} ", .{limb});
+        }
+        std.debug.warn("capacity={} positive={}\n", .{ self.limbs.len, self.positive });
+    }
 
-test "big.int div trunc single-single -/-" {
-    const u: i32 = -5;
-    const v: i32 = -3;
+    /// Negate the sign.
+    pub fn negate(self: *Managed) void {
+        self.metadata ^= sign_bit;
+    }
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+    /// Make positive.
+    pub fn abs(self: *Managed) void {
+        self.metadata &= ~sign_bit;
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    pub fn isOdd(self: Managed) bool {
+        return self.limbs[0] & 1 != 0;
+    }
 
-    //  n = q *  d + r
-    // -5 = 1 * -3 - 2
-    const eq = 1;
-    const er = -2;
+    pub fn isEven(self: Managed) bool {
+        return !self.isOdd();
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// Returns the number of bits required to represent the absolute value of an integer.
+    pub fn bitCountAbs(self: Managed) usize {
+        return self.toConst().bitCountAbs();
+    }
 
-test "big.int div floor single-single +/+" {
-    const u: i32 = 5;
-    const v: i32 = 3;
+    /// Returns the number of bits required to represent the integer in twos-complement form.
+    ///
+    /// If the integer is negative the value returned is the number of bits needed by a signed
+    /// integer to represent the value. If positive the value is the number of bits for an
+    /// unsigned integer. Any unsigned integer will fit in the signed integer with bitcount
+    /// one greater than the returned value.
+    ///
+    /// e.g. -127 returns 8 as it will fit in an i8. 127 returns 7 since it fits in a u7.
+    pub fn bitCountTwosComp(self: Managed) usize {
+        return self.toConst().bitCountTwosComp();
+    }
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+    pub fn fitsInTwosComp(self: Managed, is_signed: bool, bit_count: usize) bool {
+        return self.toConst().fitsInTwosComp(is_signed, bit_count);
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divFloor(&q, &r, a, b);
+    /// Returns whether self can fit into an integer of the requested type.
+    pub fn fits(self: Managed, comptime T: type) bool {
+        return self.toConst().fits(T);
+    }
 
-    //  n =  q *  d + r
-    //  5 =  1 *  3 + 2
-    const eq = 1;
-    const er = 2;
+    /// Returns the approximate size of the integer in the given base. Negative values accommodate for
+    /// the minus sign. This is used for determining the number of characters needed to print the
+    /// value. It is inexact and may exceed the given value by ~1-2 bytes.
+    pub fn sizeInBaseUpperBound(self: Managed, base: usize) usize {
+        return self.toConst().sizeInBaseUpperBound(base);
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// Sets an Managed to value. Value must be an primitive integer type.
+    pub fn set(self: *Managed, value: var) Allocator.Error!void {
+        try self.ensureCapacity(calcLimbLen(value));
+        var m = self.toMutable();
+        m.set(value);
+        self.setMetadata(m.positive, m.len);
+    }
 
-test "big.int div floor single-single -/+" {
-    const u: i32 = -5;
-    const v: i32 = 3;
+    pub const ConvertError = Const.ConvertError;
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+    /// Convert self to type T.
+    ///
+    /// Returns an error if self cannot be narrowed into the requested type without truncation.
+    pub fn to(self: Managed, comptime T: type) ConvertError!T {
+        return self.toConst().to(T);
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divFloor(&q, &r, a, b);
+    /// Set self from the string representation `value`.
+    ///
+    /// `value` must contain only digits <= `base` and is case insensitive.  Base prefixes are
+    /// not allowed (e.g. 0x43 should simply be 43).  Underscores in the input string are
+    /// ignored and can be used as digit separators.
+    ///
+    /// Returns an error if memory could not be allocated or `value` has invalid digits for the
+    /// requested base.
+    ///
+    /// self's allocator is used for temporary storage to boost multiplication performance.
+    pub fn setString(self: *Managed, base: u8, value: []const u8) !void {
+        if (base < 2 or base > 16) return error.InvalidBase;
+        const den = (@sizeOf(Limb) * 8 / base);
+        try self.ensureCapacity((value.len + (den - 1)) / den);
+        const limbs_buffer = try self.allocator.alloc(Limb, calcSetStringLimbsBufferLen(base, value.len));
+        defer self.allocator.free(limbs_buffer);
+        var m = self.toMutable();
+        try m.setString(base, value, limbs_buffer, self.allocator);
+        self.setMetadata(m.positive, m.len);
+    }
 
-    //  n =  q *  d + r
-    // -5 = -2 *  3 + 1
-    const eq = -2;
-    const er = 1;
+    /// Converts self to a string in the requested base. Memory is allocated from the provided
+    /// allocator and not the one present in self.
+    pub fn toString(self: Managed, allocator: *Allocator, base: u8, uppercase: bool) ![]u8 {
+        if (base < 2 or base > 16) return error.InvalidBase;
+        return self.toConst().toStringAlloc(self.allocator, base, uppercase);
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// To allow `std.fmt.format` to work with `Managed`.
+    /// If the integer is larger than `pow(2, 64 * @sizeOf(usize) * 8), this function will fail
+    /// to print the string, printing "(BigInt)" instead of a number.
+    /// This is because the rendering algorithm requires reversing a string, which requires O(N) memory.
+    /// See `toString` and `toStringAlloc` for a way to print big integers without failure.
+    pub fn format(
+        self: Managed,
+        comptime fmt: []const u8,
+        options: std.fmt.FormatOptions,
+        out_stream: var,
+    ) !void {
+        return self.toConst().format(fmt, options, out_stream);
+    }
 
-test "big.int div floor single-single +/-" {
-    const u: i32 = 5;
-    const v: i32 = -3;
+    /// Returns math.Order.lt, math.Order.eq, math.Order.gt if |a| < |b|, |a| ==
+    /// |b| or |a| > |b| respectively.
+    pub fn orderAbs(a: Managed, b: Managed) math.Order {
+        return a.toConst().orderAbs(b.toConst());
+    }
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+    /// Returns math.Order.lt, math.Order.eq, math.Order.gt if a < b, a == b or a
+    /// > b respectively.
+    pub fn order(a: Managed, b: Managed) math.Order {
+        return a.toConst().order(b.toConst());
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divFloor(&q, &r, a, b);
+    /// Returns true if a == 0.
+    pub fn eqZero(a: Managed) bool {
+        return a.toConst().eqZero();
+    }
 
-    //  n =  q *  d + r
-    //  5 = -2 * -3 - 1
-    const eq = -2;
-    const er = -1;
+    /// Returns true if |a| == |b|.
+    pub fn eqAbs(a: Managed, b: Managed) bool {
+        return a.toConst().eqAbs(b.toConst());
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// Returns true if a == b.
+    pub fn eq(a: Managed, b: Managed) bool {
+        return a.toConst().eq(b.toConst());
+    }
 
-test "big.int div floor single-single -/-" {
-    const u: i32 = -5;
-    const v: i32 = -3;
+    /// Normalize a possible sequence of leading zeros.
+    ///
+    /// [1, 2, 3, 4, 0] -> [1, 2, 3, 4]
+    /// [1, 2, 0, 0, 0] -> [1, 2]
+    /// [0, 0, 0, 0, 0] -> [0]
+    pub fn normalize(r: *Managed, length: usize) void {
+        assert(length > 0);
+        assert(length <= r.limbs.len);
 
-    var a = try Int.initSet(testing.allocator, u);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, v);
-    defer b.deinit();
+        var j = length;
+        while (j > 0) : (j -= 1) {
+            if (r.limbs[j - 1] != 0) {
+                break;
+            }
+        }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divFloor(&q, &r, a, b);
+        // Handle zero
+        r.setLen(if (j != 0) j else 1);
+    }
 
-    //  n =  q *  d + r
-    // -5 =  2 * -3 + 1
-    const eq = 1;
-    const er = -2;
+    /// r = a + scalar
+    ///
+    /// r and a may be aliases.
+    /// scalar is a primitive integer type.
+    ///
+    /// Returns an error if memory could not be allocated.
+    pub fn addScalar(r: *Managed, a: Const, scalar: var) Allocator.Error!void {
+        try r.ensureCapacity(math.max(a.limbs.len, calcLimbLen(scalar)) + 1);
+        var m = r.toMutable();
+        m.addScalar(a, scalar);
+        r.setMetadata(m.positive, m.len);
+    }
 
-    testing.expect((try q.to(i32)) == eq);
-    testing.expect((try r.to(i32)) == er);
-}
+    /// r = a + b
+    ///
+    /// r, a and b may be aliases.
+    ///
+    /// Returns an error if memory could not be allocated.
+    pub fn add(r: *Managed, a: Const, b: Const) Allocator.Error!void {
+        try r.ensureCapacity(math.max(a.limbs.len, b.limbs.len) + 1);
+        var m = r.toMutable();
+        m.add(a, b);
+        r.setMetadata(m.positive, m.len);
+    }
 
-test "big.int div multi-multi with rem" {
-    var a = try Int.initSet(testing.allocator, 0x8888999911110000ffffeeeeddddccccbbbbaaaa9999);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x99990000111122223333);
-    defer b.deinit();
+    /// r = a - b
+    ///
+    /// r, a and b may be aliases.
+    ///
+    /// Returns an error if memory could not be allocated.
+    pub fn sub(r: *Managed, a: Const, b: Const) !void {
+        try r.ensureCapacity(math.max(a.limbs.len, b.limbs.len) + 1);
+        var m = r.toMutable();
+        m.sub(a, b);
+        r.setMetadata(m.positive, m.len);
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// rma = a * b
+    ///
+    /// rma, a and b may be aliases. However, it is more efficient if rma does not alias a or b.
+    ///
+    /// Returns an error if memory could not be allocated.
+    ///
+    /// rma's allocator is used for temporary storage to speed up the multiplication.
+    pub fn mul(rma: *Managed, a: Const, b: Const) !void {
+        try rma.ensureCapacity(a.limbs.len + b.limbs.len + 1);
+        var alias_count: usize = 0;
+        if (rma.limbs.ptr == a.limbs.ptr)
+            alias_count += 1;
+        if (rma.limbs.ptr == b.limbs.ptr)
+            alias_count += 1;
+        var m = rma.toMutable();
+        if (alias_count == 0) {
+            m.mulNoAlias(a, b, rma.allocator);
+        } else {
+            const limb_count = calcMulLimbsBufferLen(a.limbs.len, b.limbs.len, alias_count);
+            const limbs_buffer = try rma.allocator.alloc(Limb, limb_count);
+            defer rma.allocator.free(limbs_buffer);
+            m.mul(a, b, limbs_buffer, rma.allocator);
+        }
+        rma.setMetadata(m.positive, m.len);
+    }
 
-    testing.expect((try q.to(u128)) == 0xe38f38e39161aaabd03f0f1b);
-    testing.expect((try r.to(u128)) == 0x28de0acacd806823638);
-}
+    /// q = a / b (rem r)
+    ///
+    /// a / b are floored (rounded towards 0).
+    ///
+    /// Returns an error if memory could not be allocated.
+    ///
+    /// q's allocator is used for temporary storage to speed up the multiplication.
+    pub fn divFloor(q: *Managed, r: *Managed, a: Const, b: Const) !void {
+        try q.ensureCapacity(a.limbs.len + b.limbs.len + 1);
+        try r.ensureCapacity(a.limbs.len);
+        var mq = q.toMutable();
+        var mr = r.toMutable();
+        const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.limbs.len, b.limbs.len));
+        defer q.allocator.free(limbs_buffer);
+        mq.divFloor(&mr, a, b, limbs_buffer, q.allocator);
+        q.setMetadata(mq.positive, mq.len);
+        r.setMetadata(mr.positive, mr.len);
+    }
 
-test "big.int div multi-multi no rem" {
-    var a = try Int.initSet(testing.allocator, 0x8888999911110000ffffeeeedb4fec200ee3a4286361);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x99990000111122223333);
-    defer b.deinit();
+    /// q = a / b (rem r)
+    ///
+    /// a / b are truncated (rounded towards -inf).
+    ///
+    /// Returns an error if memory could not be allocated.
+    ///
+    /// q's allocator is used for temporary storage to speed up the multiplication.
+    pub fn divTrunc(q: *Managed, r: *Managed, a: Const, b: Const) !void {
+        try q.ensureCapacity(a.limbs.len + b.limbs.len + 1);
+        try r.ensureCapacity(a.limbs.len);
+        var mq = q.toMutable();
+        var mr = r.toMutable();
+        const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.limbs.len, b.limbs.len));
+        defer q.allocator.free(limbs_buffer);
+        mq.divTrunc(&mr, a, b, limbs_buffer, q.allocator);
+        q.setMetadata(mq.positive, mq.len);
+        r.setMetadata(mr.positive, mr.len);
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// r = a << shift, in other words, r = a * 2^shift
+    pub fn shiftLeft(r: *Managed, a: Managed, shift: usize) !void {
+        try r.ensureCapacity(a.len() + (shift / Limb.bit_count) + 1);
+        var m = r.toMutable();
+        m.shiftLeft(a.toConst(), shift);
+        r.setMetadata(m.positive, m.len);
+    }
 
-    testing.expect((try q.to(u128)) == 0xe38f38e39161aaabd03f0f1b);
-    testing.expect((try r.to(u128)) == 0);
-}
+    /// r = a >> shift
+    pub fn shiftRight(r: *Managed, a: Managed, shift: usize) !void {
+        if (a.len() <= shift / Limb.bit_count) {
+            r.metadata = 1;
+            r.limbs[0] = 0;
+            return;
+        }
 
-test "big.int div multi-multi (2 branch)" {
-    var a = try Int.initSet(testing.allocator, 0x866666665555555588888887777777761111111111111111);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x86666666555555554444444433333333);
-    defer b.deinit();
+        try r.ensureCapacity(a.len() - (shift / Limb.bit_count));
+        var m = r.toMutable();
+        m.shiftRight(a.toConst(), shift);
+        r.setMetadata(m.positive, m.len);
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// r = a | b
+    ///
+    /// a and b are zero-extended to the longer of a or b.
+    pub fn bitOr(r: *Managed, a: Managed, b: Managed) !void {
+        try r.ensureCapacity(math.max(a.len(), b.len()));
+        var m = r.toMutable();
+        m.bitOr(a.toConst(), b.toConst());
+        r.setMetadata(m.positive, m.len);
+    }
 
-    testing.expect((try q.to(u128)) == 0x10000000000000000);
-    testing.expect((try r.to(u128)) == 0x44444443444444431111111111111111);
-}
+    /// r = a & b
+    pub fn bitAnd(r: *Managed, a: Managed, b: Managed) !void {
+        try r.ensureCapacity(math.min(a.len(), b.len()));
+        var m = r.toMutable();
+        m.bitAnd(a.toConst(), b.toConst());
+        r.setMetadata(m.positive, m.len);
+    }
 
-test "big.int div multi-multi (3.1/3.3 branch)" {
-    var a = try Int.initSet(testing.allocator, 0x11111111111111111111111111111111111111111111111111111111111111);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x1111111111111111111111111111111111111111171);
-    defer b.deinit();
+    /// r = a ^ b
+    pub fn bitXor(r: *Managed, a: Managed, b: Managed) !void {
+        try r.ensureCapacity(math.max(a.len(), b.len()));
+        var m = r.toMutable();
+        m.bitXor(a.toConst(), b.toConst());
+        r.setMetadata(m.positive, m.len);
+    }
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    /// rma may alias x or y.
+    /// x and y may alias each other.
+    ///
+    /// rma's allocator is used for temporary storage to boost multiplication performance.
+    pub fn gcd(rma: *Managed, x: Managed, y: Managed) !void {
+        try rma.ensureCapacity(math.min(x.len(), y.len()));
+        var m = rma.toMutable();
+        var limbs_buffer = std.ArrayList(Limb).init(rma.allocator);
+        defer limbs_buffer.deinit();
+        try m.gcd(x.toConst(), y.toConst(), &limbs_buffer);
+        rma.setMetadata(m.positive, m.len);
+    }
+};
 
-    testing.expect((try q.to(u128)) == 0xfffffffffffffffffff);
-    testing.expect((try r.to(u256)) == 0x1111111111111111111110b12222222222222222282);
-}
+/// Knuth 4.3.1, Algorithm M.
+///
+/// r MUST NOT alias any of a or b.
+fn llmulacc(opt_allocator: ?*Allocator, r: []Limb, a: []const Limb, b: []const Limb) void {
+    @setRuntimeSafety(false);
+
+    const a_norm = a[0..llnormalize(a)];
+    const b_norm = b[0..llnormalize(b)];
+    var x = a_norm;
+    var y = b_norm;
+    if (a_norm.len > b_norm.len) {
+        x = b_norm;
+        y = a_norm;
+    }
+
+    assert(r.len >= x.len + y.len + 1);
+
+    // 48 is a pretty abitrary size chosen based on performance of a factorial program.
+    if (x.len > 48) {
+        if (opt_allocator) |allocator| {
+            llmulacc_karatsuba(allocator, r, x, y) catch |err| switch (err) {
+                error.OutOfMemory => {}, // handled below
+            };
+        }
+    }
 
-test "big.int div multi-single zero-limb trailing" {
-    var a = try Int.initSet(testing.allocator, 0x60000000000000000000000000000000000000000000000000000000000000000);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x10000000000000000);
-    defer b.deinit();
-
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
-
-    var expected = try Int.initSet(testing.allocator, 0x6000000000000000000000000000000000000000000000000);
-    defer expected.deinit();
-    testing.expect(q.eq(expected));
-    testing.expect(r.eqZero());
+    // Basecase multiplication
+    var i: usize = 0;
+    while (i < x.len) : (i += 1) {
+        llmulDigit(r[i..], y, x[i]);
+    }
 }
 
-test "big.int div multi-multi zero-limb trailing (with rem)" {
-    var a = try Int.initSet(testing.allocator, 0x86666666555555558888888777777776111111111111111100000000000000000000000000000000);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x8666666655555555444444443333333300000000000000000000000000000000);
-    defer b.deinit();
-
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
-
-    testing.expect((try q.to(u128)) == 0x10000000000000000);
+/// Knuth 4.3.1, Algorithm M.
+///
+/// r MUST NOT alias any of a or b.
+fn llmulacc_karatsuba(allocator: *Allocator, r: []Limb, x: []const Limb, y: []const Limb) error{OutOfMemory}!void {
+    @setRuntimeSafety(false);
 
-    const rs = try r.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(rs);
-    testing.expect(std.mem.eql(u8, rs, "4444444344444443111111111111111100000000000000000000000000000000"));
-}
+    assert(r.len >= x.len + y.len + 1);
 
-test "big.int div multi-multi zero-limb trailing (with rem) and dividend zero-limb count > divisor zero-limb count" {
-    var a = try Int.initSet(testing.allocator, 0x8666666655555555888888877777777611111111111111110000000000000000);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x8666666655555555444444443333333300000000000000000000000000000000);
-    defer b.deinit();
+    const split = @divFloor(x.len, 2);
+    var x0 = x[0..split];
+    var x1 = x[split..x.len];
+    var y0 = y[0..split];
+    var y1 = y[split..y.len];
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    var tmp = try allocator.alloc(Limb, x1.len + y1.len + 1);
+    defer allocator.free(tmp);
+    mem.set(Limb, tmp, 0);
 
-    testing.expect((try q.to(u128)) == 0x1);
+    llmulacc(allocator, tmp, x1, y1);
 
-    const rs = try r.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(rs);
-    testing.expect(std.mem.eql(u8, rs, "444444434444444311111111111111110000000000000000"));
-}
+    var length = llnormalize(tmp);
+    _ = llaccum(r[split..], tmp[0..length]);
+    _ = llaccum(r[split * 2 ..], tmp[0..length]);
 
-test "big.int div multi-multi zero-limb trailing (with rem) and dividend zero-limb count < divisor zero-limb count" {
-    var a = try Int.initSet(testing.allocator, 0x86666666555555558888888777777776111111111111111100000000000000000000000000000000);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x866666665555555544444444333333330000000000000000);
-    defer b.deinit();
-
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
-
-    const qs = try q.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(qs);
-    testing.expect(std.mem.eql(u8, qs, "10000000000000000820820803105186f"));
-
-    const rs = try r.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(rs);
-    testing.expect(std.mem.eql(u8, rs, "4e11f2baa5896a321d463b543d0104e30000000000000000"));
-}
+    mem.set(Limb, tmp[0..length], 0);
 
-test "big.int div multi-multi fuzz case #1" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-    var b = try Int.init(testing.allocator);
-    defer b.deinit();
+    llmulacc(allocator, tmp, x0, y0);
 
-    try a.setString(16, "ffffffffffffffffffffffffffffc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
-    try b.setString(16, "3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000000000000000000000000000000001ffffffffffffffffffffffffffffffffffffffffffffffffffc000000000000000000000000000000007fffffffffff");
+    length = llnormalize(tmp);
+    _ = llaccum(r[0..], tmp[0..length]);
+    _ = llaccum(r[split..], tmp[0..length]);
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    const x_cmp = llcmp(x1, x0);
+    const y_cmp = llcmp(y1, y0);
+    if (x_cmp * y_cmp == 0) {
+        return;
+    }
+    const x0_len = llnormalize(x0);
+    const x1_len = llnormalize(x1);
+    var j0 = try allocator.alloc(Limb, math.max(x0_len, x1_len));
+    defer allocator.free(j0);
+    if (x_cmp == 1) {
+        llsub(j0, x1[0..x1_len], x0[0..x0_len]);
+    } else {
+        llsub(j0, x0[0..x0_len], x1[0..x1_len]);
+    }
 
-    const qs = try q.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(qs);
-    testing.expect(std.mem.eql(u8, qs, "3ffffffffffffffffffffffffffff0000000000000000000000000000000000001ffffffffffffffffffffffffffff7fffffffe000000000000000000000000000180000000000000000000003fffffbfffffffdfffffffffffffeffff800000100101000000100000000020003fffffdfbfffffe3ffffffffffffeffff7fffc00800a100000017ffe000002000400007efbfff7fe9f00000037ffff3fff7fffa004006100000009ffe00000190038200bf7d2ff7fefe80400060000f7d7f8fbf9401fe38e0403ffc0bdffffa51102c300d7be5ef9df4e5060007b0127ad3fa69f97d0f820b6605ff617ddf7f32ad7a05c0d03f2e7bc78a6000e087a8bbcdc59e07a5a079128a7861f553ddebed7e8e56701756f9ead39b48cd1b0831889ea6ec1fddf643d0565b075ff07e6caea4e2854ec9227fd635ed60a2f5eef2893052ffd54718fa08604acbf6a15e78a467c4a3c53c0278af06c4416573f925491b195e8fd79302cb1aaf7caf4ecfc9aec1254cc969786363ac729f914c6ddcc26738d6b0facd54eba026580aba2eb6482a088b0d224a8852420b91ec1"));
+    const y0_len = llnormalize(y0);
+    const y1_len = llnormalize(y1);
+    var j1 = try allocator.alloc(Limb, math.max(y0_len, y1_len));
+    defer allocator.free(j1);
+    if (y_cmp == 1) {
+        llsub(j1, y1[0..y1_len], y0[0..y0_len]);
+    } else {
+        llsub(j1, y0[0..y0_len], y1[0..y1_len]);
+    }
+    const j0_len = llnormalize(j0);
+    const j1_len = llnormalize(j1);
+    if (x_cmp == y_cmp) {
+        mem.set(Limb, tmp[0..length], 0);
+        llmulacc(allocator, tmp, j0, j1);
 
-    const rs = try r.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(rs);
-    testing.expect(std.mem.eql(u8, rs, "310d1d4c414426b4836c2635bad1df3a424e50cbdd167ffccb4dfff57d36b4aae0d6ca0910698220171a0f3373c1060a046c2812f0027e321f72979daa5e7973214170d49e885de0c0ecc167837d44502430674a82522e5df6a0759548052420b91ec1"));
+        length = llnormalize(tmp);
+        llsub(r[split..], r[split..], tmp[0..length]);
+    } else {
+        llmulacc(allocator, r[split..], j0, j1);
+    }
 }
 
-test "big.int div multi-multi fuzz case #2" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-    var b = try Int.init(testing.allocator);
-    defer b.deinit();
+// r = r + a
+fn llaccum(r: []Limb, a: []const Limb) Limb {
+    @setRuntimeSafety(false);
+    assert(r.len != 0 and a.len != 0);
+    assert(r.len >= a.len);
 
-    try a.setString(16, "3ffffffffe00000000000000000000000000fffffffffffffffffffffffffffffffffffffffffffffffffffffffffe000000000000000000000000000000000000000000000000000000000000001fffffffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffc000000000000000000000000000000000000000000000000000000000000000");
-    try b.setString(16, "ffc0000000000000000000000000000000000000000000000000");
+    var i: usize = 0;
+    var carry: Limb = 0;
 
-    var q = try Int.init(testing.allocator);
-    defer q.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-    try Int.divTrunc(&q, &r, a, b);
+    while (i < a.len) : (i += 1) {
+        var c: Limb = 0;
+        c += @boolToInt(@addWithOverflow(Limb, r[i], a[i], &r[i]));
+        c += @boolToInt(@addWithOverflow(Limb, r[i], carry, &r[i]));
+        carry = c;
+    }
 
-    const qs = try q.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(qs);
-    testing.expect(std.mem.eql(u8, qs, "40100400fe3f8fe3f8fe3f8fe3f8fe3f8fe4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f91e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4992649926499264991e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4792e4b92e4b92e4b92e4b92a4a92a4a92a4"));
+    while ((carry != 0) and i < r.len) : (i += 1) {
+        carry = @boolToInt(@addWithOverflow(Limb, r[i], carry, &r[i]));
+    }
 
-    const rs = try r.toString(testing.allocator, 16, false);
-    defer testing.allocator.free(rs);
-    testing.expect(std.mem.eql(u8, rs, "a900000000000000000000000000000000000000000000000000"));
+    return carry;
 }
 
-test "big.int shift-right single" {
-    var a = try Int.initSet(testing.allocator, 0xffff0000);
-    defer a.deinit();
-    try a.shiftRight(a, 16);
-
-    testing.expect((try a.to(u32)) == 0xffff);
-}
+/// Returns -1, 0, 1 if |a| < |b|, |a| == |b| or |a| > |b| respectively for limbs.
+pub fn llcmp(a: []const Limb, b: []const Limb) i8 {
+    @setRuntimeSafety(false);
+    const a_len = llnormalize(a);
+    const b_len = llnormalize(b);
+    if (a_len < b_len) {
+        return -1;
+    }
+    if (a_len > b_len) {
+        return 1;
+    }
 
-test "big.int shift-right multi" {
-    var a = try Int.initSet(testing.allocator, 0xffff0000eeee1111dddd2222cccc3333);
-    defer a.deinit();
-    try a.shiftRight(a, 67);
+    var i: usize = a_len - 1;
+    while (i != 0) : (i -= 1) {
+        if (a[i] != b[i]) {
+            break;
+        }
+    }
 
-    testing.expect((try a.to(u64)) == 0x1fffe0001dddc222);
+    if (a[i] < b[i]) {
+        return -1;
+    } else if (a[i] > b[i]) {
+        return 1;
+    } else {
+        return 0;
+    }
 }
 
-test "big.int shift-left single" {
-    var a = try Int.initSet(testing.allocator, 0xffff);
-    defer a.deinit();
-    try a.shiftLeft(a, 16);
+fn llmulDigit(acc: []Limb, y: []const Limb, xi: Limb) void {
+    @setRuntimeSafety(false);
+    if (xi == 0) {
+        return;
+    }
 
-    testing.expect((try a.to(u64)) == 0xffff0000);
-}
+    var carry: usize = 0;
+    var a_lo = acc[0..y.len];
+    var a_hi = acc[y.len..];
 
-test "big.int shift-left multi" {
-    var a = try Int.initSet(testing.allocator, 0x1fffe0001dddc222);
-    defer a.deinit();
-    try a.shiftLeft(a, 67);
+    var j: usize = 0;
+    while (j < a_lo.len) : (j += 1) {
+        a_lo[j] = @call(.{ .modifier = .always_inline }, addMulLimbWithCarry, .{ a_lo[j], y[j], xi, &carry });
+    }
 
-    testing.expect((try a.to(u128)) == 0xffff0000eeee11100000000000000000);
+    j = 0;
+    while ((carry != 0) and (j < a_hi.len)) : (j += 1) {
+        carry = @boolToInt(@addWithOverflow(Limb, a_hi[j], carry, &a_hi[j]));
+    }
 }
 
-test "big.int shift-right negative" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
-
-    try a.shiftRight(try Int.initSet(testing.allocator, -20), 2);
-    defer a.deinit();
-    testing.expect((try a.to(i32)) == -20 >> 2);
+/// returns the min length the limb could be.
+fn llnormalize(a: []const Limb) usize {
+    @setRuntimeSafety(false);
+    var j = a.len;
+    while (j > 0) : (j -= 1) {
+        if (a[j - 1] != 0) {
+            break;
+        }
+    }
 
-    try a.shiftRight(try Int.initSet(testing.allocator, -5), 10);
-    defer a.deinit();
-    testing.expect((try a.to(i32)) == -5 >> 10);
+    // Handle zero
+    return if (j != 0) j else 1;
 }
 
-test "big.int shift-left negative" {
-    var a = try Int.init(testing.allocator);
-    defer a.deinit();
+/// Knuth 4.3.1, Algorithm S.
+fn llsub(r: []Limb, a: []const Limb, b: []const Limb) void {
+    @setRuntimeSafety(false);
+    assert(a.len != 0 and b.len != 0);
+    assert(a.len > b.len or (a.len == b.len and a[a.len - 1] >= b[b.len - 1]));
+    assert(r.len >= a.len);
 
-    try a.shiftRight(try Int.initSet(testing.allocator, -10), 1232);
-    defer a.deinit();
-    testing.expect((try a.to(i32)) == -10 >> 1232);
-}
+    var i: usize = 0;
+    var borrow: Limb = 0;
 
-test "big.int bitwise and simple" {
-    var a = try Int.initSet(testing.allocator, 0xffffffff11111111);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0xeeeeeeee22222222);
-    defer b.deinit();
+    while (i < b.len) : (i += 1) {
+        var c: Limb = 0;
+        c += @boolToInt(@subWithOverflow(Limb, a[i], b[i], &r[i]));
+        c += @boolToInt(@subWithOverflow(Limb, r[i], borrow, &r[i]));
+        borrow = c;
+    }
 
-    try a.bitAnd(a, b);
+    while (i < a.len) : (i += 1) {
+        borrow = @boolToInt(@subWithOverflow(Limb, a[i], borrow, &r[i]));
+    }
 
-    testing.expect((try a.to(u64)) == 0xeeeeeeee00000000);
+    assert(borrow == 0);
 }
 
-test "big.int bitwise and multi-limb" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb) + 1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, maxInt(Limb));
-    defer b.deinit();
-
-    try a.bitAnd(a, b);
+/// Knuth 4.3.1, Algorithm A.
+fn lladd(r: []Limb, a: []const Limb, b: []const Limb) void {
+    @setRuntimeSafety(false);
+    assert(a.len != 0 and b.len != 0);
+    assert(a.len >= b.len);
+    assert(r.len >= a.len + 1);
 
-    testing.expect((try a.to(u128)) == 0);
-}
+    var i: usize = 0;
+    var carry: Limb = 0;
 
-test "big.int bitwise xor simple" {
-    var a = try Int.initSet(testing.allocator, 0xffffffff11111111);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0xeeeeeeee22222222);
-    defer b.deinit();
+    while (i < b.len) : (i += 1) {
+        var c: Limb = 0;
+        c += @boolToInt(@addWithOverflow(Limb, a[i], b[i], &r[i]));
+        c += @boolToInt(@addWithOverflow(Limb, r[i], carry, &r[i]));
+        carry = c;
+    }
 
-    try a.bitXor(a, b);
+    while (i < a.len) : (i += 1) {
+        carry = @boolToInt(@addWithOverflow(Limb, a[i], carry, &r[i]));
+    }
 
-    testing.expect((try a.to(u64)) == 0x1111111133333333);
+    r[i] = carry;
 }
 
-test "big.int bitwise xor multi-limb" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb) + 1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, maxInt(Limb));
-    defer b.deinit();
+/// Knuth 4.3.1, Exercise 16.
+fn lldiv1(quo: []Limb, rem: *Limb, a: []const Limb, b: Limb) void {
+    @setRuntimeSafety(false);
+    assert(a.len > 1 or a[0] >= b);
+    assert(quo.len >= a.len);
 
-    try a.bitXor(a, b);
+    rem.* = 0;
+    for (a) |_, ri| {
+        const i = a.len - ri - 1;
+        const pdiv = ((@as(DoubleLimb, rem.*) << Limb.bit_count) | a[i]);
 
-    testing.expect((try a.to(DoubleLimb)) == (maxInt(Limb) + 1) ^ maxInt(Limb));
+        if (pdiv == 0) {
+            quo[i] = 0;
+            rem.* = 0;
+        } else if (pdiv < b) {
+            quo[i] = 0;
+            rem.* = @truncate(Limb, pdiv);
+        } else if (pdiv == b) {
+            quo[i] = 1;
+            rem.* = 0;
+        } else {
+            quo[i] = @truncate(Limb, @divTrunc(pdiv, b));
+            rem.* = @truncate(Limb, pdiv - (quo[i] *% b));
+        }
+    }
 }
 
-test "big.int bitwise or simple" {
-    var a = try Int.initSet(testing.allocator, 0xffffffff11111111);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0xeeeeeeee22222222);
-    defer b.deinit();
-
-    try a.bitOr(a, b);
+fn llshl(r: []Limb, a: []const Limb, shift: usize) void {
+    @setRuntimeSafety(false);
+    assert(a.len >= 1);
+    assert(r.len >= a.len + (shift / Limb.bit_count) + 1);
 
-    testing.expect((try a.to(u64)) == 0xffffffff33333333);
-}
+    const limb_shift = shift / Limb.bit_count + 1;
+    const interior_limb_shift = @intCast(Log2Limb, shift % Limb.bit_count);
 
-test "big.int bitwise or multi-limb" {
-    var a = try Int.initSet(testing.allocator, maxInt(Limb) + 1);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, maxInt(Limb));
-    defer b.deinit();
+    var carry: Limb = 0;
+    var i: usize = 0;
+    while (i < a.len) : (i += 1) {
+        const src_i = a.len - i - 1;
+        const dst_i = src_i + limb_shift;
 
-    try a.bitOr(a, b);
+        const src_digit = a[src_i];
+        r[dst_i] = carry | @call(.{ .modifier = .always_inline }, math.shr, .{
+            Limb,
+            src_digit,
+            Limb.bit_count - @intCast(Limb, interior_limb_shift),
+        });
+        carry = (src_digit << interior_limb_shift);
+    }
 
-    // TODO: big.int.cpp or is wrong on multi-limb.
-    testing.expect((try a.to(DoubleLimb)) == (maxInt(Limb) + 1) + maxInt(Limb));
+    r[limb_shift - 1] = carry;
+    mem.set(Limb, r[0 .. limb_shift - 1], 0);
 }
 
-test "big.int var args" {
-    var a = try Int.initSet(testing.allocator, 5);
-    defer a.deinit();
+fn llshr(r: []Limb, a: []const Limb, shift: usize) void {
+    @setRuntimeSafety(false);
+    assert(a.len >= 1);
+    assert(r.len >= a.len - (shift / Limb.bit_count));
 
-    const b = try Int.initSet(testing.allocator, 6);
-    defer b.deinit();
-    try a.add(a, b);
-    testing.expect((try a.to(u64)) == 11);
+    const limb_shift = shift / Limb.bit_count;
+    const interior_limb_shift = @intCast(Log2Limb, shift % Limb.bit_count);
 
-    const c = try Int.initSet(testing.allocator, 11);
-    defer c.deinit();
-    testing.expect(a.cmp(c) == .eq);
+    var carry: Limb = 0;
+    var i: usize = 0;
+    while (i < a.len - limb_shift) : (i += 1) {
+        const src_i = a.len - i - 1;
+        const dst_i = src_i - limb_shift;
 
-    const d = try Int.initSet(testing.allocator, 14);
-    defer d.deinit();
-    testing.expect(a.cmp(d) != .gt);
+        const src_digit = a[src_i];
+        r[dst_i] = carry | (src_digit >> interior_limb_shift);
+        carry = @call(.{ .modifier = .always_inline }, math.shl, .{
+            Limb,
+            src_digit,
+            Limb.bit_count - @intCast(Limb, interior_limb_shift),
+        });
+    }
 }
 
-test "big.int gcd non-one small" {
-    var a = try Int.initSet(testing.allocator, 17);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 97);
-    defer b.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
+fn llor(r: []Limb, a: []const Limb, b: []const Limb) void {
+    @setRuntimeSafety(false);
+    assert(r.len >= a.len);
+    assert(a.len >= b.len);
 
-    try r.gcd(a, b);
-
-    testing.expect((try r.to(u32)) == 1);
+    var i: usize = 0;
+    while (i < b.len) : (i += 1) {
+        r[i] = a[i] | b[i];
+    }
+    while (i < a.len) : (i += 1) {
+        r[i] = a[i];
+    }
 }
 
-test "big.int gcd non-one small" {
-    var a = try Int.initSet(testing.allocator, 4864);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 3458);
-    defer b.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-
-    try r.gcd(a, b);
+fn lland(r: []Limb, a: []const Limb, b: []const Limb) void {
+    @setRuntimeSafety(false);
+    assert(r.len >= b.len);
+    assert(a.len >= b.len);
 
-    testing.expect((try r.to(u32)) == 38);
+    var i: usize = 0;
+    while (i < b.len) : (i += 1) {
+        r[i] = a[i] & b[i];
+    }
 }
 
-test "big.int gcd non-one large" {
-    var a = try Int.initSet(testing.allocator, 0xffffffffffffffff);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0xffffffffffffffff7777);
-    defer b.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
+fn llxor(r: []Limb, a: []const Limb, b: []const Limb) void {
+    assert(r.len >= a.len);
+    assert(a.len >= b.len);
 
-    try r.gcd(a, b);
-
-    testing.expect((try r.to(u32)) == 4369);
+    var i: usize = 0;
+    while (i < b.len) : (i += 1) {
+        r[i] = a[i] ^ b[i];
+    }
+    while (i < a.len) : (i += 1) {
+        r[i] = a[i];
+    }
 }
 
-test "big.int gcd large multi-limb result" {
-    var a = try Int.initSet(testing.allocator, 0x12345678123456781234567812345678123456781234567812345678);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 0x12345671234567123456712345671234567123456712345671234567);
-    defer b.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-
-    try r.gcd(a, b);
+// Storage must live for the lifetime of the returned value
+fn fixedIntFromSignedDoubleLimb(A: SignedDoubleLimb, storage: []Limb) Mutable {
+    assert(storage.len >= 2);
 
-    testing.expect((try r.to(u256)) == 0xf000000ff00000fff0000ffff000fffff00ffffff1);
+    const A_is_positive = A >= 0;
+    const Au = @intCast(DoubleLimb, if (A < 0) -A else A);
+    storage[0] = @truncate(Limb, Au);
+    storage[1] = @truncate(Limb, Au >> Limb.bit_count);
+    return .{
+        .limbs = storage[0..2],
+        .positive = A_is_positive,
+        .len = 2,
+    };
 }
 
-test "big.int gcd one large" {
-    var a = try Int.initSet(testing.allocator, 1897056385327307);
-    defer a.deinit();
-    var b = try Int.initSet(testing.allocator, 2251799813685248);
-    defer b.deinit();
-    var r = try Int.init(testing.allocator);
-    defer r.deinit();
-
-    try r.gcd(a, b);
-
-    testing.expect((try r.to(u64)) == 1);
+test "" {
+    _ = @import("int_test.zig");
 }
diff --git a/lib/std/math/big/int_test.zig b/lib/std/math/big/int_test.zig
new file mode 100644
index 0000000000..d7e354879e
--- /dev/null
+++ b/lib/std/math/big/int_test.zig
@@ -0,0 +1,1455 @@
+const std = @import("../../std.zig");
+const mem = std.mem;
+const testing = std.testing;
+const Managed = std.math.big.int.Managed;
+const Limb = std.math.big.Limb;
+const DoubleLimb = std.math.big.DoubleLimb;
+const maxInt = std.math.maxInt;
+const minInt = std.math.minInt;
+
+// NOTE: All the following tests assume the max machine-word will be 64-bit.
+//
+// They will still run on larger than this and should pass, but the multi-limb code-paths
+// may be untested in some cases.
+
+test "big.int comptime_int set" {
+    comptime var s = 0xefffffff00000001eeeeeeefaaaaaaab;
+    var a = try Managed.initSet(testing.allocator, s);
+    defer a.deinit();
+
+    const s_limb_count = 128 / Limb.bit_count;
+
+    comptime var i: usize = 0;
+    inline while (i < s_limb_count) : (i += 1) {
+        const result = @as(Limb, s & maxInt(Limb));
+        s >>= Limb.bit_count / 2;
+        s >>= Limb.bit_count / 2;
+        testing.expect(a.limbs[i] == result);
+    }
+}
+
+test "big.int comptime_int set negative" {
+    var a = try Managed.initSet(testing.allocator, -10);
+    defer a.deinit();
+
+    testing.expect(a.limbs[0] == 10);
+    testing.expect(a.isPositive() == false);
+}
+
+test "big.int int set unaligned small" {
+    var a = try Managed.initSet(testing.allocator, @as(u7, 45));
+    defer a.deinit();
+
+    testing.expect(a.limbs[0] == 45);
+    testing.expect(a.isPositive() == true);
+}
+
+test "big.int comptime_int to" {
+    var a = try Managed.initSet(testing.allocator, 0xefffffff00000001eeeeeeefaaaaaaab);
+    defer a.deinit();
+
+    testing.expect((try a.to(u128)) == 0xefffffff00000001eeeeeeefaaaaaaab);
+}
+
+test "big.int sub-limb to" {
+    var a = try Managed.initSet(testing.allocator, 10);
+    defer a.deinit();
+
+    testing.expect((try a.to(u8)) == 10);
+}
+
+test "big.int to target too small error" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffff);
+    defer a.deinit();
+
+    testing.expectError(error.TargetTooSmall, a.to(u8));
+}
+
+test "big.int normalize" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+    try a.ensureCapacity(8);
+
+    a.limbs[0] = 1;
+    a.limbs[1] = 2;
+    a.limbs[2] = 3;
+    a.limbs[3] = 0;
+    a.normalize(4);
+    testing.expect(a.len() == 3);
+
+    a.limbs[0] = 1;
+    a.limbs[1] = 2;
+    a.limbs[2] = 3;
+    a.normalize(3);
+    testing.expect(a.len() == 3);
+
+    a.limbs[0] = 0;
+    a.limbs[1] = 0;
+    a.normalize(2);
+    testing.expect(a.len() == 1);
+
+    a.limbs[0] = 0;
+    a.normalize(1);
+    testing.expect(a.len() == 1);
+}
+
+test "big.int normalize multi" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+    try a.ensureCapacity(8);
+
+    a.limbs[0] = 1;
+    a.limbs[1] = 2;
+    a.limbs[2] = 0;
+    a.limbs[3] = 0;
+    a.normalize(4);
+    testing.expect(a.len() == 2);
+
+    a.limbs[0] = 1;
+    a.limbs[1] = 2;
+    a.limbs[2] = 3;
+    a.normalize(3);
+    testing.expect(a.len() == 3);
+
+    a.limbs[0] = 0;
+    a.limbs[1] = 0;
+    a.limbs[2] = 0;
+    a.limbs[3] = 0;
+    a.normalize(4);
+    testing.expect(a.len() == 1);
+
+    a.limbs[0] = 0;
+    a.normalize(1);
+    testing.expect(a.len() == 1);
+}
+
+test "big.int parity" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.set(0);
+    testing.expect(a.isEven());
+    testing.expect(!a.isOdd());
+
+    try a.set(7);
+    testing.expect(!a.isEven());
+    testing.expect(a.isOdd());
+}
+
+test "big.int bitcount + sizeInBaseUpperBound" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.set(0b100);
+    testing.expect(a.bitCountAbs() == 3);
+    testing.expect(a.sizeInBaseUpperBound(2) >= 3);
+    testing.expect(a.sizeInBaseUpperBound(10) >= 1);
+
+    a.negate();
+    testing.expect(a.bitCountAbs() == 3);
+    testing.expect(a.sizeInBaseUpperBound(2) >= 4);
+    testing.expect(a.sizeInBaseUpperBound(10) >= 2);
+
+    try a.set(0xffffffff);
+    testing.expect(a.bitCountAbs() == 32);
+    testing.expect(a.sizeInBaseUpperBound(2) >= 32);
+    testing.expect(a.sizeInBaseUpperBound(10) >= 10);
+
+    try a.shiftLeft(a, 5000);
+    testing.expect(a.bitCountAbs() == 5032);
+    testing.expect(a.sizeInBaseUpperBound(2) >= 5032);
+    a.setSign(false);
+
+    testing.expect(a.bitCountAbs() == 5032);
+    testing.expect(a.sizeInBaseUpperBound(2) >= 5033);
+}
+
+test "big.int bitcount/to" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.set(0);
+    testing.expect(a.bitCountTwosComp() == 0);
+
+    testing.expect((try a.to(u0)) == 0);
+    testing.expect((try a.to(i0)) == 0);
+
+    try a.set(-1);
+    testing.expect(a.bitCountTwosComp() == 1);
+    testing.expect((try a.to(i1)) == -1);
+
+    try a.set(-8);
+    testing.expect(a.bitCountTwosComp() == 4);
+    testing.expect((try a.to(i4)) == -8);
+
+    try a.set(127);
+    testing.expect(a.bitCountTwosComp() == 7);
+    testing.expect((try a.to(u7)) == 127);
+
+    try a.set(-128);
+    testing.expect(a.bitCountTwosComp() == 8);
+    testing.expect((try a.to(i8)) == -128);
+
+    try a.set(-129);
+    testing.expect(a.bitCountTwosComp() == 9);
+    testing.expect((try a.to(i9)) == -129);
+}
+
+test "big.int fits" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.set(0);
+    testing.expect(a.fits(u0));
+    testing.expect(a.fits(i0));
+
+    try a.set(255);
+    testing.expect(!a.fits(u0));
+    testing.expect(!a.fits(u1));
+    testing.expect(!a.fits(i8));
+    testing.expect(a.fits(u8));
+    testing.expect(a.fits(u9));
+    testing.expect(a.fits(i9));
+
+    try a.set(-128);
+    testing.expect(!a.fits(i7));
+    testing.expect(a.fits(i8));
+    testing.expect(a.fits(i9));
+    testing.expect(!a.fits(u9));
+
+    try a.set(0x1ffffffffeeeeeeee);
+    testing.expect(!a.fits(u32));
+    testing.expect(!a.fits(u64));
+    testing.expect(a.fits(u65));
+}
+
+test "big.int string set" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.setString(10, "120317241209124781241290847124");
+    testing.expect((try a.to(u128)) == 120317241209124781241290847124);
+}
+
+test "big.int string negative" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.setString(10, "-1023");
+    testing.expect((try a.to(i32)) == -1023);
+}
+
+test "big.int string set number with underscores" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.setString(10, "__1_2_0_3_1_7_2_4_1_2_0_____9_1__2__4_7_8_1_2_4_1_2_9_0_8_4_7_1_2_4___");
+    testing.expect((try a.to(u128)) == 120317241209124781241290847124);
+}
+
+test "big.int string set case insensitive number" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    try a.setString(16, "aB_cD_eF");
+    testing.expect((try a.to(u32)) == 0xabcdef);
+}
+
+test "big.int string set bad char error" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+    testing.expectError(error.InvalidCharacter, a.setString(10, "x"));
+}
+
+test "big.int string set bad base error" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+    testing.expectError(error.InvalidBase, a.setString(45, "10"));
+}
+
+test "big.int string to" {
+    var a = try Managed.initSet(testing.allocator, 120317241209124781241290847124);
+    defer a.deinit();
+
+    const as = try a.toString(testing.allocator, 10, false);
+    defer testing.allocator.free(as);
+    const es = "120317241209124781241290847124";
+
+    testing.expect(mem.eql(u8, as, es));
+}
+
+test "big.int string to base base error" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffff);
+    defer a.deinit();
+
+    testing.expectError(error.InvalidBase, a.toString(testing.allocator, 45, false));
+}
+
+test "big.int string to base 2" {
+    var a = try Managed.initSet(testing.allocator, -0b1011);
+    defer a.deinit();
+
+    const as = try a.toString(testing.allocator, 2, false);
+    defer testing.allocator.free(as);
+    const es = "-1011";
+
+    testing.expect(mem.eql(u8, as, es));
+}
+
+test "big.int string to base 16" {
+    var a = try Managed.initSet(testing.allocator, 0xefffffff00000001eeeeeeefaaaaaaab);
+    defer a.deinit();
+
+    const as = try a.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(as);
+    const es = "efffffff00000001eeeeeeefaaaaaaab";
+
+    testing.expect(mem.eql(u8, as, es));
+}
+
+test "big.int neg string to" {
+    var a = try Managed.initSet(testing.allocator, -123907434);
+    defer a.deinit();
+
+    const as = try a.toString(testing.allocator, 10, false);
+    defer testing.allocator.free(as);
+    const es = "-123907434";
+
+    testing.expect(mem.eql(u8, as, es));
+}
+
+test "big.int zero string to" {
+    var a = try Managed.initSet(testing.allocator, 0);
+    defer a.deinit();
+
+    const as = try a.toString(testing.allocator, 10, false);
+    defer testing.allocator.free(as);
+    const es = "0";
+
+    testing.expect(mem.eql(u8, as, es));
+}
+
+test "big.int clone" {
+    var a = try Managed.initSet(testing.allocator, 1234);
+    defer a.deinit();
+    var b = try a.clone();
+    defer b.deinit();
+
+    testing.expect((try a.to(u32)) == 1234);
+    testing.expect((try b.to(u32)) == 1234);
+
+    try a.set(77);
+    testing.expect((try a.to(u32)) == 77);
+    testing.expect((try b.to(u32)) == 1234);
+}
+
+test "big.int swap" {
+    var a = try Managed.initSet(testing.allocator, 1234);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 5678);
+    defer b.deinit();
+
+    testing.expect((try a.to(u32)) == 1234);
+    testing.expect((try b.to(u32)) == 5678);
+
+    a.swap(&b);
+
+    testing.expect((try a.to(u32)) == 5678);
+    testing.expect((try b.to(u32)) == 1234);
+}
+
+test "big.int to negative" {
+    var a = try Managed.initSet(testing.allocator, -10);
+    defer a.deinit();
+
+    testing.expect((try a.to(i32)) == -10);
+}
+
+test "big.int compare" {
+    var a = try Managed.initSet(testing.allocator, -11);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 10);
+    defer b.deinit();
+
+    testing.expect(a.orderAbs(b) == .gt);
+    testing.expect(a.order(b) == .lt);
+}
+
+test "big.int compare similar" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffffeeeeeeeeffffffffeeeeeeee);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0xffffffffeeeeeeeeffffffffeeeeeeef);
+    defer b.deinit();
+
+    testing.expect(a.orderAbs(b) == .lt);
+    testing.expect(b.orderAbs(a) == .gt);
+}
+
+test "big.int compare different limb size" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 1);
+    defer b.deinit();
+
+    testing.expect(a.orderAbs(b) == .gt);
+    testing.expect(b.orderAbs(a) == .lt);
+}
+
+test "big.int compare multi-limb" {
+    var a = try Managed.initSet(testing.allocator, -0x7777777799999999ffffeeeeffffeeeeffffeeeef);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x7777777799999999ffffeeeeffffeeeeffffeeeee);
+    defer b.deinit();
+
+    testing.expect(a.orderAbs(b) == .gt);
+    testing.expect(a.order(b) == .lt);
+}
+
+test "big.int equality" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffff1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, -0xffffffff1);
+    defer b.deinit();
+
+    testing.expect(a.eqAbs(b));
+    testing.expect(!a.eq(b));
+}
+
+test "big.int abs" {
+    var a = try Managed.initSet(testing.allocator, -5);
+    defer a.deinit();
+
+    a.abs();
+    testing.expect((try a.to(u32)) == 5);
+
+    a.abs();
+    testing.expect((try a.to(u32)) == 5);
+}
+
+test "big.int negate" {
+    var a = try Managed.initSet(testing.allocator, 5);
+    defer a.deinit();
+
+    a.negate();
+    testing.expect((try a.to(i32)) == -5);
+
+    a.negate();
+    testing.expect((try a.to(i32)) == 5);
+}
+
+test "big.int add single-single" {
+    var a = try Managed.initSet(testing.allocator, 50);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 5);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.add(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u32)) == 55);
+}
+
+test "big.int add multi-single" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 1);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+
+    try c.add(a.toConst(), b.toConst());
+    testing.expect((try c.to(DoubleLimb)) == maxInt(Limb) + 2);
+
+    try c.add(b.toConst(), a.toConst());
+    testing.expect((try c.to(DoubleLimb)) == maxInt(Limb) + 2);
+}
+
+test "big.int add multi-multi" {
+    const op1 = 0xefefefef7f7f7f7f;
+    const op2 = 0xfefefefe9f9f9f9f;
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, op2);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.add(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u128)) == op1 + op2);
+}
+
+test "big.int add zero-zero" {
+    var a = try Managed.initSet(testing.allocator, 0);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.add(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u32)) == 0);
+}
+
+test "big.int add alias multi-limb nonzero-zero" {
+    const op1 = 0xffffffff777777771;
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0);
+    defer b.deinit();
+
+    try a.add(a.toConst(), b.toConst());
+
+    testing.expect((try a.to(u128)) == op1);
+}
+
+test "big.int add sign" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    var one = try Managed.initSet(testing.allocator, 1);
+    defer one.deinit();
+    var two = try Managed.initSet(testing.allocator, 2);
+    defer two.deinit();
+    var neg_one = try Managed.initSet(testing.allocator, -1);
+    defer neg_one.deinit();
+    var neg_two = try Managed.initSet(testing.allocator, -2);
+    defer neg_two.deinit();
+
+    try a.add(one.toConst(), two.toConst());
+    testing.expect((try a.to(i32)) == 3);
+
+    try a.add(neg_one.toConst(), two.toConst());
+    testing.expect((try a.to(i32)) == 1);
+
+    try a.add(one.toConst(), neg_two.toConst());
+    testing.expect((try a.to(i32)) == -1);
+
+    try a.add(neg_one.toConst(), neg_two.toConst());
+    testing.expect((try a.to(i32)) == -3);
+}
+
+test "big.int sub single-single" {
+    var a = try Managed.initSet(testing.allocator, 50);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 5);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.sub(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u32)) == 45);
+}
+
+test "big.int sub multi-single" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 1);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.sub(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(Limb)) == maxInt(Limb));
+}
+
+test "big.int sub multi-multi" {
+    const op1 = 0xefefefefefefefefefefefef;
+    const op2 = 0xabababababababababababab;
+
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, op2);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.sub(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u128)) == op1 - op2);
+}
+
+test "big.int sub equal" {
+    var a = try Managed.initSet(testing.allocator, 0x11efefefefefefefefefefefef);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x11efefefefefefefefefefefef);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.sub(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u32)) == 0);
+}
+
+test "big.int sub sign" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    var one = try Managed.initSet(testing.allocator, 1);
+    defer one.deinit();
+    var two = try Managed.initSet(testing.allocator, 2);
+    defer two.deinit();
+    var neg_one = try Managed.initSet(testing.allocator, -1);
+    defer neg_one.deinit();
+    var neg_two = try Managed.initSet(testing.allocator, -2);
+    defer neg_two.deinit();
+
+    try a.sub(one.toConst(), two.toConst());
+    testing.expect((try a.to(i32)) == -1);
+
+    try a.sub(neg_one.toConst(), two.toConst());
+    testing.expect((try a.to(i32)) == -3);
+
+    try a.sub(one.toConst(), neg_two.toConst());
+    testing.expect((try a.to(i32)) == 3);
+
+    try a.sub(neg_one.toConst(), neg_two.toConst());
+    testing.expect((try a.to(i32)) == 1);
+
+    try a.sub(neg_two.toConst(), neg_one.toConst());
+    testing.expect((try a.to(i32)) == -1);
+}
+
+test "big.int mul single-single" {
+    var a = try Managed.initSet(testing.allocator, 50);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 5);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.mul(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u64)) == 250);
+}
+
+test "big.int mul multi-single" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb));
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 2);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.mul(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(DoubleLimb)) == 2 * maxInt(Limb));
+}
+
+test "big.int mul multi-multi" {
+    const op1 = 0x998888efefefefefefefef;
+    const op2 = 0x333000abababababababab;
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, op2);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.mul(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u256)) == op1 * op2);
+}
+
+test "big.int mul alias r with a" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb));
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 2);
+    defer b.deinit();
+
+    try a.mul(a.toConst(), b.toConst());
+
+    testing.expect((try a.to(DoubleLimb)) == 2 * maxInt(Limb));
+}
+
+test "big.int mul alias r with b" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb));
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 2);
+    defer b.deinit();
+
+    try a.mul(b.toConst(), a.toConst());
+
+    testing.expect((try a.to(DoubleLimb)) == 2 * maxInt(Limb));
+}
+
+test "big.int mul alias r with a and b" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb));
+    defer a.deinit();
+
+    try a.mul(a.toConst(), a.toConst());
+
+    testing.expect((try a.to(DoubleLimb)) == maxInt(Limb) * maxInt(Limb));
+}
+
+test "big.int mul a*0" {
+    var a = try Managed.initSet(testing.allocator, 0xefefefefefefefef);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.mul(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u32)) == 0);
+}
+
+test "big.int mul 0*0" {
+    var a = try Managed.initSet(testing.allocator, 0);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0);
+    defer b.deinit();
+
+    var c = try Managed.init(testing.allocator);
+    defer c.deinit();
+    try c.mul(a.toConst(), b.toConst());
+
+    testing.expect((try c.to(u32)) == 0);
+}
+
+test "big.int div single-single no rem" {
+    var a = try Managed.initSet(testing.allocator, 50);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 5);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u32)) == 10);
+    testing.expect((try r.to(u32)) == 0);
+}
+
+test "big.int div single-single with rem" {
+    var a = try Managed.initSet(testing.allocator, 49);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 5);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u32)) == 9);
+    testing.expect((try r.to(u32)) == 4);
+}
+
+test "big.int div multi-single no rem" {
+    const op1 = 0xffffeeeeddddcccc;
+    const op2 = 34;
+
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, op2);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u64)) == op1 / op2);
+    testing.expect((try r.to(u64)) == 0);
+}
+
+test "big.int div multi-single with rem" {
+    const op1 = 0xffffeeeeddddcccf;
+    const op2 = 34;
+
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, op2);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u64)) == op1 / op2);
+    testing.expect((try r.to(u64)) == 3);
+}
+
+test "big.int div multi>2-single" {
+    const op1 = 0xfefefefefefefefefefefefefefefefe;
+    const op2 = 0xefab8;
+
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, op2);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == op1 / op2);
+    testing.expect((try r.to(u32)) == 0x3e4e);
+}
+
+test "big.int div single-single q < r" {
+    var a = try Managed.initSet(testing.allocator, 0x0078f432);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x01000000);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u64)) == 0);
+    testing.expect((try r.to(u64)) == 0x0078f432);
+}
+
+test "big.int div single-single q == r" {
+    var a = try Managed.initSet(testing.allocator, 10);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 10);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u64)) == 1);
+    testing.expect((try r.to(u64)) == 0);
+}
+
+test "big.int div q=0 alias" {
+    var a = try Managed.initSet(testing.allocator, 3);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 10);
+    defer b.deinit();
+
+    try Managed.divTrunc(&a, &b, a.toConst(), b.toConst());
+
+    testing.expect((try a.to(u64)) == 0);
+    testing.expect((try b.to(u64)) == 3);
+}
+
+test "big.int div multi-multi q < r" {
+    const op1 = 0x1ffffffff0078f432;
+    const op2 = 0x1ffffffff01000000;
+    var a = try Managed.initSet(testing.allocator, op1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, op2);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == 0);
+    testing.expect((try r.to(u128)) == op1);
+}
+
+test "big.int div trunc single-single +/+" {
+    const u: i32 = 5;
+    const v: i32 = 3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    // n = q * d + r
+    // 5 = 1 * 3 + 2
+    const eq = @divTrunc(u, v);
+    const er = @mod(u, v);
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div trunc single-single -/+" {
+    const u: i32 = -5;
+    const v: i32 = 3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    //  n = q *  d + r
+    // -5 = 1 * -3 - 2
+    const eq = -1;
+    const er = -2;
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div trunc single-single +/-" {
+    const u: i32 = 5;
+    const v: i32 = -3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    // n =  q *  d + r
+    // 5 = -1 * -3 + 2
+    const eq = -1;
+    const er = 2;
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div trunc single-single -/-" {
+    const u: i32 = -5;
+    const v: i32 = -3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    //  n = q *  d + r
+    // -5 = 1 * -3 - 2
+    const eq = 1;
+    const er = -2;
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div floor single-single +/+" {
+    const u: i32 = 5;
+    const v: i32 = 3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divFloor(&q, &r, a.toConst(), b.toConst());
+
+    //  n =  q *  d + r
+    //  5 =  1 *  3 + 2
+    const eq = 1;
+    const er = 2;
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div floor single-single -/+" {
+    const u: i32 = -5;
+    const v: i32 = 3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divFloor(&q, &r, a.toConst(), b.toConst());
+
+    //  n =  q *  d + r
+    // -5 = -2 *  3 + 1
+    const eq = -2;
+    const er = 1;
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div floor single-single +/-" {
+    const u: i32 = 5;
+    const v: i32 = -3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divFloor(&q, &r, a.toConst(), b.toConst());
+
+    //  n =  q *  d + r
+    //  5 = -2 * -3 - 1
+    const eq = -2;
+    const er = -1;
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div floor single-single -/-" {
+    const u: i32 = -5;
+    const v: i32 = -3;
+
+    var a = try Managed.initSet(testing.allocator, u);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, v);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divFloor(&q, &r, a.toConst(), b.toConst());
+
+    //  n =  q *  d + r
+    // -5 =  2 * -3 + 1
+    const eq = 1;
+    const er = -2;
+
+    testing.expect((try q.to(i32)) == eq);
+    testing.expect((try r.to(i32)) == er);
+}
+
+test "big.int div multi-multi with rem" {
+    var a = try Managed.initSet(testing.allocator, 0x8888999911110000ffffeeeeddddccccbbbbaaaa9999);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x99990000111122223333);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == 0xe38f38e39161aaabd03f0f1b);
+    testing.expect((try r.to(u128)) == 0x28de0acacd806823638);
+}
+
+test "big.int div multi-multi no rem" {
+    var a = try Managed.initSet(testing.allocator, 0x8888999911110000ffffeeeedb4fec200ee3a4286361);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x99990000111122223333);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == 0xe38f38e39161aaabd03f0f1b);
+    testing.expect((try r.to(u128)) == 0);
+}
+
+test "big.int div multi-multi (2 branch)" {
+    var a = try Managed.initSet(testing.allocator, 0x866666665555555588888887777777761111111111111111);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x86666666555555554444444433333333);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == 0x10000000000000000);
+    testing.expect((try r.to(u128)) == 0x44444443444444431111111111111111);
+}
+
+test "big.int div multi-multi (3.1/3.3 branch)" {
+    var a = try Managed.initSet(testing.allocator, 0x11111111111111111111111111111111111111111111111111111111111111);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x1111111111111111111111111111111111111111171);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == 0xfffffffffffffffffff);
+    testing.expect((try r.to(u256)) == 0x1111111111111111111110b12222222222222222282);
+}
+
+test "big.int div multi-single zero-limb trailing" {
+    var a = try Managed.initSet(testing.allocator, 0x60000000000000000000000000000000000000000000000000000000000000000);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x10000000000000000);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    var expected = try Managed.initSet(testing.allocator, 0x6000000000000000000000000000000000000000000000000);
+    defer expected.deinit();
+    testing.expect(q.eq(expected));
+    testing.expect(r.eqZero());
+}
+
+test "big.int div multi-multi zero-limb trailing (with rem)" {
+    var a = try Managed.initSet(testing.allocator, 0x86666666555555558888888777777776111111111111111100000000000000000000000000000000);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x8666666655555555444444443333333300000000000000000000000000000000);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == 0x10000000000000000);
+
+    const rs = try r.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(rs);
+    testing.expect(std.mem.eql(u8, rs, "4444444344444443111111111111111100000000000000000000000000000000"));
+}
+
+test "big.int div multi-multi zero-limb trailing (with rem) and dividend zero-limb count > divisor zero-limb count" {
+    var a = try Managed.initSet(testing.allocator, 0x8666666655555555888888877777777611111111111111110000000000000000);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x8666666655555555444444443333333300000000000000000000000000000000);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    testing.expect((try q.to(u128)) == 0x1);
+
+    const rs = try r.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(rs);
+    testing.expect(std.mem.eql(u8, rs, "444444434444444311111111111111110000000000000000"));
+}
+
+test "big.int div multi-multi zero-limb trailing (with rem) and dividend zero-limb count < divisor zero-limb count" {
+    var a = try Managed.initSet(testing.allocator, 0x86666666555555558888888777777776111111111111111100000000000000000000000000000000);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x866666665555555544444444333333330000000000000000);
+    defer b.deinit();
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    const qs = try q.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(qs);
+    testing.expect(std.mem.eql(u8, qs, "10000000000000000820820803105186f"));
+
+    const rs = try r.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(rs);
+    testing.expect(std.mem.eql(u8, rs, "4e11f2baa5896a321d463b543d0104e30000000000000000"));
+}
+
+test "big.int div multi-multi fuzz case #1" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+    var b = try Managed.init(testing.allocator);
+    defer b.deinit();
+
+    try a.setString(16, "ffffffffffffffffffffffffffffc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
+    try b.setString(16, "3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000000000000000000000000000000001ffffffffffffffffffffffffffffffffffffffffffffffffffc000000000000000000000000000000007fffffffffff");
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    const qs = try q.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(qs);
+    testing.expect(std.mem.eql(u8, qs, "3ffffffffffffffffffffffffffff0000000000000000000000000000000000001ffffffffffffffffffffffffffff7fffffffe000000000000000000000000000180000000000000000000003fffffbfffffffdfffffffffffffeffff800000100101000000100000000020003fffffdfbfffffe3ffffffffffffeffff7fffc00800a100000017ffe000002000400007efbfff7fe9f00000037ffff3fff7fffa004006100000009ffe00000190038200bf7d2ff7fefe80400060000f7d7f8fbf9401fe38e0403ffc0bdffffa51102c300d7be5ef9df4e5060007b0127ad3fa69f97d0f820b6605ff617ddf7f32ad7a05c0d03f2e7bc78a6000e087a8bbcdc59e07a5a079128a7861f553ddebed7e8e56701756f9ead39b48cd1b0831889ea6ec1fddf643d0565b075ff07e6caea4e2854ec9227fd635ed60a2f5eef2893052ffd54718fa08604acbf6a15e78a467c4a3c53c0278af06c4416573f925491b195e8fd79302cb1aaf7caf4ecfc9aec1254cc969786363ac729f914c6ddcc26738d6b0facd54eba026580aba2eb6482a088b0d224a8852420b91ec1"));
+
+    const rs = try r.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(rs);
+    testing.expect(std.mem.eql(u8, rs, "310d1d4c414426b4836c2635bad1df3a424e50cbdd167ffccb4dfff57d36b4aae0d6ca0910698220171a0f3373c1060a046c2812f0027e321f72979daa5e7973214170d49e885de0c0ecc167837d44502430674a82522e5df6a0759548052420b91ec1"));
+}
+
+test "big.int div multi-multi fuzz case #2" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+    var b = try Managed.init(testing.allocator);
+    defer b.deinit();
+
+    try a.setString(16, "3ffffffffe00000000000000000000000000fffffffffffffffffffffffffffffffffffffffffffffffffffffffffe000000000000000000000000000000000000000000000000000000000000001fffffffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffc000000000000000000000000000000000000000000000000000000000000000");
+    try b.setString(16, "ffc0000000000000000000000000000000000000000000000000");
+
+    var q = try Managed.init(testing.allocator);
+    defer q.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+    try Managed.divTrunc(&q, &r, a.toConst(), b.toConst());
+
+    const qs = try q.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(qs);
+    testing.expect(std.mem.eql(u8, qs, "40100400fe3f8fe3f8fe3f8fe3f8fe3f8fe4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f93e4f91e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4992649926499264991e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4791e4792e4b92e4b92e4b92e4b92a4a92a4a92a4"));
+
+    const rs = try r.toString(testing.allocator, 16, false);
+    defer testing.allocator.free(rs);
+    testing.expect(std.mem.eql(u8, rs, "a900000000000000000000000000000000000000000000000000"));
+}
+
+test "big.int shift-right single" {
+    var a = try Managed.initSet(testing.allocator, 0xffff0000);
+    defer a.deinit();
+    try a.shiftRight(a, 16);
+
+    testing.expect((try a.to(u32)) == 0xffff);
+}
+
+test "big.int shift-right multi" {
+    var a = try Managed.initSet(testing.allocator, 0xffff0000eeee1111dddd2222cccc3333);
+    defer a.deinit();
+    try a.shiftRight(a, 67);
+
+    testing.expect((try a.to(u64)) == 0x1fffe0001dddc222);
+}
+
+test "big.int shift-left single" {
+    var a = try Managed.initSet(testing.allocator, 0xffff);
+    defer a.deinit();
+    try a.shiftLeft(a, 16);
+
+    testing.expect((try a.to(u64)) == 0xffff0000);
+}
+
+test "big.int shift-left multi" {
+    var a = try Managed.initSet(testing.allocator, 0x1fffe0001dddc222);
+    defer a.deinit();
+    try a.shiftLeft(a, 67);
+
+    testing.expect((try a.to(u128)) == 0xffff0000eeee11100000000000000000);
+}
+
+test "big.int shift-right negative" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    var arg = try Managed.initSet(testing.allocator, -20);
+    defer arg.deinit();
+    try a.shiftRight(arg, 2);
+    testing.expect((try a.to(i32)) == -20 >> 2);
+
+    var arg2 = try Managed.initSet(testing.allocator, -5);
+    defer arg2.deinit();
+    try a.shiftRight(arg2, 10);
+    testing.expect((try a.to(i32)) == -5 >> 10);
+}
+
+test "big.int shift-left negative" {
+    var a = try Managed.init(testing.allocator);
+    defer a.deinit();
+
+    var arg = try Managed.initSet(testing.allocator, -10);
+    defer arg.deinit();
+    try a.shiftRight(arg, 1232);
+    testing.expect((try a.to(i32)) == -10 >> 1232);
+}
+
+test "big.int bitwise and simple" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffff11111111);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222);
+    defer b.deinit();
+
+    try a.bitAnd(a, b);
+
+    testing.expect((try a.to(u64)) == 0xeeeeeeee00000000);
+}
+
+test "big.int bitwise and multi-limb" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, maxInt(Limb));
+    defer b.deinit();
+
+    try a.bitAnd(a, b);
+
+    testing.expect((try a.to(u128)) == 0);
+}
+
+test "big.int bitwise xor simple" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffff11111111);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222);
+    defer b.deinit();
+
+    try a.bitXor(a, b);
+
+    testing.expect((try a.to(u64)) == 0x1111111133333333);
+}
+
+test "big.int bitwise xor multi-limb" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, maxInt(Limb));
+    defer b.deinit();
+
+    try a.bitXor(a, b);
+
+    testing.expect((try a.to(DoubleLimb)) == (maxInt(Limb) + 1) ^ maxInt(Limb));
+}
+
+test "big.int bitwise or simple" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffff11111111);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222);
+    defer b.deinit();
+
+    try a.bitOr(a, b);
+
+    testing.expect((try a.to(u64)) == 0xffffffff33333333);
+}
+
+test "big.int bitwise or multi-limb" {
+    var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, maxInt(Limb));
+    defer b.deinit();
+
+    try a.bitOr(a, b);
+
+    // TODO: big.int.cpp or is wrong on multi-limb.
+    testing.expect((try a.to(DoubleLimb)) == (maxInt(Limb) + 1) + maxInt(Limb));
+}
+
+test "big.int var args" {
+    var a = try Managed.initSet(testing.allocator, 5);
+    defer a.deinit();
+
+    var b = try Managed.initSet(testing.allocator, 6);
+    defer b.deinit();
+    try a.add(a.toConst(), b.toConst());
+    testing.expect((try a.to(u64)) == 11);
+
+    var c = try Managed.initSet(testing.allocator, 11);
+    defer c.deinit();
+    testing.expect(a.order(c) == .eq);
+
+    var d = try Managed.initSet(testing.allocator, 14);
+    defer d.deinit();
+    testing.expect(a.order(d) != .gt);
+}
+
+test "big.int gcd non-one small" {
+    var a = try Managed.initSet(testing.allocator, 17);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 97);
+    defer b.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+
+    try r.gcd(a, b);
+
+    testing.expect((try r.to(u32)) == 1);
+}
+
+test "big.int gcd non-one small" {
+    var a = try Managed.initSet(testing.allocator, 4864);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 3458);
+    defer b.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+
+    try r.gcd(a, b);
+
+    testing.expect((try r.to(u32)) == 38);
+}
+
+test "big.int gcd non-one large" {
+    var a = try Managed.initSet(testing.allocator, 0xffffffffffffffff);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0xffffffffffffffff7777);
+    defer b.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+
+    try r.gcd(a, b);
+
+    testing.expect((try r.to(u32)) == 4369);
+}
+
+test "big.int gcd large multi-limb result" {
+    var a = try Managed.initSet(testing.allocator, 0x12345678123456781234567812345678123456781234567812345678);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 0x12345671234567123456712345671234567123456712345671234567);
+    defer b.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+
+    try r.gcd(a, b);
+
+    const answer = (try r.to(u256));
+    testing.expect(answer == 0xf000000ff00000fff0000ffff000fffff00ffffff1);
+}
+
+test "big.int gcd one large" {
+    var a = try Managed.initSet(testing.allocator, 1897056385327307);
+    defer a.deinit();
+    var b = try Managed.initSet(testing.allocator, 2251799813685248);
+    defer b.deinit();
+    var r = try Managed.init(testing.allocator);
+    defer r.deinit();
+
+    try r.gcd(a, b);
+
+    testing.expect((try r.to(u64)) == 1);
+}
diff --git a/lib/std/math/big/rational.zig b/lib/std/math/big/rational.zig
index f5f2f53113..3624a16139 100644
--- a/lib/std/math/big/rational.zig
+++ b/lib/std/math/big/rational.zig
@@ -5,10 +5,10 @@ const mem = std.mem;
 const testing = std.testing;
 const Allocator = mem.Allocator;
 
-const bn = @import("int.zig");
-const Limb = bn.Limb;
-const DoubleLimb = bn.DoubleLimb;
-const Int = bn.Int;
+const Limb = std.math.big.Limb;
+const DoubleLimb = std.math.big.DoubleLimb;
+const Int = std.math.big.int.Managed;
+const IntConst = std.math.big.int.Const;
 
 /// An arbitrary-precision rational number.
 ///
@@ -17,6 +17,9 @@ const Int = bn.Int;
 ///
 /// Rational's are always normalized. That is, for a Rational r = p/q where p and q are integers,
 /// gcd(p, q) = 1 always.
+///
+/// TODO rework this to store its own allocator and use a non-managed big int, to avoid double
+/// allocator storage.
 pub const Rational = struct {
     /// Numerator. Determines the sign of the Rational.
     p: Int,
@@ -98,20 +101,20 @@ pub const Rational = struct {
         if (point) |i| {
             try self.p.setString(10, str[0..i]);
 
-            const base = Int.initFixed(([_]Limb{10})[0..]);
+            const base = IntConst{ .limbs = &[_]Limb{10}, .positive = true };
 
             var j: usize = start;
             while (j < str.len - i - 1) : (j += 1) {
-                try self.p.mul(self.p, base);
+                try self.p.mul(self.p.toConst(), base);
             }
 
             try self.q.setString(10, str[i + 1 ..]);
-            try self.p.add(self.p, self.q);
+            try self.p.add(self.p.toConst(), self.q.toConst());
 
             try self.q.set(1);
             var k: usize = i + 1;
             while (k < str.len) : (k += 1) {
-                try self.q.mul(self.q, base);
+                try self.q.mul(self.q.toConst(), base);
             }
 
             try self.reduce();
@@ -218,14 +221,14 @@ pub const Rational = struct {
         }
 
         // 2. compute quotient and remainder
-        var q = try Int.init(self.p.allocator.?);
+        var q = try Int.init(self.p.allocator);
         defer q.deinit();
 
         // unused
-        var r = try Int.init(self.p.allocator.?);
+        var r = try Int.init(self.p.allocator);
         defer r.deinit();
 
-        try Int.divTrunc(&q, &r, a2, b2);
+        try Int.divTrunc(&q, &r, a2.toConst(), b2.toConst());
 
         var mantissa = extractLowBits(q, BitReprType);
         var have_rem = r.len() > 0;
@@ -293,14 +296,14 @@ pub const Rational = struct {
 
     /// Set a Rational directly from an Int.
     pub fn copyInt(self: *Rational, a: Int) !void {
-        try self.p.copy(a);
+        try self.p.copy(a.toConst());
         try self.q.set(1);
     }
 
     /// Set a Rational directly from a ratio of two Int's.
     pub fn copyRatio(self: *Rational, a: Int, b: Int) !void {
-        try self.p.copy(a);
-        try self.q.copy(b);
+        try self.p.copy(a.toConst());
+        try self.q.copy(b.toConst());
 
         self.p.setSign(@boolToInt(self.p.isPositive()) ^ @boolToInt(self.q.isPositive()) == 0);
         self.q.setSign(true);
@@ -327,13 +330,13 @@ pub const Rational = struct {
 
     /// Returns math.Order.lt, math.Order.eq, math.Order.gt if a < b, a == b or a
     /// > b respectively.
-    pub fn cmp(a: Rational, b: Rational) !math.Order {
+    pub fn order(a: Rational, b: Rational) !math.Order {
         return cmpInternal(a, b, true);
     }
 
     /// Returns math.Order.lt, math.Order.eq, math.Order.gt if |a| < |b|, |a| ==
     /// |b| or |a| > |b| respectively.
-    pub fn cmpAbs(a: Rational, b: Rational) !math.Order {
+    pub fn orderAbs(a: Rational, b: Rational) !math.Order {
         return cmpInternal(a, b, false);
     }
 
@@ -341,16 +344,16 @@ pub const Rational = struct {
     fn cmpInternal(a: Rational, b: Rational, is_abs: bool) !math.Order {
         // TODO: Would a div compare algorithm of sorts be viable and quicker? Can we avoid
         // the memory allocations here?
-        var q = try Int.init(a.p.allocator.?);
+        var q = try Int.init(a.p.allocator);
         defer q.deinit();
 
-        var p = try Int.init(b.p.allocator.?);
+        var p = try Int.init(b.p.allocator);
         defer p.deinit();
 
-        try q.mul(a.p, b.q);
-        try p.mul(b.p, a.q);
+        try q.mul(a.p.toConst(), b.q.toConst());
+        try p.mul(b.p.toConst(), a.q.toConst());
 
-        return if (is_abs) q.cmpAbs(p) else q.cmp(p);
+        return if (is_abs) q.orderAbs(p) else q.order(p);
     }
 
     /// rma = a + b.
@@ -364,7 +367,7 @@ pub const Rational = struct {
 
         var sr: Rational = undefined;
         if (aliased) {
-            sr = try Rational.init(rma.p.allocator.?);
+            sr = try Rational.init(rma.p.allocator);
             r = &sr;
             aliased = true;
         }
@@ -373,11 +376,11 @@ pub const Rational = struct {
             r.deinit();
         };
 
-        try r.p.mul(a.p, b.q);
-        try r.q.mul(b.p, a.q);
-        try r.p.add(r.p, r.q);
+        try r.p.mul(a.p.toConst(), b.q.toConst());
+        try r.q.mul(b.p.toConst(), a.q.toConst());
+        try r.p.add(r.p.toConst(), r.q.toConst());
 
-        try r.q.mul(a.q, b.q);
+        try r.q.mul(a.q.toConst(), b.q.toConst());
         try r.reduce();
     }
 
@@ -392,7 +395,7 @@ pub const Rational = struct {
 
         var sr: Rational = undefined;
         if (aliased) {
-            sr = try Rational.init(rma.p.allocator.?);
+            sr = try Rational.init(rma.p.allocator);
             r = &sr;
             aliased = true;
         }
@@ -401,11 +404,11 @@ pub const Rational = struct {
             r.deinit();
         };
 
-        try r.p.mul(a.p, b.q);
-        try r.q.mul(b.p, a.q);
-        try r.p.sub(r.p, r.q);
+        try r.p.mul(a.p.toConst(), b.q.toConst());
+        try r.q.mul(b.p.toConst(), a.q.toConst());
+        try r.p.sub(r.p.toConst(), r.q.toConst());
 
-        try r.q.mul(a.q, b.q);
+        try r.q.mul(a.q.toConst(), b.q.toConst());
         try r.reduce();
     }
 
@@ -415,8 +418,8 @@ pub const Rational = struct {
     ///
     /// Returns an error if memory could not be allocated.
     pub fn mul(r: *Rational, a: Rational, b: Rational) !void {
-        try r.p.mul(a.p, b.p);
-        try r.q.mul(a.q, b.q);
+        try r.p.mul(a.p.toConst(), b.p.toConst());
+        try r.q.mul(a.q.toConst(), b.q.toConst());
         try r.reduce();
     }
 
@@ -430,8 +433,8 @@ pub const Rational = struct {
             @panic("division by zero");
         }
 
-        try r.p.mul(a.p, b.q);
-        try r.q.mul(b.p, a.q);
+        try r.p.mul(a.p.toConst(), b.q.toConst());
+        try r.q.mul(b.p.toConst(), a.q.toConst());
         try r.reduce();
     }
 
@@ -442,7 +445,7 @@ pub const Rational = struct {
 
     // reduce r/q such that gcd(r, q) = 1
     fn reduce(r: *Rational) !void {
-        var a = try Int.init(r.p.allocator.?);
+        var a = try Int.init(r.p.allocator);
         defer a.deinit();
 
         const sign = r.p.isPositive();
@@ -450,15 +453,15 @@ pub const Rational = struct {
         try a.gcd(r.p, r.q);
         r.p.setSign(sign);
 
-        const one = Int.initFixed(([_]Limb{1})[0..]);
-        if (a.cmp(one) != .eq) {
-            var unused = try Int.init(r.p.allocator.?);
+        const one = IntConst{ .limbs = &[_]Limb{1}, .positive = true };
+        if (a.toConst().order(one) != .eq) {
+            var unused = try Int.init(r.p.allocator);
             defer unused.deinit();
 
             // TODO: divexact would be useful here
             // TODO: don't copy r.q for div
-            try Int.divTrunc(&r.p, &unused, r.p, a);
-            try Int.divTrunc(&r.q, &unused, r.q, a);
+            try Int.divTrunc(&r.p, &unused, r.p.toConst(), a.toConst());
+            try Int.divTrunc(&r.q, &unused, r.q.toConst(), a.toConst());
         }
     }
 };
@@ -596,25 +599,25 @@ test "big.rational copy" {
     var a = try Rational.init(testing.allocator);
     defer a.deinit();
 
-    const b = try Int.initSet(testing.allocator, 5);
+    var b = try Int.initSet(testing.allocator, 5);
     defer b.deinit();
 
     try a.copyInt(b);
     testing.expect((try a.p.to(u32)) == 5);
     testing.expect((try a.q.to(u32)) == 1);
 
-    const c = try Int.initSet(testing.allocator, 7);
+    var c = try Int.initSet(testing.allocator, 7);
     defer c.deinit();
-    const d = try Int.initSet(testing.allocator, 3);
+    var d = try Int.initSet(testing.allocator, 3);
     defer d.deinit();
 
     try a.copyRatio(c, d);
     testing.expect((try a.p.to(u32)) == 7);
     testing.expect((try a.q.to(u32)) == 3);
 
-    const e = try Int.initSet(testing.allocator, 9);
+    var e = try Int.initSet(testing.allocator, 9);
     defer e.deinit();
-    const f = try Int.initSet(testing.allocator, 3);
+    var f = try Int.initSet(testing.allocator, 3);
     defer f.deinit();
 
     try a.copyRatio(e, f);
@@ -680,7 +683,7 @@ test "big.rational swap" {
     testing.expect((try b.q.to(u32)) == 23);
 }
 
-test "big.rational cmp" {
+test "big.rational order" {
     var a = try Rational.init(testing.allocator);
     defer a.deinit();
     var b = try Rational.init(testing.allocator);
@@ -688,11 +691,11 @@ test "big.rational cmp" {
 
     try a.setRatio(500, 231);
     try b.setRatio(18903, 8584);
-    testing.expect((try a.cmp(b)) == .lt);
+    testing.expect((try a.order(b)) == .lt);
 
     try a.setRatio(890, 10);
     try b.setRatio(89, 1);
-    testing.expect((try a.cmp(b)) == .eq);
+    testing.expect((try a.order(b)) == .eq);
 }
 
 test "big.rational add single-limb" {
@@ -703,11 +706,11 @@ test "big.rational add single-limb" {
 
     try a.setRatio(500, 231);
     try b.setRatio(18903, 8584);
-    testing.expect((try a.cmp(b)) == .lt);
+    testing.expect((try a.order(b)) == .lt);
 
     try a.setRatio(890, 10);
     try b.setRatio(89, 1);
-    testing.expect((try a.cmp(b)) == .eq);
+    testing.expect((try a.order(b)) == .eq);
 }
 
 test "big.rational add" {
@@ -723,7 +726,7 @@ test "big.rational add" {
     try a.add(a, b);
 
     try r.setRatio(984786924199, 290395044174);
-    testing.expect((try a.cmp(r)) == .eq);
+    testing.expect((try a.order(r)) == .eq);
 }
 
 test "big.rational sub" {
@@ -739,7 +742,7 @@ test "big.rational sub" {
     try a.sub(a, b);
 
     try r.setRatio(979040510045, 290395044174);
-    testing.expect((try a.cmp(r)) == .eq);
+    testing.expect((try a.order(r)) == .eq);
 }
 
 test "big.rational mul" {
@@ -755,7 +758,7 @@ test "big.rational mul" {
     try a.mul(a, b);
 
     try r.setRatio(571481443, 17082061422);
-    testing.expect((try a.cmp(r)) == .eq);
+    testing.expect((try a.order(r)) == .eq);
 }
 
 test "big.rational div" {
@@ -771,7 +774,7 @@ test "big.rational div" {
     try a.div(a, b);
 
     try r.setRatio(75531824394, 221015929);
-    testing.expect((try a.cmp(r)) == .eq);
+    testing.expect((try a.order(r)) == .eq);
 }
 
 test "big.rational div" {
@@ -784,11 +787,11 @@ test "big.rational div" {
     a.invert();
 
     try r.setRatio(23341, 78923);
-    testing.expect((try a.cmp(r)) == .eq);
+    testing.expect((try a.order(r)) == .eq);
 
     try a.setRatio(-78923, 23341);
     a.invert();
 
     try r.setRatio(-23341, 78923);
-    testing.expect((try a.cmp(r)) == .eq);
+    testing.expect((try a.order(r)) == .eq);
 }