123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411 |
|
/** Arbitrary-precision ('bignum') arithmetic
*
* Copyright: Copyright (C) 2008 Don Clugston. All rights reserved.
* License: BSD style: $(LICENSE)
* Authors: Don Clugston
*/
module tango.math.BigInt;
private import tango.math.internal.BiguintCore;
/** A struct representing an arbitrary precision integer
*
* All arithmetic operations are supported, except
* unsigned shift right (>>>).
* Reverse operations are supported only for int, long,
* and ulong, due to language limitations.
* It implements value semantics using copy-on-write. This means that
* assignment is cheap, but operations such as x++ will cause heap
* allocation. (But note that for most bigint operations, heap allocation is
* inevitable anyway).
*
* Performance is excellent for numbers below ~1000 decimal digits.
* For X86 machines, highly optimised assembly routines are used.
*/
struct BigInt
{
private:
BigUint data; // BigInt adds signed arithmetic to BigUint.
bool sign = false;
public:
/// Construct a BigInt from a decimal or hexadecimal string.
/// The number must be in the form of a D decimal or hex literal:
/// It may have a leading + or - sign; followed by "0x" if hexadecimal.
/// Underscores are permitted.
/// BUG: Should throw a IllegalArgumentException/ConvError if invalid character found
static BigInt opCall(T : char[])(T z) {
char [] s = z;
BigInt r;
bool neg = false;
if (s[0] == '-') {
neg = true;
s = s[1..$];
} else if (s[0]=='+') {
s = s[1..$];
}
auto q = 0X3;
bool ok;
if (s.length>2 && (s[0..2]=="0x" || s[0..2]=="0X")) {
ok = r.data.fromHexString(s[2..$]);
} else {
ok = r.data.fromDecimalString(s);
}
assert(ok);
if (r.isZero()) neg = false;
r.sign = neg;
return r;
}
static BigInt opCall(T: int)(T x) {
BigInt r;
r.data = cast(ulong)((x < 0) ? -x : x);
r.sign = (x < 0);
return r;
}
///
void opAssign(T:int)(T x) {
data = cast(ulong)((x < 0) ? -x : x);
sign = (x < 0);
}
///
BigInt opAdd(T: int)(T y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
BigInt r;
r.sign = sign;
r.data = BigUint.addOrSubInt(data, u, sign!=(y<0), &r.sign);
return r;
}
///
BigInt opAddAssign(T: int)(T y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
data = BigUint.addOrSubInt(data, u, sign!=(y<0), &sign);
return *this;
}
///
BigInt opAdd(T: BigInt)(T y) {
BigInt r;
r.sign = sign;
r.data = BigUint.addOrSub(data, y.data, sign != y.sign, &r.sign);
return r;
}
///
BigInt opAddAssign(T:BigInt)(T y) {
data = BigUint.addOrSub(data, y.data, sign != y.sign, &sign);
return *this;
}
///
BigInt opSub(T: int)(T y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
BigInt r;
r.sign = sign;
r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign);
return r;
}
///
BigInt opSubAssign(T: int)(T y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
data = BigUint.addOrSubInt(data, u, sign == (y<0), &sign);
return *this;
}
///
BigInt opSub(T: BigInt)(T y) {
BigInt r;
r.sign = sign;
r.data = BigUint.addOrSub(data, y.data, sign == y.sign, &r.sign);
return r;
}
///
BigInt opSub_r(int y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
BigInt r;
r.sign = sign;
r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign);
r.negate();
return r;
}
///
BigInt opSub_r(long y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
BigInt r;
r.sign = sign;
r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign);
r.negate();
return r;
}
///
BigInt opSub_r(ulong y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
BigInt r;
r.sign = sign;
r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign);
r.negate();
return r;
}
///
BigInt opSubAssign(T:BigInt)(T y) {
data = BigUint.addOrSub(data, y.data, sign == y.sign, &sign);
return *this;
}
///
BigInt opMul(T: int)(T y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
return mulInternal(*this, u, sign != (y<0));
}
///
BigInt opMulAssign(T: int)(T y) {
ulong u = cast(ulong)(y < 0 ? -y : y);
*this = mulInternal(*this, u, sign != (y<0));
return *this;
}
///
BigInt opMul(T:BigInt)(T y) {
return mulInternal(*this, y);
}
///
BigInt opMulAssign(T: BigInt)(T y) {
*this = mulInternal(*this, y);
return *this;
}
///
BigInt opDiv(T:int)(T y) {
assert(y!=0, "Division by zero");
BigInt r;
uint u = y < 0 ? -y : y;
r.data = BigUint.divInt(data, u);
r.sign = r.isZero()? false : sign != (y<0);
return r;
}
///
BigInt opDivAssign(T: int)(T y) {
assert(y!=0, "Division by zero");
uint u = y < 0 ? -y : y;
data = BigUint.divInt(data, u);
sign = data.isZero()? false : sign ^ (y<0);
return *this;
}
///
BigInt opDivAssign(T: BigInt)(T y) {
*this = divInternal(*this, y);
return *this;
}
///
BigInt opDiv(T: BigInt)(T y) {
return divInternal(*this, y);
}
///
int opMod(T:int)(T y) {
assert(y!=0);
uint u = y < 0 ? -y : y;
int rem = BigUint.modInt(data, u);
// x%y always has the same sign as x.
// This is not the same as mathematical mod.
return sign? -rem : rem;
}
///
BigInt opModAssign(T:int)(T y) {
assert(y!=0);
uint u = y < 0 ? -y : y;
data = BigUint.modInt(data, u);
// x%y always has the same sign as x.
// This is not the same as mathematical mod.
return *this;
}
///
BigInt opMod(T: BigInt)(T y) {
return modInternal(*this, y);
}
///
BigInt opModAssign(T: BigInt)(T y) {
*this = modInternal(*this, y);
return *this;
}
///
BigInt opNeg() {
BigInt r = *this;
r.negate();
return r;
}
///
BigInt opPos() { return *this; }
///
BigInt opPostInc() {
BigInt old = *this;
data = BigUint.addOrSubInt(data, 1, false, &sign);
return old;
}
///
BigInt opPostDec() {
BigInt old = *this;
data = BigUint.addOrSubInt(data, 1, true, &sign);
return old;
}
///
BigInt opShr(T:int)(T y) {
BigInt r;
r.data = data.opShr(y);
r.sign = r.data.isZero()? false : sign;
return r;
}
///
BigInt opShrAssign(T:int)(T y) {
data = data.opShr(y);
if (data.isZero()) sign = false;
return *this;
}
///
BigInt opShl(T:int)(T y) {
BigInt r;
r.data = data.opShl(y);
r.sign = sign;
return r;
}
///
BigInt opShlAssign(T:int)(T y) {
data = data.opShl(y);
return *this;
}
///
int opEquals(T: BigInt)(T y) {
return sign == y.sign && y.data == data;
}
///
int opEquals(T: int)(T y) {
if (sign!=(y<0)) return 0;
return data.opEquals(cast(ulong)(y>=0?y:-y));
}
///
int opCmp(T:int)(T y) {
// if (y==0) return sign? -1: 1;
if (sign!=(y<0)) return sign ? -1 : 1;
int cmp = data.opCmp(cast(ulong)(y>=0? y: -y));
return sign? -cmp: cmp;
}
///
int opCmp(T:BigInt)(T y) {
if (sign!=y.sign) return sign ? -1 : 1;
int cmp = data.opCmp(y.data);
return sign? -cmp: cmp;
}
/// Returns the value of this BigInt as a long,
/// or +- long.max if outside the representable range.
long toLong() {
return (sign ? -1 : 1)*
(data.ulongLength() == 1 && (data.peekUlong(0) <= cast(ulong)(long.max)) ? cast(long)(data.peekUlong(0)): long.max);
}
/// Returns the value of this BigInt as an int,
/// or +- long.max if outside the representable range.
long toInt() {
return (sign ? -1 : 1)*
(data.uintLength() == 1 && (data.peekUint(0) <= cast(uint)(int.max)) ? cast(int)(data.peekUint(0)): int.max);
}
/// Number of significant uints which are used in storing this number.
/// The absolute value of this BigInt is always < 2^(32*uintLength)
int uintLength() { return data.uintLength(); }
/// Number of significant ulongs which are used in storing this number.
/// The absolute value of this BigInt is always < 2^(64*ulongLength)
int ulongLength() { return data.ulongLength(); }
/// Return x raised to the power of y
/// This interface is tentative and may change.
static BigInt pow(BigInt x, ulong y) {
BigInt r;
r.sign = (y&1)? x.sign : false;
r.data = BigUint.pow(x.data, y);
return r;
}
public:
/// Deprecated. Use uintLength() or ulongLength() instead.
int numBytes() {
return data.numBytes();
}
/// BUG: For testing only, this will be removed eventually
/// (needs formatting options)
char [] toDecimalString(){
char [] buff = data.toDecimalString(1);
if (isNegative()) buff[0] = '-';
else buff = buff[1..$];
return buff;
}
/// Convert to a hexadecimal string, with an underscore every
/// 8 characters.
char [] toHex() {
char [] buff = data.toHexString(1, '_');
if (isNegative()) buff[0] = '-';
else buff = buff[1..$];
return buff;
}
public:
void negate() { if (!data.isZero()) sign = !sign; }
bool isZero() { return data.isZero(); }
bool isNegative() { return sign; }
package:
/// BUG: For testing only, this will be removed eventually
BigInt sliceHighestBytes(uint numbytes) {
assert(numbytes<=numBytes());
BigInt x;
x.sign = sign;
x.data = data.sliceHighestBytes(numbytes);
return x;
}
private:
static BigInt addsubInternal(BigInt x, BigInt y, bool wantSub) {
BigInt r;
r.sign = x.sign;
r.data = BigUint.addOrSub(x.data, y.data, wantSub, &r.sign);
return r;
}
static BigInt mulInternal(BigInt x, BigInt y) {
BigInt r;
r.data = BigUint.mul(x.data, y.data);
r.sign = r.isZero() ? false : x.sign ^ y.sign;
return r;
}
static BigInt modInternal(BigInt x, BigInt y) {
if (x.isZero()) return x;
BigInt r;
r.sign = x.sign;
r.data = BigUint.mod(x.data, y.data);
return r;
}
static BigInt divInternal(BigInt x, BigInt y) {
if (x.isZero()) return x;
BigInt r;
r.sign = x.sign ^ y.sign;
r.data = BigUint.div(x.data, y.data);
return r;
}
static BigInt mulInternal(BigInt x, ulong y, bool negResult)
{
BigInt r;
if (y==0) {
r.sign = false;
r.data = 0;
return r;
}
r.sign = negResult;
r.data = BigUint.mulInt(x.data, y);
return r;
}
}
debug(UnitTest)
{
unittest {
// Radix conversion
assert( BigInt("-1_234_567_890_123_456_789").toDecimalString
== "-1234567890123456789");
assert( BigInt("0x1234567890123456789").toHex == "123_45678901_23456789");
assert( BigInt("0x00000000000000000000000000000000000A234567890123456789").toHex
== "A23_45678901_23456789");
assert( BigInt("0x000_00_000000_000_000_000000000000_000000_").toHex == "0");
assert(BigInt(-0x12345678).toInt() == -0x12345678);
assert(BigInt(-0x12345678).toLong() == -0x12345678);
assert(BigInt(0x1234_5678_9ABC_5A5AL).toLong() == 0x1234_5678_9ABC_5A5AL);
assert(BigInt(0xF234_5678_9ABC_5A5AL).toLong() == long.max);
assert(BigInt(-0x123456789ABCL).toInt() == -int.max);
}
}
|