Cómo implementar big int en C++

Un desafío divertido. :)

Supongo que quieres números enteros de longitud arbitraria. Sugiero el siguiente enfoque:

Considere la naturaleza binaria del tipo de datos "int". Piense en utilizar operaciones binarias simples para emular lo que hacen los circuitos de su CPU cuando agregan cosas. En caso de que esté interesado en profundizar más, considere leer este artículo de Wikipedia sobre semisumadores y sumadores completos . Harás algo similar a eso, pero puedes bajar a un nivel tan bajo como ese, pero como soy vago, pensé en renunciar y encontrar una solución aún más simple.

Pero antes de entrar en detalles algorítmicos sobre sumar, restar y multiplicar, busquemos alguna estructura de datos. Una forma sencilla es, por supuesto, almacenar cosas en un std::vector.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

Es posible que desee considerar si desea que el vector tenga un tamaño fijo y si desea preasignarlo. La razón es que para diversas operaciones, tendrá que pasar por cada elemento del vector: O (n). Es posible que desee saber de antemano qué tan compleja será una operación y una n fija hace precisamente eso.

Pero ahora veamos algunos algoritmos para operar con números. Podrías hacerlo a nivel lógico, pero usaremos esa potencia mágica de la CPU para calcular los resultados. Pero lo que tomaremos de la ilustración lógica de Half- y FullAdders es la forma en que trata los acarreos. Como ejemplo, considere cómo implementaría el operador += . Para cada número en BigInt<>::value_, los agregaría y vería si el resultado produce alguna forma de acarreo. No lo haremos bit a bit, sino que confiaremos en la naturaleza de nuestro BaseType (ya sea largo, int, corto o lo que sea): se desborda.

Seguramente, si sumas dos números, el resultado debe ser mayor que el mayor de esos números, ¿verdad? Si no es así, entonces el resultado se desbordó.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

La otra operación aritmética es análoga. Diablos, incluso podrías usar los functores stl std::plus y std::minus, std::times y std::divides, ..., pero ten cuidado con el transporte. :) También puedes implementar la multiplicación y la división usando los operadores más y menos, pero eso es muy lento, porque volvería a calcular los resultados que ya calculaste en llamadas anteriores a más y menos en cada iteración. Existen muchos algoritmos buenos para esta sencilla tarea; utilice wikipedia o la web.

Y, por supuesto, debes implementar operadores estándar como operator<<(simplemente desplaza cada valor en value_ hacia la izquierda durante n bits, comenzando en value_.size()-1... ah, y recuerda el acarreo :), operator<- incluso puedes optimizar un poco aquí, verificando el número aproximado de dígitos con size()el primero. Etcétera. Luego haz que tu clase sea útil, haciéndote amigo de std::ostream operator<<.

¡Espero que este enfoque sea útil!

Nov 06 '2008 20:11 mstrobl