Cómo implementar big int en C++

biginteger bignum

Question

Me gustaría implementar una gran clase int en C ++ como ejercicio de programación, 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 las mías. 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 (por ejemplo, dígitos únicos) 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 de código de trabajo real.

Answer 1

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

Answer 2

Clase C ++ BigInt que permite al usuario trabajar con enteros de precisión arbitrarios. http://sourceforge.net/projects/cpp-bigint/

Answer 3

Como otros dijeron, hágalo a la vieja usanza de la mano dura, 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 4

Cosas a considerar para una gran clase int:

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

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

3. Conversiones / Cast: Averigua a qué tipos / clases debe ser convertible tu gran clase int, y cómo manejar adecuadamente la conversión. Una lista rápida incluiría double y float, y puede incluir int (con la comprobación apropiada de límites) y compleja (suponiendo que pueda manejar el rango).

Answer 5

Eche un vistazo here para ver cómo GMP implementa sus algoritmos.

Answer 6

Hay una sección completa sobre esto: [The Art of Computer Programming, vol.2: Seminérmica Algorithms, sección 4.3 Multiple Precision Arithmetic, pp. 265-318 (ed.3)]. Puede encontrar otro material interesante en el Capítulo 4, Aritmética.

Si realmente no quieres ver otra implementación, ¿has considerado qué es lo que estás aprendiendo? 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 adecuadas para evitar problemas graves de rendimiento.

Una pregunta de desafío para usted: ¿cómo pretende 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 generalizar sin esperar un nivel de prueba exagerado. No olvide considerar los modos de falla (problemas de falta de memoria, fuera de la pila, demasiado tiempo, etc.).

¡Que te diviertas!

Answer 7

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

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

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

Answer 8

No estoy convencido de que usar una cuerda sea el camino correcto, aunque nunca he escrito el código, creo que usar una matriz de tipo numérico básico podría ser una mejor solución. La idea es que simplemente amplíes lo que ya obtuviste de la misma forma en que la CPU amplía un solo bit en un entero.

Por ejemplo, si tienes 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 simplista, pero debería ser bastante obvio cómo extender a una estructura que tenía un número variable de cualquier clase numérica básica que esté utilizando.

Answer 9

No olvide que no necesita limitarse a 0-9 como dígitos, es decir, usar bytes como dígitos (0-255) y aún puede hacer cálculos aritméticos largos de la misma manera que lo haría con los dígitos decimales. Incluso podría usar una matriz de largo.

Answer 10

Podría intentar implementar algo como esto:

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

Solo necesitarías 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 serie 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, puede ralentizarlo.

No tengo ninguna prueba de velocidad, pero mirando la versión java de BigInteger parece que está haciendo un montón de 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 11

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

Los chips de la serie Motorola 68K tenían esto. No es que sea amargo ni nada por el estilo.

Answer 12

Un desafío divertido. :)

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

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

Pero antes de entrar en detalles algorítmicos sobre cómo sumar, restar, multiplicar, busquemos alguna estructura de datos. Una manera 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 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 primera mano qué tan compleja será una operación y una n fija lo hace.

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

Sin duda, si agrega 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ía usar stl-functors std :: plus y std :: minus, std :: times y std :: divide, ..., pero tenga en cuenta el carry. :) También puede implementar la multiplicación y la división usando los operadores más y menos, pero eso es muy lento, porque eso recalcula 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 operator< carry :) operator< - incluso puedes optimizar un poco aquí, primero verificando el número aproximado de dígitos con size() . Y así. Luego haz que tu clase sea útil, por befriendigt std :: ostream operator<< .

Espero que este enfoque sea útil.

Answer 13

Una vez que tenga los dígitos del número en una matriz, puede hacer la suma y la multiplicación exactamente como lo haría a mano.

Answer 14

Usa los algoritmos que aprendiste en 1 ° a 4 ° grado.
Comience con la columna de uno, luego las decenas, y así sucesivamente.

Answer 15

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