поддержка троично-десятичной арифметики

[sva]

поскольку первым реальным применением 3й арифметики (в силу скромности наших возможностей) полагается калькуляторный ЦПУ то возникает вопрос с поддержкой троично десятичной арифметики и преобразований.
предлагаю здесь обсусдить аспекты которые могут быть интересными для реализации данного метода вычислений



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

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

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

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

[Mac Buster]

Мне кажется у вас получилась не столько троично-десятичная арифметика, сколько обычная троичная арифметика. Я не прав?

[sva]

правы
но она все равно связана с преобразованиями туда и обратно
в частности для хранения или обмена м/у устроствами

[Shaos]

с делением чего-то не сильно срастается - (a-a/9)/9=a*8/9/9=a*8/81=a/10.125

[Mac Buster]

Да, погрешность в самом деле достаточно велика и накапливается к концу диапазона.

[sva]

попробуйте провести вычисления в целочисленной области

[Alexandr]

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

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

[Mac Buster]

Пробовал, при переходе за диапазон трита ошибка появляется и в целой части.

[Mac Buster]

В случае деления на некоторые чётные числа неплохой результат даёт алгоритм ЛеРуа (LeRoy Eide). Алгоритм был хорошо известен и раньше, но у него не было ни названия ни имени автора, поэтому дальше для устранения неопределённости буду ссылаться на него таким образом. Особенность этого алгоритма в том, что результат формируется начиная со старшего разряда.

[Shaos]

попробуйте провести вычисления в целочисленной области ;)

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

Code: Select all

#!/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);

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

>> [(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)

[sva]

а вы уверены что ваши вычисления были точны?

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

[Mac Buster]

Вот ссылка на описание алгоритма ЛеРуа - http://www.dyalog.com/dfnsdws/n_JitSub.htm

[Alexandr]

Очень интересный и простой алгоритм!
Особое внимание заслуживает деление
По аналогии можно предложить быстрое умножение на любое число:
Быстрое умножение на 16:
a>>2 + a>>2 - a - a
Быстрое умножение на 8:
a>>2 - a

[Shaos]

а вы уверены что ваши вычисления были точны?

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

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

[Shaos]

Переделал с округлением (в этой реализации языка Hope тип num - вещественное число):

Code: Select all

#!/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:

>> [(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