Infinite-precision arithmetic

xbury.cs at clearstream.com xbury.cs at clearstream.com
Tue May 24 05:10:34 EDT 2005


Very nice!

That's the easy part though ;)

Divisions is where it gets harder and using arrays may be much more 
efficient than
using strings or numbers... But items could work well too but wouldn't it 
be slower?

cheers
Xavier

On 24.05.2005 11:02:36 use-revolution-bounces wrote:
>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.
>_______________________________________________
>use-revolution mailing list
>use-revolution at lists.runrev.com
>http://lists.runrev.com/mailman/listinfo/use-revolution


-----------------------------------------
Visit us at http://www.clearstream.com
IMPORTANT MESSAGE    Internet communications are not secure and therefore
Clearstream International does not accept legal responsibility for the
contents of this message.    The information contained in this e-mail is
confidential and may be legally privileged. It is intended solely for the
addressee. If you are not the intended recipient, any disclosure, copying,
distribution or any action taken or omitted to be taken in reliance on it,
is prohibited and may be unlawful. Any views expressed in this e-mail are
those of the individual sender, except where the sender specifically states
them to be the views of Clearstream International or of any of its
affiliates or subsidiaries.    END OF DISCLAIMER


More information about the use-livecode mailing list