Acomodar el split().

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

diff --git a/src/number.h b/src/number.h
index 3a42d7ee552f23735a0b021c4f7ad447a78a1085..28e853e3f244edc2372e7c4222caa26cd066d263 100644 (file)
--- a/src/number.h
+++ b/src/number.h
@@ -7,12 +7,18 @@
 #include <deque>
 #include <utility>
 #include <algorithm>
-#include <iterator>
+#include <iomanip>
 #include <stdint.h>
 
 /* 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
 {
@@ -76,6 +82,10 @@ struct number
        const_reverse_iterator rbegin() const { return chunk.rbegin(); }
        const_reverse_iterator rend() const { return chunk.rend(); }
 
+       // Friends
+       template < typename NN, typename EE >
+       friend std::ostream& operator<< (std::ostream& os, const number< NN, EE>& n);
+
        private:
        // Atributos
        chunk_type chunk;
@@ -206,7 +216,10 @@ 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;
 }
 
@@ -258,14 +271,16 @@ 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]);
        }
@@ -274,7 +289,7 @@ std::pair< number< N, E >, number< N, E > > number< N, E >::split() const
 
 // 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)
+number < N, E > karatsuba(number< N, E > u, number< N, E > v)
 {
        typedef number< N, E > num_type;
 
@@ -297,9 +312,9 @@ number < N, E > divide_n_conquer(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 = 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,
+       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);
 
        // H-D-M = u1*u2+u1*v2+u2*v1+u2*v2 - u2*v2 - u1*v1 = u1*v2+u2*v1