#include <utility>
#include <algorithm>
#include <iomanip>
+#include <string>
+#include <sstream>
#include <cassert>
#ifdef _WIN32
number(native_type n, sign_type s = positive):
chunk(1, n), sign(s) {}
- number(const std::string& str);
+ number(std::string str);
// Operadores
number& operator++ ()
number& operator*= (const number& n);
number& operator<<= (const size_type n);
number& operator-= (const number& n);
- bool operator< (const number& n) const;
bool operator== (const number& n) const;
+ bool operator< (const number& n) const;
+
+ // Compara si es menor en módulo.
+ bool menorEnModuloQue(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).
};
-template < typename N, typename E >
-number< N, E >::number(const std::string& origen)
+inline unsigned ascii2uint(char c)
{
- const N MAX_N = (~( (N)0 ) );
- E increment = 0;
- E acum = 0;
-
- unsigned length = origen.length();
- unsigned number_offset = 0;
+ return c & 0xF;
+}
- while (number_offset<length)
+// Convierte pasando el string a forma polinómica y evalúa el polinómio
+// utilizando la regla de Horner:
+// Polinomio: str[0] * 10^0 ... str[size-1] * 10^(size-1)
+// Paso inicial: *this = str[0]; z = 10; i = n-1
+// Paso iterativo: *this = *this * z + str[i-1]; i--
+template < typename N, typename E >
+number< N, E >::number(std::string str):
+ chunk(1, 0), sign(positive)
+{
+ if (!str.size())
+ return; // Si está vacío, no hace nada
+
+ number< N, E > diez = 10u;
+ std::string::size_type i = 0;
+ std::string::size_type fin = str.size() - 1;
+ if (str[0] == '-') // Si es negativo, salteo el primer caracter
+ ++i;
+ chunk[0] = ascii2uint(str[i]);
+ while (i < fin)
{
- // si encuentro un signo + ó - corto
- if (!isdigit(origen[length-number_offset-1]))
- break;
-
- increment = (10*number_offset)*(origen[length-number_offset-1]-'0');
- if ((acum + increment) > MAX_N)
- {
- chunk.push_back(acum);
- }
-
+ *this = *this * diez + number< N, E >(ascii2uint(str[i+1]));
+ ++i;
}
-
-
+ if (str[0] == '-') // Si es negativo, le pongo el signo
+ sign = negative;
}
template < typename N, typename E >
{
chunk[i] += n.chunk[i] + c;
if ((chunk[i] < n.chunk[i]) || \
+ ( c && ((n.chunk[i] + c) == 0)) || \
( (n.chunk[i] == 0) && c && (chunk[i] == 0) ))
c = 1; // Overflow
else
number< N, E > subtrahend;
// voy a hacer siempre el mayor menos el menor
- if (*this < n)
+ if (menorEnModuloQue(n))
{
minuend = n;
subtrahend = *this;
return true; // n es más grande
}
+ if (sign == negative) // Si comparamos 2 negativos, usamos
+ return !menorEnModuloQue(n); // "lógica inversa"
+ else
+ return menorEnModuloQue(n);
+}
+
+
+template < typename N, typename E >
+bool number< N, E >::menorEnModuloQue(const number< N, E >& n) const
+{
size_type i; //problema de VC++, da error de redefinición
if (chunk.size() > n.chunk.size()) // yo tengo más elementos
return false; // Son iguales
}
+
// efectúa un shifteo a izquierda del chunk, agregando 0s en los casilleros
// menos significativos
template < typename N, typename E >
return tmp;
}
+// Este es un 'workarround' HORRIBLE, de lo peor que hicimos en nuestras vidas,
+// pero realmente no encontramos manera alguna de convertir un número a un
+// string decimal que no requiera de divisiones sucesivas. Para no cambiar la
+// semántica del programa, decidimos convertir externamente nuestra salida en
+// hexadecimal a decimal utilizando un programa externo (en este caso Python
+// porque sabemos que está disponible en el laboratorio B).
+//
+// Estamos realmente avergonzados de haber tenido que llegar a esto, pero no nos
+// imaginamos que iba a sernos tan compleja esta conversión. Y nuevamente
+// pedimos disculpas.
template < typename NN, typename EE >
std::ostream& operator<< (std::ostream& os, const number< NN, EE >& n)
{
+ std::string cmd = "python -c 'print ";
+ if (n.sign == negative)
+ cmd += '-';
+ cmd += "0x" + numberToHex(n) + "'";
+
+ char buf[BUFSIZ];
+ FILE *ptr;
+
+ if ((ptr = popen(cmd.c_str(), "r")) != NULL)
+ while (fgets(buf, BUFSIZ, ptr) != NULL)
+ os << buf;
+ pclose(ptr);
+ return os;
+}
+
+template < typename N, typename E >
+std::string numberToHex(const number< N, E >& n)
+{
+ std::ostringstream os;
+ typename number< N, E >::const_reverse_iterator i = n.chunk.rbegin();
+ typename number< N, E >::const_reverse_iterator end = n.chunk.rend();
+ // Salteo ceros
+ for (; i != end; ++i)
+ if (*i != 0)
+ break;
+ if (i != end) // Si no llegué al final, imprimo sin 'leading zeros'
+ {
+ os << std::hex << *i;
+ ++i; // y voy al próximo
+ }
+ // imprimo el resto con 'leading zeros'
+ for (; i != end; ++i)
+ os << std::setfill('0') << std::setw(sizeof(N) * 2) << std::hex
+ << *i;
+ return os.str();
+}
+
+template < typename N, typename E >
+std::string numberToHexDebug(const number< N, E >& n)
+{
+ std::ostringstream os;
// FIXME sacar una salida bonita en ASCII =)
- if (n.sign == positive)
- os << "+ ";
- else
- os << "- ";
- typename number< NN, EE >::const_reverse_iterator i = n.chunk.rbegin();
- typename number< NN, EE >::const_reverse_iterator end = n.chunk.rend();
+ if (n.sign == negative)
+ os << "-";
+ typename number< N, E >::const_reverse_iterator i = n.chunk.rbegin();
+ typename number< N, E >::const_reverse_iterator end = n.chunk.rend();
for (; i != end; ++i)
- os << std::setfill('0') << std::setw(sizeof(NN) * 2) << std::hex
+ os << std::setfill('0') << std::setw(sizeof(N) * 2) << std::hex
<< *i << " ";
- return os;
+ return os.str();
}
template < typename N, typename E >
template < typename N, typename E >
std::pair< number< N, E >, number< N, E > > number< N, E >::split() const
{
+ assert(chunk.size() > 1);
typedef number< N, E > num_type;
typename num_type::size_type full_size = chunk.size();
typename num_type::size_type halves_size = full_size / 2;
projects / z.facultad / 75.29 / dale.git / commitdiff