nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 27 Apr 2024 01:44



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

Joined: 08 Jan 2003 23:22
Posts: 22597
Location: Silicon Valley
Reply with quote
Алгоритм деления уравновешенно-троичного числа на 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
Profile WWW
Online
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22597
Location: Silicon Valley
Reply with quote
Вот мой перевод на русский объяснения деления на 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
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 2 posts ] 

Who is online

Users browsing this forum: No registered users and 52 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

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