Changeset 3831
- Timestamp:
- 07/31/08 16:16:02 (4 months ago)
- Files:
-
- trunk/tango/math/internal (moved) (moved from trunk/tango/math/impl) (1 prop)
- trunk/tango/math/internal/BignumNoAsm.d (modified) (2 diffs)
- trunk/tango/math/internal/BignumX86.d (modified) (1 diff)
- trunk/tango/math/internal/BiguintCore.d (copied) (copied from trunk/tango/math/impl/BiguintCore.d) (6 diffs)
Legend:
- Unmodified
- Added
- Removed
- Modified
- Copied
- Moved
trunk/tango/math/internal
- Property svn:mergeinfo set
trunk/tango/math/internal/BignumNoAsm.d
r3825 r3831 7 7 * This module is intended only to assist development of high-speed routines 8 8 * on currently unsupported processors. 9 * The X86 asm version is about 30 times faster than the D version(DMD). 9 10 * 10 11 * Copyright: Copyright (C) 2008 Don Clugston. All rights reserved. … … 13 14 */ 14 15 15 module tango.math.i mpl.BignumNoAsm;16 module tango.math.internal.BignumNoAsm; 16 17 17 18 public: trunk/tango/math/internal/BignumX86.d
r3825 r3831 40 40 */ 41 41 42 module tango.math.i mpl.BignumX86;42 module tango.math.internal.BignumX86; 43 43 44 44 /* trunk/tango/math/internal/BiguintCore.d
r3829 r3831 6 6 */ 7 7 8 module tango.math.impl.BiguintCore; 9 10 version(GNU) { 8 module tango.math.internal.BiguintCore; 9 10 version(TangoBignumNoAsm) { 11 private import tango.math.internal.BignumNoAsm; 12 } else version(GNU) { 11 13 // GDC lies about its X86 support 12 private import tango.math.i mpl.BignumNoAsm;14 private import tango.math.internal.BignumNoAsm; 13 15 } else version(D_InlineAsm_X86) { 14 private import tango.math.i mpl.BignumX86;16 private import tango.math.internal.BignumX86; 15 17 } else { 16 private import tango.math.i mpl.BignumNoAsm;18 private import tango.math.internal.BignumNoAsm; 17 19 } 18 20 … … 294 296 uint chunksize = y.length + (x.length % y.length); 295 297 // We make the buffer a bit bigger so we have space for the partial sums. 296 uint [] scratchbuff = new uint[karatsubaRequiredBuffSize( chunksize) + y.length * 2];298 uint [] scratchbuff = new uint[karatsubaRequiredBuffSize(y.length+ chunksize) + y.length * 2+1]; 297 299 if (y.length == half) { 298 300 chunksize = x.length - y.length; … … 308 310 result[done + y.length .. done + y.length + chunksize] 309 311 = partial[y.length .. y.length + chunksize]; 310 simpleAddAssign(result[done .. y.length +chunksize], partial[0 .. y.length]);312 simpleAddAssign(result[done .. done + y.length+chunksize], partial[0 .. y.length]); 311 313 done += y.length; 312 314 } … … 391 393 assert(result.length > right.length); 392 394 uint c = multibyteAddSub!('+')(result[0..right.length], result[0..right.length], right, 0); 393 if (c) c = multibyteIncrementAssign!('+')(result[right.length .. $], c); 394 assert(c==0); 395 if (c) { 396 c = multibyteIncrementAssign!('+')(result[right.length .. $], c); 397 assert(c==0); 398 } 395 399 } 396 400 … … 403 407 uint karatsubaRequiredBuffSize(uint xlen) 404 408 { 405 return xlen <= KARATSUBALIMIT ? 0 : xlen * 2; 406 } 407 409 uint half = (xlen >> 1) + (xlen & 1); 410 return xlen <= KARATSUBALIMIT ? 0 : 2*half+1 + karatsubaRequiredBuffSize(half); 411 } 412 413 //uint lastleftover = 0; 408 414 /* Sets result = x*y, using Karatsuba multiplication. 409 415 * Valid only for balanced multiplies, and x must be longer than y. 410 416 * ie 2*y.length > x.length >= y.length. 417 * It is efficient only if sqrt(2)*y.length > x.length >= y.length 411 418 * Params: 412 419 * scratchbuff An array long enough to store all the temporaries. Will be destroyed. … … 435 442 uint [] ysum = result[half .. half*2]; 436 443 uint [] mid = scratchbuff[0 .. half*2+1]; 437 uint [] newscratchbuff = scratchbuff[half*2+ 2.. $];444 uint [] newscratchbuff = scratchbuff[half*2+1 .. $]; 438 445 uint [] resultLow = result[0 .. x0.length + y0.length]; 439 446 uint [] resultHigh = result[x0.length + y0.length .. $];
