View Single Post 2014-12-06, 03:15   #59
ewmayer
2ω=0

Sep 2002
República de California

2·11·13·41 Posts Quote:
 Originally Posted by legendarymudkip Is the carry step like with the GS method? So say if you had (48,52,52,52), would you then get the result 52+520+5200+48000=53772? If not, how else would you do it?
Assuming digit significance (power of 10) decreases from left to right, yes. But in practice we would start with the 0-index output term, the rightmost 52 in your notation, and work our way upward (leftward) like so, with the left-column index indicating power of 10, and /= denoting integer (truncating) divde and %= indicating (nonnegative-output) modulo:

0: 52, /= 5 (carry), %= 2;
1: 5+52, /= 5 (carry), %= 7;
2: 5+52, /= 5 (carry), %= 7;
3: 5+48, /= 5 (carry), %= 3;
4: 5+0, no carry, hence done.

Now *really* in practice we would use a modulo based on nearest-int rounding of the DIV result, yielding a balanced-digit representation of the result, 53772, which has much better numerical properties as far as the next FFT-squaring (assuming one occurs) is concerned. Same as above, but everytime the %= result is > 5 (i.e. half the base) we subtract 10 from the current digit and increment the carry by 1 to account for the -10:

0: 52, /= 5 (carry), %= 2;
1: 5+52, /= 6 (carry), %= -3;
2: 6+52, /= 6 (carry), %= -2;
3: 6+48, /= 5 (carry), %= 4;
4: 5+0, no carry, hence done.

Check the result: 2 + 10*( -3 + 10*( -2 + 10*( 4 + 10*(5)))) = 53772, as expected.

In the case where the "coin lands on its edge" (%= 5 in base-10) you can either use an IEEE-compliant round-to-nearest-even (if your hardware can do that efficiently), or just take whichever direction your preferred NINT emulation (e.g. NINT(x) = (x + c) - c, where the "magic constant" c = 0.75*2^b and b = #bits of the mantissa in your floating point type) - which of the 2 is not crucial, in my experience with these types of computations.  