sumas - Cómo sumar grandes números?

suma de fracciones

Question

Estoy tratando de calcular 1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + ... + 1 * 2 * ... * n donde n es la entrada del usuario. Funciona para valores de n hasta 12. Quiero calcular la suma para n = 13 , n = 14 y n = 15 . ¿Cómo hago eso en C89? Como sé, puedo usar unsigned long long int solo en C99 o C11.

1. Entrada 13, resultado 2455009817, esperado 6749977113
2. Entrada 14, resultado 3733955097, esperado 93928268313
3. Entrada 15, resultado 1443297817, esperado 1401602636313

Mi código:

#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned long int n;
unsigned long int P = 1;
int i;
unsigned long int sum = 0;
scanf("%lu", &n);
for(i = 1; i <= n; i++)
{
P *= i;
sum += P;
}
printf("%lu", sum);
return 0;
}

Answer 1

En la práctica, quiere una biblioteca aritmética de precisión arbitraria (también conocida como bigint o bignum ). Mi recomendación es GMPlib pero hay otras .

No intente codificar su propia biblioteca bignum. Existen algoritmos eficientes e inteligentes, pero son poco intuitivos y difíciles de comprender (puede encontrar libros completos dedicados a esa pregunta). Además, las bibliotecas existentes como GMPlib están aprovechando las instrucciones de máquinas específicas (por ejemplo, ADC -add with carry) que un compilador estándar de C no emitirá (a partir del código C puro).

Si esto es una tarea y no tiene permiso para usar un código externo, considere, por ejemplo, representar un número en base o radix 1000000000 (mil millones) y codificar las operaciones de una manera muy ingenua, similar a lo que aprendió cuando era niño . Pero tenga en cuenta que existen algoritmos más eficientes (y que las bibliotecas reales de bignum los están usando).

Un número podría representarse en la base 1000000000 al tener una matriz de unsigned , siendo cada uno un "dígito" de la base 1000000000. Por lo tanto, debe administrar las matrices (probablemente el montón asignado, utilizando malloc ) y su longitud.

Answer 2

Podría usar un double , especialmente si su plataforma usa IEEE754.

Tal double te da 53 bits de precisión, lo que significa que los enteros son exactos hasta la potencia 53 de 2. Eso es lo suficientemente bueno para este caso.

Si su plataforma no utiliza IEEE754, consulte la documentación sobre el esquema de punto flotante adoptado. Puede ser adecuado.

Answer 3

Un enfoque simple cuando está justo por encima del límite de MaxInt, es hacer el cómputo módulo 10 ^ n para un n adecuado y realiza el mismo cálculo que el cálculo de punto flotante pero donde divide todo por 10 ^ r.El resultado anterior le dará los primeros n dígitos, mientras que el último resultado le dará los últimos dígitos de la respuesta con los primeros r dígitos eliminados. Entonces, los últimos dígitos aquí serán inexactos debido a errores de redondeo, por lo que debe elegir un bit un poco menor que n. En este caso, tomar n = 9 yr = 5 funcionará bien.