在不使用乘法的情况下获取数字的阶乘

Question

我需要在不使用乘法运算符的情况下计算一个数的阶乘。因为这个限制，我直接尝试使用重复加法。有点管用。但是，我的程序正在努力获取更大数字的阶乘。有没有更好的方法解决问题？

这是我的代码：

void main(){
     unsigned long num = 0, ans = 1, temp = 1;

    printf("Enter a number: ");
    scanf("%lu", &num);

    while (temp <= num){
        int temp2 = 0, ctr = 0;
        while (ctr != temp){
            temp2 += ans;
            ctr ++;
        }
        ans = temp2;
        temp ++;
    }

    printf("%lu! is %lu\n", num, ans);
}

Answer 1

您可以使用位移位和加法实现更快（比重复加法）的乘法函数以执行二进制“长乘法”。

unsigned long long mul_ull(unsigned long long a, unsigned long long b)
{
    unsigned long long product = 0;
    unsigned int shift = 0;

    while (b)
    {
        if (b & 1)
        {
            product += a << shift;
        }
        shift++;
        b >>= 1;
    }
    return product;
}

编辑：使用单个位移位和加法实现上述的替代实现：

unsigned long long mul_ull(unsigned long long a, unsigned long long b)
{
    unsigned long long product = 0;

    while (b)
    {
        if (b & 1)
        {
            product += a;
        }
        a <<= 1;
        b >>= 1;
    }
    return product;
}

实际上，这是否比重复添加更快取决于编译器所做的任何优化。优化编译器可以分析重复的加法并将其替换为乘法。优化编译器还可以分析上面 mul_ull 函数的代码并将其替换为乘法，但优化器可能更难发现。所以在实践中，重复加法算法比优化后的位移加法算法结束得更快是完全合理的！

此外，如果第二个参数 b 是被相乘的数字中较小的一个，而其中一个数字远大于另一个（对于阶乘计算是典型的）。执行时间大致与 b 的对数成正比（当 b 非零时），但也取决于 b 的二进制值中 1 位的数量。因此对于阶乘计算，将旧的运行乘积放在第一个参数 a 中，将新的因子放在第二个参数 b.

中

使用上述乘法函数的阶乘函数：

unsigned long long factorial(unsigned int n)
{
    unsigned long long fac = 1;
    unsigned int i;

    for (i = 2; i <= n; i++)
    {
        fac = mul_ull(fac, i);
    }
    return fac;
}

上面的 factorial 函数可能会由于算术溢出而产生不正确的结果 n > 20。需要66位才能表示21！但是 unsigned long long 只需要 64 位宽（这通常是大多数实现的实际宽度）。

Answer 2

对于 n 的大值，需要大格式。
由于您不能使用乘法，因此您必须自己实现它似乎合乎逻辑。
实际操作中，只需要加法，如果不是追求高效率的话，实现起来也不是那么困难。

无论如何有点困难：您必须将输入的整数转换为数字数组。由于我猜不允许取模，我在 snprintf 函数的帮助下实现了它。

结果：

100! is 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

注意：此结果几乎是即时提供的。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NDIGITS     1000        // maximum number of digits

struct MyBig {
    int digits[NDIGITS + 2];        // "+2" to ease overflow control
    int degree;
};

void reset (struct MyBig *big) {
    big->degree = 0;
    for (int i = 0; i <= NDIGITS; ++i) big->digits[i] = 0;
}

void create_with_div (struct MyBig *big, int n) {  // not used here
    reset (big);
    while (n != 0) {
        big->digits[big->degree++] = n%10;
        n /= 10;
    }
    if (big->degree != 0) big->degree--;
}

void create (struct MyBig *big, int n) {
    const int ND = 21;
    char dig[ND];
    snprintf (dig, ND, "%d", n);
    int length = strlen (dig);
    
    reset (big);
    big->degree = length - 1;
    for (int i = 0; i < length; i++) {
        big->digits[i] = dig[length - 1 - i] - '0';
    }
}

void print (struct MyBig *big) {
    for (int i = big->degree; i >= 0; --i) {
        printf ("%d", big->digits[i]);
    }
}

void accumul (struct MyBig *a, struct MyBig *b) {
    int carry_out = 0;
    for (int i = 0; i <= b->degree; ++i) {
        int sum = carry_out + a->digits[i] + b->digits[i];
        if (sum >= 10) {
            carry_out = 1;
            a->digits[i] = sum - 10;
        } else {
            carry_out = 0;
            a->digits[i] = sum;
        }
    }
    int degree = b->degree;
    while (carry_out != 0) {
        degree++;
        int sum = carry_out + a->digits[degree];
        carry_out = sum/10;
        a->digits[degree] = sum % 10;
    }
    if (a->degree < degree) a->degree = degree;
    if (degree > NDIGITS) {
        printf ("OVERFLOW!!\n");
        exit (1);
    }
}

void copy (struct MyBig *a, struct MyBig *b) {
    reset (a);
    a->degree = b->degree;
    for (int i = 0; i <= a->degree; ++i) {
        a->digits[i] = b->digits[i];
    }
}

void fact_big (struct MyBig *ans, unsigned int num) {
    create (ans, 1);
    int temp = 1;
    while (temp <= num){
        int ctr = 0;
        struct MyBig temp2;
        reset (&temp2);
        while (ctr != temp){
            accumul (&temp2, ans);
            ctr ++;
        }
        copy (ans, &temp2);
        temp ++;
    }
    return;
}

unsigned long long int fact (unsigned int num) {
    unsigned long long int ans = 1;
    int temp = 1;
    while (temp <= num){
        int ctr = 0;
        unsigned long long int temp2 = 0;
        while (ctr != temp){
            temp2 += ans;
            ctr ++;
        }
        ans = temp2;
        temp ++;
    }
    return ans;
}

void main(){
    unsigned long long int ans;
    unsigned int num;
    
    printf("Enter a number: ");
    scanf("%u", &num);
    
    ans = fact (num);
    printf("%u! is %llu\n", num, ans);
    
    struct MyBig fact;
    fact_big (&fact, num);
    printf("%u! is ", num);
    print (&fact);
    printf ("\n");
}

在不使用乘法的情况下获取数字的阶乘

Get the factorial of a number without using multiplication

c

factorial