Limpiar salida de debugging.

[z.facultad/75.29/dale.git] / src / number.h

diff --git a/src/number.h b/src/number.h
index 92862552feca655e29830de64163afb62b14a5e1..2b4b78f5d1ead45a1c2b3325dffa6d4c2823fca4 100644 (file)
--- a/src/number.h
+++ b/src/number.h
@@ -128,13 +128,13 @@ struct number
                else
                        chunk.push_back(1);
        }
                else
                        chunk.push_back(1);
        }

-       // Propaga borrow a partir del 'átomo' i (resta 1 al 'átomo' i propagando
-       // borrow)
+       // Propaga borrow a partir del 'átomo' i (resta 1 al 'átomo' i
+       // propagando borrow)

        void borrow(size_type i)
        {
                // para poder pedir prestado debo tener uno a la izquierda
                assert (chunk.size() >= i);
        void borrow(size_type i)
        {
                // para poder pedir prestado debo tener uno a la izquierda
                assert (chunk.size() >= i);

-               
+

                if (chunk[i] == 0)
                {
                        borrow(i+1); // Overflow, pido prestado
                if (chunk[i] == 0)
                {
                        borrow(i+1); // Overflow, pido prestado


@@ -317,9 +317,9 @@ number< N, E >& number< N, E >::operator-= (const number< N, E >& n)
        size_type fin = std::min(minuend.chunk.size(), subtrahend.chunk.size());
        size_type i; //problema de VC++, da error de redefinición
 
        size_type fin = std::min(minuend.chunk.size(), subtrahend.chunk.size());
        size_type i; //problema de VC++, da error de redefinición
 

-       //estoy seguro de que minuend > subtrahend, con lo cual itero hasta el size del
-       //menor de los dos. Si el otro es más grande, puede ser que esté lleno de 0's pero
-       //no puede ser realmente mayor como cifra
+       //estoy seguro de que minuend > subtrahend, con lo cual itero hasta el
+       //size del menor de los dos. Si el otro es más grande, puede ser que
+       //esté lleno de 0's pero no puede ser realmente mayor como cifra

        for (i = ini; i < fin; ++i)
        {
                // si no alcanza para restar pido prestado
        for (i = ini; i < fin; ++i)
        {
                // si no alcanza para restar pido prestado


@@ -331,11 +331,11 @@ number< N, E >& number< N, E >::operator-= (const number< N, E >& n)
                        // le pido uno al que me sigue
                        minuend.borrow(i+1);
                }
                        // le pido uno al que me sigue
                        minuend.borrow(i+1);
                }

-               
-               // es como hacer 24-5: el 4 pide prestado al 2 (borrow(i+1)) y después
-               // se hace 4 + (9-5) + 1

 
 

-               minuend.chunk[i] += (~((N)0) - subtrahend.chunk[i]) + 1; 
+               // es como hacer 24-5: el 4 pide prestado al 2 (borrow(i+1)) y
+               // después se hace 4 + (9-5) + 1
+
+               minuend.chunk[i] += (~((N)0) - subtrahend.chunk[i]) + 1;

        }
 
        //retorno el minuendo ya restado
        }
 
        //retorno el minuendo ya restado


@@ -407,7 +407,8 @@ bool number< N, E >::operator< (const number< N, E >& n) const
        return false; // Son iguales
 }
 
        return false; // Son iguales
 }
 

-// efectúa un shifteo a izquierda del chunk, agregando 0s en los casilleros menos significativos
+// 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)
 {
 template < typename N, typename E >
 number< N, E >& number< N, E >::operator<<= (size_type n)
 {


@@ -486,7 +487,9 @@ bool number< N, E >::operator==(const number< N, E >& n) const
                chunk_grande = &n.chunk;
                fin = n.chunk.size() - chunk.size();
        }
                chunk_grande = &n.chunk;
                fin = n.chunk.size() - chunk.size();
        }

-       if (chunk_grande) // Si tienen tamaños distintos, vemos que el resto sea cero.
+
+       // Si tienen tamaños distintos, vemos que el resto sea cero.
+       if (chunk_grande)

        {
                for (; i < fin; ++i) // Sigo desde el i que había quedado
                {
        {
                for (; i < fin; ++i) // Sigo desde el i que había quedado
                {


@@ -541,35 +544,41 @@ std::pair< number< N, E >, number< N, E > > number< N, E >::split() const
 }
 
 
 }
 
 

+// Lleva los tamaños de chunk a la potencia de 2 más cercana, eliminando o
+// agregando ceros.

 template < typename N, typename E >
 void normalize_length(const number< N, E >& u, const number< N, E >& v)
 {
 template < typename N, typename E >
 void normalize_length(const number< N, E >& u, const number< N, E >& v)
 {

-       typedef number< N, E > num_type;
-       typename num_type::size_type max, p, t, pot2;
+       typename number< N, E >::size_type max, p, t, pot2, size_u, size_v;

 
 

-       max = std::max(u.chunk.size(), v.chunk.size());
+       // Busco el primer chunk no nulo de u
+       for (size_u = u.chunk.size() - 1; size_u != 0; --size_u)
+               if (u.chunk[size_u] != 0)
+                       break;
+       size_u++;
+
+       // Busco el primer chunk no nulo de v
+       for (size_v = v.chunk.size() - 1; size_v != 0; --size_v)
+               if (v.chunk[size_v] != 0)
+                       break;
+       size_v++;
+
+       max = std::max(size_u, size_v);

 
        /* 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;
 
        /* 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;
+       while ((1u << p) < max)

                p++;
                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. */
 
        /* 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;
+       u.chunk.resize(pot2, 0);
+       v.chunk.resize(pot2, 0);

 }
 
 
 }
 
 


@@ -592,8 +601,6 @@ number < N, E > naif(const number< N, E > &u, const number< N, E > &v)
                sign = negative;
        }
 
                sign = negative;
        }
 

-       //printf("naif %d %d\n", u.chunk.size(), v.chunk.size() );
-

        if (chunk_size == 1)
        {
                /* Si llegamos a multiplicar dos de tamaño 1, lo que hacemos
        if (chunk_size == 1)
        {
                /* Si llegamos a multiplicar dos de tamaño 1, lo que hacemos


@@ -606,17 +613,12 @@ number < N, E > naif(const number< N, E > &u, const number< N, E > &v)
                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);
                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();
 
                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
        /* m11 = u1*v1
         * m12 = u1*v2
         * m21 = u2*v1


@@ -627,33 +629,15 @@ number < N, E > naif(const number< N, E > &u, const number< N, E > &v)
        num_type m21 = naif(u12.second, v12.first);
        num_type m22 = naif(u12.second, 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
         */
        num_type res;
        res = m22 << chunk_size;
        /* 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
         */
        num_type res;
        res = m22 << chunk_size;

-       //std::cout << "ra: " << res << "\n";

        res = res + ((m12 + m21) << (chunk_size / 2));
        res = res + ((m12 + m21) << (chunk_size / 2));

-       /*
-       std::cout << "rb: " << res << "\n";
-       std::cout << "12+21: " << (m12 + m21) << "\n";
-       std::cout << "cs/2: " << (chunk_size / 2) << "\n";
-       std::cout << "t: " << ((m12 + m21) << (chunk_size / 2)) << "\n";
-       */

        res = res + m11;
        res = res + m11;

-       //std::cout << "rc: " << res << "\n";

        res.sign = sign;
        res.sign = sign;

-       //std::cout << "r: " << res << "\n";
-       //std::cout << "\n";

        return res;
 }
 
        return res;
 }
 


@@ -689,11 +673,6 @@ number < N, E > karatsuba(const number< N, E > &u, const number< N, E > &v)
        std::pair< num_type, num_type > u12 = u.split();
        std::pair< num_type, num_type > v12 = v.split();
 
        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";
-       */
-

        /* Aca esta la gracia de toda la cuestion:
         * m = u1*v1
         * d = u2*v2
        /* Aca esta la gracia de toda la cuestion:
         * m = u1*v1
         * d = u2*v2


@@ -710,26 +689,13 @@ number < N, E > karatsuba(const number< N, E > &u, const number< N, E > &v)
        num_type sumsnd = v12.first + v12.second;
        num_type h = karatsuba(sumfst, sumsnd);
 
        num_type sumsnd = v12.first + v12.second;
        num_type h = karatsuba(sumfst, sumsnd);
 

-       /*
-       fflush(stdout); fflush(stderr);
-       std::cout << "m: " << m << "\n";
-       std::cout << "d: " << d << "\n";
-       std::cout << "h: " << h << "\n";
-       fflush(stdout); fflush(stderr);
-       */
-

        num_type res, tmp;
 
        /* tmp = h - d - m */
        normalize_length(h, d);
        tmp = h - d;
        normalize_length(tmp, m);
        num_type res, tmp;
 
        /* tmp = h - d - m */
        normalize_length(h, d);
        tmp = h - d;
        normalize_length(tmp, m);

-       /*
-       std::cout << "t: " << tmp << "\n";
-       std::cout << "m: " << m << "\n";
-       */

        tmp = tmp - m;
        tmp = tmp - m;

-       //std::cout << "t: " << tmp << "\n";

 
        /* Resultado final */
        res = d << chunk_size;
 
        /* Resultado final */
        res = d << chunk_size;


@@ -795,24 +761,16 @@ template < typename N, typename E >
 number< N, E > pot_dyc_n(const number< N, E > &x, const number< N, E > &y)
 {
        assert(y.sign == positive);
 number< N, E > pot_dyc_n(const number< N, E > &x, const number< N, E > &y)
 {
        assert(y.sign == positive);

-       //std::cout << "pot(" << x << ", " << y << ")\n";

        if (y == number< N, E >(1))
        {
        if (y == number< N, E >(1))
        {

-               std::cout << "y es 1 => FIN pot(" << x << ", " << y << ")\n";

                return x;
        }
        number< N, E > res = pot_dyc_n(x, y.dividido_dos());
                return x;
        }
        number< N, E > res = pot_dyc_n(x, y.dividido_dos());

-       //std::cout << "y.dividido_dos() = " << y.dividido_dos() << "\n";
-       //std::cout << "res = " << res << "\n";

        res = naif(res, res);
        res = naif(res, res);

-       //std::cout << "res = " << res << "\n";

        if (y.es_impar())
        {
        if (y.es_impar())
        {

-               //std::cout << y << " es IMPAR => ";

                res = naif(res, x); // Multiplico por el x que falta
                res = naif(res, x); // Multiplico por el x que falta

-               //std::cout << "res = " << res << "\n";

        }
        }

-       //std::cout << "FIN pot(" << x << ", " << y << ")\n\n";

        return res;
 }
 
        return res;
 }
 


@@ -821,24 +779,16 @@ template < typename N, typename E >
 number< N, E > pot_dyc_k(const number< N, E > &x, const number< N, E > &y)
 {
        assert(y.sign == positive);
 number< N, E > pot_dyc_k(const number< N, E > &x, const number< N, E > &y)
 {
        assert(y.sign == positive);

-       //std::cout << "pot(" << x << ", " << y << ")\n";

        if (y == number< N, E >(1))
        {
        if (y == number< N, E >(1))
        {

-               //std::cout << "y es 1 => FIN pot(" << x << ", " << y << ")\n";

                return x;
        }
        number< N, E > res = pot_dyc_k(x, y.dividido_dos());
                return x;
        }
        number< N, E > res = pot_dyc_k(x, y.dividido_dos());

-       //std::cout << "y.dividido_dos() = " << y.dividido_dos() << "\n";
-       //std::cout << "res = " << res << "\n";

        res = karatsuba(res, res);
        res = karatsuba(res, res);

-       //std::cout << "res = " << res << "\n";

        if (y.es_impar())
        {
        if (y.es_impar())
        {

-               //std::cout << y << " es IMPAR => ";

                res = karatsuba(res, x);
                res = karatsuba(res, x);

-               //std::cout << "res = " << res << "\n";

        }
        }

-       //std::cout << "FIN pot(" << x << ", " << y << ")\n\n";

        return res;
 }
 
        return res;
 }