Se busca: biblioteca para números grandes (muy grandes)

[Lord Delfos]

Buenas, gente.

Hace ya un tiempo que vengo con esta idea de mejorar mi Calculadora v1 con una representación de números reales con más dígitos (digamos, unos 500:eek:)

Para tal efecto he andado buscando como loco bibliotecas que tengan implementación de los números y, lógicamente, sus operaciones. Pero los resultados no han sido muy buenos que digamos.

Así que pregunto: ¿Alguno sabe de alguna biblioteca que haga estas cosas?

Mil gracias.

[Delphius]

Hola Lord Delfos,
Hace una semana más o menos, viendo las respuesta de un usuario (http://ar.answers.yahoo.com/my/profile;_ylt=Aud.t5MPwdn6k.owltJkL4I6IRV.;_ylv=3?show=t2rTNH0naa) de YR llegué a una pregunta (http://ar.answers.yahoo.com/question/index;_ylt=ArGWxWADxGiBXVt2OJSXgciB9gt.;_ylv=3?qid=20100123113434AA8kDgL&show=7#profile-info-1yo7FlBNaa) relacionado con esto.
En su respuesta, breve pero directa, da un enlace a un artículo (http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic) en Wikipedia.

Allí hay una lista (http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries) de bibliotecas. Entre ellas, hay una disponible para Delphi: MPArith (http://home.netsurf.de/wolfgang.ehrhardt/mp_intro.html).

No se para que versión de Delphi estará diseñada, no la he probado. Intuyo que debe estar bastante estable y actualizada para varias versiones porque veo en dicha página en la parte superior que la última actualización se realizó el 26/11/09.

Si no funciona habrá que buscar otras alternativas, lamentablemente desconozco si existirá alguna otra opción.

De última no te quedará que implementarla desde cero. Desconozco como es que se consigue esto... mucho del tema de Aritmética de Precisión Arbitraria no sé (en realidad estoy en cero) y al artículo en wikipedia en su profundidad no lo he leído.

Saludos,

[Lord Delfos]

¡Ah la marosca! Esto parece interesante.

Parece completa. Aunque por lo que veo no tiene mucha documentación... Pero, bueno.

Gracias mil, Delphius. Le voy a pegar una ojeada.

PD: Yo también pensé en implementar mi propia representación. Y lo hice. Lo que pasa es que hay algunas operaciones que no sé en qué consisten. Por ejemplo, cómo calculo un Coseno... Ahí estoy frito. Y el proyecto en sí es bastante, digamos, light, como para ponerme a ver semejantes cosas.

[DriverOp]

Tampoco he usando una de esas unidades, pero sí entiendo cómo se calculan números grandes.

A grandes rasgos, toda operación aritmética, por compleja que sea, se puede reducir a una serie de sumas y restas de enteros, por ejemplo, una multiplicación no es más que una sucesión de sumas, la división una sucesión de restas y a partir de allí salen la potenciación, radización y logaritmo. Incluso si los operandos son reales, basta correr la coma a la derecha tantos dígitos como sea necesario y luego regresar la coma al lugar adecuado.

Sabiendo esto, en una computadora, para usar operandos más grandes que el tipo de dato más grande permitido, hay que imitar las operaciones sumas y restas como se hace "a mano". Por ejemplo, tomar los operandos como strings e ir convirtiendo cada dígito a byte, sumarlos (o restarlos), guardar el acarreo en otro byte y así ir formando el resultado.

Este método puede ser muy lento para el caso de grandes volúmenes de operaciones, por eso se busca optimizar utilizando aritmética de bit para sumar/restar cada dígito en complenento a 2. Porque en el fondo, la ALU del CPU usa este método con todas las operaciones.

De esta forma no importa la cantidad de dígitos que tengan los operandos, tanto puede ser uno como 500.

[Lord Delfos]

Claro, DriverOp. El problema es que yo puedo codificar las operaciones suma, resta, potencia entera, etc... El problema lo tengo con funciones que no sé ni qué hacen.

De nuevo, el Coseno. Qué cuenta hace realmente el coseno. 2^5 es 2 multiplicado por 2, cinco veces. Pero cos 0,3 ¿qué es? Ahí es donde se pone peludo el asunto.

[rgstuamigo]

Tampoco he usando una de esas unidades, pero sí entiendo cómo se calculan números grandes.

A grandes rasgos, toda operación aritmética, por compleja que sea, se puede reducir a una serie de sumas y restas de enteros, por ejemplo, una multiplicación no es más que una sucesión de sumas, la división una sucesión de restas y a partir de allí salen la potenciación, radización y logaritmo. Incluso si los operandos son reales, basta correr la coma a la derecha tantos dígitos como sea necesario y luego regresar la coma al lugar adecuado.

Sabiendo esto, en una computadora, para usar operandos más grandes que el tipo de dato más grande permitido, hay que imitar las operaciones sumas y restas como se hace "a mano". Por ejemplo, tomar los operandos como strings e ir convirtiendo cada dígito a byte, sumarlos (o restarlos), guardar el acarreo en otro byte y así ir formando el resultado.

Este método puede ser muy lento para el caso de grandes volúmenes de operaciones, por eso se busca optimizar utilizando aritmética de bit para sumar/restar cada dígito en complenento a 2. Porque en el fondo, la ALU del CPU usa este método con todas las operaciones.

De esta forma no importa la cantidad de dígitos que tengan los operandos, tanto puede ser uno como 500.
Totalmente válida tu explicacion y la entiendo perfectamente, pero hay algo que no se esta tomando en cuenta, pues resulta que los registros de la CPU tienen una limitacion, es decir en arquitectura de 32 Bit solo se puede representar 2^32 -1 que es el numero maximo, en arquitectura de 64 bit pues el numero maximo seria 2^64 -1 de cada Registro de la CPU, ahora viene la pregunta-> ¿Que hago si una multiplicacion sobrepasa esa cantidad? :confused:. Creo por ahi va el problema. ¿Cómo podemos resolverlo?:confused:.
Aunque he visto hace algun tiempo atras un truco en algun libro(el cual no recuerdo)que el resultado de la multiplicacion lo ponian en dos registros de la CPU algo por el estilo:rolleyes:. Claro esta que hay que ver la forma y creo que por ahí puede estar la solucion.;).
Saludos...:)

[Delphius]

Hola,
Como he dicho, mucho del tema no se por lo que no soy el más indicado para hablar al respecto.

Tengo entendido que estos tipos de bibliotecas se basan en el uso de memoria dinámica. Es decir se reserva la cantidad de memoria según se necesite y rompiendo de este modo, al menos en parte, las limitaciones de la capacidad de los registros.

Para simplificar el escenario, hagamos el supuesto en que el número se representa como un arreglo (o array si prefieren) bien grande. En cada posición se almacena un número o parte de éste.

Los algoritmos de suma, resta, etc basandose en esta "estructura" van calculando dígito a dígito el valor, dependiendo de la posición que ocupan.

Respecto a los cálculos de senos, cosenos, y demás funciones trigonométicas, cálculo de pi, etc deberías consultar libros de cálculo numérico (o análisis numérico) y matemático. La gran mayoría de las funciones trigonométricas se basan en series de Taylor. Por ejemplo, se puede estimar el valor del seno, a la n-ésima sucesión, con la siguiente fórmula:

sin x = x - x^3/3! + x^5/5! - x^7/7! + ... + (-1)^n/(2n + 1)! x^2n+1

Puedes consultar y ver el desarrollo de cada función en los artículos de wikipedia, tal como lo hice (http://es.wikipedia.org/wiki/Seno_%28trigonometr%C3%ADa%29) para exponerla aquí:D El "chiste" es como implementar los cálculos para la estructura de los números bien grandes;).

También que se puede estimar el valor de e (http://es.wikipedia.org/wiki/N%C3%BAmero_e), y pi (http://es.wikipedia.org/wiki/N%C3%BAmero_%CF%80) como series, combinatorias, etc.

Implementar las operaciones básicas no suponen demasiado retos, cuando se tratan números manejables... y a mano. Pero en la implementación a grandes números, y de forma rápida y eficiente las cosas se ponen duras.

Por ejemplo, en el caso de la multiplicación por general el algoritmo que aplicamos a mano y el que nos enseñaron en la escuela ofrece una complejidad computacional estable y esperada (n^2), pero para grandes números es mejor optar por implementaciones más rápidas como los algoritmos de Schönhage–Strassen (http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorithm), Karatsuba (http://en.wikipedia.org/wiki/Karatsuba_algorithm), entre otros.

Recomiendo visitar este enlace (http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations) para familiarizarse con los algoritmos de las operaciones matemáticas... y como dije darle muchas horas a leídas a los libros de cálculo/análisis numérico y matemáticos.

Y si se tiene pensado ir mucho más lejos, y se desea llevar manejos e implementaciones de matrices, etc. Ya, a modo de ejemplo, deben pensarse en implementaciones los más numéricamente estables y rápidas. En el caso del cálculo de los valores y vectores propios se recurre por lo general al uso de la factorización QR (http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_QR), y en caso de matrices simétricas reales puede recurrirse al método de Jacobi (http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm). Este último está un poco en desuso, pero se le reconoce que tiene mejor precisión que QR y tiene la particularidad de poder implementarse en computación paralela (algo que no es posible en QR).

Recomiendo además que se estudie sobre teoría de error... y familiarizarse con el término numéricamente estable... eso mayormente se trata en libros de análisis numérico (y en algunos de álgebra).

Esto lo digo por experiencia:D... ya que he pasado por cosas relacionadas con esto:mad:. Por ejemplo en términos algebraicos, y para un simple humano, esto:

a(b + c)

es igual a:

ab + ac

Pero en la práctica, numérica y computacionalmente hablando, el primero ofrece una mejor precisión que el segundo ya que el error relativo acumulado es menor. Al menos cuando se trata de números que una máquina puede procesar.... para los casos de grandes números y de precisión arbitraria creería que sucede algo similar.

Si todavía estás en la idea de darle rienda suelta a tu ingenio y elaborar tu propia biblioteca lo mejor es repasar mucho de cálculo y empezar a ver estudiar e investigar sobre los algoritmos más eficientes posibles. En teoría si se desean tener grandes números es para tener mejor precisión. Mejor precisión implica disponer de una buena cantidad de decimales y un error bajo.

Bueno, creo que dicho mucho y nada.

Saludos,

[Lord Delfos]

La técnica más común y fácil (bueno, fácil fácil no es) de todas es hacer la misma representación de números que hace el microprocesador (el estándar IEEE 754), pero en vez de tener un patrón de 32 bits, uno tiene un muuucho más grande, hecho incluso con arreglos de bytes.

Uno crea un tipo entero de 100 bytes (800 bits, bastante) y sus correspondientes operaciones.
Después lo usa como mantisa. En vez de tener los 23 bits de IEEE 754, uno tiene 800.
En vez de tener un exponente de 8 bits, uno tiene uno de 800 bits.

Es decir, todo exagerado lo más posible.

Y, claro, el pequeño asunto de crear las operaciones, y para más eficiencia, en assembler...

Lo más fácil es usar un Int64 en vez de definir uno mismo un nuevo entero. Te ahorrás trabajo, pero también te queda una representación de menor capacidad.

Por supuesto, todo esto funciona si uno tiene la suficiente paciencia...:) Que es lo que yo no tengo.

PD: Amigo Delphius, ¡¿porqué me odiás tanto?! ¡¿Qué te hice?! Estoy familiarizado con los asuntos de matemáticas, pero la verdad, para lo que es el proyecto... Gracias, muy amable.:cool: