python - 将非常大的 n 基数转换为字节

Question

我在 n 基数中有一个非常大的数字(n 由用户指定)，存储为一个数组，每个元素代表一个数字。 u[0] 是最高位，u[1] 是次高位，u[-1] 是最低位等等在。前导零被理解为无意义:例如，如果 n 为 8，则 [0, 0, 0, 4, 7, 3] 等同于 [ 4, 7, 3] 并且都等于 8 进制的 (473)，或 10 进制的 315，或十六进制的 13B，或 [1, 59] 作为字节数组。

我想将其转换为一个字节数组，该字节数组与相同数字的 base-256 表示相对应，前导零最少。我有以下代码可以这样做:

def base_n_to_byte_array(digits, from_base):
    """ Converts a base n number to a byte array.

    :param digits: Digits of the number, starting from highest.
    :param from_base: Base in which the number is given.
    """

    x = 0
    n = len(digits)
    for i in range(0, len(digits)):
        x += digits[i] * int(math.pow(from_base, n - i - 1))

    min_length = max(math.ceil(math.log(x, 256)), 1)
    byte_array = x.to_bytes(min_length, byteorder='big')
    return byte_array

这适用于较小的数字(几百位)。然而，事实证明 math.pow 非常有限，例如，如果我们使用 8 进制，math.pow(8, 341) 是我可以获得的最高幂, 和 math.pow(8,342) 因 OverflowError: math range error 而失败。

我知道处理大数的常用方法是将它们表示为 float - 但在这种情况下，我使用此代码将二进制文件编码/解码为替代表示形式(例如 trytes)。因此，如果由于精度损失导致次要字节被更改，大量数据将被破坏，所以我不能使用近似功率计算 - 我需要准确的结果。

我该如何解决这个问题？有没有不会溢出的 math.pow 版本？有没有我忽略的更有效的碱基转换算法？

Answer 1

Is there a version of math.pow that doesn't overflow?

尝试使用内置的求幂运算符 **。据我所知，它没有 math.pow 那样的限制。

>>> math.pow(8,342)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: math range error

>>> 8**342
719077253944926363091722076315609893447190791576922629093720324630930703222003852530833909289630144084480455519485573430635159075257666489971389722557896497511071573699461941105208878404984376477812331808340023075352602729369851525895652442163308948653402042738345192959788983753918865219341425318496896548864L