Можно ли оптимизировать целочисленное деление числовой мощности? - PullRequest
Новая
       56

Можно ли оптимизировать целочисленное деление числовой мощности?

0 голосов
/ 20 января 2020

В Python есть встроенная функция pow, которая оптимизирует расчет a**b%c. Почему не существует функция, которая вычисляет a**b//c?

1 Ответ

1 голос
/ 20 января 2020

Здесь я попытаюсь сделать вывод, почему расчет a ** b // c нельзя оптимизировать, вряд ли a ** b % c.

Предварительные условия: расчет a ** b % c

Давайте возьмем иллюстративный пример: скажем a=2 и b=11. Если мы предположим, что это довольно медленно, то мы можем вывести это b = 1 + 2 + 8 = 2**0 + 2**1 + 0*2**2 + 2**3. После этого этот вычет можно использовать как правило для умножения результатов a, a**2, a**4, a**8. Каждый результат присваивается после возведения в квадрат предыдущего. Наконец, a**11 = a*(a**2)*(a**8), и для этого процесса требуется только 3 отделения.

Если мы обобщим этот процесс, это можно сделать так: 

a, b, r = 2, 11 , []

while b>0:
    if b % 2: r.append(a)
    b = b//2
    a = a*a
else:
    if b % 2: r.append(a)

print(r)

Выходное значение равно r=[2, 4, 256]. Далее нам нужно умножить эти множители. Это можно сделать с помощью from functools import reduce с командой reduce(lambda x,y: x*y, r).

Наконец, если множители становятся достаточно большими, умножение становится очень медленным, поэтому нам нужно заменить каждый множитель m его модулем m%c и сделать то же самое в функции reduce. Наконец, мы имеем: 

from functools import reduce
def pow(a, b, c):
    # returns a ** b % c
    r = []
    while b > 0:
        if b % 2: r.append(a)
        b = b // 2
        a = (a * a) % c
    else:
        if b % 2: r.append(a)

    return reduce(lambda x, y: (x * y) % c, r)

Выходные данные 4, поскольку 2 ** 11 % 7 равно 4.

Я также проверил результат 2046457 ** 1103207 % 71872 на моем компьютере. Вывод был 18249, и для расчета потребовалось 9 секунд, в то время как pow(2046457, 1103207, 71872) мгновенно дал тот же результат.

Обновление: включение a ** b // c в расчет

Следуя вышеупомянутым идеям, я буду Попробуйте добиться аналогичной оптимизации для расчета a**b // c. Я предполагаю, что процесс возведения в квадрат остается тем же самым, и основное отличие здесь состоит в том, что мы должны учитывать как интегральную, так и остаточную части при взятии квадратов (предыдущая была легкой, потому что интегральная часть не была важной). Если x является неотъемлемой частью, а y является остаточной, мы имеем соотношение:

[1]: https://i.stack.imgur.com/ReNeV.gif

Нам также необходимо ввести аналогичный расчет для два различных множителя:

enter image description here

Мой скрипт выглядит следующим образом: 

from functools import reduce
def pow(a, b, c):
    #returns tuple (a ** b // c,  a ** b % c)
    print(f'calculating: {a}**{b} = ', end='')
    r = []
    ir = (a//c, a%c) # we keep integral and residual part of a instead of a
    while b > 0:
        if b % 2: r.append(ir)
        b = b // 2
        ir = (ir[0]*ir[0]*c + 2*ir[0]*ir[1]+ (ir[1]*ir[1])//c, (ir[1]*ir[1]) % c)
    else:
        if b % 2: r.append(ir)
    out = reduce(lambda x, y: (c*x[0]*y[0] + x[0]*y[1] + x[1]*y[0] + (x[1] * y[1])//c, (x[1] * y[1]) % c), [(2, 2)]+[r[-1]])

    print(' * '.join(str(n[0]*c+n[1]) for n in r), end=' = ')
    print(' * '.join(str(n) for n in r),'=', out)
    return out

pow(2,7,3)

Выход 

calculating: 2**7 = 2 * 4 * 16 = (0, 2) * (1, 1) * (5, 1) = (42, 2)

Примечания

Почему это еще не оптимизация? Мы можем видеть, что второе слагаемое в каждом факторе остается всегда небольшим, но это не правило для первых слагаемых, как в этом примере pow(26,31,35): 

calculating: 26**31 = 26 * 676 * 456976 * 208827064576 * 43608742899428874059776 = 
(0, 26) * (19, 11) * (13056, 16) * (5966487559, 11) * (1245964082840824973136, 16) = 
(89709413964539398065824, 32)

В этом случае мы не можем избежать экспоненциального роста a%b // c. Вот почему никакая существующая встроенная функция для a%b // c не кажется мне разумной.

...