src/number.h

   1 #ifdef _WIN32\r
   2 //min y max entran en conflicto con la windows.h, son rebautizadas en Windows\r
   3 #define min _cpp_min\r
   4 #define max _cpp_max\r
   5 #endif\r
   6 \r
   7 //#include <vector>\r
   8 #include <deque>
   9 #include <algorithm>
  10 #include <iterator>\r
  11
  12 //XXX Pensado para andar con unsigned's (si anda con otra cosa es casualidad =)
  13
  14 template < typename T >
  15 struct number
  16 {
  17
  18         // Tipos
  19         typedef T atomic_type;
  20         typedef typename std::vector< T > chunk_type;
  21         typedef typename chunk_type::size_type size_type;
  22         typedef typename chunk_type::iterator iterator;\r
  23         typedef typename chunk_type::const_iterator const_iterator;\r
  24         typedef typename chunk_type::reverse_iterator reverse_iterator;\r
  25         typedef typename chunk_type::const_reverse_iterator const_reverse_iterator;
  26
  27         // Constructores (después de construído, el chunk siempre tiene al menos
  28         // un elemento).
  29         // Constructor default (1 'átomo con valor 0)
  30         number(): chunk(1, 0) {}
  31         // Constructor a partir de buffer (de 'átomos') y tamaño
  32         // Copia cada elemento del buffer como un 'átomo' del chunk
  33         // (el átomo menos significativo es el chunk[0] == buf[0])
  34         number(atomic_type* buf, size_type len, sign_type sign = positive):
  35                 chunk(buf, buf + len), sign(sign)
  36                 { fix_empty(); }
  37         // Constructor a partir de un buffer (de 'átomos') terminado en 0
  38         // FIXME (en realidad está 'roto' este contructor porque no puedo
  39         // inicializar números con un átomo == 0 en el medio)
  40         number(atomic_type* buf, sign_type sign = positive): sign(sign)
  41                 { while (*buf) chunk.push_back(*(buf++)); fix_empty(); }
  42         // Constructor a partir de un 'átomo' (lo asigna como único elemento del
  43         // chunk)
  44         number(atomic_type n, sign_type sign = positive):
  45                 chunk(1, n), sign(sign) {} // copia una vez n en el vector
  46         // TODO constructor a partir de string.
  47
  48         // Operadores
  49         number& operator++ () { carry(0); return *this; }
  50         number& operator+= (const number& n);\r
  51         number& operator* (const number& n);\r
  52         number& operator*= (const number< T >& n);\r
  53         number& operator << (const size_type N);\r
  54 \r
  55         // Devuelve referencia a 'átomo' i del chunk (no debería ser necesario
  56         // si la multiplicación es un método de este objeto).
  57         atomic_type& operator[] (size_type i) { return chunk[i]; }
  58
  59         // Iteradores (no deberían ser necesarios)
  60         iterator begin() { return chunk.begin(); }
  61         iterator end() { return chunk.end(); }\r
  62         const_iterator begin() const { return chunk.begin(); }
  63         const_iterator end() const { return chunk.end(); }\r
  64         reverse_iterator rbegin() { return chunk.rbegin(); }\r
  65         reverse_iterator rend() { return chunk.rend(); }\r
  66         const_reverse_iterator rbegin() const { return chunk.rbegin(); }\r
  67         const_reverse_iterator rend() const { return chunk.rend(); }\r
  68
  69
  70         private:
  71         // Atributos
  72         chunk_type chunk;
  73         sign_type sign;
  74
  75         // Helpers
  76         // Pone un chunk en 0 para que sea un invariante de representación que
  77         // el chunk no sea vacío (siempre tenga la menos un elemento).
  78         void fix_empty() { if (!chunk.size()) chunk.push_back(0); }\r
  79         // Propaga carry a partir del 'átomo' i (suma 1 al 'átomo' i propagando
  80         // carry)\r
  81         void carry(size_type i)
  82         {
  83                 if (chunk.size() > i)
  84                 {
  85                         ++chunk[i];
  86                         if (!chunk[i]) carry(i+1); // Overflow
  87                 }
  88                 else chunk.push_back(1);
  89         }\r
  90 \r
  91 };
  92
  93 template < typename T >
  94 number< T >& number< T >::operator+= (const number< T >& n)
  95 {
  96         atomic_type c = 0;
  97         size_type ini = 0;
  98         size_type fin = std::min(chunk.size(), n.chunk.size());\r
  99         size_type i; //problema de VC++, da error de redefinición\r
 100
 101         // "intersección" entre ambos chunks
 102         // +-----+-----+------+------+
 103         // |     |     |      |      | <--- mio
 104         // +-----+-----+------+------+
 105         // +-----+-----+------+
 106         // |     |     |      |        <--- chunk de n
 107         // +-----+-----+------+
 108         //
 109         // |------------------|
 110         // Esto se procesa en este for
 111         for (i = ini; i < fin; ++i)
 112         {
 113                 chunk[i] += n.chunk[i] + c;
 114                 if (chunk[i] || (!n.chunk[i] && !c)) c = 0; // OK
 115                 else                                 c = 1; // Overflow
 116         }
 117         // si mi chunk es más grande que el del otro, sólo me queda
 118         // propagar el carry
 119         if (chunk.size() >= n.chunk.size())
 120         {
 121                 if (c) carry(fin); // Propago carry
 122                 return *this;
 123         }
 124         // Hay más
 125         // +-----+-----+------+
 126         // |     |     |      |         <--- mío
 127         // +-----+-----+------+
 128         // +-----+-----+------+------+
 129         // |     |     |      |      |  <--- chunk de n
 130         // +-----+-----+------+------+
 131         //
 132         //                    |------|
 133         //            Esto se procesa en este for
 134         // (suma los chunks de n propagando algún carry si lo había)
 135         ini = fin;
 136         fin = n.chunk.size();
 137         for (i = ini; i < fin; ++i)
 138         {
 139                 chunk.push_back(n.chunk[i] + c); // Agrego nuevo átomo
 140                 if (chunk[i] || !c) c = 0; // OK
 141                 else                c = 1; // Overflow
 142         }
 143         // Si me queda algún carry colgado, hay que agregar un "átomo"
 144         // más al chunk.
 145         if (c) chunk.push_back(1); // Último carry
 146         return *this;
 147 }\r
 148 \r
 149 // efectúa un shifteo a izquierda del chunk, agregando 0s en los casilleros menos significativos\r
 150 template < typename T >\r
 151 number< T >& number< T >::operator << (size_type N)\r
 152 {\r
 153         size_type i;\r
 154         for (i = 0; i < N; i++)\r
 155         {\r
 156                 chunk.push_front(0);\r
 157         }\r
 158 \r
 159         return *this;\r
 160 }
 161
 162 template < typename T >
 163 number< T > operator+ (const number< T >& n1, const number< T >& n2)
 164 {
 165         number< T > tmp = n1;
 166         tmp += n2;
 167         return tmp;
 168 }
 169
 170 template < typename T >
 171 std::ostream& operator<< (std::ostream& os, const number< T >& n)
 172 {
 173         // FIXME sacar una salida bonita en ASCII =)\r
 174         std::copy(n.rbegin(), n.rend(), std::ostream_iterator< T >(os, " "));
 175         return os;
 176 }\r
 177 \r
 178 // Normaliza las longitudes de 2 numbers, completando con 0s a la izquierda\r
 179 // al más pequeño. Sirve para División y Conquista\r
 180 template < typename T >\r
 181 void normalize_length (number< T >& l_op, number< T >& r_op)\r
 182 {\r
 183         //si son de distinto tamaño tengo que agregar ceros a la izquierda al menor para división y conquista\r
 184         while (l_op.chunk.size()<r_op.chunk.size())\r
 185         {\r
 186                 l_op.chunk.push_back(0);\r
 187         }\r
 188 \r
 189         while (l_op.chunk.size()>r_op.chunk.size())\r
 190         {\r
 191                 r_op.chunk.push_back(0);\r
 192         }\r
 193 \r
 194         //si no tiene cantidad par de números le agrego un atomic_type 0 a la izquierda para no tener que contemplar\r
 195         //splits de chunks impares\r
 196         if (l_op.chunk.size()%2 != 0)\r
 197         {\r
 198                 l_op.chunk.push_back(0);\r
 199                 r_op.chunk.push_back(0);\r
 200         }\r
 201 }\r
 202 \r
 203 //parte un número en dos mitades de misma longitud\r
 204 template < typename T >\r
 205 void split (const number< T >&full, number< T >& upper_half, number< T >& lower_half)\r
 206 {\r
 207         size_type full_size = full.chunk.size();\r
 208         size_type halves_size = full_size / 2;\r
 209         size_type i = 0;\r
 210 \r
 211         // vacío las mitades\r
 212         upper_half.chunk.clear();\r
 213         lower_half.chunk.clear();\r
 214 \r
 215         // la primera mitad va al pedazo inferior\r
 216         for (i = 0; i < halves_size; i++)\r
 217         {\r
 218                 lower_half.chunk.push_back(full.chunk[i]);\r
 219         }\r
 220 \r
 221         // la segunda mitad (si full_size es impar es 1 más que la primera mitad) va al pedazo superior\r
 222         for ( ; i < full_size; i++)\r
 223         {\r
 224                 upper_half.chunk.push_back(full.chunk[i]);\r
 225         }\r
 226 }\r
 227 \r
 228 // es el algoritmo de división y conquista, que se llama recursivamente\r
 229 template < typename T >\r
 230 number < T > divide_n_conquer (number< T > u, number< T > v)\r
 231 {\r
 232         //tomo el chunk size de u (el de v DEBE ser el mismo)\r
 233         size_type chunk_size = u.chunk.size();\r
 234         \r
 235         if (chunk_size == 1)\r
 236         {\r
 237                 //condición de corte. Ver que por más que tenga 1 único elemento puede "rebalsar" la capacidad\r
 238                 //del atomic_type, como ser multiplicando 0xff * 0xff usando bytes!!!\r
 239                 return u.chunk[0]*v.chunk[0];\r
 240         }\r
 241         \r
 242         number < T > u1, u2, v1, v2;\r
 243         split (u, u1, u2);\r
 244         split (v, v1, v2);\r
 245 \r
 246         // Los nombres M, D y H los puso Rosita en clase, cambiar si se les ocurren algunos mejores!\r
 247         // M = u1*v1\r
 248         // D = u2*v2\r
 249         // H = (u1+v1)*(u2+v2) = u1*u2+u1*v2+u2*v1+u2*v2\r
 250         number < T > M = divide_n_conquer (u1, v1);\r
 251         number < T > D = divide_n_conquer (u2, v2);\r
 252         number < T > H = divide_n_conquer (u1+v1, u2+v2);\r
 253 \r
 254         // H-D-M = u1*u2+u1*v2+u2*v1+u2*v2 - u2*v2 - u1*v1 = u1*v2+u2*v1\r
 255         // u1*v1 << base^N + u1*v2+u2*v1 << base^N/2 + u2*v2\r
 256         return (M << chunk_size) + ((H-D-M) << chunk_size/2) + H;\r
 257         \r
 258 }\r
 259 \r
 260 template < typename T >
 261 number< T >& number< T >::operator*= (const number< T >& n)\r
 262 {\r
 263         number < T > r_op = n;\r
 264 \r
 265         normalize_length(*this, n);\r
 266         *this = divide_n_conquer(*this, n);\r
 267         \r
 268         return *this;\r
 269 }\r
 270 \r
 271 template < typename T >\r
 272 number< T > operator* (const number< T >& n1, const number< T >& n2)\r
 273 {\r
 274         number< T > tmp = n1;\r
 275         tmp *= n2;\r
 276         return tmp;\r
 277 }\r