nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 02:48



This topic is locked, you cannot edit posts or make further replies.  [ 23 posts ]  Go to page 1, 2  Next
Троичные форматы данных ( или TRIBBLE = 2*TRIT ) 
Author Message
видел сообщение в другом разделе по представлению данных с плавающей точкой в троичной системе.


предлагаю определиться по всем типам данных и по целочисленным в т.ч.
(вероятнее всего это уже рассматривалось и обсуждалось - здесь я предлагаю это систематизировать)

предлагаю следующие варианты:
Image

все типы предлагаю использовать знаковые (!) для представления сравнимого по мощности двоичного числа необходимо почти втрое большее троичное что позволяет той же разрядность перкрыть диапазон беззнакового представления числа в существующей 2ной системе представления так и такой же диапазон отрицательных чисел.

ЦЕЛОЧИСЛЕННЫЕ:
1. тип Digit - для поддержки 3-10ной арифметики наиболее очевидно применение - калькуляторы, что представляется одним и наиболе вероятных первых коммерческих применний 3ного МК.

2. тип Nibble - логичное расширение типа Digit для использования всей мощности представления числа 3мя разрядами.

3. тип Tryte - размер основной рабочей единицы информации должен перекрывать диапазон представления существующей 2ной системы (байт)

4. тип Int - размер должен покрывать Int существующего 2ного представления (вообще-то это 11 разрядов но для удобства предлагется использовать числа кратные трайтам)

5. тип Word - предполагется что этот тип будет равен машинному слову. на мой взгляд естественным представляется использование для машинного слова 3 трайт (учитывая что и изменение адреса так же будет производиться в 3ной системе счисления то логичным представляется следующем шагом после трайта иметь машинное слово 3 трайта)

6. тип Long - так же для покрытия диапазона Long существующего 2ного.

С ПЛАВАЮЩЕЙ ТОЧКОЙ:
fp_Single - базовый тип представления чисел с плавающей точкой.

не вижу необходимости использования отдельного разряда для обозначения знака числа и скрытого разряда как в 2ном представлении, посему представляется целесообразным отказаться от прямого следования стандарту представления чисел с плавающей точкой для 2ных и 2-10ных чисел (IEEE754 и IEEE854 соотв.)

для удобства работы целесообразно было бы иметь величины мантиссы и порядков кратными трайту если он удовлетворяют условию необходимой точности представления чисел.
учитывая что базовым машинным словом при котором имеет смысл представлять число с плавающей точкой является 3х-трайтное с учетом вышесказанного буду отталкиваться от разрядности 18 и представления 12 разрядов на мантиссу и 6 на порядок - соотвественно диапазон представляе5мых чисел 2,00E-180 ... 2,35E+173

на мой взгляд этот диапазон более чем достаточен для базового типа с плавающей точкой потому что к примеру число атомов на земле оценивается порядка 1,0Е+108

теперь что касается 2й точности (fp_Double) - его назначение повысить точность вычислений в основном за счет точности представления данных. двукратное повышение точности требует не менее чем 2-кратного повышения разрядности мантиссы, следовательно если брать базовый тип 6+12 разрядов то получаем что мантиса не должны быть меньше 2х12=24 разряда. учитывая что следующее по размерам машинное слово логично было представить удвоенным одинарным (т.е 2х18=36) получаем что число удвоеной точности должно быть 36 разрядным. не вижу необходимости увеличивать разрядность порядка т.к. мы уже имеем достаточно мощный диапазон представления чисел при том что значительно повышется точность, в то же время при сохранении порядка кратым 1 трайту сильно упрощает обработку таких чисел в т.ч. и програмным путем.
+ это сущестуенно упростит преобразование типов с плавающей чочкой(!) без существенной потери точности.

тип fp_Extended предназначен для проведения операций над числами с плавающей чтокой сминимизацией потерь точности за счет округления при вычислениях.
соотвесвтенно длина его мантиссы должна быть не меньше суммы длинн мантисс типов с одинарной и двойной точностями.

теперь о представляемых значениях
предлагаю следующие:
<e++..++ m++..++> +бесконечность(+OO)
<e++..++ m - -.. - -> -бесконечность(-OO)
<e00..00 m00..00> абсолютный 0
<e++..++ m00..00> не число (NAN)
<e - -.. - - m00..00> не число (NAN)
<e - -.. - - m00..0+> минимально представимое положительное (+0)
<e - -.. - - m00..0 -> минимально представимое отрицательное (-0)
<e##..## m0#..##> денормализованное число
<e##..## m##..##> нормализованное число

касательно минимально представимых - дальнейшее уменьшение не изменяет числа по сути младший разряд выполняет роль guard-разряда

ЛОГИЧЕСКИЕ ТИПЫ:
1. trit - минимальная единица информации. много не представшь ;) (см начало)

2. proposition - основной тип для реализации логики высказываний. в отлчие от значений представляемых trit-ом обладает замкнутостью относительно логических операций (результат принатдлежит тому же множеству что и аргументы).


ОКРУГЛЕНИЕ
предлагаю использовать 5 способов округления
1. round - округление к ближайшему (отбрасывание хвоста)
2. round+ - округление к +OO
3. round- - округление к -OO
4. roundU - округление к OO
5. roundZ - округление к 0

реализация округления важный момент для интервальной арифметики и операций с плавающей точкой.
round+ и round-
для целочисленных типов - приводят к округлению соотвевенно к ближайшему большему и к ближайшему меньшему целому.
для плавающей точки - эти способы округления представляются не имеющими ценности (во всяком случае я пока не вижу)

roundU и roundZ
для целочисленных типов - приводят к оруглению соотвевенно к ближайшему большему по модулю и к ближайшему меньшему по модулю целому.
для плавающей точки - соотвествнно к ближайшему большему и ближайшему меньшему представимым.

пока примерно так.
хотелось бы услышать мнения, предложения, возражения и дополнения.
желательно с описанием обоснования.


PS: кстати, ввиду того что зачастую логически операции в современном программировании используются для маскирования и других битовых операций или для ускоренного вычисления арифметичских выражений то есть прдложение отказаться от такого устройства как АЛУ в принципе и разделить операции по классам:
1. арифметические
2. операции над разрядами (туда же можно отнести и основные операции такие как логическое И и логическое ИЛИ и т.п.
и вообще класс поразрядных операций и логических функций)
3. собствено логические операции.

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


22 Oct 2008 05:18
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Непонятно назначение округлений, отличных от отбрасывания, которое есть самое точное троичное округление :)


Я тут уже писал в форуме почти год назад по поводу троичных типов:

Quote:
1 trit - 3 values (N,O,P or -1,0,+1);
1 triad (3 trits) - 27 values;
1 tryte (6 trits, 2 triads) - 729 values;
1 tradr (9 trits, 3 triads) - 19 683 values;
1 trord (12 trits, 4 triads, 2 trytes) - 531 441 values;
1 truadr (18 trits, 6 triads, 3 trytes, 2 tradrs) - 387 420 489 values;
1 truble (24 trits, 8 triads, 4 trytes, 2 trords) - 282 429 536 481 values;

New words "tradr" and "trord" mean "ternary address" and "ternary word" respectively.
New words "truadr" and "truble" mean "double ternary address" and "double ternary word" respectively.
Another idea to rename "triad" (half of tryte) to "tribble" (like nibble that is half of byte).


и по поводу троичной плавающей точки:

Quote:
Idea about representation of floating point numbers: Lets take "truble" and divide it to 2 parts: 6-trit exponent and 18-trit fraction. By accuracy it is better than 32-bit "float", worse than 64-bit "double" and similar to 36-bit floating number in IBM System/360 from 1964 that had 9-bit sign and exponent and 27-bit fraction. Because of nature of balanced ternary numeric system we don't need "biasing" exponent. Also we don't need separate sign bit - we simply combine it with "hidden" most significant bit of fraction instead and it will be part of full 18-trit fraction. So range of exponent is from -364 to +364 (3^6/2) and fraction from -193710244 to +193710244 (3^18/2 that is max possible integer represented by this floating point format). To simplify formula for calculation number from representation we may simply forget about "fractional" nature of fraction and say F*3^E


P.S. По поводу tribble - некоторые товарищи считают, что в отличие от nibble, который есть половина байта, троичный tribble должен быть третью трайта (не половиной) - в этом случае триббл должен быть 2-тритным (при 6-тритном трайте), либо трайт должен быть 9-тритным (и триббл останется 3-тритным).


22 Oct 2008 16:35
Profile WWW
я к сожалению не видел этой вашей заметки про типы.

наличие разных способов округления крайне важно
особенно для вычислений. для интервальной арифметики это просто необзходимо. так же это важно для арифметики большой точности.

truble - классно звучит - почти как trouble :)
а если серьезно то
1. предполагается неудобным использование типов начинающихся одинково - это ухудшает читаемость программы
2. даже в обычных мшинах не всегда совпадают разрядности int (и уж тем более word) так что проблемы при переносе кода все равно есть.
3. зачастую в программах пользуюьтся числами небольшой разрядности так что при перносе кода критичным будет только момент с поразрядными операциями
4. зачем осложнять пользователям переход на новое железо еще и необходимостью привыкать к новым типам? (имеется ввиду наименованиям типов)

я нахожу что название типа не только должно отражать представимость тех или иных чисел и разрядность, но так же быть удобным в использовании и простым для перехода от обычного программизма - я думаю не секрет что мощь языка С в его библиотеках и в том что он достаточно прост для того чтобы им управлялся низкоквалифицированный специалистю а для такого специлиста чем меньше разного рода сущностей тем лучше - зачем плодить сущности сверх необходимого?

по воводу nibblе/tribble
я тоже изначально ориентировался на 9 разрядный трайт (это было бы логично) и соотвественно 3 nibble-a в но дело в том что разрядность машин обычно берут равной основной единице информации (в данном случае трайту) т.о. для представления int (ну не откажутся программисты от него так просто да и не стоит забывать про необходимость переноса программ и библиотек) необходимо 11 разрядов по факту или 18 в машине с 9 разрядным трайтом - не слишком ли жирно?

nibble по сути отражает небольшую порцию данных и по факту равен полубайту - так почему бы полутрайт не обозначить тем же обрзом?
хотя и triad мне лично нравится но это будет неудобным использовать в англоязычной литературе из-за схожести с обозначением 3х разрядов (что не всегда тождественно отражению информации представляемой nibble-ом)

по поводу ФП я уже писал.
1 и самое важное не вижу необходимости полностью следовать стандарту ФП для 2ного представления чисел потому что некоторые моменты привязаны именно к 2ному и 2-10ному представлениям чисел и не целесообразны в реализации в 3ной симметричной системе счисления(!)

2 основная часть пользуется достаточно небольшой точностью представления в то время как для высокоточных вычислений необходимы вычисления с более высокой точностью чем предоставляют типы float и double, для этого можно использовать предлагаемый тип fp_extended

3 на мой взгляд точности у 18 разрядного вполне достаточно для базового
6*1,58 = 9,6 двоичных разрядов экспоненциальной части что заметно больше чем 8 разрядов одиночной точности и немногим меньше 11 двойной
вто же время при разрядности трайта 6 трит это существенно упрощает не только программную реализацию ФП но и преобзоазование ФП величин из одной точности в другую с минимальными потерями.
12*1,58 = 19 тоже достаточно большой диапазон для мантиссы числа

ps: я понимаю что у каждого свое видение размерности и наименования типов но лично я против простого и необоснованного использования типов и стандартов имеющегося 2ного представления чисел.
еще раз повторюсь - я нахожу неочевидным использование ФП типов полностью перекрывающих диапазон аналогичного представления типов в 2ной арифметике.

я считаю что вопрос формирование сисемы представления данных не праздным - поскольку это завязано на аппаратную реализацию.


22 Oct 2008 21:39
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
sva wrote:

наличие разных способов округления крайне важно
особенно для вычислений. для интервальной арифметики это просто необзходимо. так же это важно для арифметики большой точности.


ну это как бы уже и не округление - для этих целей есть функции floor и ceil :)


23 Oct 2008 06:58
Profile WWW
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Quote:
ну это как бы уже и не округление - для этих целей есть функции floor и ceil :)


Мне тоже кажется что округление выполняется только один раз по завершении всех операций. Если вообще выполняется.


23 Oct 2008 07:40
Profile
эти функции реализуются программно или аппаратно?
я говорю об аппаратной реализации.
о необходимости предусмотреть разные варианты округления в аппаратуре.
это надо сделать аппаратно потому что округление зависит не только от знака но числа но так же и от знака хвоста получаеющегося при вычислениях и выходящего за разрядную сетку. при сохранении числа в памяти или регистрах этот хвост теряется и нет возможности правильно скорректировать результат. потому что результат в отличие от 2ного представления может быть как меньше так и больше числа получающегося при округлении отбрасыванием (у нас знак хвоста может быть отличным от знака числа) т.о. мы может получить 2 интервала <число>-d .. <число> и <число> .. <число>+d
либо использовать расширенный интервал <число>-d .. <число>+d что вдвое снижает точность (!).

в IEEE754 для это коррекции предусмотрены 2 разряда.


23 Oct 2008 07:46
Mac Buster wrote:
Quote:
ну это как бы уже и не округление - для этих целей есть функции floor и ceil :)


Мне тоже кажется что округление выполняется только один раз по завершении всех операций. Если вообще выполняется.


это верно для операций с плавающей точкой, но совершенно неверно для операций интервальной арифметики.
опять же для операции с числами повышеной точности надо будет реализовывать программно - не всегда может хвтить размерности типов удвоеной точности.


23 Oct 2008 12:10
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Quote:
это верно для операций с плавающей точкой, но совершенно неверно для операций интервальной арифметики.


К сожалению не понимаю в какой ситуации можно столкнуться с подобным выполнением арифметических операций. Очень похоже на ошибку планирования.

Quote:
опять же для операции с числами повышеной точности надо будет реализовывать программно - не всегда может хвтить размерности типов удвоеной точности.


В тексте исходного сообщения контекст применения предложенных методов округления в области аппаратуры мне совсем не очевиден.


24 Oct 2008 04:40
Profile
Mac Buster wrote:
Quote:
это верно для операций с плавающей точкой, но совершенно неверно для операций интервальной арифметики.


К сожалению не понимаю в какой ситуации можно столкнуться с подобным выполнением арифметических операций. Очень похоже на ошибку планирования.

именно класс задач интервально арифметики. большинство программистов с ним никогда не сталкивается. в основном это используется для научных расчетов. так же как и вычисления с очень высокой точностью.

Mac Buster wrote:
Quote:
опять же для операции с числами повышеной точности надо будет реализовывать программно - не всегда может хвтить размерности типов удвоеной точности.


В тексте исходного сообщения контекст применения предложенных методов округления в области аппаратуры мне совсем не очевиден.


задачу обработки ФП можно по сути разбить на 2 варианта:
1. программный - тогда эти методы округления действительно можно выполнять вручную.

2. аппаратный - когда ФП вычисляется в отдельном операционном модуле - тут уже эти саме способы округления должны быть заложены в железо (в идеале на выходе ФП мы должны иметь 2 значения, равных границам интервала и указатель которое из них более точное, получающееся отбрасыванием хвоста).
кстати, если обратить внимание то в IEEE754 для этой коррекции есть 2 guard-разряда. эти разряды не видимы пррограммисту ииспользуются только при вычислениях. при чтении/записи это хвост теряется без возможности восстановления.
если проверка и коррекция результата будет занимать несколько команд то какой смысл в аппаратной реализации ФП?
потому что при удачной поддержке ФП на уровне целочисленной арифметики можно уложиться в диапазон 10-20 команд зато сильно сэкономить на аппаратном ФП (а это весьма жирный кусок)

в контексте формирования стандартных типов я считаю необходимо рассмотреть все возможные варианты применения этих самых типов. приведенные 5 типов округления исчерпывают все способы округления которые могут потребоваться при арифметике как с целыми числами так и с ФП. те

кстати, еще не однозначным является представление чисел:
представление для "+OO", "+0", "0", "-0" и "-OO" получается последовательным прибавлением и вычитанием наименьшей представимой величины
из подобного рода получаемых величин выпадают денормализованные (когда старший разряд мантиссы "0") и числа где все разряды мантиссы равны "0".


24 Oct 2008 05:21
вообще я склонен согласиться что нет необходимости реализации всех ранее приведенных способов округления для всех чисел, потому что округления к +/-OO прменимы к целым числам и несущественны для ФП, в то время как округления к 0 и к OO наоборот. т.о. получается 2 множества операций округления:
а) для целочисленных операций
1. к ближайшему
2. к +ОО
3. к -ОО
и
б) для ФП
1. к ближайшему
2. к ОО
3. к 0


24 Oct 2008 07:34
Первое впечатление - избыточно сложно. Было бы интересно увидеть обоснования существования каждого из типов.


25 Oct 2008 23:28
все написаноо в самом начале
вот кратко:
1. Digit [3]- для троично-десятичной арифметики (3 разряда покрывают все представления цифр от 0 до 9 как со знаком так и без)
2. Nibble [3]- представление полного диапазона 3х разрядов
3. Tryte [6] - основная единица информации (6 для перекрытия типа byte)
остальные типы строятся по принципу N x Tryte
4. Int [12] - 2 x Tryte (основной целочисленный тип) перекрывает представление int 2ных машин
5. Word[18] - 3 x Tryte (машинное слово) наиболее целесообразный размер при 6 разрядном трайте и 3ной адресации
6. Long[24] - 2 x Int - 4 x Tryte (тип больших целых чисел) перекрывает тип Long

следует обратить внимание что целочисленнные типы имеющие эквиваленты в двоичной арифметике перекрываются с минимальной избыточностью не рушашей кратность представления в единицах измерения троичной системы счисления.


7. fp_single [18=e6+m12] - основной тип представления чисел с ПТ перекрывает (?) представление float 2го по точности.
8. fp_double [36=e6+m30] - тип представления чисел с ПТ увеличеной точности - повышение точности вычислений и проверки методов (если результаты вычислений с обычной и двойной точностью совпадаюст то ссчитается что метод точен)
9. fp_extended [54=e12+m42] - расширенный тип чисел с ПТ - предназначен для промежуточных вычислений.

обращаю внимание что из-за кратности трайту полей представления чисел с ПТ заметно повышается удобство обработки их програмным путем

10. trit[1] - минимальный элемент данных. тип можно использовать как для доступа к отдальным разрядам так и в качестве базового логического для многозначной логики
11. proposition[2] - тип для представления логики высказываний. в отличие от trit-а обладает замкнутостью относительно логических операций. по сути минимальный замкнутый тип многозначной логики.


ps: короче некуда


26 Oct 2008 03:47
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Моё личное мнение - троичные типы данных НИ В КОЕМ СЛУЧАЕ НЕЛЬЗЯ называть также, как существующие двоичные типы данных - чтобы не вызывать путаницу, т.е. никаких int, long и даже nibble с word-ом в троичном мире не должно существовать...


26 Oct 2008 08:47
Profile WWW
а мне кажется с точностью до наоборот. как можно больше должно быть соотвествий (но в то же время по возможности меньшее отступление от удобстав троичности)

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

не забывайте в конце концов мы не для себя это делаем а для пользователя - продукт не имеющий конкретного применения не имеет ценности -

"знания сами по себе не имеют цены - ценно применение знаний"

ps: в конце-концов для этого я тему и создал - чтобы формализовать типы, их размеры, представление данных и названия.
и важно не просто предложить, но и аргументирвоать.
потому что от выбора типов данных будет зависеть и аппаратная реализация и удобство с ними работать и много чего еще.
поэтому все аспекты на мой взгляд должны быть хорошо взвешены.

вполне допускаю что в моем предложении много спорного но пока альтернативного предложения нет (во вском случе его обосновния) хотелось бы его услышать.

если с целочисленными типами все более менее ясно и основная дискуссия булет о названиях
то в вопросе о представлении чисел с ПТ и работе с ними еще много вопросов.
да и инетерсно было бы услышать мнение о логических типах и операциях.


26 Oct 2008 12:48
Doomed

Joined: 10 Mar 2012 16:21
Posts: 598
Location: РФ
Post 
Уж простите, что очень схожие сообщения сразу в двух ветках пишу, но мне кажется это важно именно для двух веток одновременно :
Quote:
Насчёт шрифтов есть простейшая идея - использовать UTF , а оставшиеся комбинации с отрицательными значениями тритов назначить для представления других типов данных, в первую очередь специфичных для троичных систем. Первый (старший) трит будет указывать :
если 0 , то следующие 8 трит при их положительном значении кодируют без изменений первый байт UTF , при их отрицательных значениях кодируют другие типы данных,
если -1 , то следующие триты содержат код команды или ещё что-нибудь системное или значения нечёткой логики,
ну а если +1 , то следующие триты кодируют числовые данные, причём второй и третий триты ещё не кодирует, а указывают на тип числа и его длину
.

Что думаете о таком устроении форматов данных ?


09 Nov 2012 15:30
Profile
Display posts from previous:  Sort by  
This topic is locked, you cannot edit posts or make further replies.   [ 23 posts ]  Go to page 1, 2  Next

Who is online

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