Infinite-precision arithmetic

Cubist at aol.com Cubist at aol.com
Tue May 24 05:02:36 EDT 2005


   I've just started to work on a suite of handlers for infinite-precision 
calculations. The core idea I shall exploit: Break up each calculation into a 
series of smaller operations which are within the machine's capability, and 
combine the results into an aggregate result which would otherwise be beyond the 
machine's capability. To simplify (and, hopefully, speed up) the code, the 
actual number-crunching will be done on integers and *only* integers; I'll take 
care of decimals by feeding them to "wrapper functions" which convert decimals 
into integers, hand the newly-converted numbers off to the i-p code, get the 
result, and do what's necessary to convert the result to the correct decimal.
   Here is the first handler of this suite-to-be:

local ChunkLen = 14

function InfPreAdd N1, N2
  put "X" into Rezult
  repeat
    put char (-1 * ChunkLen) to -1 of N1 into F1
    delete char (-1 * ChunkLen) to -1 of N1
    put char (-1 * ChunkLen) to -1 of N2 into F2
    delete char (-1 * ChunkLen) to -1 of N2
    put (F1 + F2) & "," before Rezult
    if N1 = "" and N2 = "" then exit repeat
  end repeat
  delete the last item of Rezult
  
  # we now have the result, divided up into (ChunkLen)- or (ChunkLen + 
1)-digit chunks.
  # time to move any "excess" digits from item N to item (N-1)
  
  repeat with K1 = (the number of items in Rezult) down to 2
    if the length of item K1 of Rezult = ChunkLen then next repeat
    add (char 1 of item K1 of Rezult) to item (K1 - 1) of Rezult
    delete char 1 of item K1 of Rezult
  end repeat
  
  # now all the items are the proper length. nuke the commas and return the 
result
  
  replace "," with "" in Rezult
  return Rezult
end InfPreAdd

   Speed being a consideration, particularly where large numbers of digits 
are concerned: I'm working with MetaCard 2.4.1 running under MacOS 9.1 on a 
400-MHz G3 "Pismo" PowerBook. I added pairs of randomly-generated N-digit numbers, 
timed the calculations, and here are some of the typical results I got. In 
all cases, the time-unit is milliseconds:

     50-digit numbers:     1
    100-digit numbers:     2
    200-digit numbers:     4
    500-digit numbers:     9
  1,000-digit numbers:    20
  2,000-digit numbers:    48
  5,000-digit numbers:   175
 10,000-digit numbers:   580
 20,000-digit numbers:  2270
 50,000-digit numbers: 14300

   There is clearly some room for improvement (on the high end in 
particular), but the InfPreAdd handler as it stands would appear to be fast enough for 
most purposes.


More information about the use-livecode mailing list