(Arbitrarily) Long-Division Script

[Geoff Canyon]

FYI, here's my original bignum multiplier:

function bigTimes X,Y
   if char 1 of X is "-" then
      put "-" into leadChar
      delete char 1 of X
   end if
   if char 1 of Y is "-"  then
      if leadChar is "-" then put empty into leadChar else put "-" into leadChar
      delete char 1 of Y
   end if
   put (3 + length(X)) div 4 * 4 into XL
   put char 1 to XL - length(X) of "000" before X
   put (3 + length(Y)) div 4 * 4 into YL
   put char 1 to YL - length(y) of "000" before y
   repeat with N = XL + YL down to 9 step -4
      repeat with M = max(4,N - YL) to min(XL,N - 4) step 4
         add (char M - 3 to M of X) * (char N - M - 3 to N - M of Y) to S
      end repeat
      put char -4 to -1 of S before R
      delete char -4 to -1 of S
   end repeat
   if S is 0 then put empty into S
   return leadChar & S & R
end bigTimes



On Fri, Oct 31, 2014 at 11:32 PM, Geoff Canyon <gcanyon at gmail.com> wrote:

> I've created similar routines in the past. Are you saying you do or don't
> want to allow for arbitrarily-large divisors?
>
> a pseudo-code algo for divisors that LC can handle:
>
> 1. remove the decimal points, remembering where they were
> 2. get the length of the divisor
> 3. grab that many characters from the dividend as the working dividend
> 4. if the working dividend is larger than the divisor, divide it by the
> divisor to find the quotient and remainder (new working dividend) and put
> the quotient after the final quotient
> 5. put the next character from the dividend after the working dividend and
> return to (4) until you run out of dividend
> 6. figure out where the decimal point goes and insert it
>
> for divisors that LC can't handle, (4) becomes:
>
> 4. if the working dividend is larger than the divisor, use your bignum
> subtraction to repeatedly subtract the divisor from the working dividend to
> find the quotient and remainder (new working dividend) and put the quotient
> after the final quotient
>
>
> On Thu, Oct 30, 2014 at 7:51 PM, Igor de Oliveira Couto <
> igor at semperuna.com> wrote:
>
>> Hi all,
>>
>> I wanted to develop a library to allow me to perform basic maths (add,
>> subtract, multiply, divide) with arbitrarily long numbers in LiveCode. My
>> requirements are simple:
>>
>> - integers and floating-point numbers must be supported as all operands
>> in all operations, to an arbitrarily large number of decimal cases
>>
>> - speed is NOT an issue: performances can safely be relatively slow, as
>> it is unlikely that it’ll need to perform hundreds of thousands of
>> operations per second
>>
>> - accuracy IS an issue: needless to say, all operations must provide
>> *accurate* and *reliable* results, regardless of how many decimal cases are
>> used
>>
>> It proved relatively easy to do the addition, multiplication and
>> subtraction operations in LiveCode. I followed the ‘pen-and-paper’
>> algorithm, and it all seems to be working really well - I’m happy to
>> provide anybody with a copy of the scripts off-list, if you wish (just send
>> me an email directly). I’m stuck, however, trying to implement DIVISION.
>> There does not seem to be an “easy” pen-and-paper algorithm that would
>> support arbitrarily large numbers with unknown number of decimal cases.
>>
>> Most long-division algorithm seems to expect that the number being
>> divided can be of an arbitrarily length, but they expect that the divisor
>> (the number we are dividing BY) is going to be low enough, so that the
>> person making the division will “know” instinctively how many times it
>> would “fit” into the number being divided. These algorithms are not
>> recommended once we start dealing with divisor of 3 digits or more. There
>> does not seem to be an algorithm that would allow us to procede
>> “digit-by-digit” with the division, as can be done with
>> addition/subtraction/multiplication… Or is there?
>>
>> Searching Google and Wikipedia has yielded articles about using bitwise
>> operations, or complex mathematical theory, both of which are beyond me. Is
>> there a Math Wiz in this list, who could give us a layman’s explantion of
>> an algorithm that could be used? Any help would be much appreciated!
>>
>> Kindest regards to all,
>>
>> --
>> Igor Couto
>> Sydney, Australia
>>
>> _______________________________________________
>> use-livecode mailing list
>> use-livecode at lists.runrev.com
>> Please visit this url to subscribe, unsubscribe and manage your
>> subscription preferences:
>> http://lists.runrev.com/mailman/listinfo/use-livecode
>
>
>