Как суммировать большие числа?

Я пытаюсь вычислить 1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + ... + 1 * 2 * ... * n, где n - пользовательский ввод. Он работает для значений n до 12. Я хочу рассчитать сумму для n = 13, n = 14 и n = 15. Как это сделать на C89? Как я знаю, я могу использовать unsigned long long int только на C99 или C11.

Вход 13, результат 2455009817, ожидается 6749977113
Вход 14, результат 3733955097, ожидаемый 93928268313
Вход 15, результат 1443297817, ожидаемый 1401602636313

Мой код:

#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;
}

Ответ 1

На практике вам нужна библиотека произвольная точность арифметики (a.k.a. bigint или bignum). Моя рекомендация GMPlib, но есть другие.

Не пытайтесь закодировать свою собственную библиотеку bignum. Существуют эффективные и умные алгоритмы, но они немыслимы и трудно понять (вы можете найти целые книги, посвященные этому вопросу). Кроме того, существующие библиотеки, такие как GMPlib, используют конкретные машинные инструкции (например, ADC -add with carry), что стандартный компилятор C не будет излучать (из чистого кода C).

Если это домашняя работа, и вам не разрешено использовать внешний код, рассмотрите, например, число в базе или radix 1000000000 (один миллиард) и кодировать себя операции очень наивно, подобно тому, что вы узнали в детстве. Но имейте в виду, что существуют более эффективные алгоритмы (и что используются настоящие библиотеки bignum).

Число может быть представлено в базе 1000000000 с помощью массива unsigned, каждый из которых является "цифрой" базы 1000000000. Таким образом, вам необходимо управлять массивами (возможно, с кучей, используя malloc) и их длину.

Ответ 2

Вы можете использовать double, особенно если ваша платформа использует IEEE754.

Такой double дает вам 53 бит точности, что означает, что целые числа точны вплоть до 53-й степени 2. Это достаточно хорошо для этого случая.

Если ваша платформа не использует IEEE754, обратитесь к документации по принятой схеме с плавающей точкой. Это может быть адекватно.

Ответ 3

Простой подход, когда вы чуть выше предела MaxInt, заключается в выполнении вычислений по модулю 10 ^ n для подходящего n, и вы выполняете то же вычисление, что и вычисление с плавающей запятой, но где вы делите все на 10 ^ r. Первый результат даст вам первые n цифр, в то время как последний результат даст вам последние цифры ответа с удалением первых r цифр. Тогда последние несколько цифр будут неточными из-за ошибок округления, поэтому вы должны выбрать r немного меньше, чем n. В этом случае n = 9 и r = 5 будут работать хорошо.