Cómo implementar big int en C ++

Me gustaría implementar una clase int grande en C ++ como un ejercicio de programación, una clase que puede manejar números mayores que un int largo. Sé que ya existen varias implementaciones de código abierto, pero me gustaría escribir la mía propia. Estoy tratando de tener una idea de cuál es el enfoque correcto.

Entiendo que la estrategia general es obtener el número como una cadena y luego dividirlo en números más pequeños (un solo dígito, por ejemplo) y colocarlos en una matriz. En este punto, debería ser relativamente sencillo implementar los distintos operadores de comparación. Mi principal preocupación es cómo implementaría cosas como la suma y la multiplicación.

Estoy buscando un enfoque y un consejo general en lugar de un código de trabajo real.

Cosas a considerar para una gran clase internacional:

1. Operadores matemáticos: +, -, /, *,% No olvide que su clase puede estar a cualquier lado del operador, que los operadores pueden encadenarse, que uno de los operandos puede ser un int, float, double, etc. .

2. Operadores de E / S: >>, << Aquí es donde averigua cómo crear correctamente su clase a partir de la entrada del usuario y también cómo formatearla para la salida.

3. Conversiones / Casts: averigüe a qué tipos / clases debería ser convertible su gran clase int y cómo manejar correctamente la conversión. Una lista rápida incluiría double y float, y puede incluir int (con la verificación de límites adecuada) y complex (asumiendo que puede manejar el rango).

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 usar operaciones binarias simples para emular lo que hacen los circuitos en su CPU cuando agregan cosas. En caso de que esté interesado en más profundidad, considere leer este artículo de wikipedia sobre medios sumadores y sumadores completos . Harás algo similar a eso, pero puedes bajar a un nivel tan bajo como ese, pero siendo 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, multiplicar, busquemos una estructura de datos. Una forma sencilla, por supuesto, es 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 hacer el vector de un tamaño fijo y si 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 a algunos algoritmos sobre cómo operar con números. Podrías hacerlo en un 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 con 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 en términos de bits, sino que confíe en la naturaleza de nuestro BaseType (ya sea largo, int, corto o lo que sea): se desborda.

Seguramente, si suma dos números, el resultado debe ser mayor que el mayor de esos números, ¿verdad? Si no es así, 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. Demonios, incluso podrías usar los stl-functors std :: plus y std :: minus, std :: times y std :: divides, ..., pero cuidado con el carry. :) También puede implementar la multiplicación y la división usando sus operadores más y menos, pero eso es muy lento, porque eso volvería a calcular los resultados que ya calculó en llamadas anteriores a más y menos en cada iteración. Hay muchos buenos algoritmos para esta simple tarea, use wikipedia o la web.

Y, por supuesto, debe implementar operadores estándar como operator<<(simplemente cambie cada valor en value_ a la izquierda para n bits, comenzando en value_.size()-1... oh y recuerde el acarreo :), operator<- incluso puede optimizar un poco aquí, verificando el número aproximado de dígitos con el size()primero. Y así. Luego haga que su clase sea útil, befriendig std :: ostream operator<<.

¡Espero que este enfoque sea útil!

Hay una sección completa sobre esto: [El arte de la programación informática, vol. 2: Algoritmos seminuméricos, sección 4.3 Aritmética de precisión múltiple, págs. 265-318 (ed.3)]. Puede encontrar otro material interesante en el Capítulo 4, Aritmética.

Si realmente no quiere ver otra implementación, ¿ha considerado qué es lo que quiere aprender? Se pueden cometer innumerables errores y descubrirlos es instructivo y también peligroso. También existen desafíos para identificar economías computacionales importantes y tener estructuras de almacenamiento adecuadas para evitar problemas graves de rendimiento.

Una pregunta de desafío para usted: ¿Cómo piensa probar su implementación y cómo se propone demostrar que su aritmética es correcta?

Es posible que desee probar con otra implementación (sin mirar cómo lo hace), pero se necesitará más que eso para poder generalizar sin esperar un nivel de prueba insoportable. No olvide considerar los modos de falla (problemas de falta de memoria, falta de pila, ejecución demasiado larga, etc.)

¡Que te diviertas!

La adición probablemente tendría que hacerse en el algoritmo de tiempo lineal estándar,
pero para la multiplicación, puede probar http://en.wikipedia.org/wiki/Karatsuba_algorithm

Una vez que tenga los dígitos del número en una matriz, puede sumar y multiplicar exactamente como lo haría a mano.

No olvide que no necesita restringirse a 0-9 como dígitos, es decir, use bytes como dígitos (0-255) y aún puede hacer aritmética de mano larga de la misma manera que lo haría con los dígitos decimales. Incluso podría usar una matriz de archivos long.

No estoy convencido de que usar una cadena sea la forma correcta de hacerlo, aunque nunca he escrito código, creo que usar una matriz de un tipo numérico básico podría ser una mejor solución. La idea es que simplemente extienda lo que ya tiene de la misma manera que la CPU extiende un solo bit a un entero.

Por ejemplo, si tiene una estructura

typedef struct {
    int high, low;
} BiggerInt;

A continuación, puede realizar manualmente operaciones nativas en cada uno de los "dígitos" (alto y bajo, en este caso), teniendo en cuenta las condiciones de desbordamiento:

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

Es un ejemplo un poco simplista, pero debería ser bastante obvio cómo extenderse a una estructura que tenía un número variable de cualquier clase numérica base que esté usando.

Utilice los algoritmos que aprendió de 1º a 4º grado.
Empiece con la columna de las unidades, luego las decenas y así sucesivamente.

Como dijeron otros, hágalo a la antigua usanza, pero evite hacer todo esto en la base 10. Sugeriría hacerlo todo en la base 65536 y almacenar las cosas en una variedad de largos.

Si su arquitectura de destino admite la representación de números BCD (decimal codificado en binario), puede obtener algún soporte de hardware para la multiplicación / suma a mano que necesita hacer. Conseguir que el compilador emita instrucciones BCD es algo en lo que tendrás que leer ...

Los chips de la serie Motorola 68K tenían esto. No es que esté amargado ni nada.

Mi comienzo sería tener una matriz de números enteros de tamaño arbitrario, usando 31 bits y 32n como desbordamiento.

La operación inicial sería ADD, y luego, MAKE-NEGATIVE, usando el complemento de 2. Después de eso, la resta fluye trivialmente, y una vez que tiene add / sub, todo lo demás es factible.

Probablemente existen enfoques más sofisticados. Pero este sería el enfoque ingenuo de la lógica digital.

Podría intentar implementar algo como esto:

http://www.docjar.org/html/api/java/math/BigInteger.java.html

Solo necesitaría 4 bits para un solo dígito 0 - 9

Entonces, un valor de Int permitiría hasta 8 dígitos cada uno. Decidí que me quedaría con una variedad de caracteres, así que uso el doble de memoria, pero para mí solo se usa una vez.

Además, cuando se almacenan todos los dígitos en un solo int, se complica demasiado y, en todo caso, incluso puede ralentizarlo.

No tengo ninguna prueba de velocidad, pero mirando la versión java de BigInteger parece que está haciendo un gran trabajo.

Para mi hago lo de abajo

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

reste 48 de su cadena de números enteros e imprima para obtener el número de dígitos grandes. luego realice la operación matemática básica. de lo contrario, proporcionaré una solución completa.