nedoPC.org

Electronics hobbyists community established in 2002
Last visit was: 16 Jun 2024 13:56
It is currently 16 Jun 2024 13:56



 [ 2 posts ] 
Алгоритм быстрого троичного деления на 2,4,8,10... 
Author Message
Admin
User avatar

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


01 Aug 2011 19:46 WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22884
Location: Silicon Valley
Вот мой перевод на русский объяснения деления на 2 из второй ссылки (заодно поменял обозначения значений трита на наш NOP):

Code:
У нас есть 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)


01 Aug 2011 20:17 WWW
 [ 2 posts ] 

Who is online

Users browsing this forum: Claude AI [Bot] and 12 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.