Mod C++ 中的两个大数

Question

我有一个名为 LargeNum 的 class，它按数组存储大量数字，例如 digit[]。因为int不够大，放不下。

基数是10000，所以数字'9876 8764 7263'的存储方式是：

digit[4] = {9876, 8764, 7263};

（基数可以改成10或100，如digit[12] = {9,8,7,6,8,7,6,4,7,2,6,3}）

问题是我想重载运算符%，这样我就能得到两个大数的余数。大数之间的重载运算符*、-是通过处理大数的每一位来完成的。但我真的不知道如何使用 % 来做到这一点。喜欢：

{1234,7890,1234} % {4567,0023}

谁能帮帮我？

Answer 1

伪代码应该是：

while digits_source > digits_base {
    while first_digit_source > first_digit_base {
        source -= base << (digits_source - digits_base)
    }

    second_digit_source += first_digit_source * LargeNum.base
    first_digit_source = 0
    digits_source--
}

while (source >= base) {
    source -= base
}

return source

这个要利用你的"digits"的大号。

编辑：为简单起见，我假设数组中的一个数字可以包含（从数字上讲）两个数字。如果不能，那么代码会变得非常棘手，因为你不能做 second_digit_source += first_digit_source * LargeNum.base

编辑：

关于示例操作（基数 = 10000）

{65,0000,0099} % {32,0001}

由于65>32，则继续做：

65 - 32 = 33
0 - 1 = -1

然后我们有 {33, -1, 99} % {32, 1}。再次进行

33 - 32 = 1
-1 - 1 = -2

我们有 {1, -2, 99} % {32, 1}。因为 32 > 1，所以我们加入源的前两位数字，得到 {1*1000 - 2, 99} % {32, 1}。现在我们可以进入简单的 while，只需执行减号操作即可。 while 对 source >= base 进行了全面比较，因为我们不能承受负数。但是，在算法的第一部分我们可以，因为我们保证前两个数字的组合将为正数。

Mod C++ 中的两个大数

Mod of two large numbers in C++

c++

overloading

operator-keyword