martedì 1 settembre 2015

Lavorare con numeri molto grandi

Se si deve lavorare con numeri molto grandi, composti da centinaia di cifre, non si possono utilizzare le normali funzioni matematiche dei software.
Quasi tutti i linguaggi di programmazione usano delle funzioni di basso livello per velocizzare i conti, ma questo implica portarsi dietro i limiti dei processori ad esempio in linea teorica un computer a 32bit può gestire solo numeri fino a 232, mentre computer a 64 bit possono gestire 264.
Ogni software opera un certo grado di approssimazione per numeri molto grandi, quindi bisogna scrivere delle funzioni particolari che possano elaborare numeri senza limiti od errori.
Qui di seguito trovate il codice per fare somma (bigSum), sottrazione (bigSub), moltiplicazione (bigMultiply) e divisione (bigDivide) e anche per capire se un numero è più grande di un altro (bigGreater).
Con queste funzioni potrete gestire tutti i numeri senza alcune errore e di qualunque dimensione.


function bigAdd a1, a2
   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
   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 & " , " & a1)
end bigDivide


Ad esempio per fare la sottrazione "123456789123456789123456789 - 1234567891023456789", basta usare :

bigSub(123456789123456789123456789, 1234567891023456789) = 123456787888888898100000000

mentre per molti altri software il risultato è 1.23456787888889E+26 che è sbagliato!

La spiegazione è che molti software approssimano quando non hanno più bit a disposizione, quindi usano solo le prime 15 cifre e poi aggiungo zeri. In questo modo danno come risultato

1.23456787888889E+26

che significa
123456787888889000000000000

mentre il risultato corretto è
123456787888888898100000000

L'errore è di 101'900'000'000, vi sembra un piccolo errore?