Merge con parche anterior.

diff --git a/src/number.h b/src/number.h
index 23e847f01c87b2dc96af31f56a99f8e96ea424ee..a079e8f45dfc58dd7a04928e242100c1e65dbd01 100644 (file)
--- a/src/number.h
+++ b/src/number.h
@@ -4,10 +4,15 @@
 #define max _cpp_max
 #endif
 
+#ifdef DEBUG
+#include <iostream>
+#endif
+
 #include <deque>
 #include <utility>
 #include <algorithm>
 #include <iomanip>
+#include <cassert>
 
 #ifdef _WIN32
 // VC++ no tiene la stdint.h, se agrega a mano
@@ -75,6 +80,7 @@ struct number
        number& operator<<= (const size_type n);
        number& operator-= (const number& n);
        bool    operator< (const number& n);
+       bool operator==(const number& n) const;
 
        // Devuelve referencia a 'átomo' i del chunk (no debería ser necesario
        // si la multiplicación es un método de este objeto).
@@ -140,6 +146,30 @@ struct number
                }
                //else ERROR, están haciendo a-b con a>b
        }
+       // Verifica si es un número par
+       bool es_impar() const
+       {
+               return chunk[0] & 1; // Bit menos significativo
+       }
+       // Divide por 2.
+       number dividido_dos() const
+       {
+               number n = *this;
+               bool lsb = 0; // bit menos significativo
+               bool msb = 0; // bit más significativo
+               for (typename chunk_type::reverse_iterator i = n.chunk.rbegin();
+                               i != n.chunk.rend(); ++i)
+               {
+                       lsb = *i & 1; // bit menos significativo
+                       *i >>= 1;     // shift
+                       // seteo bit más significativo de ser necesario
+                       if (msb)
+                               *i |= 1 << (sizeof(native_type) * 8 - 1);
+                       msb = lsb;
+               }
+               return n;
+       }
+
 };
 
 template < typename N, typename E >
@@ -366,6 +396,62 @@ std::ostream& operator<< (std::ostream& os, const number< N, E >& n)
        return os;
 }
 
+template < typename N, typename E >
+bool number< N, E >::operator==(const number< N, E >& n) const
+{
+       if (sign != n.sign)
+       {
+               return false;
+       }
+
+       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
+
+       // "intersección" entre ambos chunks
+       // +-----+-----+------+------+
+       // |     |     |      |      | <--- mio
+       // +-----+-----+------+------+
+       // +-----+-----+------+
+       // |     |     |      |        <--- chunk de n
+       // +-----+-----+------+
+       //
+       // |------------------|
+       // Esto se procesa en este for
+       for (i = ini; i < fin; ++i)
+       {
+               if (chunk[i] != n.chunk[i])
+               {
+                       return false;
+               }
+       }
+
+       // si mi chunk es más grande que el del otro, sólo me queda
+       // ver si el resto es cero.
+       chunk_type const *chunk_grande = 0;
+       if (chunk.size() > n.chunk.size())
+       {
+               chunk_grande = &chunk;
+               fin = chunk.size() - n.chunk.size();
+       }
+       else if (chunk.size() < n.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.
+       {
+               for (; i < fin; ++i) // Sigo desde el i que había quedado
+               {
+                       if ((*chunk_grande)[i] != 0)
+                       {
+                               return false;
+                       }
+               }
+       }
+       return true; // Son iguales
+}
+
 template < typename N, typename E >
 number< N, E >& number< N, E >::operator*= (const number< N, E >& n)
 {
@@ -577,6 +663,7 @@ number < N, E > karatsuba(const number< N, E > &u, const number< N, E > &v)
 template < typename N, typename E >
 number < N, E > pot_ko(const number< N, E > &u, const number< N, E > &v)
 {
+       assert(v.sign == positive);
        number< N, E > res, i;
 
        res = u;
@@ -589,3 +676,59 @@ number < N, E > pot_ko(const number< N, E > &u, const number< N, E > &v)
        return res;
 }
 
+/* Potenciacion usando división y conquista.
+ * Toma dos parametros u y v, devuelve u^v; asume v positivo.
+ *
+ * El pseudocódigo del algoritmo es:
+ * pot(x, y):
+ *     if y == 1:
+ *             return x
+ *     res = pot(x, y/2)
+ *     res = res * res
+ *     if y es impar:
+ *             res = res * x
+ *     return res
+ *
+ * Es O(n) ya que la ecuación es T(n) = T(n/2) + O(1)
+ *
+ * El grafo que lo 'representa' (siendo los nodos el exponente y) algo como:
+ *
+ *                      1 3
+ *                   _/  |  \_
+ *                 _/    |    \_
+ *                /      |      \
+ *               6       1       6
+ *             /   \           /   \
+ *            /     \         /     \
+ *           3       3       3       3
+ *          /|\     /|\     /|\     /|\
+ *         2 1 2   2 1 2   2 1 2   2 1 2
+ *        / \ / \ / \ / \ / \ / \ / \ / \
+ *        1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
+ *
+ */
+template < typename N, typename E >
+number< N, E > pot_dyc(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))
+       {
+               std::cout << "y es 1 => FIN pot(" << x << ", " << y << ")\n";
+               return x;
+       }
+       number< N, E > res = pot_dyc(x, y.dividido_dos());
+       //std::cout << "y.dividido_dos() = " << y.dividido_dos() << "\n";
+       //std::cout << "res = " << res << "\n";
+       res *= res;
+       //std::cout << "res = " << res << "\n";
+       if (y.es_impar())
+       {
+               //std::cout << y << " es IMPAR => ";
+               res *= x; // Multiplico por el x que falta
+               //std::cout << "res = " << res << "\n";
+       }
+       //std::cout << "FIN pot(" << x << ", " << y << ")\n\n";
+       return res;
+}
+

diff --git a/tests/number.cpp b/tests/number.cpp
index f971b4809fea713fb0fec9ff7bdcc6c4781f57c7..fc74c5501d832ac03fe3877850cac78f86c6eae2 100644 (file)
--- a/tests/number.cpp
+++ b/tests/number.cpp
@@ -13,6 +13,7 @@ int main()
        std::cout << "nu2 = "  << nu2 << "\n\n";
        std::cout << "nu + nu2 = "  << nu + nu2 << "\n\n";
        std::cout << "nu * nu2 = "  << nu * nu2 << "\n\n";
+       std::cout << "nu^nu2 = "  << potencia(nu, nu2) << "\n\n";
 #endif
 
 #if 0
@@ -21,8 +22,7 @@ int main()
 
        nu << 5;
        std::cout << "nu = " << nu << "\n\n";
-#endif
-\r
+
        number<> n1 = 0x00000000;
        number<> n2 = 0x00000000;
 
@@ -34,26 +34,33 @@ int main()
        if (n1 < n2)
                std::cout << "n1 es menor que n2\n";
        else if (n2 < n1)
-               std::cout << "n1 es mayor que n2\n";\r
+               std::cout << "n1 es mayor que n2\n";
        else 
-               std::cout << "n1 es igual que n2\n";\r
-\r
+               std::cout << "n1 es igual que n2\n";
+
        std::cout << "\n";
-       \r
-\r
-//     for (int j=0; j<10; j++)\r
-//             n1.borrow(0);\r
-\r
-       std::cout << "n1: " << n1 ;\r
-       std::cout << "\n";\r
-       std::cout << "n2: " << n2 ;\r
-       std::cout << "\n";\r
-\r
-       n1 -= n2;\r
-\r
-       std::cout << "n1-n2: " << n1 ;\r
+       
 
-       return 0;
+//     for (int j=0; j<10; j++)
+//             n1.borrow(0);
+
+       std::cout << "n1: " << n1 ;
+       std::cout << "\n";
+       std::cout << "n2: " << n2 ;
+       std::cout << "\n";
 
+       n1 -= n2;
+
+       std::cout << "n1-n2: " << n1 ;
+#endif
+
+       uint32_t buf[] = { 0x00000040, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000 };
+       number<> nu(buf, 8);
+       number<> nu2 = 0x2;
+       std::cout << "nu = " << nu << "\n\n";
+       std::cout << "nu2 = " << nu2 << "\n\n";
+       std::cout << "nu * nu2 = "  << naif(nu, nu2) << "\n\n";
+
+       return 0;
 }