If you spot a problem with this page, click here to create a GitHub issue.

Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

mir.bignum.integer

Note The module doesn't provide full arithmetic API for now.

struct BigInt(uint size64) if (size64 && (size64 <= (ushort).max));

Stack-allocated big signed integer.

Parameters:

size64

count of 64bit words in coefficient

Examples:

Check @nogc toString impl

import mir.format;
auto str = "-34010447314490204552169750449563978034784726557588085989975288830070948234680";
auto integer = BigInt!4(str);
auto buffer = stringBuf;
buffer << integer;
assert(buffer.data == str);

Examples:

import mir.test;
import mir.bignum.fixed;
import mir.bignum.low_level_view;

{
    auto a = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7");
    auto b = UInt!128.fromHexString("f79a222050aaeaaa417fa25a2ac93291");

    // ca3d7e25aebe687b 168dcef32d0bb2f0
    auto c = BigInt!4.fromHexString("bf4c87424431d21563f23b1fc00d75ac");
    a %= b;
    a.should == c;
    a = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7");
    a /= b;
    assert(a == BigInt!4.fromHexString("ca3d7e25aebe687b7cc1b250b44690fb"));
}

{
    auto a = BigInt!4.fromHexString("7fff000080000000000000000000");
    auto b = UInt!128.fromHexString("80000000000000000001");

    auto c = BigInt!4.fromHexString("fffe0000");
    a /= b;
    a.should == c;

    a = BigInt!4.fromHexString("7fff000080000000000000000000");
    assert((a %= b) == BigInt!4.fromHexString("7fffffffffff00020000"));
}

{
    auto a = BigInt!16.fromHexString("76d053cdcc87ec8c9455c375d6a08c799fad73cf07415e70af5dfacaff4bd306647a7cceb98839cce89ae65900938821564fd2af3c9d881c172264bb17e3530ce79b938d5eb7ffec558be43ab5b684978417c5053fb8df63fc65c9efd8b2e86469c53259509eb597f81647930f24ef05a79bfecf04e5ec52414c6a3f7481d533");
    auto b = UInt!128.fromHexString("9c5c1aa6ad7ad18065a3a74598e27bee");

    assert((a /= b) == BigInt!16.fromHexString("c2871f2b07522bda1e63de12850d2208bb242c716b5739d6744ee1d9c937b8d765d3742e18785d08c2405e5c83f3c875d5726d09dfaee29e813675a4f91bfee01e8cbbbca9588325d54cf2a625faffde4d8709e0517f786f609d8ce6997e0e71d2f976ae169b0c4be7a7dba3135af96c"));
    a = BigInt!16.fromHexString("76d053cdcc87ec8c9455c375d6a08c799fad73cf07415e70af5dfacaff4bd306647a7cceb98839cce89ae65900938821564fd2af3c9d881c172264bb17e3530ce79b938d5eb7ffec558be43ab5b684978417c5053fb8df63fc65c9efd8b2e86469c53259509eb597f81647930f24ef05a79bfecf04e5ec52414c6a3f7481d533");
    assert((a %= b) == BigInt!16.fromHexString("85d81587a8b62af1874315d26ebf0ecb"));
}

{
    auto a = BigInt!4.fromHexString("DEADBEEF");
    auto b = UInt!256.fromHexString("18aeff9fa4aace484a9f8f9002cdf38fa6e53fc0f6c035051dc86931c1c08316");

    assert((a /= b) == 0);
    a = BigInt!4.fromHexString("DEADBEEF");
    assert((a %= b) == 0xDEADBEEF);
}

void test(const long av, const long bv)
{
    auto a = BigInt!4(av);
    const b = BigInt!4(bv);
    a /= b;
    assert(a == av / bv);
    a = BigInt!4(av);
    a %= b;
    assert(a == av % bv);
}

{
    auto av = 0xDEADBEEF;
    auto bv = 0xDEAD;
    test(+av, +bv);
    // test(+av, -bv);
    // test(-av, +bv);
    // test(+av, +bv);
}

Examples:

import mir.bignum.fixed;
import mir.bignum.low_level_view;

auto a = BigInt!4.fromHexString("4b313b23aa560e1b0985f89cbe6df5460860e39a64ba92b4abdd3ee77e4e05b8");
auto b = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7");
auto c = BigInt!4.fromHexString("7869dd864619cace5953a09910327b3971413e6aa5f417fa25a2ac93291b941f");
c.sign = true;
assert(a != b);
assert(a < b);
a -= b;
assert(a.sign);
assert(a == c);
a -= a;
assert(!a.sign);
assert(!a.length);

auto d = BigInt!4.fromHexString("0de1a911c6dc8f90a7169a148e65d22cf34f6a8254ae26362b064f26ac44218a");
assert((b *= 0x7869dd86) == 0x5c019770);
assert(b == d);

d = BigInt!4.fromHexString("856eeb23e68cc73f2a517448862cdc97e83f9dfa23768296724bf00fda7df32a");
auto o = b *= UInt!128.fromHexString("f79a222050aaeaaa417fa25a2ac93291");
assert(o == UInt!128.fromHexString("d6d15b99499b73e68c3331eb0f7bf16"));
assert(b == d);

d = BigInt!4.fromHexString("d"); // initial value
d.mulPow5(60);
c = BigInt!4.fromHexString("81704fcef32d3bd8117effd5c4389285b05d");
assert(d == c);

d >>= 80;
c = BigInt!4.fromHexString("81704fcef32d3bd8");
assert(d == c);

c = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7");
d = BigInt!4.fromHexString("9935cea0707f79a222050aaeaaaed17feb7aa76999d700000000000000000000");
c <<= 80;
assert(d == c);
c >>= 80;
c <<= 84;
d <<= 4;
assert(d == c);
assert(c != b);
b.sign = true;
assert(!c.copyFrom(b.coefficients, b.sign));
assert(c == b);
b >>= 18;
auto bView = cast(BigIntView!ushort)b.view;
assert(!c.copyFrom(bView.coefficients[0 .. $ - 1], bView.sign));
assert(c == b);

bool sign;

uint length;

size_t[(ulong).sizeof / size_t.sizeof * size64] data;

this(uint size)(UInt!size fixedInt);

this(uint N)(size_t[N] data) if (N <= this.data.length);

this(ulong data);

this(long data);

this(int data);

this(uint data);

pure @nogc @safe this()(scope const(char)[] str);

inout @property inout(size_t)[] coefficients()() scope return;

ref auto opAssign(ulong data) return scope;

ref auto opAssign(long data) return scope;

ref auto opAssign(uint data) return scope;

ref auto opAssign(int data) return scope;

ref auto opAssign(uint rhsSize)(UInt!rhsSize data) return scope;

Examples:

import mir.math.constant: PI;
BigInt!4 integer = "-34010447314490204552169750449563978034784726557588085989975288830070948234680"; // constructor
assert(integer.sign);
integer.sign = false;
assert(integer == BigInt!4.fromHexString("4b313b23aa560e1b0985f89cbe6df5460860e39a64ba92b4abdd3ee77e4e05b8"));

pure nothrow @nogc ref @trusted auto opAssign(uint rhsSize64)(auto ref scope const BigInt!rhsSize64 rhs) return;

pure @nogc @trusted BigInt fromBigEndian()(scope const(ubyte)[] data, bool sign = false);

pure @nogc @trusted bool copyFromBigEndian()(scope const(ubyte)[] data, bool sign = false);

pure nothrow @nogc @trusted bool fromStringImpl(C)(scope const(C)[] str) scope if (isSomeChar!C);

Returns:

false in case of overflow or incorrect string.

Precondition non-empty coefficients.

@property @trusted BigInt copy();

const pure nothrow @nogc @safe bool opEquals()(auto const ref BigInt rhs);

const pure nothrow @nogc @safe bool opEquals(ulong rhs, bool rhsSign = false);

const pure nothrow @nogc @safe bool opEquals(long rhs);

const pure nothrow @nogc @safe bool opEquals(uint rhs);

const pure nothrow @nogc @safe bool opEquals(int rhs);

const pure nothrow @nogc @safe auto opCmp()(auto const ref BigInt rhs);

@property BigIntView!size_t view()() scope return;

const @property BigIntView!(const(size_t)) view()() scope return;

void normalize()();

void putCoefficient(size_t value);

pure nothrow @nogc @safe size_t opOpAssign(string op : "*")(size_t rhs, size_t overflow = 0u);

Performs size_t overflow = (big += overflow) *= scalar operatrion.

Parameters:

size_t `rhs`	unsigned value to multiply by
size_t `overflow`	initial overflow value

Returns:

unsigned overflow value

pure nothrow @nogc @safe uint opOpAssign(string op : "/")(uint rhs, uint overflow = 0);

Performs uint remainder = (overflow$big) /= scalar operatrion, where $ denotes big-endian concatenation.

Precondition overflow < rhs

Parameters:

uint `rhs`	unsigned value to devide by
uint `overflow`	initial unsigned overflow

Returns:

unsigned remainder value (evaluated overflow)

pure nothrow @nogc @safe UInt!size opOpAssign(string op : "*", size_t size)(UInt!size rhs, UInt!size overflow = 0);

Performs size_t overflow = (big += overflow) *= fixed operatrion.

Parameters:

UInt!size `rhs`	unsigned value to multiply by
UInt!size `overflow`	initial overflow value

Returns:

unsigned overflow value

pure nothrow @nogc ref @safe auto opOpAssign(string op, size_t size)(UInt!size rhs) scope return if (op == "/" || op == "%"); pure nothrow @nogc ref @safe auto opOpAssign(string op)(ulong rhs) scope return if (op == "/" || op == "%"); pure nothrow @nogc ref @safe auto opOpAssign(string op)(long rhs) scope return if (op == "/" || op == "%");

pure nothrow @nogc ref @safe auto powMod(uint expSize)(ref scope const BigInt!expSize exponent, ref scope const BigInt modulus) return scope; pure nothrow @nogc ref @trusted auto powMod()(scope BigUIntView!(const(size_t)) exponent, ref scope const BigInt modulus) return scope;

Examples:

BigInt!3 x = 2;
BigInt!3 e = 10;
BigInt!3 m = 100;

x.powMod(e, m);
assert(x == 24);

Examples:

BigInt!3 x = 564321;
BigInt!3 e = "13763753091226345046315979581580902400000310";
BigInt!3 m = "13763753091226345046315979581580902400000311";

x.powMod(e, m);
assert(x == 1);

pure nothrow @nogc ref @safe auto multiply(uint aSize64, uint bSize64)(ref scope const BigInt!aSize64 a, ref scope const BigInt!bSize64 b) scope return if (size64 >= aSize64 + bSize64);

const pure nothrow @nogc ref @trusted auto divMod(uint divisorSize64, uint remainderSize = size64)(ref scope const BigInt!divisorSize64 divisor, ref scope BigInt!size64 quotient, ref scope BigInt!remainderSize remainder) scope return if (remainderSize >= divisorSize64);

pure nothrow @nogc ref @safe auto opOpAssign(string op, size_t rhsSize64)(ref scope const BigInt!rhsSize64 rhs) return if (op == "/" || op == "%");

Performs this %= rhs and this /= rhs operations.

Parameters:

BigInt!rhsSize64 rhs value to divide by

Returns:

remainder or quotient from the truncated division

pure nothrow @nogc ref @trusted auto opOpAssign(string op : "*", size_t rhsSize64)(ref scope const BigInt!rhsSize64 rhs) return;

Performs this %= rhs and this /= rhs operations.

Parameters:

BigInt!rhsSize64 rhs value to divide by

Returns:

remainder or quotient from the truncated division

Examples:

BigInt!32 x = "236089459999051800787306800176765276560685597708945239133346035689205694959466543423391020917332149321603397284295007899190053323478336179162578944";
BigInt!32 y = "19095614279677503764429420557677401943131308638097701560446870251856566051181587499424174939645900335127490246389509326965738171086235365599977209919032320327138167362675030414072140005376";
BigInt!32 z = "4508273263639244391466225874448166762388283627989411942887789415132291146444880491003321910228134369483394456858712486391978856464207606191606690798518090459546799016472580324664149788791167494389789813815605288815981925073283892089331019170542792502117265455020551819803771537458327634120582677504637693661973404860326560198184402944";
x *= y;
assert(x == z);

pure nothrow @nogc @safe bool opOpAssign(string op, size_t rhsSize64)(const ref BigInt!rhsSize64 rhs) if (op == "+" || op == "-"); pure nothrow @nogc @safe bool opOpAssign(string op)(BigIntView!(const(size_t)) rhs) if (op == "+" || op == "-"); pure nothrow @nogc @safe bool opOpAssign(string op)(ulong rhs) if (op == "+" || op == "-"); pure nothrow @nogc @safe bool opOpAssign(string op)(uint rhs) if (op == "+" || op == "-"); pure nothrow @nogc @safe bool opOpAssign(string op)(long rhs) if (op == "+" || op == "-"); pure nothrow @nogc @safe bool opOpAssign(string op)(int rhs) if (op == "+" || op == "-");

Performs size_t overflow = big *= fixed operatrion.

Parameters:

BigInt!rhsSize64 rhs unsigned value to multiply by

Returns:

overflow

pure @trusted BigInt fromHexString(bool allowUnderscores = false)(scope const(char)[] str);

pure nothrow @nogc @safe bool fromHexStringImpl(C, bool allowUnderscores = false)(scope const(C)[] str) if (isSomeChar!C);

pure @trusted BigInt fromBinaryString(bool allowUnderscores = false)(scope const(char)[] str);

pure nothrow @nogc @safe bool fromBinaryStringImpl(C, bool allowUnderscores = false)(scope const(C)[] str) if (isSomeChar!C);

ref auto pow()(ulong degree);

bool mulPow5()(ulong degree);

pure nothrow @nogc ref @safe BigInt opOpAssign(string op)(size_t shift) return if (op == "<<" || op == ">>");

const T opCast(T)() if (isFloatingPoint!T && isMutable!T);

const T opCast(T, bool nonZero = false)() if (is(T == long) || is(T == int));

bool copyFrom(W)(scope const(W)[] coefficients, bool sign = false) if (__traits(isUnsigned, W));

Returns:

overflow flag

const pure nothrow @safe immutable(C)[] toString(C = char)() scope if (isSomeChar!C && isMutable!C);

Examples:

auto str = "-34010447314490204552169750449563978034784726557588085989975288830070948234680";
auto integer = BigInt!4(str);
assert(integer.toString == str);

integer = BigInt!4.init;
assert(integer.toString == "0");

const void toString(C = char, W)(ref scope W w) scope if (isSomeChar!C && isMutable!C);

const @property size_t bitLength()();

const @property size_t ctlz()();

Library Reference

mir.bignum.integer