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 for uint
- Struct representing a multiprecision integer
- 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.
- 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)
- 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 '^'