我有很多几百字节长的大数。如何有效地将这些数字从base-256转换为base-255，使数字最多增加一个字节，但在任何输出字节中不使用值（或数字）0xFF？（我已经编写了一个通用的解决方案，但它的复杂度为O（n*n），因为每个输入数字都会影响许多输出数字。）在将长数字从256进制转换为255进制，然后再转换回来时，有没有捷径或特殊情况？
ht4b089n1#
为了加快速度，你需要考虑更大的基数。第一步是将原始“基数256”转换为“基数1〈〈32”或“基数1〈〈64”（取决于你的CPU是什么）。这将数字中的位数减少了4倍（或8）。如果字节顺序（“字节顺序”）兼容，并且“字节长度”是8的倍数（这在早期代码中应该很容易确保）这可能不涉及实际执行任何操作（类型转换和源代码中严格的别名规则会带来一些麻烦，使机器代码变为零字节）。以相关的方式;可以先转换为“base 255255 * 255 * 255”，而不是直接转换为“base 255”;然后将每个“大数字”拆分为一对较小的“基数255255”数字，再将它们拆分为较小的“基数255”数字。这种拆分使用SIMD（同时拆分多个数字）可以非常快。这些变化应该会使它快16倍。本质上，如果你的除法算法是“O（nn）”，它将变成“O（n/4 * n/4）”或“O（nn/16）"。当然，“O（nn/16）”被认为是与“O（nn）”相同的，尽管快了很多。
1条答案
按热度按时间ht4b089n1#
为了加快速度，你需要考虑更大的基数。
第一步是将原始“基数256”转换为“基数1〈〈32”或“基数1〈〈64”（取决于你的CPU是什么）。这将数字中的位数减少了4倍（或8）。如果字节顺序（“字节顺序”）兼容，并且“字节长度”是8的倍数（这在早期代码中应该很容易确保）这可能不涉及实际执行任何操作（类型转换和源代码中严格的别名规则会带来一些麻烦，使机器代码变为零字节）。
以相关的方式;可以先转换为“base 255255 * 255 * 255”，而不是直接转换为“base 255”;然后将每个“大数字”拆分为一对较小的“基数255255”数字，再将它们拆分为较小的“基数255”数字。这种拆分使用SIMD（同时拆分多个数字）可以非常快。
这些变化应该会使它快16倍。本质上，如果你的除法算法是“O（nn）”，它将变成“O（n/4 * n/4）”或“O（nn/16）"。当然，“O（nn/16）”被认为是与“O（nn）”相同的，尽管快了很多。