Эффективный алгоритм для преобразования между системой счисления

Question

Есть ли эффективный алгоритм преобразования между системой счисления, когда размер исходного целого числа является произвольным?

Например, предположим, что существует целочисленный массив {1, 4, 8}, который в качестве входных данных равен 148 в десятичном формате. Он может быть преобразован в {9, 4} в шестнадцатеричном формате, или {2, 2, 4} в восьмеричном, или {1, 0, 0, 1, 0, 1, 0, 0} в двоичном формате, или просто {148} в 1234-м формате или что-то в этом роде.

Это просто, когда фактическое значение может быть выражено в формате слова, поддерживаемом машиной. Но когда дело доходит до произвольного размера, я не могу найти эффективный способ лучше, чем O(n^2).

Answer 1

Разделите на основание, отодвиньте модуль назад, промойте и повторите, пока коэффициент!= 0.

Так, например, конвертировать 148 в базу 16

148 / 16 = 9 r 4
  9 / 16 = 0 r 9

Итак, 148 в гексе - это 0x94. Это не должно занять так много времени.

Answer 2

Предположим, мы хотим преобразовать из базы в базу. Если и обе степени общего основанияbсказатьb1 = b^i1иb2 = b^i2то это можно сделать вO(n). В частности, это относится, например, к преобразованию между двоичными, восьмеричными, шестнадцатеричными,2^32,2^64и т. д. Это потому, что вы действительно просто перераспределяете биты. Рассмотрим биты цифр числа 3214 в восьмеричном и шестнадцатеричном виде:

      3214 = 12*16^2 + 8*16 + 14 = 6*8^3 + 2*8^2 + 1*8 + 6
     = {1100, 1000, 1110} base 16
     = {110, 010, 001, 110} base 8

Вы можете видеть, что это одни и те же биты, просто по-разному разделенные между цифрами в каждой базе. Нетрудно создать алгоритм, который преобразует одно в другое, используя битовые сдвиги и маски. То же самое относится и к преобразованию, например, из базы 9 в базу 27, за исключением того, что вы разделяете цифры базы 3, а не биты, а затем перемещаете их в разные сегменты.

Сейчас еслиb1иb2несоизмеримы, то это не так просто, но это все же можно сделать за субквадратичное время, используя подходы «разделяй и властвуй». Раздел 7.1 учебника [1] описывает алгоритмы 1.25 и 1.26 для преобразования базы. Презумпция этих алгоритмов заключается в том, что вы конвертируете в базу и из нее, которая используется для арифметики больших целых чисел (и что вы можете выполнять арифметику больших целых чисел в этой базе). Вы можете использовать это для реализации произвольного базового преобразования путем преобразованияb1 -> bigint -> b2хотя.

Здесь я продемонстрирую алгоритм 1.25 на Python, который естественным образом поддерживает арифметику больших целых чисел из коробки:

      # Algorithm 1.25:

def parse_int(S: str, B: int = 10) -> int:
    """parse string S as an integer in base B"""
    m = len(S)
    l = list(map(int, S[::-1]))
    b, k = B, m
    while k > 1:
        last = [l[-1]] if k % 2 == 1 else []
        l = [l1 + b*l2 for l1, l2 in zip(l[::2], l[1::2])]
        l.extend(last)
        b, k = b**2, (k + 1) >> 1
    [l0] = l
    return l0

Поскольку это сначала преобразует все символы вintсstrэта реализация будет работать только для оснований от 2 до 10, но если бы ввод был предоставлен в виде списка целых чисел, а не строки, тогда этот шаг не был бы необходим. Обратите внимание, что здесь в этом коде это не указано явно, ноl1 + b*l2иb**2нужно вычислять с помощью большой целочисленной арифметики. Здесь возвращается большое целое число.

Алгоритм 1.26 может преобразовать большое целое число в строку цифр по любому основанию. Простая реализация:

      # Algorithm 1.26:

def format_int(A: int, B: int = 10) -> str:
    """Format integer A as a string in base B"""
    if A < B:
        # Here we use str for the base case of a single digit but probably
        # there should be some cutoff for using an O(n^2) algorithm for
        # sufficiently small inputs.
        return str(A)
    else:
        # find k so that B**(2*k-2) <= A < B**(2*k)
        k = 1
        B2k = B2 = B**2
        while A > B2k:
            k += 1
            B2k *= B2
        if A == B2k:
            k += 1
        # assert B**(2*k - 2) <= A < B**(2*k)

        Q, R = divmod(A, B**k)
        r = format_int(R, B)
        q = format_int(Q, B)
        pad = '0'*(k - len(r))
        return ''.join([q, pad, r])

Оба эти алгоритма имеют сложностьM(n)*log(n)где количество битов в большом целом числе иM(n)это стоимость умножения двухnбитовые целые числа. Если умножение и деление больших целых чисел имеет субквадратичную производительность для умножения, то и эти алгоритмы будут такими же.

[1] Ричард П. Брент и Пол Циммерманн, Современная компьютерная арифметика. https://members.loria.fr/PZimmermann/mca/mca-cup-0.5.9.pdf