¿Qué estructura de datos debo usar para la clase BigInt?

Me gustaría implementar una clase BigInt que sea capaz de manejar números realmente grandes. Solo quiero agregar y multiplicar números, sin embargo, la clase también debe manejar números negativos.¿Qué estructura de datos debo usar para la clase BigInt?

Quería representar el número como una cadena, pero hay una gran sobrecarga con la conversión de cadena a int y viceversa para agregar. Deseo implementar la adición como en la escuela secundaria, agregar el orden correspondiente y si el resultado es mayor que 10, agregue el acarreo al siguiente pedido.

Luego pensé que sería mejor manejarlo como una matriz de uns long long int y mantener el signo separado por bool. Con esto tengo miedo del tamaño de la int, ya que el estándar de C++, por lo que sé, garantiza solo que int < float < double. Corrígeme si estoy equivocado. Entonces, cuando llegue a algún número, debo moverme hacia adelante y comenzar a agregar el número a la siguiente posición de la matriz.

¿Hay alguna estructura de datos adecuada o mejor para esto?

Fuente

2012-03-30 user1086004

Me parece una implementación razonable. Pero si está utilizando ULONG, cada elemento de la matriz puede contener un valor de 0 a 2^32-1 en lugar de 0 a 10. Eso le ahorrará unos pocos bytes. :-) –

El estándar garantiza solo 'float <= double' (tenga en cuenta el signo igual) – ipc

Sí, eso es exactamente lo que quise decir. ¿Pero es 2^32 - 1 lo mismo en Linux y en Solaris? Respectivamente es el tamaño garantizado en todas partes? Mi punto es que, por ejemplo, obtengo MyBigIntClass number = "234567434256547"; , y empiezo a convertir este número de serie a mi representación interna en la clase que se utiliza long long int (quizás :-)), y después de que el número llegue a 2^32 me muevo a otra posición en el conjunto. ¿Es correcto? – user1086004

Entonces, ¿desea una matriz dinámica de números enteros de un tamaño conocido?

Suena como vector<uint32_t> debería funcionar para usted.

Fuente

2012-03-30 12:12:15 Joni

desafortunadamente STL no está permitido – user1086004

¿deberes? ¿incrustado? En cualquier caso, necesitarás algo como 'vector'. Afortunadamente, es un ejercicio simple para recrear una matriz dinámica básica." – Joni

Como ya descubrió, necesitará usar tipos específicos en su plataforma (o el idioma si tiene C++ 11) que tienen un tamaño fijo. Una implementación común de un gran número usaría enteros de 32 bits y garantizaría que solo se configuraran los 16 bits más bajos. Esto le permite operar en los dígitos (donde el dígito sería [0..2^16)] y luego normalizar el resultado aplicando las prórrogas.

Fuente

2012-03-30 12:15:15

Para sumar/restar, se puede llevar en el camino y no necesita dos pasadas. Para la multiplicación, depende del algoritmo, pero si está usando, por ejemplo, métodos FFT de punto flotante, no necesita también lleva (pero es mejor usar "dígitos" de 16 bit ya que acumulará error de redondeo durante la FFT). –

En una plataforma moderna de 64 bits x86, el mejor enfoque es probablemente almacenar su bigint como una matriz asignada dinámicamente de enteros de 32 bits sin signo, por lo que su aritmética puede caber en 64 bits. Puede manejar su signo por separado, como una variable miembro de la clase, o puede usar la aritmética de complemento a 2 (que es cómo se representan típicamente los signed int).

El archivo de inclusión estándar C <stdint.h> define uint32_t y uint64_t, por lo que puede evitar los tipos enteros dependientes de la plataforma. O bien, (si su plataforma no proporciona estos), puede improvisar y definir este tipo de cosas usted mismo, preferiblemente en un archivo separado "platform_dependent.h" ...

Fuente

2012-03-30 17:25:04 comingstorm

El complemento de 2 s no es fácil de hacer para bigints de longitud dinámica (y no compra mucho), pero Estoy de acuerdo con el resto. – Sopel

¿Qué estructura de datos debo usar para la clase BigInt?

Respuesta

Cuestiones relacionadas