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