对一个非常大的数进行取模运算

Question

如果无法使用模指数运算，你会如何对一个相当大的数字执行取模操作？

例如，考虑以下质数取模操作：

6864797660130609714981900799081393217269435300143305409394463459185543183
3976560521225596406614545549772963113914808580371219879997166438125740282
91115057151 % 4

WolframAlpha告诉我答案是3。这很好，但我想编写一个算法，使我的计算器应用程序也能处理它。

我假设对于这样一个大数字，我将把数字存储在一个数组中，每个数字占据一个元素。

- A. Esposito

---

你可以使用最后两位数字执行模4运算。51 % 4 - 因此更好的问题是，需要多少个最后数字才能确定模数。 - Nina Scholz

谢谢你，Nina。这很有帮助。 - A. Esposito

如果你只是想对4取模，这很有帮助。但对于其他许多数字来说，这并不是很有用。 - Parker Kemp

Answer 1

我没有足够的声望来发表评论，但是这两个人说你只能看最后几位数字是错误的，以%7为例 - 你总是要查看所有数字。

正如您可能知道的那样，(a+b)%n = (a%n + b%n) % n和(a*b)%n = (a%n * b%n) % n。使用这个公式，我们可以首先计算1%n、10%n、100%n等值，然后将这些值乘以您的数字中的每个数字，最后将它们全部加在一起。

我用C++写了它：

//assume we have number of length len in reversed order
//example: 123%9 -> n = 9, num[0] = 3, num[1] = 2; num[2] = 1, len = 3
int mod(int n, int num[], int len)
{
    int powersOf10modn = 1;
    int anwser = 0;
    for(int i = 0; i < len; i++)
    {
        anwser = (anwser + powersOf10modn * num[i]) % n;
        powersOf10modn = (powersOf10modn*10) % n;
    }
    return anwser;
}

- misztsu

---

评论中说，你可以使用最后两位数字执行模4运算。就像只需要最后一位数字执行模2运算一样。他并没有说模运算符总是只需要最后两位数字。 - Jim Mischel

这条评论暗示着你总是可以将这个问题简化为最后的n位数字，这显然是不正确的。 - Parker Kemp

Answer 2

如果你有一个这样的数字：xyz % n，你只需要做yz % n。 为了使你的操作表现最佳，你需要n％10 + 1个最后的数字。

- JSFnta

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Jim Mischel