Вычислить сумму цифр в 100 factorial

Question

Редактировать - Изменено название, чтобы соответствовать фактической постановке задачи.

Я программирую функцию, которая вычисляет сумму цифр в 100! но у меня, похоже, есть две большие проблемы.

1. Фактический результат 100! точна только на несколько первых цифр (фактический результат 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000)

2. Мой метод сложения цифр получившегося числа не выводит правильный результат.

Это мой текущий код:

void factorialSum() 
{ 
    double fact100 = factorial(100); 
    double suma = 0; 

    printf("100! is equal to: %.0f", fact100); 

    while (fact100 > 0) 
    { 
     double temporal = fmod(fact100, 10); 
     suma = suma + temporal; 
     fact100 = fact100/10; 
    } 
    printf("\nThe sum of all digits in 100! is: %.0f", suma); 
} 

И функция факториала() определяется как:

double factorial (double n) 
{ 
    double mult = 1; 
    double i = n; 

    while (i>=1) 
    { 
     mult *= i; 
     i = i - 1; 
    } 
    return mult; 
} 

Программа выводит 93326215443944102188325606108575267240944254854960571509166910400407995064242937148632694030450512898042989296944474898258737204311236641477561877016501813248 в результате за 100! и говорит, что сумма его цифр равна 666.

Любая помощь приветствуется, спасибо.

Answer 1

В C double обычно имеет 53 бита точности, что соответствует 16 или 17 цифрам точности. Поэтому, как только вы выходите за пределы 22!, double больше не может представлять точный результат, о чем свидетельствует следующий код. Обратите внимание, что при 23! конечные нули исчезают, поскольку double больше не представляет точное значение.

#include <stdio.h> 
#include <stdint.h> 

int main(void) 
{ 
    double y; 

    y = 1; 
    for (int i = 2; i < 30; i++) 
    { 
     y *= i; 
     printf("%2d %32.0lf\n", i, y); 
    } 
} 

Вот выход из программы

2        2 
3        6 
4        24 
5        120 
6        720 
7        5040 
8       40320 
9       362880 
10       3628800 
11       39916800 
12      479001600 
13      6227020800 
14      87178291200 
15     1307674368000 
16     20922789888000 
17     355687428096000 
18     6402373705728000 
19    121645100408832000 
20    2432902008176640000 
21    51090942171709440000 
22   1124000727777607680000 
23   25852016738884978212864 
24   620448401733239409999872 
25  15511210043330986055303168 
26  403291461126605650322784256 
27 10888869450418351940239884288 
28 304888344611713836734530715648 
29 8841761993739700772720181510144 

Если вы хотите, чтобы вычислить точное значение 100! вам нужно использовать массивы цифр (ака bignums), чтобы сделать расчеты. Вы можете либо найти библиотеку bignum для использования, либо реализовать бинарное умножение самостоятельно. Статья Википедии о бонусах предоставляет pseudocode для расчета факториалов.

Answer 2

Вот что может помочь. Предположим, у вас есть номер 2356. Как вы можете добавить его цифры. Ну, вы можете извлечь наименее значащую цифру, добавить ее к результату и выбросить (правую смену). Вы извлекаете наименьшую цифру, принимая номер мод 10. Вы меняете делением на 10. Таким образом, 2356 mod 10 = 6 и 2356/10 = 235.

Принимая моду легко, вы просто просматриваете номера в своем продукте , модифицировать их и умножить моды вместе. Например, 12 * 6 mod 10 = (12 mod 10) * (6 mod 10) = 2 * 6 = 12, а затем взять один последний мод в конце: 12 mod 10 = 2. Если вы должны были сделать это, умножив 12 * 6 вы получите 72, равный 2 мод 10.

Твердая часть делится на 10. Теперь, если произведение содержит кратное 10 (например, 100), вы делите это число на 10, и вы сделанный. Если такого номера нет, вы все равно можете разделить на 10, но это наверняка испортит результаты. Поэтому, если вы можете найти, как это сделать, вы можете решить проблему без реализации BIGNUM.Если нет, то это тоже не так сложно, вам нужно только реализовать функцию, чтобы добавить два BIGNUM вместе (умножение - это просто повторное добавление).

Answer 3

Как уже упоминалось, вы можете либо написать свою собственную библиотеку bignum для этого (используя массивы байтов), либо вы можете использовать что-то вроде реализации OpenSSL BIGNUM.

Вот версия функции факта OpenSSL (скомпилирована с gcc main.c -lcrypto практически на любой дистрибутив). Вам просто нужно включить <openssl/bn.h>.

BIGNUM* fact (unsigned long n, BN_CTX* ctx) { 

    BIGNUM *mult, *i, *one; 

    mult = BN_new(); 
    i = BN_new(); 
    one = BN_new(); 

    BN_one(one); 

    BN_set_word(mult, 1L); 
    BN_set_word(i, n); 


    while (BN_cmp(i, one) >= 0) { 
     BIGNUM *a, *b; 

     a = BN_new(); 
     b = BN_new(); 

     BN_mul(a, i, mult, ctx); 

     BN_sub(b, i, one); 

     BN_free(mult); 
     BN_free(i); 
     mult = a; 
     i = b; 
    } 

    BN_free(one); 
    BN_free(i); 

    return mult; 
} 

При том, что вы можете использовать BN_bn2bin для создания строкового представления этого числа, которые вы можете использовать, чтобы вычислить сумму цифр.

Answer 4

#include <stdio.h> 
#include <stdlib.h> 

typedef unsigned char byte; 

int main(){ 
    size_t size =16;//initial size 
    size_t temp, len; 
    byte *n = malloc(size); 
    byte i, carry = 0; 
    *n = 1; 
    len = 1; 

    for(i=2;i<=100; ++i){ 
     size_t k; 
     for(k = 0; k < len; ++k){ 
      if(k == size){ 
       n = realloc(n, size*=2);//expand, check omitted 
      } 
      temp = n[k] * i + carry;//Calculation is performed on the promoted to int 
      carry = (temp >= 10) ? temp/10 : 0;//or simply temp/10 
      n[k] = temp % 10; 
     } 
     while(carry){ 
      if(k == size){ 
       n = realloc(n, size*=2); 
      } 
      temp = carry; 
      carry = (temp >= 10) ? temp/10 : 0; 
      n[k++] = temp % 10; 
      ++len; 
     } 
    } 
    temp = 0; 
    while(len){ 
     printf("%u", n[--len]); 
     temp += n[len]; 
    } 
    puts(""); 
    printf("sum=%zu\n", temp); 
    free(n); 

    return 0; 
} 
#if 0 
anticipate in advance the required size 
100! = 1*2*...99*100 
size > (log(1)+log(2)+...log(99)+log(100))/log(10) 
(∫1->100 log(x)dx)/log(10) 
f(x)=log(x) => F(x)=x(log(x)-1)+C 
(∫1->101 log(x)dx)/log(10) = (101*log(101)-101+1)/log(10) ≒ 159.00.. 
160 digits are sufficient. 
http://en.wikipedia.org/wiki/Stirling%27s_approximation 
log10(n!)≒log10(√(2nπ)(n/e)^n)=log10(√(2nπ))+nlog10(n/e)=157.9696.. 
size=158 
#endif