C语言 为什么这个阶乘算法不准确

yk9xbfzb  于 2023-03-17  发布在  其他
关注(0)|答案(5)|浏览(224)

对不起,我觉得问这个问题很愚蠢,我准备失去我一半的分数,但为什么这个算法不工作?它工作到一个点。在数字13之后的阶乘有点偏离。例如,数字不完全匹配在几十万位和以后。

#include <stdio.h>

float factorial(unsigned int i) {

    if (i <= 1) {
        return 1;
    }
    return i * factorial(i - 1);
}

int  main() {
    int i = 13;
    printf("Factorial of %d is %f\n", i, factorial(i));
    return 0;
}

下面是输出:

Factorial of 13 is 6227020800.000000

以下是不准确输出的示例:

Factorial of 14 is 87178289152.000000

数字14的输出实际上应该是这样的(来自mathisfun.com)
14 87,178,291,200
我将返回类型更改为float以获得更精确的输出,但我主要是从这里获得以下代码的:https://www.tutorialspoint.com/cprogramming/c_recursion.htm

**编辑:**如果将返回类型更改为double,则输出的精度最高可达21。我在 printf 函数中使用 %Lf 字符串格式化程序作为输出。

gijlo24d

gijlo24d1#

Simple. float无法在不损失精度的情况下准确存储大于16777216的整数。
int比float更好。但是尝试long long,这样你就可以正确地存储19位数。

svmlkihl

svmlkihl2#

float可以表示比int更宽的数字“范围”,但它不能表示该范围内的所有值--当你接近范围的边缘时(即,随着值的大小增加),可表示值之间差距会变大。
例如,如果不能表示0.123到0.124之间的值,那么也不能表示123.0到124.0、1230.0到1240.0、12300.0到12400.0等之间的值(当然,IEEE-754单精度floatthat 提供的精度要高一些)。
话虽如此,float应该能够精确地表示所有最大为224的整数值,所以我敢打赌问题出在printf调用中-float参数被“提升”为double,因此涉及到表示法的更改,这可能是精度损失的原因。
尝试将factorial的返回类型更改为double,看看是否有帮助。

〈无端的咆哮〉

每当我看到递归阶乘函数时,我都想大叫一声,在这个特定的例子中,递归在代码清晰度和性能方面都没有比迭代解法更好的地方:

double fac( int x )
{
  double result = 1.0;
  while ( x )
  {
    result *= x--;
  }
  return result;
}

并且实际上由于如此多的函数调用的开销而导致“更差”的性能。
是的,阶乘的 * 定义 * 是递归的,但是阶乘函数的 * 实现 * 不一定是递归的。斐波那契数列也是如此。甚至斐波那契数也有一个 * 封闭形式 * 的解

Fn = ((1 + √5)n - (1 - √5)n) / (2n * √5)

一开始就不需要任何循环。
递归对于将数据划分为相对较少的、大小相等的子集的算法(快速排序、树遍历等)来说是很好的。对于这样的算法,如果划分是1个元素的N-1个子集,那么递归就不那么好了。

〈/无端的咆哮〉

rhfm7lfc

rhfm7lfc3#

OP遇到float的精度限制。对于typical float,大于16777216.0f的整数值并非全部都可精确表示。* 高于此点的某些 * 阶乘结果可精确表示。
让我们用不同的类型来试试这个。
11!处,float结果超过16777216.0f,并且完全正确。
14!中,float结果不精确,因为 * 精度 * 有限。
23!中,double结果不精确,因为 * 精度 * 有限。
22!,答案超出了我的uintmax_t * 范围 *。(64位)
35!,答案超出了我的float * 范围 *。
171!,答案超出了我的double * 范围 *。

  • string* 表示法在达到缓冲区限制之前一直是准确的。
#include <stdint.h>
#include <string.h>
#include <stdio.h>

uintmax_t factorial_uintmax(unsigned int i) {
  if (i <= 1) {
    return 1;
  }
  return i * factorial_uintmax(i - 1);
}

float factorial_float(unsigned int i) {
  if (i <= 1) {
    return 1;
  }
  return i * factorial_float(i - 1);
}

double factorial_double(unsigned int i) {
  if (i <= 1) {
    return 1;
  }
  return i * factorial_double(i - 1);
}

char * string_mult(char *y, unsigned base, unsigned x) {
  size_t len = strlen(y);
  unsigned acc = 0;
  size_t i = len;
  while (i > 0) {
    i--;
    acc += (y[i] - '0') * x;
    y[i] = acc % base + '0';
    acc /= base;
  }
  while (acc) {
    memmove(&y[1], &y[0], ++len);
    y[0] = acc % base + '0';
    acc /= base;
  }
  return y;
}

char *factorial_string(char *dest, unsigned int i) {
  strcpy(dest, "1");
  for (unsigned m = 2; m <= i; m++) {
    string_mult(dest, 10, m);
  }
  return dest;
}

void factorial_test(unsigned int i) {
  uintmax_t u = factorial_uintmax(i);
  float f = factorial_float(i);
  double d = factorial_double(i);
  char s[2000];
  factorial_string(s, i);
  printf("factorial of %3d is uintmax_t: %ju\n", i, u);
  printf("                    float:     %.0f %s\n", f, "*" + (1.0 * f == u));
  printf("                    double:    %.0f %s\n", d, "*" + (d == u));
  printf("                    string:    %s\n", s);
}

int main(void) {
  for (unsigned i = 11; i < 172; i++)
    factorial_test(i);
  return 0;
}

产出

factorial of  11 is uintmax_t: 39916800
                    float:     39916800 
                    double:    39916800 
                    string:    39916800
factorial of  12 is uintmax_t: 479001600
                    float:     479001600 
                    double:    479001600 
                    string:    479001600
factorial of  13 is uintmax_t: 6227020800
                    float:     6227020800 
                    double:    6227020800 
                    string:    6227020800
factorial of  14 is uintmax_t: 87178291200
                    float:     87178289152 *
                    double:    87178291200 
                    string:    87178291200
factorial of  20 is uintmax_t: 2432902008176640000
                    float:     2432902023163674624 *
                    double:    2432902008176640000 
                    string:    2432902008176640000
factorial of  21 is uintmax_t: 14197454024290336768
                    float:     51090940837169725440 *
                    double:    51090942171709440000 *
                    string:    51090942171709440000
factorial of  22 is uintmax_t: 17196083355034583040
                    float:     1124000724806013026304 *
                    double:    1124000727777607680000 *
                    string:    1124000727777607680000
factorial of  23 is uintmax_t: 8128291617894825984
                    float:     25852017444594485559296 *
                    double:    25852016738884978212864 *
                    string:    25852016738884976640000
factorial of  34 is uintmax_t: 4926277576697053184
                    float:     295232822996533287161359432338880069632 *
                    double:    295232799039604119555149671006000381952 *
                    string:    295232799039604140847618609643520000000
factorial of  35 is uintmax_t: 6399018521010896896
                    float:     inf *
                    double:    10333147966386144222209170348167175077888 *
                    string:    10333147966386144929666651337523200000000
factorial of 170 is uintmax_t: 0
                    float:     inf *
                    double:    72574156153079940453996357155895914678961840000000... *
                    string:    72574156153079989673967282111292631147169916812964...
factorial of 171 is uintmax_t: 0
                    float:     inf *
                    double:    inf *
                    string:    12410180702176678234248405241031039926166055775016...
uurity8g

uurity8g4#

正如其他答复中所解释的那样,这与可用的不同类型数字的范围和精度有关。
可以使用字符数组(字符串)来表示数字并获得精确值。例如:

/* Fact50.c -- display a table of factorials from 0! to 50! */

#include <stdio.h>

#define NUMBER      50
#define LEN         65

int multiply(int n, char fact[], int limit)
{
    int carry = 0;
    for (int i = LEN - 1; i >= limit; --i) {
        int product = (fact[i] - '0') * n + carry;
        fact[i] = product % 10 + '0';
        carry = 0;
        if (product > 9) {
            carry = product / 10;
            if (i == limit) {
                --limit;
                fact[limit] = '0';
            }
        }
    }

    return limit;
}

int main (void)
{
    printf("\n"
           "                           Table of Factorials\n"
           "\n");

    char fact[] = "................................................................1";

    printf("%2d! = %s\n", 0, fact);
    printf("%2d! = %s\n", 1, fact);

    int limit = LEN - 1;
    for (int n = 2; n <= NUMBER; ++n) {
        limit = multiply(n, fact, limit);
        printf("%2d! = %s\n", n, fact);
    }

    return 0;
}
hvvq6cgz

hvvq6cgz5#

为什么这个阶乘算法不准确
algorithm本身并没有什么问题。只是您使用的数据类型对它们可以存储的最大数量有限制。无论您选择哪种算法,这都会是一个问题。您可以将数据类型从float更改为类似long double的数据类型,以存储更大的数据。但最终,一旦阶乘值超过了该数据类型的容量,它仍然会开始失败。在我看来,你应该在阶乘函数中放置一个a条件,如果传入的参数大于你选择的数据类型所能支持的值,则不进行任何计算而返回。

相关问题