c++ - 如何优化将无符号任意精度整数转换为字符串以进行打印？

Question

我正在研究 C++ 中的无符号任意精度整数类，作为我自己的练习。在运行一些基准测试（计算某个数字的斐波那契数列）时，我注意到将我的类转换为字符串以进行打印大约占用了总运行时间的 40%。目前，我正在使用传统的小学方法将整数连续除以 10 以获得可打印的字符串，并且想知道是否有更快的方法。

我曾尝试实施 Newton-Raphson 部门，但即使使用我的 Karatsuba 实施，它仍然比传统方法慢得多。

我目前的想法是生成具有足够精度的数字 0.1，以便我可以用乘法运算代替除法运算。当然，这种方法在尝试打印大数字时会导致舍入错误。我的一个测试的一个例子：

Print test:   11111111112345678906735299999996
My old print: 11111111112345678906735300000000

以下是我的问题：

1. 有没有办法知道计算 0.1 需要多少精度，这样当我将它乘以我要打印的数字时，它不会有明显的舍入误差？即当转换回整数时，舍入误差将被移走。
2. 在处理任意精度时，是否有其他方法可以优化常数除法？在我看来，我可能会找到某种方法来将这种乘法方法用于最高有效位，并将小学方法用于最低有效位，但我怀疑运行时的回报是否会显着。

注意：我将整数存储为 anstd::vector<bool>并且正在使用-O3优化标志。这方面的任何信息都会有很大帮助！提前致谢。

编辑：创建这个类时我最初的想法是保持它相当基本。即因为内存中的整数只是一个位数组，那么这就是我存储位的方式。存储是相当不言自明的，如果arr是我的向量，则arr[0]表示 2^0，并且arr[1]是 2^1，依此类推。

对于任何想知道的人来说，我最初对 to_string 的丑陋实现：

std::string uInt::to_string() const {
    if (*this == ZERO) return std::string("0");
    uInt n(*this), mod;
    std::string result("");
    while (n != ZERO) {
        std::pair<uInt, uInt> div_mod_result = n.div_and_mod(TEN);
        mod = div_mod_result.second;
        n = div_mod_result.first;
        if (mod == ZERO)
            result = '0' + result;
        else if (mod == ONE)
            result = '1' + result;
        else if (mod == TWO)
            result = '2' + result;
        else if (mod == THREE)
            result = '3' + result;
        else if (mod == FOUR)
            result = '4' + result;
        else if (mod == FIVE)
            result = '5' + result;
        else if (mod == SIX)
            result = '6' + result;
        else if (mod == SEVEN)
            result = '7' + result;
        else if (mod == EIGHT)
            result = '8' + result;
        else if (mod == NINE)
            result = '9' + result;
        else {
            throw std::runtime_error("ERROR: To String Failed");
        }
    }
    return result;
}

我的定点尝试：

std::string uInt::to_string() const {
    if (this->bits.empty()) return std::string("0");
    uint64_t precision = this->bits.size(); // Unsure what precision would be necessary
    one_over_ten = uInt::get_one_over_ten(precision);
    mask = (ONE << precision) - ONE;
    uInt n(*this), mod;
    std::string result("");
    while (n.bits.size()) {
        floating_point_result = n * one_over_ten; // Leaves me with n/10 with precision fraction bits
        mod = ((floating_point_result & mask) * TEN) >> precision; // Extracts the fraction
                                                                   // bits, multiplies by ten,
                                                                   // then converts to an integer
        n = floating_point_result >> precision; // Turns n back into an integer
        /* Same if chain as before */
    }
    return result;
}

希望这能更好地解释我一直在尝试的事情。

标签： c++integer-divisionunsigned-integerarbitrary-precision