X-Git-Url: https://git.llucax.com/z.facultad/75.29/dale.git/blobdiff_plain/5e6b85a00fe62bb0a04c91d4312c34af74ebafd8..4dc84da8d6147088b21c96cec142b38f11618e0d:/src/number.h diff --git a/src/number.h b/src/number.h index d4593bc..e7e9c7b 100644 --- a/src/number.h +++ b/src/number.h @@ -7,13 +7,13 @@ #include #include #include -#include - -#ifdef _WIN32 +#include + +#ifdef _WIN32 // VC++ no tiene la stdint.h, se agrega a mano -#include "stdint.h" -#else -#include +#include "stdint.h" +#else +#include #endif enum sign_type { positive, negative }; @@ -61,7 +61,7 @@ struct number number(native_type n, sign_type sign = positive): chunk(1, n), sign(sign) {} - // TODO constructor a partir de string. + number(const std::string& str); // Operadores number& operator++ () @@ -72,8 +72,8 @@ struct number number& operator+= (const number& n); number& operator*= (const number& n); - number& operator<<= (const size_type n); - number& operator-= (const number& n); + number& operator<<= (const size_type n); + number& operator-= (const number& n); bool operator< (const number& n); // Devuelve referencia a 'átomo' i del chunk (no debería ser necesario @@ -103,9 +103,6 @@ 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; @@ -126,33 +123,33 @@ struct number chunk.push_back(1); } -}; - -template < typename N, typename E > -number< N, E >::number(const std::string& str) -{ - const N MAX_N = (~( (N)0 ) ); - E increment = 0; - E acum = 0; - - unsigned length = origen.length(); - unsigned number_offset = 0; - - while (number_offset MAX_N) - { - chunk.push_back(acum); - } - - } - - +}; + +template < typename N, typename E > +number< N, E >::number(const std::string& origen) +{ + const N MAX_N = (~( (N)0 ) ); + E increment = 0; + E acum = 0; + + unsigned length = origen.length(); + unsigned number_offset = 0; + + while (number_offset MAX_N) + { + chunk.push_back(acum); + } + + } + + } template < typename N, typename E > @@ -228,54 +225,53 @@ 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 >::operator-= (const number< N, E >& n) -{ - //TODO IMPLEMENTAR +} + +template < typename N, typename E > +number< N, E >& number< N, E >::operator-= (const number< N, E >& n) +{ + //TODO IMPLEMENTAR 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 > -bool number< N, E >::operator< (const number< N, E >& n) -{ - number< N, E > n1 = *this; - number< N, E > n2 = n; - - // igualo los largos - n1.normalize_length(n2); - n2.normalize_length(n1); - - // obtengo el largo - size_type length = n1.chunk.size(); - size_type i = length - 1; - - // me voy fijando desde "la cifra" más significativa si alguno es menor que el otro - // sigo iterando si son iguales hasta recorrer todo el número hasta la parte menos significativa - while (i > 0) - { - if (n1[i]n2[i]) - return false; - - i--; - } - - // si llegué hasta acá es porque son iguales, por lo tanto no es menor estricto - return false; - -} +} + +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 > +bool number< N, E >::operator< (const number< N, E >& n) +{ + number< N, E > n1 = *this; + number< N, E > n2 = n; + + // igualo los largos + normalize_length(n1, n2); + + // obtengo el largo + size_type length = n1.chunk.size(); + size_type i = length - 1; + + // me voy fijando desde "la cifra" más significativa si alguno es menor que el otro + // sigo iterando si son iguales hasta recorrer todo el número hasta la parte menos significativa + while (i > 0) + { + if (n1[i]n2[i]) + return false; + + i--; + } + + // si llegué hasta acá es porque son iguales, por lo tanto no es menor estricto + return false; + +} // efectúa un shifteo a izquierda del chunk, agregando 0s en los casilleros menos significativos template < typename N, typename E > @@ -324,20 +320,6 @@ number< N, E > operator* (const number< N, E >& n1, const number< N, E >& n2) return naif(n1, n2); } -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); - } - - return *this; - -} - template < typename N, typename E > std::pair< number< N, E >, number< N, E > > number< N, E >::split() const { @@ -366,40 +348,36 @@ std::pair< number< N, E >, number< N, E > > number< N, E >::split() const return par; } -// es el algoritmo de división y conquista, que se llama recursivamente + template < typename N, typename E > -number < N, E > karatsuba(const number< N, E > &u, const number< N, E > &v) +void normalize_length(number< N, E >& u, number< N, E >& v) { typedef number< N, E > num_type; + typename num_type::size_type max, p, t, pot2; - // tomo el chunk size de u (el de v DEBE ser el mismo) - typename num_type::size_type chunk_size = u.chunk.size(); + max = std::max(u.chunk.size(), v.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]; + /* Buscamos hacer crecer a ambos a la potencia de 2 mas proxima; para + * lo cual la obtenemos y guardamos en p. */ + t = max; + p = 0; + while (t != 0) { + t = t >> 1; + p++; } - std::pair< num_type, num_type > u12 = u.split(); - std::pair< num_type, num_type > v12 = v.split(); + /* Ahora guardamos en pot2 el tamaño que deben tener. */ + pot2 = 1 << p; - // 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 = karastuba(u12.first, v12.first); - num_type d = karastuba(u12.second, v12.second); - num_type h = karastuba(u12.first + v12.first, - u12.second + v12.second); + /* Y finalmente hacemos crecer los dos numeros agregando 0s hasta + * completar sus tamaños. */ + while (u.chunk.size() < pot2) + u.chunk.push_back(0); - // 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; + while (v.chunk.size() < pot2) + v.chunk.push_back(0); + return; } @@ -467,6 +445,7 @@ number < N, E > naif(const number< N, E > &u, const number< N, E > &v) /* u*v = (u1*v1) * 2^n + (u1*v2 + u2*v1) * 2^(n/2) + u2*v2 * PERO! Como los numeros estan "al reves" nos queda: * = m22 * 2^n + (m12 + m21) * 2^(n/2) + m11 + * FIXME: seria mejor hacer el acomode en la llamada a naif arriba? */ num_type res; res = m22 << chunk_size; @@ -481,4 +460,70 @@ number < N, E > naif(const number< N, E > &u, const number< N, E > &v) } +/* Algoritmo de multiplicacion de Karatsuba-Ofman + * Ver los comentarios del algoritmo naif, es practicamente identico salvo en + * los calculos numericos que se especifican debajo. + */ +template < typename N, typename E > +number < N, E > karatsuba(const number< N, E > &u, const number< N, E > &v) +{ + typedef number< N, E > num_type; + + typename num_type::size_type chunk_size = u.chunk.size(); + + sign_type sign; + + if ( (u.sign == positive && v.sign == positive) || + (u.sign == negative && v.sign == negative) ) { + sign = positive; + } else { + sign = negative; + } + + if (chunk_size == 1) { + E tmp; + tmp = static_cast< E >(u.chunk[0]) * static_cast< E >(v.chunk[0]); + num_type tnum = num_type(static_cast< N* >(&tmp), 2, sign); + return tnum; + } + + 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 = karastuba(u12.second, v12.second); + num_type d = karastuba(u12.first, v12.first); + num_type h = karastuba(u12.second + v12.second, + u12.first + v12.first); + + // 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 + num_type res; + res = (m << chunk_size) + ((h - d - m) << (chunk_size / 2) ) + h; + res.sign = sign; + return res; +} + + +/* Potenciacion usando multiplicaciones sucesivas. + * Toma dos parametros u y v, devuelve u^v; asume v positivo. + */ +template < typename N, typename E > +number < N, E > pot_ko(const number< N, E > &u, const number< N, E > &v) +{ + number< N, E > res, i; + + res = u; + res.sign = u.sign; + + for (i = 1; i < v; i += 1) { + res *= u; + } + + return res; +}