¿Algún documento que diga exactamente para qué rango de números están diseñados .NET BigIntegers?

Estoy jugando con .NET BigInteger y básicamente me pregunto qué número, una respuesta estimada, estaría bien, es el punto de desviación de la curva de (la gráfica de (aumento del tiempo requerido para las operaciones) vs (valor de BigInteger))?

¿o están diseñados sin tal desviación de modo que si graficamos el aumento de tiempo requerido para las operaciones frente al valor de BigInteger de 1 a infinito, tendremos una curva suave en todo momento?

por ejemplo, suponiendo que las matrices están diseñadas con la capacidad de manejar 50 artículos. Esto significa que si tengo 1 elemento, las operaciones son f (1) tiempo. y cuando tengo 2 artículos, las operaciones son f (2) tiempo. Si tengo 50 artículos, las operaciones son f (50) tiempo. pero como está diseñado para manejar solo 50 artículos, las operaciones que se realicen cuando tengamos 51 artículos serán g (51) donde g (51)> f (51).

Si se implementa correctamente, la complejidad de la aritmética BigInteger debería ser una curva suave. Por ejemplo, la complejidad temporal de la multiplicación debe ser O (NM) donde N es el número de dígitos en el primer multiplicando y M es el número de dígitos en el segundo multiplicando. Por supuesto, hay límites prácticos en el sentido de que puede elegir N y M tan grandes que los números no caben en su máquina.

¿Hay alguno / alguien sabe de algún documento que afirme que se implementa como tal?

Cualquier número que pueda ser más grande que ULong.MaxValue o más pequeño que Long.MinValue debe representarse con BigInteger.

Si NO (Long.MinValue <= X <= ULong.MaxValue) Entonces BigInteger

BigInteger es para cantidades demasiado grandes que las primitivas normales pueden manejar.

Por ejemplo, si su número entero está fuera del rango de Long, probablemente debería usar BigInteger. Sin embargo, estos casos son muy raros, y el uso de estas clases tiene una sobrecarga significativamente mayor que sus contrapartes primitivas.

Por ejemplo, longtiene 64 bits de ancho y puede contener el rango: -9,223,372,036,854,775,808 a 9,223,372,036,854,775,80. ulong puede contener de 0 a 18,446,744,073,709,551,615. Si sus números son más grandes o más pequeños que eso, BigInteger es su única opción

La única vez que los he visto utilizados en una aplicación del mundo real fue una aplicación de diagrama de estrellas.

Vea también: Rangos primitivos en .NET

En cierto sentido, el objetivo de BigInteger no es tanto el tamaño absoluto como la precisión ilimitada. Los números de coma flotante también pueden ser muy grandes, pero tienen una precisión limitada. BigInteger le permite realizar operaciones aritméticas sin preocuparse por errores de redondeo o desbordamiento. El precio que paga es que es cientos de veces más lento que la aritmética con números enteros ordinarios o números de coma flotante.

Como otros han señalado, ulong puede contener entre 0 y 18,446,744,073,709,551,615, y siempre que permanezca en ese rango puede hacer operaciones aritméticas exactas. Si va incluso 1 más allá de ese rango, obtendrá un desbordamiento, por lo que la respuesta a su pregunta es usar BigInteger si necesita una aritmética exacta y existe la posibilidad de que cualquier resultado intermedio exceda 18,446,744,073,709,551,615.

La mayoría de los problemas en ciencia, ingeniería y finanzas pueden vivir con las aproximaciones forzadas por los números de coma flotante, y no pueden permitirse el costo del tiempo de la aritmética BigInteger. La mayoría de los cálculos comerciales no pueden vivir con las aproximaciones de la aritmética de coma flotante, pero funcionan dentro del rango de 0 a 18,446,744,073,709,551,615, por lo que pueden usar la aritmética ordinaria. BigInteger es necesario cuando se utilizan algoritmos de la teoría de números que incluyen cosas como la criptografía (piense en números primos de 50 dígitos). A veces también se usa en aplicaciones comerciales cuando se necesitan cálculos exactos, la velocidad no es demasiado importante y establecer un sistema de punto decimal fijo adecuado es demasiado problema.

Si se implementa correctamente, la complejidad de la aritmética BigInteger debería ser una curva suave. Por ejemplo, la complejidad temporal de la multiplicación debería ser O (NM) donde N es el número de dígitos en el primer multiplicando y M es el número de dígitos en el segundo multiplicando. Por supuesto, hay límites prácticos en el sentido de que puede elegir N y M tan grandes que los números no caben en su máquina.

Si buscas en Google "Complejidad computacional de biginteger" obtendrás más referencias de las que puedes sacudir. Una que responde directamente a su pregunta es la siguiente: Comparación de dos paquetes aritméticos de precisión arbitraria .

Limite de memoria

BigInteger se basa en la matriz int para el almacenamiento. Suponiendo esto, el límite teórico para el número máximo, que BigInteger es capaz de representar, puede derivarse del tamaño máximo de matriz disponible en .net. Aquí hay un tema SO sobre las matrices: encontrar la cantidad de memoria que puedo asignar para una matriz en C # .

Suponiendo que conocemos el tamaño máximo de matriz, podemos estimar el número máximo, que BigInteger puede representar: (2 ^ 32) ^ max_array_size, donde:

• 2 ^ 32 - número máximo en la celda de la matriz (int)
• max_array_size: tamaño máximo permitido de la matriz int que está limitado por un tamaño de objeto de 2 GB

Esto da número con 600 millones de dígitos decimales.

Límite de rendimiento

En cuanto al rendimiento, BigInteger utiliza el algoritmo Karatsuba para la multiplicación y el algoritmo lineal para sumar. La complejidad de la multiplicación es , eso significa que escalará bastante bien incluso para grandes números ( Gráfico de complejidad ), sin embargo, aún puede afectar la penalización del rendimiento dependiendo del tamaño de la RAM y la memoria caché del procesador.

Hasta ahora, dado que el tamaño máximo de número está limitado a 2 GB, en la máquina de descenso no verá una brecha de rendimiento inesperada, pero aún operando en números de 600 millones de dígitos será muy lento.

El límite es el tamaño de su memoria (y el tiempo que tiene). Entonces, puedes tener números realmente grandes. Como dijo Kevin, en criptografía uno tiene que multiplicar o exponer números con unos mil dígitos (binarios), y esto es posible sin ningún problema.

Por supuesto, a menudo los algoritmos se vuelven más lentos a medida que los números se hacen más grandes, pero no tanto más lento.

Sin embargo, cuando usa números en el rango de mega dígitos, es posible que desee pensar en otras soluciones, ya que calcular realmente con ellas también se vuelve lento.

Hay algunos usos dentro de la comunidad científica (es decir, la distancia entre las galaxias, el número de átomos en un campo de hierba, etc.)

Como sugiere la respuesta de kevin cline, BigNumbers se agregaron a las bibliotecas .NET principalmente porque se necesitaban como un bloque de construcción para muchos algoritmos criptográficos modernos (firmas digitales, cifrado de clave pública / privada, etc.). Muchos algoritmos criptográficos modernos implican cálculos sobre valores enteros con tamaños de hasta varios miles de bits. Dado que la clase BigNumber describe una clase bien definida y útil, decidieron hacerla pública (en lugar de mantenerla como un detalle interno de las API criptográficas).