c++ - C++中两个大数的模数

Question

我有一个名为 LargeNum 的类，它按数组存储大数字，例如 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

这应该利用大数的“位数”。

编辑:为简单起见，我假设数组中的一个数字可以包含(从数字上讲)两个数字。如果不能，那么代码将变得非常棘手，因为您不能执行 second_digit_source += first_digit_source * LargeNum.base

---

编辑:

关于示例操作(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 进行了全面比较，因为我们不能承受负数。但是，在算法的第一部分我们可以，因为我们保证前两位数字的组合将为正数。