giovedì 10 settembre 2015

Lavorare con numeri molto grandi 2

In un post precedente avevo scritto delle funzioni per avere una precisione assoluta facendo le operazioni basilari con un numero grande quanto si vuole, superando così i limiti imposti dai bit del processore.
Mi è stato fatto notare che l'operazione di divisione diventava estremamente lunga quando la differenza di cifre tra i due numeri erano notevoli.
Per questo ho scritto una nuova funzione, bigDivide2() per dividere i numeri molto grandi, che spezza l'operazione in operazioni più piccole, come facciamo noi esseri umani quando facciamo la divisione, rendendo l'operazione complessiva velocissima. Si appoggia dalla funzione bigDivide(), che già conoscete.
Vi metto qui tutto il codice:

`function bigAdd a1, a2`
`   #let's check if it's negative...`
`   #end check`
`   put reverse2(a1) into b1`
`   put reverse2(a2) into b2`
`   put 0 into mem`
`   if length(b1) < length(b2) then`
`      put b1 into temp`
`      put b2 into b1`
`      put temp into b1`
`   end if `
`   repeat while b2 is not empty`
`      put (char 1 of b1) + (char 1 of b2) + mem into ppp`
`      if length(ppp) = 1 then`
`         put 0 into mem`
`         put ppp before rrr`
`      else`
`         put 1 into mem`
`         put char 2 of ppp before rrr`
`      end if`
`      delete char 1 of b1`
`      delete char 1 of b2`
`   end repeat`
`   repeat while (b1 is not empty) `
`      put mem + (char 1 of b1) into ppp`
`      if length(ppp) = 1 then`
`         put 0 into mem`
`         put ppp before rrr`
`      else`
`         put 1 into mem`
`         put char 2 of ppp before rrr`
`      end if`
`      delete char 1 of b1`
`   end repeat`
`   if mem = 1 then`
`      put 1 before rrr`
`   else`
`      put b1 before rrr`
`   end if`
`   return rrr`
`end bigAdd`

`function reverse2 temp`
`repeat for each char tChar in temp`
`put tChar before temp2`
`end repeat`
`return temp2`
`end reverse2`

`function bigMultiply a1,a2`
`   put reverse2(a1) into a1`
`   put 0 into temp`
`   repeat for each char tChar in a1`
`      repeat with i=1 to tChar `
`         put bigAdd(temp,a2) into temp`
`      end repeat`
`      put 0 after a2`
`   end repeat`
`   return temp`
`end bigMultiply`

`function bigGreater a1,a2`
`   #compare two bignumbers:`
`   #return true if n1 > n2`
`   #return false if n1 < n2`
`   #return empty if n1 = n2 `
`   #let's check is a number is negative`
`   if ((char 1 of a1 = "-") or (char 1 of a2 = "-")) then`
`      if ((char 1 of a1 = "-") and (char 1 of a2 is not "-")) then`
`         return false`
`      end if      `
`      if ((char 1 of a1 is not "-") and ( char 1 of a2 = "-" )) then`
`         return true`
`      end if      `
`      #if we are here, both are negative`
`      delete char 1 of a1`
`      delete char 1 of a2`
`      if a1 = a2 then `
`         return empty`
`      else`
`         return (not bigGreater(a1,a2))`
`      end if`
`   end if`
`   if length(a1) is not length(a2) then`
`      return ( length(a1) > length(a2) ) #this is evalueted true or false`
`   else`
`      if a1 = a2 then `
`         return empty`
`      else`
`         repeat while ((char 1 of a1) = (char 1 of a2) )`
`            delete char 1 of a1`
`            delete char 1 of a2`
`         end repeat`
`         return ((char 1 of a1) > (char 1 of a2)) #this is evalueted true or false`
`      end if `
`   end if`
`end bigGreater`

`function bigSub a1,a2`
`   #substract the smallest big number from the largest one `
`   if bigGreater(a2,a1) then`
`      put a1 into temp`
`      put a2 into a1`
`      put temp into a2`
`   end if`
`   put reverse2(a1) into a1`
`   put reverse2(a2) into a2`
`   put 0 into mem`
`   repeat while (a2 is not empty)`
`      put (char 1 of a1) - mem + 10 - (char 1 of a2) into minus`
`      if length(minus) = 1 then`
`         put 1 into mem`
`         put minus before rrr`
`      else`
`         put 0 into mem`
`         put char 2 of minus before rrr`
`      end if`
`      delete char 1 of a1`
`      delete char 1 of a2`
`   end repeat`
`   repeat while (a1 is not empty)`
`      put char 1 of a1 + 10 - mem into minus`
`      if length(minus) = 1 then`
`         put 1 into mem`
`         put minus before rrr`
`      else`
`         put 0 into mem`
`         put char 2 of minus before rrr`
`      end if`
`      delete char 1 of a1`
`   end repeat`
`   #remove inital zeros`
`   repeat while (char 1 of rrr is "0")`
`      delete char 1 of rrr`
`   end repeat`
`   return rrr`
`end bigSub`

`function bigDivide a1,a2`
`   #output is a block of two numbers "quotient , remainder"`
`   if bigGreater(a2,a1) then`
`      return ("0," & a1)`
`   end if`
`   if a1 = a2 then`
`      return "1,0"`
`   end if`
`   put 0 into count`
`   repeat while (bigGreater(a1,a2))`
`      put bigSub(a1,a2) into a1`
`      put bigAdd(1,count) into count`
`   end repeat`
`   if a1 = a2 then`
`      put bigAdd(count,1) into count`
`      put 0 into a1`
`   end if`
`   return (count & comma & a1)`
`end bigDivide`

`function bigDivide2 a1,a2    `
`   put length(a1) into ldividendo`
`   put length(a2) into ldivisore   `
`   if ldividendo <= ldivisore then `
`      return bigDivide(a1,a2)`
`   end if   `
`   put char 1 to ldivisore of a1 into tDiv`
`   put bigDivide(tDiv,a2) into rrr `
`   put item 1 of rrr into quoziente`
`   put item 2 of rrr into resto`
`   put ldivisore + 1 into nn   `
`   repeat with i = nn to ldividendo`
`      put char i of a1 after resto`
`      put bigDivide(resto,a2) into temp`
`      put item 1 of temp after quoziente`
`      put item 2 of temp into resto      `
`   end repeat`
`   put removezeros(quoziente) into quoziente`
`   put removezeros(resto) into resto`
`   return (quoziente & comma & resto)`
`end bigDivide2`

`function removezeros temp`
`   repeat while char 1 of temp is "0"`
`      delete char 1 of temp`
`   end repeat`
`   return temp`
`end removezeros`