вопрос по умножению карацубы

Question

Я хочу реализовать умножение Карацубы на 2 деления в Python. Тем не менее, написание чисел в виде

A=c*x+d

где x - степень основания (пусть x = b ^ m), близкая к sqrt (A).

Как мне найти х, если я даже не могу использовать деление и умножение? Должен ли я считать количество цифр и сдвинуть A влево на половину количества цифр?

Спасибо.

Answer 1

Почти. Вы не сдвигаете A на половину количества цифр; Вы сдвигаете 1. Конечно, это эффективно, только если основание имеет степень 2, так как «сдвиг» в основании 10 (например) должен быть сделан с умножением. (Правка: хорошо, хорошо, вы можете размножаться со сдвигами и дополнениями. Но с степенью 2 это намного проще.)

Если вы используете Python 3.1 или выше, считать биты легко, потому что 3.1 ввел метод int.bit_length(). Для других версий Python вы можете подсчитать биты, скопировав A и сдвинув его вправо до нуля. Это можно сделать за время O (log N) (N = количество цифр) с помощью своего рода метода двоичного поиска - сдвиг на много битов, если это 0, то это было слишком много и т. д.

Answer 2

Вы уже приняли ответ, так как я начал писать это, но:

Что сказал Том: в Python 3.x вы можете получить n = int.bit_length () напрямую. В Python 2.x вы получаете n за O (log2 (A)) с помощью бинарного поиска, как показано ниже.

Вот код (2.x), который вычисляет оба. Пусть показатель степени 2 для x равен n, то есть x = 2 ** n.

Сначала мы получаем n при бинарном поиске, сдвигая. (На самом деле нам нужно было только n / 2, так что это одна ненужная последняя итерация). Тогда, когда мы знаем n, получить x, c, d легко (все еще не используя деление)

def karatsuba_form(A,n=32):
    """Binary-search for Karatsuba form using binary shifts"""
    # First search for n ~ log2(A)
    step = n >> 1
    while step>0:
        c = A >> n
        print 'n=%2d step=%2d -> c=%d' % (n,step,c)
        if c:
            n += step
        else:
            n -= step
        # More concisely, could say: n = (n+step) if c else (n-step)
        step >>= 1
    # Then take x = 2^(n/2) ˜ sqrt(A)
    ndiv2 = n/2
    # Find Karatsuba form
    c = (A >> ndiv2)
    x = (1 << ndiv2)
    d = A - (c << ndiv2)
    return (x,c,d)

Answer 3

На ваш вопрос уже дан ответ в статье, на которую вы ссылались: «Базовый шаг Карацубы работает для любой базы B и любого m, но рекурсивный алгоритм наиболее эффективен, когда m равно n / 2, округлено в большую сторону» ... n - количество цифр, и 0 <= value_of_digit <B. </p>

Некоторая перспектива, которая может помочь:

Вам разрешено (и необходимо!) Использовать элементарный операций, таких как number_of_digits // 2 и divmod(digit_x * digit_x, B) ... в школьной арифметике, где B равно 10, вам необходимо (например) знать, что divmod(9 * 8, 10) производит (7, 2).

При реализацииарифметика большого числа на компьютере, обычно делают В наибольшей степенью 2, которая будет удобно поддерживать элементарную операцию умножения.Например, в реализации CPython на 32-битной машине B выбирается равным 2 ** 15 (т.е. 32768), потому что тогда product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF; работает без переполнения и не заботится о знаковом бите.

Я не уверен, что вы пытаетесь достичь с помощью реализации в Python, которая использует B == 2, с числами, представленными целочисленными значениями Python, чья реализация в C уже использует алгоритм Карацубы для умножения чисел, достаточно больших, чтобы сделать его стоящим,Это не может быть скорость.

В качестве учебного упражнения вы можете попытаться представить число в виде списка цифр, причем основание B является входным параметром.