Infinite precision - Addition

[Cubist at aol.com]

use-revolution at lists.runrev.com

   I am unreasonably pleased with myself. Tonight, I found and cured a most 
heinous bug in my InfPreAdd handler. In addition, I found a way to make that 
puppy run Significantly Faster. And best of all, the speed boost *increases* 
with the number of digits!

   The bug: Breaking up vast numbers into smaller chunks is all well and 
good, but you have to be careful when the chunks come with leading zeroes... I 
will not make the mistake of *failing* to set the numberFormat appropriately in 
any other handlers in the "infinite precision" suite, thank you very much!

   The speed-up: Instead of breaking things up into 14-character items, I 
worked with the number-strings *as* strings. See handler below for details.

   Benchmarking the new version against the old: Hardware and software 
environment is as it was for the timing data I posted a few days back  -- 400-MHz G3 
"Pismo" w/ 320 MB of RAM, MacOS 9.1, MetaCard 2.4.1 with 55 MB of RAM 
allocated to it. Yeah, I didn't provide *all* this data the last time, but nothing 
changed between then and now.
   I generated random N-digit numbers in pairs. Each pair of numbers was fed 
to the old and new InfPreAdd versions. I used the built-in milliseconds 
function for timing.
   For each value of N, I used 20 pairs of numbers; of the 20 resulting 
times, I set aside the 4 highest and and 4 lowest numbers, and took the average of 
the remaining 16 middlemost times.

   How fast *is* it, already: I've included the timing data from the original 
InfPreAdd version, which indicated that the bug-fix didn't slow anything down 
(hooray!). Aside from that, here's the high, low, and average times I got 
working with numbers of lengths from 50 digits up to 50,000.


No. of | Orig. |      Corrected      |       Real
Digits | Vrsn. |   Avg    Low   High |  Avg   Low  High
=======|=======|=====================|=================
    50 |     1 |     1      0      1 |    0.6   0     1
   100 |     2 |     2      1      2 |    1.2   1     2
   200 |     4 |     3.8    3      4 |    2.6   2     3
   500 |     9 |     9.3    8     14 |    6.1   6     7
 1,000 |    20 |    19.7   17     22 |   13    12    14
 2,000 |    48 |    46.6   45     64 |   27    26    44
 5,000 |   175 |   175    169    200 |   74    71    90
10,000 |   580 |   575    542    592 |  182   177   196
20,000 |  2270 |  2237   2159   2327 |  572   540   602
50,000 | 14300 | 14878  14711  15224 | 3489  3381  3667


   And, as mentioned above, here's the new handler...


function InfPreAdd N1, N2 # standard addition -- new and improved!
  set the numberFormat to "00000000000000"
  put "" into Rezult
  
  repeat
    put (char (-1 * SumChunkLen) to -1 of N1) + (char (-1 * SumChunkLen) to 
-1 of N2) into Fred
    
    delete char (-1 * SumChunkLen) to -1 of N1
    delete char (-1 * SumChunkLen) to -1 of N2
    
    put ((the length of Rezult) mod SumChunkLen) into ExtraPlace
    if ExtraPlace <> 0 then
      put Fred + (char 1 to ExtraPlace of Rezult) into char 1 to ExtraPlace 
of Rezult
    else
      put Fred before Rezult
    end if
    
    if (N1 = "") and (N2 = "") then exit repeat
  end repeat
  repeat while char 1 of Rezult = "0"
    delete char 1 of Rezult
  end repeat
  
  return Rezult
end InfPreAdd