Быстрое умножение и деление на степень двойки

[Mac Buster]

Давайте думать о быстрых алгоритмах умножения и деления уравновешенного троичного числа на степень двойки. Мне стало известно, что такой алгоритм уже разработан в штатах и это меня как-то настораживает

Если про умножение есть кое-какие идеи, то вот оносительно деления ничего в голову не приходит.

[Mac Buster]

Неужели ни кто ничего не может предложить ?

[Shaos]

Неужели ни кто ничего не может предложить ?

Обозначим троичные сдвиги так:
>>> троичный сдвиг вправо (равносильно делению на 3)
<<< троичный сдвиг влево (равносильно умножению на 3)

Тогда можно записать:
2*T = 3*T-T = (T<<<1)-T
4*T = 3*T+T = (T<<<1)+T
10*T = 9*T+T = (T<<<2)+T

А вот с делением такие фокусы уже не пройдут

[Mac Buster]

Тогда можно записать:
2*T = 3*T-T = (T<<<1)-T
4*T = 3*T+T = (T<<<1)+T
10*T = 9*T+T = (T<<<2)+T

Да, примерно об этом я писал выше.

А вот с делением такие фокусы уже не пройдут

Универсального решения я пока не нашёл, а выделение частных случаев занимает слишком много времени

[Alexandr]

А вот с делением такие фокусы уже не пройдут

Деление немного можно ускорить если, выполнять сдвиг делимого и делителя на количество нулевых младших разрядов делителя, а потом выполнять деление полученного делимого на полученный делитель

[Shaos]

Автор Тунгуски в 2009 году предложил делить на 2 путём умножения на число .PPPPPP... (что есть 0.5):

Code: Select all

A B C D / 2
-----------
  A B C . D 
    A B . C D
 +    A . B C D
-----------------
[0, A, A+B, A+B+C].[B + C + D, C+D, D]