From 34d83b3b16895b7e509ea9266001e94e8ce76e2f Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Mon, 3 Oct 2005 04:28:00 +0000 Subject: [PATCH] Bugfixes para que compile. --- src/number.h | 327 ++++++++++++++++++++++++++------------------------- 1 file changed, 166 insertions(+), 161 deletions(-) diff --git a/src/number.h b/src/number.h index 9352008..b5e433f 100644 --- a/src/number.h +++ b/src/number.h @@ -1,27 +1,29 @@ -#ifdef _WIN32 -//min y max entran en conflicto con la windows.h, son rebautizadas en Windows -#define min _cpp_min -#define max _cpp_max -#endif - -//#include +#ifdef _WIN32 +//min y max entran en conflicto con la windows.h, son rebautizadas en Windows +#define min _cpp_min +#define max _cpp_max +#endif + #include +#include #include -#include +#include //XXX Pensado para andar con unsigned's (si anda con otra cosa es casualidad =) -template < typename T > +template < typename N = uint32_t, typename E = uint64_t > struct number { // Tipos - typedef T atomic_type; - typedef typename std::vector< T > chunk_type; + typedef N native_type; + typedef E extended_type; + enum sign_type { positive, negative }; + typedef typename std::deque< native_type > chunk_type; typedef typename chunk_type::size_type size_type; - typedef typename chunk_type::iterator iterator; - typedef typename chunk_type::const_iterator const_iterator; - typedef typename chunk_type::reverse_iterator reverse_iterator; + typedef typename chunk_type::iterator iterator; + typedef typename chunk_type::const_iterator const_iterator; + typedef typename chunk_type::reverse_iterator reverse_iterator; typedef typename chunk_type::const_reverse_iterator const_reverse_iterator; // Constructores (después de construído, el chunk siempre tiene al menos @@ -31,41 +33,39 @@ struct number // Constructor a partir de buffer (de 'átomos') y tamaño // Copia cada elemento del buffer como un 'átomo' del chunk // (el átomo menos significativo es el chunk[0] == buf[0]) - number(atomic_type* buf, size_type len, sign_type sign = positive): + number(native_type* buf, size_type len, sign_type sign = positive): chunk(buf, buf + len), sign(sign) { fix_empty(); } // Constructor a partir de un buffer (de 'átomos') terminado en 0 // FIXME (en realidad está 'roto' este contructor porque no puedo // inicializar números con un átomo == 0 en el medio) - number(atomic_type* buf, sign_type sign = positive): sign(sign) + number(native_type* buf, sign_type sign = positive): sign(sign) { while (*buf) chunk.push_back(*(buf++)); fix_empty(); } // Constructor a partir de un 'átomo' (lo asigna como único elemento del // chunk) - number(atomic_type n, sign_type sign = positive): + number(native_type n, sign_type sign = positive): chunk(1, n), sign(sign) {} // copia una vez n en el vector // TODO constructor a partir de string. // Operadores number& operator++ () { carry(0); return *this; } - number& operator+= (const number& n); - number& operator* (const number& n); - number& operator*= (const number< T >& n); - number& operator << (const size_type N); - + number& operator+= (const number& n); + number& operator*= (const number& n); + number& operator<<= (const size_type n); + // Devuelve referencia a 'átomo' i del chunk (no debería ser necesario // si la multiplicación es un método de este objeto). - atomic_type& operator[] (size_type i) { return chunk[i]; } + native_type& operator[] (size_type i) { return chunk[i]; } // Iteradores (no deberían ser necesarios) iterator begin() { return chunk.begin(); } - iterator end() { return chunk.end(); } + iterator end() { return chunk.end(); } const_iterator begin() const { return chunk.begin(); } - const_iterator end() const { return chunk.end(); } - reverse_iterator rbegin() { return chunk.rbegin(); } - reverse_iterator rend() { return chunk.rend(); } - const_reverse_iterator rbegin() const { return chunk.rbegin(); } - const_reverse_iterator rend() const { return chunk.rend(); } - + const_iterator end() const { return chunk.end(); } + reverse_iterator rbegin() { return chunk.rbegin(); } + reverse_iterator rend() { return chunk.rend(); } + const_reverse_iterator rbegin() const { return chunk.rbegin(); } + const_reverse_iterator rend() const { return chunk.rend(); } private: // Atributos @@ -73,11 +73,17 @@ struct number sign_type sign; // Helpers + // Normaliza las longitudes de 2 numbers, completando con 0s a la izquierda + // al más pequeño. Sirve para División y Conquista + number& normalize_length(const number& n); + // parte un número en dos mitades de misma longitud, devuelve un par de + // números con (low, high) + std::pair< number, number > split() const; // Pone un chunk en 0 para que sea un invariante de representación que // el chunk no sea vacío (siempre tenga la menos un elemento). - void fix_empty() { if (!chunk.size()) chunk.push_back(0); } + void fix_empty() { if (!chunk.size()) chunk.push_back(0); } // Propaga carry a partir del 'átomo' i (suma 1 al 'átomo' i propagando - // carry) + // carry) void carry(size_type i) { if (chunk.size() > i) @@ -86,17 +92,17 @@ struct number if (!chunk[i]) carry(i+1); // Overflow } else chunk.push_back(1); - } - + } + }; -template < typename T > -number< T >& number< T >::operator+= (const number< T >& n) +template < typename N, typename E > +number< N, E >& number< N, E >::operator+= (const number< N, E >& n) { - atomic_type c = 0; + native_type c = 0; size_type ini = 0; - size_type fin = std::min(chunk.size(), n.chunk.size()); - size_type i; //problema de VC++, da error de redefinición + size_type fin = std::min(chunk.size(), n.chunk.size()); + size_type i; //problema de VC++, da error de redefinición // "intersección" entre ambos chunks // +-----+-----+------+------+ @@ -144,134 +150,133 @@ number< T >& number< T >::operator+= (const number< T >& n) // más al chunk. if (c) chunk.push_back(1); // Último carry return *this; -} - -// efectúa un shifteo a izquierda del chunk, agregando 0s en los casilleros menos significativos -template < typename T > -number< T >& number< T >::operator << (size_type N) -{ - size_type i; - for (i = 0; i < N; i++) - { - chunk.push_front(0); - } - - return *this; } -template < typename T > -number< T > operator+ (const number< T >& n1, const number< T >& n2) +template < typename N, typename E > +number< N, E > operator+ (const number< N, E >& n1, const number< N, E >& n2) { - number< T > tmp = n1; + number< N, E > tmp = n1; tmp += n2; return tmp; } -template < typename T > -std::ostream& operator<< (std::ostream& os, const number< T >& n) +// efectúa un shifteo a izquierda del chunk, agregando 0s en los casilleros menos significativos +template < typename N, typename E > +number< N, E >& number< N, E >::operator<<= (size_type n) { - // FIXME sacar una salida bonita en ASCII =) - std::copy(n.rbegin(), n.rend(), std::ostream_iterator< T >(os, " ")); + size_type i; + for (i = 0; i < n; i++) + { + chunk.push_front(0); + } + return *this; +} + +template < typename N, typename E > +number< N, E > operator<< (const number< N, E >& n, typename number< N, E >::size_type m) +{ + number< N, E > tmp = n; + tmp <<= m; + return tmp; +} + +template < typename N, typename E > +std::ostream& operator<< (std::ostream& os, const number< N, E >& n) +{ + // FIXME sacar una salida bonita en ASCII =) + std::copy(n.begin(), n.end(), std::ostream_iterator< N >(os, " ")); return os; -} - -// Normaliza las longitudes de 2 numbers, completando con 0s a la izquierda -// al más pequeño. Sirve para División y Conquista -template < typename T > -void normalize_length (number< T >& l_op, number< T >& r_op) -{ - //si son de distinto tamaño tengo que agregar ceros a la izquierda al menor para división y conquista - while (l_op.chunk.size()r_op.chunk.size()) - { - r_op.chunk.push_back(0); - } - - //si no tiene cantidad par de números le agrego un atomic_type 0 a la izquierda para no tener que contemplar - //splits de chunks impares - if (l_op.chunk.size()%2 != 0) - { - l_op.chunk.push_back(0); - r_op.chunk.push_back(0); - } -} - -//parte un número en dos mitades de misma longitud -template < typename T > -void split (const number< T >&full, number< T >& upper_half, number< T >& lower_half) -{ - size_type full_size = full.chunk.size(); - size_type halves_size = full_size / 2; - size_type i = 0; - - // vacío las mitades - upper_half.chunk.clear(); - lower_half.chunk.clear(); - - // la primera mitad va al pedazo inferior - for (i = 0; i < halves_size; i++) - { - lower_half.chunk.push_back(full.chunk[i]); - } - - // la segunda mitad (si full_size es impar es 1 más que la primera mitad) va al pedazo superior - for ( ; i < full_size; i++) - { - upper_half.chunk.push_back(full.chunk[i]); - } -} - -// es el algoritmo de división y conquista, que se llama recursivamente -template < typename T > -number < T > divide_n_conquer (number< T > u, number< T > v) -{ - //tomo el chunk size de u (el de v DEBE ser el mismo) - size_type chunk_size = u.chunk.size(); - - if (chunk_size == 1) - { - //condición de corte. Ver que por más que tenga 1 único elemento puede "rebalsar" la capacidad - //del atomic_type, como ser multiplicando 0xff * 0xff usando bytes!!! - return u.chunk[0]*v.chunk[0]; - } - - number < T > u1, u2, v1, v2; - split (u, u1, u2); - split (v, v1, v2); - - // Los nombres M, D y H los puso Rosita en clase, cambiar si se les ocurren algunos mejores! - // M = u1*v1 - // D = u2*v2 - // H = (u1+v1)*(u2+v2) = u1*u2+u1*v2+u2*v1+u2*v2 - number < T > M = divide_n_conquer (u1, v1); - number < T > D = divide_n_conquer (u2, v2); - number < T > H = divide_n_conquer (u1+v1, u2+v2); - - // H-D-M = u1*u2+u1*v2+u2*v1+u2*v2 - u2*v2 - u1*v1 = u1*v2+u2*v1 - // u1*v1 << base^N + u1*v2+u2*v1 << base^N/2 + u2*v2 - return (M << chunk_size) + ((H-D-M) << chunk_size/2) + H; - -} - -template < typename T > -number< T >& number< T >::operator*= (const number< T >& n) -{ - number < T > r_op = n; - - normalize_length(*this, n); - *this = divide_n_conquer(*this, n); - - return *this; -} - -template < typename T > -number< T > operator* (const number< T >& n1, const number< T >& n2) -{ - number< T > tmp = n1; - tmp *= n2; - return tmp; -} +} + +template < typename N, typename E > +number< N, E >& number< N, E >::operator*= (const number< N, E >& n) +{ + number < N, E > r_op = n; + normalize_length(n); + n.normalize_length(*this); + *this = divide_n_conquer(*this, n); + return *this; +} + +template < typename N, typename E > +number< N, E > operator* (const number< N, E >& n1, const number< N, E >& n2) +{ + number< N, E > tmp = n1; + tmp *= n2; + return tmp; +} + +template < typename N, typename E > +number< N, E >& number< N, E >::normalize_length(const number< N, E >& n) +{ + //si son de distinto tamaño tengo que agregar ceros a la izquierda al menor para división y conquista + while (chunk.size() < n.chunk.size()) + { + chunk.push_back(0); + } + + //si no tiene cantidad par de números le agrego un atomic_type 0 a la izquierda para no tener que contemplar + //splits de chunks impares + if ((chunk.size() % 2) != 0) + { + chunk.push_back(0); + } +} + +template < typename N, typename E > +std::pair< number< N, E >, number< N, E > > number< N, E >::split() const +{ + typedef number< N, E > num_type; + typename num_type::size_type full_size = chunk.size(); + typename num_type::size_type halves_size = full_size / 2; + typename num_type::size_type i = 0; + + // vacío las mitades + std::pair< num_type, num_type > par; + + // la primera mitad va al pedazo inferior + for (i = 0; i < halves_size; i++) + { + par.first.chunk.push_back(chunk[i]); + } + + // la segunda mitad (si full_size es impar es 1 más que la primera mitad) va al pedazo superior + for ( ; i < full_size; i++) + { + par.second.chunk.push_back(chunk[i]); + } + return par; +} + +// es el algoritmo de división y conquista, que se llama recursivamente +template < typename N, typename E > +number < N, E > divide_n_conquer(number< N, E > u, number< N, E > v) +{ + typedef number< N, E > num_type; + //tomo el chunk size de u (el de v DEBE ser el mismo) + typename num_type::size_type chunk_size = u.chunk.size(); + + if (chunk_size == 1) + { + //condición de corte. Ver que por más que tenga 1 único elemento puede "rebalsar" la capacidad + //del atomic_type, como ser multiplicando 0xff * 0xff usando bytes!!! + return u.chunk[0] * v.chunk[0]; + } + + std::pair< num_type, num_type > u12 = u.split(); + std::pair< num_type, num_type > v12 = v.split(); + + // Los nombres M, D y H los puso Rosita en clase, cambiar si se les ocurren algunos mejores! + // m = u1*v1 + // d = u2*v2 + // h = (u1+v1)*(u2+v2) = u1*u2+u1*v2+u2*v1+u2*v2 + num_type m = divide_n_conquer(u12.first, v12.first); + num_type d = divide_n_conquer(u12.second, v12.second); + num_type h = divide_n_conquer(u12.first + v12.first, u12.second + v12.second); + + // H-D-M = u1*u2+u1*v2+u2*v1+u2*v2 - u2*v2 - u1*v1 = u1*v2+u2*v1 + // u1*v1 << base^N + u1*v2+u2*v1 << base^N/2 + u2*v2 + return (m << chunk_size) + ((h - d - m) << chunk_size / 2) + h; + +} + -- 2.43.0