X-Git-Url: https://git.llucax.com/z.facultad/75.29/dale.git/blobdiff_plain/adeca343a1a55fe3992722577268cf0aec4a5b65..4dc84da8d6147088b21c96cec142b38f11618e0d:/src/number.h?ds=inline diff --git a/src/number.h b/src/number.h index 4b77f22..e7e9c7b 100644 --- a/src/number.h +++ b/src/number.h @@ -7,12 +7,27 @@ #include #include #include -#include +#include + +#ifdef _WIN32 +// VC++ no tiene la stdint.h, se agrega a mano +#include "stdint.h" +#else #include +#endif + +enum sign_type { positive, negative }; + /* sizeof(E) tiene que ser 2*sizeof(N); y son los tipos nativos con los cuales * se haran las operaciones mas basicas. */ +template < typename N, typename E > +struct number; + +template < typename N, typename E > +std::ostream& operator<< (std::ostream& os, const number< N, E >& n); + template < typename N = uint32_t, typename E = uint64_t > struct number { @@ -20,7 +35,6 @@ struct number // Tipos 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; @@ -47,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++ () @@ -59,10 +73,13 @@ struct number number& operator+= (const number& 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 // si la multiplicación es un método de este objeto). - native_type& operator[] (size_type i) { + native_type& operator[] (size_type i) + { return chunk[i]; } @@ -76,15 +93,16 @@ struct number const_reverse_iterator rbegin() const { return chunk.rbegin(); } const_reverse_iterator rend() const { return chunk.rend(); } - private: + // Friends + template < typename NN, typename EE > + friend std::ostream& operator<< (std::ostream& os, const number< NN, EE>& n); + // Atributos + //private: chunk_type chunk; 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; @@ -107,6 +125,33 @@ struct number }; +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 > number< N, E >& number< N, E >::operator+= (const number< N, E >& n) { @@ -182,6 +227,52 @@ number< N, E > operator+ (const number< N, E >& n1, const number< N, E >& n2) return tmp; } +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 + 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 > number< N, E >& number< N, E >::operator<<= (size_type n) @@ -206,44 +297,27 @@ 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, " ")); + for (typename number< N, E >::const_iterator i = n.chunk.begin(); + i != n.chunk.end(); ++i) + os << std::setfill('0') << std::setw(sizeof(N) * 2) << std::hex + << *i << " "; return os; } 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); + //number < N, E > r_op = n; + //normalize_length(n); + //n.normalize_length(*this); + *this = naif(*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); - } + return naif(n1, n2); } template < typename N, typename E > @@ -258,35 +332,159 @@ std::pair< number< N, E >, number< N, E > > number< N, E >::split() const std::pair< num_type, num_type > par; // la primera mitad va al pedazo inferior - for (i = 0; i < halves_size; i++) + par.first.chunk[0] = chunk[0]; + for (i = 1; 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[0] = chunk[i]; + for (i++ ; 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 > +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; + + max = std::max(u.chunk.size(), v.chunk.size()); + + /* 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++; + } + + /* Ahora guardamos en pot2 el tamaño que deben tener. */ + pot2 = 1 << p; + + /* Y finalmente hacemos crecer los dos numeros agregando 0s hasta + * completar sus tamaños. */ + while (u.chunk.size() < pot2) + u.chunk.push_back(0); + + while (v.chunk.size() < pot2) + v.chunk.push_back(0); + + return; +} + + +/* Algoritmo "naif" (por no decir "cabeza" o "bruto") de multiplicacion. */ template < typename N, typename E > -number < N, E > karatsuba(number< N, E > u, number< N, E > v) +number < N, E > naif(const number< N, E > &u, const 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(); + sign_type sign; + + if ( (u.sign == positive && v.sign == positive) || + (u.sign == negative && v.sign == negative) ) { + sign = positive; + } else { + sign = negative; + } + + //printf("naif %d %d\n", 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]; + /* Si llegamos a multiplicar dos de tamaño 1, lo que hacemos + * es usar la multiplicacion nativa del tipo N, guardando el + * resultado en el tipo E (que sabemos es del doble de tamaño + * de N, ni mas ni menos). + * Luego, armamos un objeto number usando al resultado como + * buffer. Si, es feo. + */ + E tmp; + tmp = static_cast< E >(u.chunk[0]) * static_cast< E >(v.chunk[0]); + num_type tnum = num_type(reinterpret_cast< N* >(&tmp), 2, sign); + //std::cout << "T:" << tnum << " " << tmp << "\n"; + //printf("1: %lu %lu %llu\n", u.chunk[0], v.chunk[0], tmp); + return tnum; + } + + std::pair< num_type, num_type > u12 = u.split(); + std::pair< num_type, num_type > v12 = v.split(); + + //std::cout << "u:" << u12.first << " - " << u12.second << "\n"; + //std::cout << "v:" << v12.first << " - " << v12.second << "\n"; + + /* m11 = u1*v1 + * m12 = u1*v2 + * m21 = u2*v1 + * m22 = u2*v2 + */ + num_type m11 = naif(u12.first, v12.first); + num_type m12 = naif(u12.first, v12.second); + num_type m21 = naif(u12.second, v12.first); + num_type m22 = naif(u12.second, v12.second); + + /* + printf("csize: %d\n", chunk_size); + std::cout << "11 " << m11 << "\n"; + std::cout << "12 " << m12 << "\n"; + std::cout << "21 " << m21 << "\n"; + std::cout << "22 " << m22 << "\n"; + */ + + /* 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; + res = res + ((m12 + m21) << (chunk_size / 2)); + res = res + m11; + res.sign = sign; + /* + std::cout << "r: " << res << "\n"; + std::cout << "\n"; + */ + return res; +} + + +/* 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(); @@ -297,14 +495,35 @@ number < N, E > karatsuba(number< N, E > u, number< N, E > v) // 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); + 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 - return (m << chunk_size) + ((h - d - m) << chunk_size / 2) + h; + 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; }