Могу ли я использовать long double для вычисления целых чисел в языке c - PullRequest
Новая
       37

Могу ли я использовать long double для вычисления целых чисел в языке c

0 голосов
/ 20 ноября 2018

Я пытаюсь написать функцию факториала для вычисления большого числа (factorial (105)), его результат имеет 168 цифр, поэтому используйте long double, но, похоже, это ошибка, не может ли она так использоваться? 

#include <stdio.h>

long double factorial(long double n,long double base = 1){
  if (n <= 1){
    return 1*base;
  }else{
    return factorial(n-1,n * base);
  }
}  
int main(){  
    printf("%.0Lf\n",factorial(25));     // this result is correct

    printf("%.0Lf\n",factorial(26));    
    //correct result is 403291461126605635584000000,but it return 403291461126605635592388608
    return 0;
}

Ответы [ 3 ]

0 голосов
/ 20 ноября 2018

Во-первых, никто не знает, что long double может или не может представлять. Конкретные свойства формата зависят от реализации.

Во-вторых, формат с плавающей точкой с расширенной точностью X86 имеет 64-битное значение с явным начальным значением 1, что означает, что он может представлять непрерывные целые числа в диапазоне ± 2 64 . За пределами этого диапазона представимые целые числа не являются смежными (то есть они начинают «пропускать» с более широкими и более широкими пробелами). Ваши факториалы выходят далеко за пределы этого диапазона, а это значит, что вполне ожидаемо, что они не будут точно представлены.

0 голосов
/ 20 ноября 2018

С 105! огромное число, которое не помещается ни в одно слово (или в два из них), вам нужна арифметика произвольной точности , также известная как bignum s.Используйте приближение Стирлинга , чтобы понять, насколько велика 105!и прочитайте вики-страницу на факториалах .

Стандарт C (прочитайте n1570 , чтобы проверить) не имеет родных бигнумов, но вы найдете много библиотек для этого.

Я рекомендую GMPlib .Кстати, часть кода написана от руки для повышения производительности (при добавлении кода bignum вы хотите воспользоваться add with carry машинными инструкциями).

Я рекомендую избегать написанияваши собственные операции bignum.Существующие библиотеки используют очень умные алгоритмы (и вам нужно заставить некоторых докторов работать, чтобы получить что-то лучше).Если вы попробуете написать свою собственную библиотеку bignum, она, вероятно, будет намного хуже, чем у конкурентов (если вы не потратите годы работы).

0 голосов
/ 20 ноября 2018

Обратный расчет конверта: 25! чуть больше 10 25 ; три порядка - это примерно 10 бит, так что вам потребуется примерно 83 бита мантиссы, даже для точного представления результата.

Учитывая, что long double на платформах, которые его поддерживают, обычно составляет 80 бит для всего значения (не только мантиссы!), Очевидно, у вас нет мантиссы, достаточной для выполнения этих вычислений такого порядка с целочисленной точностью.

Однако : факториал здесь немного волшебен, так как многие из факторов содержат степени двойки, которые просто добавляют двоичные нули справа, которые не требуют мантиссы (они заканчиваются в показателе степени) , В частности: 

25! = 2   4   2   8   2    4    2    16    2    4     2    8    = 2²² · m
        3   5 3 7   9 5 11 3 13 7 15    17 9 19 5 21 11 23 3 25

(m - произведение всех не-2 факторов, а именно m = 3 10 · 5 6 · 7 3 · 11 2 · 13 · 17 · 19 · 23, поэтому данные, которые мы должны хранить в мантиссе)

Следовательно, наша первоначальная оценка превышает фактические требования на 22 бита.

Оказывается,

log 2 (f) = 10 · log 2 3 + 6 · log 2 5 + 3 · log 2 7 + 2 · журнал 2 11 + журнал 2 13 + журнал 2 17 + журнал 2 19 + журнал 2 23 = 61,68

что на самом деле чуть меньше размера мантиссы 80-битной двойной (64-битной) длины. Но когда вы умножаете его на 26 (то есть, исключая множитель 2, который заканчивается в показателе степени на 13), вы добавляете log2 (13) = 3,7 бита. 61,7 + 3,7 - это 65,4, поэтому с 26 далее у вас больше нет точности, чтобы точно выполнить расчет.

...