Алгоритм быстрого троичного деления на 2,4,8,10...

[Shaos]

Алгоритм деления уравновешенно-троичного числа на 3^N-1 или 3^N+1 (где ^ означает возведение в степень), упоминавшийся уже несколько раз на этом форуме, предложен математиком из Юты по имени LeRoy Eide (правда есть мнение, что алгоритм был изобретён ещё в СССР и соответственно давно известен):
http://dfns.dyalog.com/n_JitSub.htm
http://web.utah.edu/utahlogic/misc/justintime.html

[Shaos]

Вот мой перевод на русский объяснения деления на 2 из второй ссылки (заодно поменял обозначения значений трита на наш NOP):

Code: Select all

У нас есть 2*x (например 12 = PPO) и нам надо получить x
Одним из способов получить x может быть вычитание 2*x из 3*x (т.к. 3*x - 2*x = x)
Или другими словами нам надо прибавить -2*x
Но, естественно мы не знаем x (т.к. это то, 
что мы хотим найти) и поэтому мы не можем знать 3*x
Однако, мы знаем одну особенность 3*x, а именно то, 
что младшая троичная цифра у него должна быть равна 
нулю (т.к. чтобы это ни было, мы ввели младший ноль 
как только умножили на 3 или что тоже самое - сдвинули
влево на один трит)

 Итак мы имеем 2*x = PPO (12), и мы хотим разделить это на 2
 Необходимое нам -2*x это NNO (-12)

 Таким образом мы знаем что:

    3*x = ????O
 + -2*x = OONNO
------------------
 =    x = ?????

 Но мы МОЖЕМ вписать самую правую цифру в x, 
 т.к. это просто сложение и мы знаем младшие цифры 
 обоих слагаемых:

    3*x = ????O
 + -2*x = OONNO
------------------
 =    x = ????O

 Но теперь мы знаем младшую цифру в x, соответственно 
 мы можем вписать следующую цифру в 3*x, т.к. они 
 идентичны (т.к. 3*x это сдвинутое влево на один трит
 троичное число x):

    3*x = ???OO
 + -2*x = OONNO
------------------
 =    x = ????O

 Но теперь легко вычисляется и вторая колонка справа, 
 т.к. обе троичные цифры уже известны - O плюс N равняется
 N, которую мы вписываем также и как следующую известную
 цифру в 3*x:

    3*x = ??NOO
 + -2*x = OONNO
------------------
 =    x = ???NO

 Теперь мы можем сложить следующие цифры слагаемых 
 и получить следующую цифру результата 
 (а также перенос в следующий разряд):

(перенос)=  N
    3*x  = ?PNOO
 + -2*x  = OONNO
------------------
 =    x  = ??PNO

 И затем:

    3*x  = ?PNOO
 + -2*x  = OONNO
------------------
 =    x  = ?OPNO

 И так далее:

    3*x  = OPNOO
 + -2*x  = OONNO
------------------
 =    x  = OOPNO

 И теперь мы имеем наш ответ - OOPNO (6)