1 /** Arbitrary-precision ('bignum') arithmetic 2 * 3 * Copyright: Copyright (C) 2008 Don Clugston. All rights reserved. 4 * License: BSD style: $(LICENSE) 5 * Authors: Don Clugston 6 */ 7 8 module tango.math.BigInt; 9 10 private import tango.math.internal.BiguintCore; 11 12 /** A struct representing an arbitrary precision integer 13 * 14 * All arithmetic operations are supported, except 15 * unsigned shift right (>>>). 16 * Reverse operations are supported only for int, long, 17 * and ulong, due to language limitations. 18 * It implements value semantics using copy-on-write. This means that 19 * assignment is cheap, but operations such as x++ will cause heap 20 * allocation. (But note that for most bigint operations, heap allocation is 21 * inevitable anyway). 22 * 23 * Performance is excellent for numbers below ~1000 decimal digits. 24 * For X86 machines, highly optimised assembly routines are used. 25 */ 26 struct BigInt 27 { 28 private: 29 BigUint data; // BigInt adds signed arithmetic to BigUint. 30 bool sign = false; 31 public: 32 /// Construct a BigInt from a decimal or hexadecimal string. 33 /// The number must be in the form of a D decimal or hex literal: 34 /// It may have a leading + or - sign; followed by "0x" if hexadecimal. 35 /// Underscores are permitted. 36 /// BUG: Should throw a IllegalArgumentException/ConvError if invalid character found 37 static BigInt opCall(T : char[])(const(T) z) { 38 const(char) [] s = z; 39 BigInt r; 40 bool neg = false; 41 if (s[0] == '-') { 42 neg = true; 43 s = s[1..$]; 44 } else if (s[0]=='+') { 45 s = s[1..$]; 46 } 47 auto q = 0X3; 48 bool ok; 49 if (s.length>2 && (s[0..2]=="0x" || s[0..2]=="0X")) { 50 ok = r.data.fromHexString(s[2..$]); 51 } else { 52 ok = r.data.fromDecimalString(s); 53 } 54 assert(ok); 55 if (r.isZero()) neg = false; 56 r.sign = neg; 57 return r; 58 } 59 static BigInt opCall(T : long)(T x) { 60 BigInt r; 61 r.data = cast(ulong)((x < 0) ? -x : x); 62 r.sign = (x < 0); 63 return r; 64 } 65 /// 66 void opAssign(T:int)(T x) { 67 data = cast(ulong)((x < 0) ? -x : x); 68 sign = (x < 0); 69 } 70 /// 71 BigInt opAdd(T: int)(T y) { 72 ulong u = cast(ulong)(y < 0 ? -y : y); 73 BigInt r; 74 r.sign = sign; 75 r.data = BigUint.addOrSubInt(data, u, sign!=(y<0), &r.sign); 76 return r; 77 } 78 /// 79 BigInt opAddAssign(T: int)(T y) { 80 ulong u = cast(ulong)(y < 0 ? -y : y); 81 data = BigUint.addOrSubInt(data, u, sign!=(y<0), &sign); 82 return this; 83 } 84 /// 85 BigInt opAdd(T: BigInt)(T y) { 86 BigInt r; 87 r.sign = sign; 88 r.data = BigUint.addOrSub(data, y.data, sign != y.sign, &r.sign); 89 return r; 90 } 91 /// 92 BigInt opAddAssign(T:BigInt)(T y) { 93 data = BigUint.addOrSub(data, y.data, sign != y.sign, &sign); 94 return this; 95 } 96 /// 97 BigInt opSub(T: int)(T y) { 98 ulong u = cast(ulong)(y < 0 ? -y : y); 99 BigInt r; 100 r.sign = sign; 101 r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign); 102 return r; 103 } 104 /// 105 BigInt opSubAssign(T: int)(T y) { 106 ulong u = cast(ulong)(y < 0 ? -y : y); 107 data = BigUint.addOrSubInt(data, u, sign == (y<0), &sign); 108 return this; 109 } 110 /// 111 BigInt opSub(T: BigInt)(T y) { 112 BigInt r; 113 r.sign = sign; 114 r.data = BigUint.addOrSub(data, y.data, sign == y.sign, &r.sign); 115 return r; 116 } 117 /// 118 BigInt opSub_r(int y) { 119 ulong u = cast(ulong)(y < 0 ? -y : y); 120 BigInt r; 121 r.sign = sign; 122 r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign); 123 r.negate(); 124 return r; 125 } 126 /// 127 BigInt opSub_r(long y) { 128 ulong u = cast(ulong)(y < 0 ? -y : y); 129 BigInt r; 130 r.sign = sign; 131 r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign); 132 r.negate(); 133 return r; 134 } 135 /// 136 BigInt opSub_r(ulong y) { 137 ulong u = cast(ulong)(y < 0 ? -y : y); 138 BigInt r; 139 r.sign = sign; 140 r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign); 141 r.negate(); 142 return r; 143 } 144 /// 145 BigInt opSubAssign(T:BigInt)(T y) { 146 data = BigUint.addOrSub(data, y.data, sign == y.sign, &sign); 147 return this; 148 } 149 /// 150 BigInt opMul(T: int)(T y) { 151 ulong u = cast(ulong)(y < 0 ? -y : y); 152 return mulInternal(this, u, sign != (y<0)); 153 } 154 /// 155 BigInt opMulAssign(T: int)(T y) { 156 ulong u = cast(ulong)(y < 0 ? -y : y); 157 this = mulInternal(this, u, sign != (y<0)); 158 return this; 159 } 160 /// 161 BigInt opMul(T:BigInt)(T y) { 162 return mulInternal(this, y); 163 } 164 /// 165 BigInt opMulAssign(T: BigInt)(T y) { 166 this = mulInternal(this, y); 167 return this; 168 } 169 /// 170 BigInt opDiv(T:int)(T y) { 171 assert(y!=0, "Division by zero"); 172 BigInt r; 173 uint u = y < 0 ? -y : y; 174 r.data = BigUint.divInt(data, u); 175 r.sign = r.isZero()? false : sign != (y<0); 176 return r; 177 } 178 /// 179 BigInt opDivAssign(T: int)(T y) { 180 assert(y!=0, "Division by zero"); 181 uint u = y < 0 ? -y : y; 182 data = BigUint.divInt(data, u); 183 sign = data.isZero()? false : sign ^ (y<0); 184 return this; 185 } 186 /// 187 BigInt opDivAssign(T: BigInt)(T y) { 188 this = divInternal(this, y); 189 return this; 190 } 191 /// 192 BigInt opDiv(T: BigInt)(T y) { 193 return divInternal(this, y); 194 } 195 /// 196 int opMod(T:int)(T y) { 197 assert(y!=0); 198 uint u = y < 0 ? -y : y; 199 int rem = BigUint.modInt(data, u); 200 // x%y always has the same sign as x. 201 // This is not the same as mathematical mod. 202 return sign? -rem : rem; 203 } 204 /// 205 BigInt opModAssign(T:int)(T y) { 206 assert(y!=0); 207 uint u = y < 0 ? -y : y; 208 data = BigUint.modInt(data, u); 209 // x%y always has the same sign as x. 210 // This is not the same as mathematical mod. 211 return this; 212 } 213 /// 214 BigInt opMod(T: BigInt)(T y) { 215 return modInternal(this, y); 216 } 217 /// 218 BigInt opModAssign(T: BigInt)(T y) { 219 this = modInternal(this, y); 220 return this; 221 } 222 /// 223 BigInt opNeg() { 224 BigInt r = this; 225 r.negate(); 226 return r; 227 } 228 /// 229 BigInt opPos() { return this; } 230 /// 231 BigInt opPostInc() { 232 BigInt old = this; 233 data = BigUint.addOrSubInt(data, 1, false, &sign); 234 return old; 235 } 236 /// 237 BigInt opPostDec() { 238 BigInt old = this; 239 data = BigUint.addOrSubInt(data, 1, true, &sign); 240 return old; 241 } 242 /// 243 BigInt opShr(T:int)(T y) { 244 BigInt r; 245 r.data = data.opShr(y); 246 r.sign = r.data.isZero()? false : sign; 247 return r; 248 } 249 /// 250 BigInt opShrAssign(T:int)(T y) { 251 data = data.opShr(y); 252 if (data.isZero()) sign = false; 253 return this; 254 } 255 /// 256 BigInt opShl(T:int)(T y) { 257 BigInt r; 258 r.data = data.opShl(y); 259 r.sign = sign; 260 return r; 261 } 262 /// 263 BigInt opShlAssign(T:int)(T y) { 264 data = data.opShl(y); 265 return this; 266 } 267 /// 268 int opEquals(T: BigInt)(T y) { 269 return sign == y.sign && y.data == data; 270 } 271 /// 272 int opEquals(T: int)(T y) { 273 if (sign!=(y<0)) return 0; 274 return data.opEquals(cast(ulong)(y>=0?y:-y)); 275 } 276 /// 277 int opCmp(T:int)(T y) { 278 // if (y==0) return sign? -1: 1; 279 if (sign!=(y<0)) return sign ? -1 : 1; 280 int cmp = data.opCmp(cast(ulong)(y>=0? y: -y)); 281 return sign? -cmp: cmp; 282 } 283 /// 284 int opCmp(T:BigInt)(T y) { 285 if (sign!=y.sign) return sign ? -1 : 1; 286 int cmp = data.opCmp(y.data); 287 return sign? -cmp: cmp; 288 } 289 /// Returns the value of this BigInt as a long, 290 /// or +- long.max if outside the representable range. 291 long toLong() { 292 return (sign ? -1 : 1)* 293 (data.ulongLength() == 1 && (data.peekUlong(0) <= cast(ulong)(long.max)) ? cast(long)(data.peekUlong(0)): long.max); 294 } 295 /// Returns the value of this BigInt as an int, 296 /// or +- long.max if outside the representable range. 297 long toInt() { 298 return (sign ? -1 : 1)* 299 (data.uintLength() == 1 && (data.peekUint(0) <= cast(uint)(int.max)) ? cast(int)(data.peekUint(0)): int.max); 300 } 301 /// Number of significant uints which are used in storing this number. 302 /// The absolute value of this BigInt is always < 2^(32*uintLength) 303 int uintLength() { return data.uintLength(); } 304 /// Number of significant ulongs which are used in storing this number. 305 /// The absolute value of this BigInt is always < 2^(64*ulongLength) 306 int ulongLength() { return data.ulongLength(); } 307 308 /// Return x raised to the power of y 309 /// This interface is tentative and may change. 310 static BigInt pow(BigInt x, ulong y) { 311 BigInt r; 312 r.sign = (y&1)? x.sign : false; 313 r.data = BigUint.pow(x.data, y); 314 return r; 315 } 316 public: 317 /// Deprecated. Use uintLength() or ulongLength() instead. 318 int numBytes() { 319 return data.numBytes(); 320 } 321 /// BUG: For testing only, this will be removed eventually 322 /// (needs formatting options) 323 char [] toDecimalString(){ 324 char [] buff = data.toDecimalString(1); 325 if (isNegative()) buff[0] = '-'; 326 else buff = buff[1..$]; 327 return buff; 328 } 329 /// Convert to a hexadecimal string, with an underscore every 330 /// 8 characters. 331 char [] toHex() { 332 char [] buff = data.toHexString(1, '_'); 333 if (isNegative()) buff[0] = '-'; 334 else buff = buff[1..$]; 335 return buff; 336 } 337 public: 338 void negate() { if (!data.isZero()) sign = !sign; } 339 bool isZero() { return data.isZero(); } 340 bool isNegative() { return sign; } 341 package: 342 /// BUG: For testing only, this will be removed eventually 343 BigInt sliceHighestBytes(uint numbytes) { 344 assert(numbytes<=numBytes()); 345 BigInt x; 346 x.sign = sign; 347 x.data = data.sliceHighestBytes(numbytes); 348 return x; 349 } 350 351 private: 352 static BigInt addsubInternal(BigInt x, BigInt y, bool wantSub) { 353 BigInt r; 354 r.sign = x.sign; 355 r.data = BigUint.addOrSub(x.data, y.data, wantSub, &r.sign); 356 return r; 357 } 358 static BigInt mulInternal(BigInt x, BigInt y) { 359 BigInt r; 360 r.data = BigUint.mul(x.data, y.data); 361 r.sign = r.isZero() ? false : x.sign ^ y.sign; 362 return r; 363 } 364 365 static BigInt modInternal(BigInt x, BigInt y) { 366 if (x.isZero()) return x; 367 BigInt r; 368 r.sign = x.sign; 369 r.data = BigUint.mod(x.data, y.data); 370 return r; 371 } 372 static BigInt divInternal(BigInt x, BigInt y) { 373 if (x.isZero()) return x; 374 BigInt r; 375 r.sign = x.sign ^ y.sign; 376 r.data = BigUint.div(x.data, y.data); 377 return r; 378 } 379 static BigInt mulInternal(BigInt x, ulong y, bool negResult) 380 { 381 BigInt r; 382 if (y==0) { 383 r.sign = false; 384 r.data = 0; 385 return r; 386 } 387 r.sign = negResult; 388 r.data = BigUint.mulInt(x.data, y); 389 return r; 390 } 391 } 392 393 debug(UnitTest) 394 { 395 unittest { 396 // Radix conversion 397 assert( BigInt("-1_234_567_890_123_456_789").toDecimalString 398 == "-1234567890123456789"); 399 assert( BigInt("0x1234567890123456789").toHex == "123_45678901_23456789"); 400 assert( BigInt("0x00000000000000000000000000000000000A234567890123456789").toHex 401 == "A23_45678901_23456789"); 402 assert( BigInt("0x000_00_000000_000_000_000000000000_000000_").toHex == "0"); 403 404 assert(BigInt(-0x12345678).toInt() == -0x12345678); 405 assert(BigInt(-0x12345678).toLong() == -0x12345678); 406 assert(BigInt(0x1234_5678_9ABC_5A5AL).toLong() == 0x1234_5678_9ABC_5A5AL); 407 assert(BigInt(0xF234_5678_9ABC_5A5AL).toLong() == long.max); 408 assert(BigInt(-0x123456789ABCL).toInt() == -int.max); 409 410 } 411 }