¿Qué estructura de datos debería usar para crear mi propia clase "BigInteger"?

Question

Como una asignación opcional, estoy pensando en escribir mi propia implementación de la clase BigInteger, donde voy a dar mis propios métodos para la suma, resta, multiplicación, etc.

Esto será para los números enteros arbitrariamente largas, incluso cientos de dígitos de largo.

Al hacer los cálculos en estos números, dígito por dígito no es difícil, ¿cuál cree que es la mejor estructura de datos para representar mi "BigInteger"?

Al principio estaba considerando usar una matriz, pero luego pensé que todavía podría desbordarme (quedarme sin ranuras de la matriz) después de una gran adición o multiplicación. ¿Sería este un buen caso para usar una lista vinculada, ya que puedo agregar dígitos con O (1) complejidad de tiempo?

¿Hay alguna otra estructura de datos que sería incluso más adecuada que una lista vinculada? ¿Debería el tipo de mi estructura de datos ser el tipo entero posible más pequeño que tengo disponible?

Además, ¿debo tener cuidado acerca de cómo almacenar mi variable "carry"? ¿Debería ser él mismo de mi tipo "BigInteger"?

Answer 1

Diría una serie de entradas.

Answer 2

que diría un std :: vector de char (ya que tiene que contener sólo 0-9) (si va a trabajar en BCD)

Si no BCD a continuación, utilizar el vector de enteros (que aún no ha hacer claro)

Mucho menos espacio superior que enlazan lista

y cualquier asesoramiento dice el 'uso de vectores a menos que tenga una buena razón para no demasiado'

Answer 3

una matriz es de hecho un ajuste natural. Creo que es aceptable lanzar OverflowException, cuando te quedas sin memoria. El maestro verá atención a los detalles.

Una multiplicación duplica los números de un dígito, además aumenta a lo sumo 1. Es fácil crear una matriz lo suficientemente grande para almacenar el resultado de su operación.

Llevar a lo sumo un número largo de un dígito en la multiplicación (9 * 9 = 1, llevar 8). Un single int servirá.

Answer 4

Utilice siempre el tipo int más pequeño que hará el trabajo que necesita (bytes). Una lista vinculada debería funcionar bien, ya que no tendrá que preocuparse por el desbordamiento.

Answer 5

Revisa el libro C Interfaces and Implementations de David R. Hanson. Tiene 2 capítulos sobre el tema, que cubren la estructura del vector, el tamaño de la palabra y muchos otros temas que es probable que encuentre.

Está escrito para C, pero la mayoría es aplicable a C++ y/o Java. Y si usa C++, será un poco más simple porque puede usar algo como std::vector para administrar la asignación de matriz por usted.

Answer 6

Si utiliza árboles binarios (cuyas hojas son ints), obtiene todas las ventajas de la lista vinculada (número ilimitado de dígitos, etc.) con algoritmos de división y conquista más simples. En este caso, no tiene una base única, pero muchas dependen del nivel en el que está trabajando.

Si hace esto, debe usar un BigInteger para el transporte.Puede considerar una ventaja del enfoque de "lista enlazada de ints" que el acarreo siempre se puede representar como un int (y esto es cierto para cualquier base, no solo para la base 10, ya que la mayoría de las respuestas parecen suponer que usted debería usar. .. En cualquier base, el acarreo es siempre un solo dígito)

Mejor diré: sería una pérdida terrible usar la base 10 cuando puede usar 2^30 o 2^31.

Answer 7

El acceso a los elementos de las listas vinculadas es lento. Creo que las matrices son el camino a seguir, con una gran cantidad de comprobaciones consolidadas y el cambio de tamaño de la matriz en tiempo de ejecución, según sea necesario.

---

Aclaración: Recorrido de una lista enlazada y atravesando una matriz son ambos O (n) operaciones. Pero atravesar una lista vinculada requiere una referenciación de un puntero en cada paso. El hecho de que dos algoritmos tengan la misma complejidad no significa que ambos tomen el mismo tiempo para ejecutarse. La sobrecarga de asignar y desasignar n nodos en una lista vinculada también será mucho más pesado que la administración de memoria de una sola matriz de tamaño n, incluso si la matriz debe redimensionarse varias veces.

Answer 8

std::vector<bool> o std::vector<unsigned int> es probablemente lo que desea. Tendrás que push_back() o resize() en ellos ya que necesitas más espacio para multiplicar, etc. Además, recuerda push_back los bits de signo correctos si estás usando dos cumplidos.

Answer 9

Como regla general, utilice std::vector en lugar de std::list, a menos que necesite insertar elementos en el medio de la secuencia muy a menudo. Los vectores tienden a ser más rápidos, ya que se almacenan contiguamente y, por lo tanto, se benefician de una mejor ubicación espacial (un factor de rendimiento importante en las plataformas modernas).

Asegúrese de utilizar elementos naturales para la plataforma. Si quiere ser independiente de la plataforma, use long. Recuerde que a menos que tenga algunos intrínsecos especiales compiladores disponibles, necesitará un tipo al menos dos veces más grande para realizar la multiplicación.

No entiendo por qué querría llevar para ser un número entero grande. Carry es un solo bit para agregar y tamaño de elemento para la multiplicación.

Asegúrese de leer el Manual de programación de la computadora de Knuth, los algoritmos relativos a la aritmética de precisión arbitraria se describen allí en gran medida.

Answer 10

Guau, hay algunas ... respuestas interesantes aquí. Recomiendo leer un libro en lugar de tratar de ordenar todo este consejo contradictorio.

Dicho esto, C/C++ tampoco es adecuado para esta tarea. Big-integer es un tipo de matemática de precisión extendida. La mayoría de las CPU proporcionan instrucciones para manejar la matemática de precisión extendida a una velocidad comparable o igual (bits por instrucción) que las matemáticas normales. Cuando agrega 2^32 + 2^32, la respuesta es 0 ... pero también hay una salida de transporte especial de la ALU del procesador que un programa puede leer y usar.

C++ no puede acceder a esa bandera, y tampoco hay forma en C. Tienes que usar ensamblador.

Solo para satisfacer la curiosidad, puede usar la aritmética booleana estándar para recuperar bits de transporte, etc. Pero será mucho mejor descargar una biblioteca existente.