nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 23 Nov 2020 16:11



Reply to topic  [ 28 posts ]  Go to page 1, 2  Next
поддержка троично-десятичной арифметики 
Author Message
Reply with quote
поскольку первым реальным применением 3й арифметики (в силу скромности наших возможностей) полагается калькуляторный ЦПУ то возникает вопрос с поддержкой троично десятичной арифметики и преобразований.
предлагаю здесь обсусдить аспекты которые могут быть интересными для реализации данного метода вычислений



на мой взгляд ключевыми являются операции умножения и деления на 10

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

умножение:
a*10 = (a<<2) + a

и деление:
a/10 = (a - (a>>2)) >>2


27 May 2009 10:24
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
Мне кажется у вас получилась не столько троично-десятичная арифметика, сколько обычная троичная арифметика. Я не прав? :)


27 May 2009 14:59
Profile
Reply with quote
правы
но она все равно связана с преобразованиями туда и обратно
в частности для хранения или обмена м/у устроствами


27 May 2009 21:19
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18964
Location: Silicon Valley
Reply with quote
с делением чего-то не сильно срастается - (a-a/9)/9=a*8/9/9=a*8/81=a/10.125


27 May 2009 21:44
Profile WWW
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
Да, погрешность в самом деле достаточно велика и накапливается к концу диапазона.


28 May 2009 01:18
Profile
Reply with quote
попробуйте провести вычисления в целочисленной области ;)


28 May 2009 10:36
Novelist

Joined: 20 Oct 2005 19:46
Posts: 34
Reply with quote
sva wrote:
на мой взгляд ключевыми являются операции умножения и деления на 10

А почему именно на 10?


28 May 2009 13:57
Profile
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
Пробовал, при переходе за диапазон трита ошибка появляется и в целой части.


28 May 2009 15:18
Profile
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
В случае деления на некоторые чётные числа неплохой результат даёт алгоритм ЛеРуа (LeRoy Eide). Алгоритм был хорошо известен и раньше, но у него не было ни названия ни имени автора, поэтому дальше для устранения неопределённости буду ссылаться на него таким образом. Особенность этого алгоритма в том, что результат формируется начиная со старшего разряда.


28 May 2009 15:22
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18964
Location: Silicon Valley
Reply with quote
sva wrote:
попробуйте провести вычисления в целочисленной области ;)


Попробовал на языке HOPE перебирать от 1 и вверх по формуле floor((x-floor(x/9))/9) и оно сбойнуло на 90 (вернуло 8 вместо 9):

Code:
#!/usr/local/bin/hopeless -f

dec tri10 : num -> num;
--- tri10(x) <= floor((x-floor(x/9))/9);

dec try : num # list(num # num) -> list(num # num);
--- try(x,l) <= if (x div 10) = tri10(x) then try(x+1,ll)
                else ll where ll==(x,tri10(x))::l;

try(0,nil);


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

Quote:
>> [(90, 8), (89, 8), (88, 8), (87, 8), (86, 8), (85, 8), (84, 8), (83, 8), (82, 8), (81, 8), (80, 8), (79, 7), (78, 7), (77, 7), (76, 7), (75, 7), (74, 7), (73, 7), (72, 7), (71, 7), (70, 7), (69, 6), (68, 6), (67, 6), (66, 6), (65, 6), (64, 6), (63, 6), (62, 6), (61, 6), (60, 6), (59, 5), (58, 5), (57, 5), (56, 5), (55, 5), (54, 5), (53, 5), (52, 5), (51, 5), (50, 5), (49, 4), (48, 4), (47, 4), (46, 4), (45, 4), (44, 4), (43, 4), (42, 4), (41, 4), (40, 4), (39, 3), (38, 3), (37, 3), (36, 3), (35, 3), (34, 3), (33, 3), (32, 3), (31, 3), (30, 3), (29, 2), (28, 2), (27, 2), (26, 2), (25, 2), (24, 2), (23, 2), (22, 2), (21, 2), (20, 2), (19, 1), (18, 1), (17, 1), (16, 1), (15, 1), (14, 1), (13, 1), (12, 1), (11, 1), (10, 1), (9, 0), (8, 0), (7, 0), (6, 0), (5, 0), (4, 0), (3, 0), (2, 0), (1, 0), (0, 0)] : list (num # num)


Last edited by Shaos on 21 Sep 2012 00:58, edited 1 time in total.



28 May 2009 20:27
Profile WWW
Reply with quote
а вы уверены что ваши вычисления были точны?

предлагаю проверить точность руками
для вашего же примера для значения 90
90 = 81 +9 = (+0+00)
(+0+00) >>2 = (+0+) =10
(+0+00) - (+0+) = (+0+00) + (-0-) = (+000-) =80
(+000-) >>2 = (+00) =9


29 May 2009 01:51
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
Вот ссылка на описание алгоритма ЛеРуа - http://www.dyalog.com/dfnsdws/n_JitSub.htm


29 May 2009 03:00
Profile
Novelist

Joined: 20 Oct 2005 19:46
Posts: 34
Reply with quote
Очень интересный и простой алгоритм!
Особое внимание заслуживает деление :)
По аналогии можно предложить быстрое умножение на любое число:
Быстрое умножение на 16:
a>>2 + a>>2 - a - a
Быстрое умножение на 8:
a>>2 - a


29 May 2009 05:26
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18964
Location: Silicon Valley
Reply with quote
sva wrote:
а вы уверены что ваши вычисления были точны?

предлагаю проверить точность руками
для вашего же примера для значения 90
90 = 81 +9 = (+0+00)
(+0+00) >>2 = (+0+) =10
(+0+00) - (+0+) = (+0+00) + (-0-) = (+000-) =80
(+000-) >>2 = (+00) =9


Да - я забыл, что троичное отбрасывание дробной части это округление :-?


30 May 2009 00:45
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18964
Location: Silicon Valley
Reply with quote
Переделал с округлением (в этой реализации языка Hope тип num - вещественное число):

Code:
#!/usr/local/bin/hopeless -f

dec round : num -> num;
--- round(x) <= if x-f < 0.5 then f
                else f+1 where f==floor(x);

dec tri10 : num -> num;
--- tri10(x) <= round((x-round(x/9))/9);

dec try : num # list(num # num) -> list(num # num);
--- try(x,l) <= if (x div 10) = tri10(x) then try(x+1,ll)
                else ll where ll==(x,tri10(x))::l;

try(0,nil);


Отвалилось уже на 6:

Quote:
>> [(6, 1), (5, 0), (4, 0), (3, 0), (2, 0), (1, 0), (0, 0)] : list (num # num)


6 = 9-3 = (+-0)
(+-0) >> 2 = (+) = 1
(+-0) - (+) = 6-1 = 5 = 9-3-1 = (+--)
(+--) >> 2 = (+) = 1


30 May 2009 01:23
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 28 posts ]  Go to page 1, 2  Next

Who is online

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