www.digitalmars.com

D Programming Language 2.0

Last update Thu Aug 7 22:02:20 2008

bigint

Provides a BigInt struct for multiprecision integer arithmetic.

The internal representation is binary, not decimal.

All relevant operators are overloaded.

Example:
        BigInt a = "9588669891916142";
        BigInt b = "7452469135154800";
        auto c = a * b;
        assert(c == "71459266416693160362545788781600");
        auto d = b * a;
        assert(d == "71459266416693160362545788781600");
        assert(d == c);
        d = c * "794628672112";
        assert(d == "56783581982794522489042432639320434378739200");
        auto e = c + d;
        assert(e == "56783581982865981755459125799682980167520800");
        auto f = d + c;
        assert(f == e);
        auto g = f - c;
        assert(g == d);
        g = f - d;
        assert(g == c);
        e = 12345678;
        g = c + e;
        auto h = g / b;
        auto i = g % b;
        assert(h == a);
        assert(i == e);


Authors:
Janice Caron

Date:
2008.05.18

License:
Public Domain



alias Digit;
alias for uint

struct BigInt;
Struct representing a multiprecision integer

void opAssign(const BigInt n);


void opAssign(int n);


void opAssign(uint n);


void opAssign(long n);


void opAssign(ulong n);


void opAssign(string s);


BigInt opCall(T)(T n);


const void castTo(out BigInt r);


const void castTo(out int r);


const void castTo(out uint r);


const void castTo(out long r);


const void castTo(out ulong r);


const void castTo(out string r);


const BigInt opPos();


const BigInt opNeg();


const BigInt opCom();


BigInt opPostInc();


BigInt opPostDec();


BigInt opAdd(T)(T n);


BigInt opAdd(T : int)(T n);


BigInt opAdd(T : const(BigInt))(T n);


void opAddAssign(T)(T n);


BigInt opSub(T)(T n);


BigInt opSub(T : int)(T n);


BigInt opSub(T : const(BigInt))(T n);


void opSubAssign(T)(T n);


BigInt opMul(T)(T n);


BigInt opMul(T : int)(T n);


BigInt opMul(T : const(BigInt))(T n);


void opMulAssign(T)(T n);


BigInt opDiv(T)(T n);


BigInt opDiv(T : int)(T n);


BigInt opDiv(T : const(BigInt))(T n);


void opDivAssign(T)(T n);


BigInt opMod(T)(T n);


int opMod(T : int)(T n);


BigInt opMod(T : const(BigInt))(T n);


void opModAssign(T : int)(T n);


void opModAssign(T)(T n);


BigInt opAnd(T)(T n);


BigInt opAnd(T : int)(T n);


uint opAnd(T : uint)(T n);


BigInt opAnd(T : const(BigInt))(T n);


void opAndAssign(T : uint)(T n);


void opAndAssign(T)(T n);


BigInt opOr(T)(T n);


BigInt opOr(T : int)(T n);


BigInt opOr(T : const(BigInt))(T n);


void opOrAssign(T)(T n);


BigInt opXor(T)(T n);


BigInt opXor(T : int)(T n);


BigInt opXor(T : const(BigInt))(T n);


void opXorAssign(T)(T n);


const BigInt opShl(uint n);


void opShlAssign(uint n);


const BigInt opShr(uint n);


void opShrAssign(uint n);


BigInt opUShr(T)(T n);


void opUShrAssign(T)(T n);


int opEquals(T)(T n);


int opEquals(T : int)(T n);


int opEquals(T : const(BigInt))(T n);


int opCmp(T)(T n);


int opCmp(T : int)(T n);


int opCmp(T : const(BigInt))(T n);


const string toString();


const hash_t toHash();


uint multibyteAddSub(char op)(uint[] dest, uint[] src1, uint[] src2, uint carry);
Multi-byte addition or subtraction dest[] = src1[] + src2[] + carry (0 or 1). or dest[] = src1[] - src2[] - carry (0 or 1). Returns carry or borrow (0 or 1). Set op == '+' for addition, '-' for subtraction.

Optimised asm arbitrary precision arithmetic ('bignum') routines for X86 processors.

All functions operate on arrays of uints, stored LSB first. If there is a destination array, it will be the first parameter. Currently, all of these functions are subject to change, and are intended for internal use only.

Author:
Don Clugston

Date:
May 2008.

License:
Public Domain

In simple terms, there are 3 modern x86 microarchitectures: (a) the P6 family (Pentium Pro, PII, PIII, PM, Core), produced by Intel; (b) the K6, Athlon, and AMD64 families, produced by AMD; and (c) the Pentium 4, produced by Marketing.

This code has been optimised for the Intel P6 family, except that it only uses the basic instruction set (doesn't use MMX, SSE, SSE2) Generally the code remains near-optimal for Core2, after translating EAX-> RAX, etc, since all these CPUs use essentially the same pipeline. The code uses techniques described in Agner Fog's superb manuals available at www.agner.org. Not optimal for AMD64, which can do two memory loads per cycle (Intel CPUs can only do one).

Timing results (cycles per int) PentiumM Core2 +,- 2.25 2.25 &,|,^ 2.0 2.0 <<,>> 2.0 2.0 cmp 2.0 2.0 * 5.0 mulAdd 5.4 div 18.0

Multi-byte addition or subtraction dest[] = src1[] + src2[] + carry (0 or 1). or dest[] = src1[] - src2[] - carry (0 or 1). Returns carry or borrow (0 or 1). Set op == '+' for addition, '-' for subtraction.

uint multibyteIncrement(char op)(uint[] dest, uint carry);
dest[] += carry, or dest[] -= carry. op must be '+' or '-' Returns final carry or borrow (0 or 1)

Optimised asm arbitrary precision arithmetic ('bignum') routines for X86 processors.

All functions operate on arrays of uints, stored LSB first. If there is a destination array, it will be the first parameter. Currently, all of these functions are subject to change, and are intended for internal use only.

Author:
Don Clugston

Date:
May 2008.

License:
Public Domain

In simple terms, there are 3 modern x86 microarchitectures: (a) the P6 family (Pentium Pro, PII, PIII, PM, Core), produced by Intel; (b) the K6, Athlon, and AMD64 families, produced by AMD; and (c) the Pentium 4, produced by Marketing.

This code has been optimised for the Intel P6 family, except that it only uses the basic instruction set (doesn't use MMX, SSE, SSE2) Generally the code remains near-optimal for Core2, after translating EAX-> RAX, etc, since all these CPUs use essentially the same pipeline. The code uses techniques described in Agner Fog's superb manuals available at www.agner.org. Not optimal for AMD64, which can do two memory loads per cycle (Intel CPUs can only do one).

Timing results (cycles per int) PentiumM Core2 +,- 2.25 2.25 &,|,^ 2.0 2.0 <<,>> 2.0 2.0 cmp 2.0 2.0 * 5.0 mulAdd 5.4 div 18.0

dest[] += carry, or dest[] -= carry. op must be '+' or '-' Returns final carry or borrow (0 or 1)

uint multibyteLogical(char op)(uint[] dest, uint[] src1, uint[] src2);
Dest[] = src1[] op src2[] where op == '&' or '|' or '^'

Optimised asm arbitrary precision arithmetic ('bignum') routines for X86 processors.

All functions operate on arrays of uints, stored LSB first. If there is a destination array, it will be the first parameter. Currently, all of these functions are subject to change, and are intended for internal use only.

Author:
Don Clugston

Date:
May 2008.

License:
Public Domain

In simple terms, there are 3 modern x86 microarchitectures: (a) the P6 family (Pentium Pro, PII, PIII, PM, Core), produced by Intel; (b) the K6, Athlon, and AMD64 families, produced by AMD; and (c) the Pentium 4, produced by Marketing.

This code has been optimised for the Intel P6 family, except that it only uses the basic instruction set (doesn't use MMX, SSE, SSE2) Generally the code remains near-optimal for Core2, after translating EAX-> RAX, etc, since all these CPUs use essentially the same pipeline. The code uses techniques described in Agner Fog's superb manuals available at www.agner.org. Not optimal for AMD64, which can do two memory loads per cycle (Intel CPUs can only do one).

Timing results (cycles per int) PentiumM Core2 +,- 2.25 2.25 &,|,^ 2.0 2.0 <<,>> 2.0 2.0 cmp 2.0 2.0 * 5.0 mulAdd 5.4 div 18.0

Dest[] = src1[] op src2[] where op == '&' or '|' or '^'