c-在不使用乘法的情况下获得一个数字的阶乘

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 %lun", 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是当数字中的一个比另一个大得多时所乘的数字中的较小者，则mul_ull函数的上述实现将倾向于执行得更好(对于阶乘计算而言是典型的(。执行时间大致与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;
}

对于CCD_ 10>，上述CCD_；20由于算术溢出。需要66位来表示21！但是CCD_ 11仅需要64位宽(并且对于大多数实现来说这通常是实际宽度(。

编辑2023-06-07

对n的值具有相同限制的稍长的factorial()函数可以使用不到一半的乘法次数。此方法基于https://scicomp.stackexchange.com/q/425102023年3月21日编辑后。

unsigned long long factorial(unsigned int n)
{
unsigned long long fac;
unsigned int m;
unsigned int i;
if (n <= 1)
{
fac = 1;
}
else
{
if ((n & 1) == 0)
{
m = n;
n -= 2;
}
else
{
m = n + n;
n -= 3;
}
fac = m;
while (n > 0)
{
m += n;
fac = mul_ull(fac, m);
n -= 2;
}
}
return fac;
}

例如，它计算9！=18·24·28·30=362880，10！=10·18·24·28·30=3628800。

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 %llun", num, ans);

struct MyBig fact;
fact_big (&fact, num);
printf("%u! is ", num);
print (&fact);
printf ("n");
}