大整数，我知道理论...在实践中仍然生锈 [英] Big Integer addition, I know the theory... still rusty in practice

问题描述

所以，我正在尝试建立一个简单的大整数类，我已经阅读了互联网上的一些页面以及所有内容，但是我陷入了困境。我知道理论，我知道我需要一个进位，但是我所看到的所有例子，它们都以字符和以10为基数出现，因此，我正在使用一种不同的方法来使其更快一些。我希望对plus赋值运算符有所帮助，其余的我会自己解决。

so, I'm trying to build a simple big integer class, I've read some pages on the internet and all that, but I'm stuck. I know the theory and I know that I need a carry but all examples I've seen, they focuded more in chars and in base 10 and well, I'm using a different approach to make it a bit more faster. I would appreciate some help with the plus assignment operator, the rest of it I'll try to figure it out by myself.

#include <iostream>
#include <string>
#include <vector>

using std::cout;
using std::endl;

class big_integer {
    using box = std::vector<int unsigned>;
    box data {0};

    box split(std::string const & p_input) const {
        box output;
        for (size_t i {}; i < p_input.size(); i += 8) {
            output.push_back(stoi(p_input.substr(i, 8)));
        }
        return output;
    }

public:
    big_integer(std::string const & p_data)
        : data {split(p_data)}
    {}

    big_integer(int unsigned const p_data)
        : data {p_data}
    {}

    big_integer & operator +=(big_integer const & p_input) {
        int carry {};

        for (size_t i {}; i < data.size(); ++i) {

            //Need help here!
            //All examples I see either use primitive arrays
            //or are too esoteric for me to understand.             
            //data[i] += p_input.data[i] + carry;

        }

        return *this;
    }

    std::string to_string() const {
        std::string output;
        output.reserve(data.size() * 8);
        for (auto const i : data) {
            output.append(std::to_string(i));
        }
        return output;
    }
};

std::ostream & operator <<(std::ostream & p_output, big_integer const & p_input) {
    return p_output << p_input.to_string();
}

int main() {
    big_integer test1 {"126355316523"};
    big_integer test2 {255};

    test1 += test1;

    cout << test1 << endl;
    cout << test2 << endl;
    return 0;
}

推荐答案

正确。因此，基本问题是如何执行 unsigned + unsigned + carry 来赋予 unsigned 和 carry 。如果我们考虑16位整数（32位工作原理相同，但键入更多），则在第一个数字上为0xFFFF + 0xFFFF == 0xFFFE +一个进位1。在随后的数字0xFFFF + 0xFFFF +进位== 0xFFFF +进位因此，进位只能是一个。算法为：

Right. So the basic problem is how to do unsigned + unsigned + carry to give unsigned and carry. If we consider 16-bit integers (it works the same in 32-bits, but is more typing), on the first digit, 0xFFFF + 0xFFFF == 0xFFFE + a carry of 1. On subsequent digits 0xFFFF + 0xFFFF + carry == 0xFFFF + carry. Hence carry can only be one. The algorithm is:

    unsigned lhs, rhs, carry_in;  // Input
    unsigned sum, carry_out;      // Output

    sum = lhs + rhs;
    carry_out = sum < lhs ;
    sum += carry_in;
    carry_out = carry_out || sum < lhs;

基本上，这个想法是在 unsigned ，然后检测换行（并因此进行进位）。非常令人讨厌的是，这是大量的条件逻辑和多个指令来实现加进位加法，这是我使用过的每条指令集中的一条指令。 （注意：使用 | 而不是 |来进行 carry_out 的最终计算可能是值得的。 | -保存分支，这对性能不利。像往常一样，通过配置文件查看它是否有帮助。）

Basically, the idea is to do the addition in unsigned, and then detect wrapping (and hence carry). What is very annoying, is that this is masses of conditional logic and multiple instructions to implement "add with carry", which is an instruction in every instruction set I have ever used. (Note: it may be worth making the final calculation of carry_out use | rather than || - it saves branching, which is bad for performance. As always, profile to see if it helps.)

如果您要最终支持乘法，您需要的宽度是数字的两倍-在这种情况下，您也可以将其用于加法。使用上面的变量，并假设 unsigned long long是您的宽类型：

If you are going to eventually support multiplication, you need a type which is twice as wide as your "digit" - in which case, you might as well use it for addition too. Using the variables from above, and assuming "unsigned long long" is your "wide" type:

    const auto temp = (unsigned long long)lhs + rhs + carry_in;
    sum = temp; // Will truncate.
    carry_out = temp > UINT_MAX;

选择宽类型可能很棘手。首先，最好使用 uint32_t 作为数字， uint64_t 作为宽字体。

Choosing your "wide" type can be tricky. As a first pass, it's probably best to use uint32_t for your digits and uint64_t for your wide type.

有关实现多精度算术的更多详细信息，请应用密码学手册的第14章看起来很有用。

For more details on implementing multi-precision arithmetic, Chapter 14 from Handbook of Applied Cryptography looks useful.

这篇关于大整数，我知道理论...在实践中仍然生锈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！