Cómo implementar big int en C ++

Question

Me gustaría implementar una clase int grande en C ++ como un ejercicio de programación & # 8212; una clase que puede manejar números más grandes que un int largo. Sé que ya hay varias implementaciones de código abierto, pero me gustaría escribir la mía. 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 (dígitos individuales, por ejemplo), y colocarlos en una matriz. En este punto, debería ser relativamente simple implementar los diversos 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 general y consejos en lugar del código de trabajo real.

Answer 1

Cosas a tener en cuenta para una gran clase int:

1. Operadores matemáticos: +, -, /, *,% No olvides que tu clase puede estar a ambos lados del operador, que los operadores pueden ser encadenado, ese de los operandos podría ser int, float, double, etc.

2. Operadores de E / S: > > ;, < < Esto es donde descubres cómo hacerlo correctamente cree su clase a partir de la entrada del usuario y cómo formatearla para la salida también.

3. Conversiones / Casts: descifrar qué tipos / clases es tu gran int la clase debe ser convertible a, y cómo manejar adecuadamente el conversión. Una lista rápida haría incluye doble y flotante, y puede incluir int (con los límites adecuados comprobación) y complejo (suponiéndolo puede manejar el rango).

Answer 2

Un desafío divertido. :)

Supongo que quieres 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 le interese más en profundidad, considere leer este artículo de wikipedia sobre sumadores y sumadores completos . Hará algo similar a eso, pero puede bajar tan bajo como eso, pero siendo perezoso, 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 alguna estructura de datos. Una forma simple, 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 debe 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 lo compleja que será una operación y una n fija hace exactamente eso.

Pero ahora a algunos algoritmos sobre la operación de los números. Podría hacerlo a nivel lógico, pero usaremos esa potencia mágica de la CPU para calcular los resultados. Pero lo que asumiremos de la ilustración lógica de Half- y FullAdders es la forma en que trata con los carry. Como ejemplo, considere cómo implementaría el + = operador . Para cada número en BigInt & Lt; & Gt; :: value_, agregaría esos y vería si el resultado produce alguna forma de acarreo. No lo haremos en términos de bits, sino que dependemos de la naturaleza de nuestro BaseType (ya sea largo o int o 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í, 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 stl-functors std :: plus y std :: minus, std :: times y std :: divide, ..., pero ten cuidado con el carry. :) También puede implementar la multiplicación y la división utilizando los 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 tarea simple, 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 carry :), <= > - incluso puede optimizar un poco aquí, verificando el número aproximado de dígitos con operator< primero. Y así. Luego, haga que su clase sea útil, por befriendig std :: ostream size().

¡Espero que este enfoque sea útil!

Answer 3

Hay una sección completa sobre esto: [The Art of Computer Programming, 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 desea ver otra implementación, ¿ha considerado qué es lo que quiere aprender? Hay innumerables errores que cometer y descubrirlos es instructivo y también peligroso. También existen desafíos para identificar economías computacionales importantes y tener estructuras de almacenamiento apropiadas para evitar serios problemas de rendimiento.

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

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

¡Diviértete!

Answer 4

La adición de

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

Answer 5

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

Answer 6

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

Answer 7

No estoy convencido de que usar una cadena sea el camino correcto; aunque nunca he escrito código yo mismo, creo que usar una matriz de un tipo numérico base 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;

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é utilizando.

Answer 8

Como han dicho 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 cosas en una variedad de largos.

Answer 9

Usa los algoritmos que aprendiste en 1º a 4º grado.
Comience con las columnas, luego las decenas, y así sucesivamente.

Answer 10

Si su arquitectura de destino es compatible con la representación de números BCD (decimal codificado en binario), puede obtener algún soporte de hardware para la multiplicación / adición manual que necesita hacer. Hacer que el compilador emita instrucciones BCD es algo que tendrá que leer ...

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

Answer 11

Mi inicio sería tener una matriz de enteros de tamaño arbitrario, usando 31 bits y 32n'd como desbordamiento.

La operación de inicio sería AGREGAR, y luego, HACER NEGATIVO, usando el complemento de 2. Después de eso, la resta fluye de manera trivial, y una vez que hayas agregado / sub, todo lo demás es factible.

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

Answer 12

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 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 1 vez.

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

No tengo ninguna prueba de velocidad, pero al mirar la versión Java de BigInteger parece que está haciendo mucho trabajo.

Para mí hago lo siguiente

//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

Answer 13

reste 48 de su cadena de 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.