优化大型乘法 C++ 的模

Question

我正在尝试使我的程序更快地处理大数与模的乘法。这是我当前的代码：

#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    long multiply = 1;
    char x;
    while ( (x = getchar()) != '\n' )
    {
        multiply = (multiply*(x-64))%26;
    }
    if (multiply < 10)
        printf("0%d\n", multiply);
    else
        printf("%d\n", multiply);
    return 0;
}

Answer 1

（首先，我得到一个警告，因为你使用符号 %d 来打印 long，可能你可以只使用 int 并且它不会有什么不同因为最大值是 26。）

我认为您可以通过使用无符号整数类型来提高速度，因为对于无符号整数，模运算要简单一些。（仅通过查看生成的程序集很难确定...https://goo.gl/LAc42f）

Answer 2

我猜 getchar 是您的瓶颈。您可以尝试一次阅读更大的块：

#include <cstdio>
#include <cctype>

#define BUFFER  2048
#define OFFSET  ('A' - 1)
#define MODULUS 26

using namespace std;

int main()
{
    char buffer[BUFFER];
    int count, done = 0, multiply = 1;
    while (!done && (count = fread(buffer, sizeof(char), BUFFER, stdin)))
    {
        for (int i = 0; i < count; i++)
        {
            if (isupper(buffer[i]))
            {
                multiply *= (buffer[i] - OFFSET);
                multiply %= MODULUS;
            }
            else
            {
                done = 1;
                break;
            }
        }
    }
    printf("%02d\n", multiply);
    return 0;
}

还修复了 printf 并删除了幻数。它适用于测试用例。

注意一点，如果模运算后得到的结果为零，那么继续下去就没有意义了，因为之后你的乘积将永远为零，所以你可以在那里做一个快捷方式：

#include <cstdio>
#include <cctype>

#define BUFFER  2048
#define OFFSET  ('A' - 1)
#define MODULUS 26

using namespace std;

int main()
{
    char buffer[BUFFER];
    int count, done = 0, multiply = 1;
    while (!done && multiply && (count = fread(buffer, sizeof(char), BUFFER, stdin)))
    {
        for (int i = 0; multiply && i < count; i++)
        {
            if (isupper(buffer[i]))
            {
                multiply *= (buffer[i] - OFFSET);
                multiply %= MODULUS;
            }
            else
            {
                done = 1;
                break;
            }
        }
    }
    printf("%02d\n", multiply);
    return 0;
}

分块阅读和快捷方式优化可能是您克服时间限制所需要的。

优化大型乘法 C++ 的模

Optimizing Modulo of Large Multiplication C++

c++

multiplication

modulo