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

Я пытаюсь вычислить 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 будут работать хорошо.