Как подружить тритичную систему с двоичной ?

← →
Кен (2004-01-16 06:03) [0]

Тритичная, значит значение может быть трёх видов 0, 1 и 2. Записываю эту информацию в 2 бита и вроде бы всё в порядке. Но не даёт мне покоя мысль, что эта запись неэкономична, так как в 2 бита можно записывать числа от 0 до 4, а значит можно сэкономить. Но как ?

← →
Романов Р.В. (2004-01-16 07:20) [1]

> эту информацию в 2 бита и вроде бы всё в порядке.

Все равно ты записываешь информацию в двоичном виде. Компьютер умеет работать только с ней.
Храни числа в двоичном виде, а при выводе/вводе конверти ее в другую систему.

← →
Anatoly Podgoretsky (2004-01-16 07:45) [2]

Тритичная система не имеет отношения к битам, к этому имеет отношение двоичная.

← →
Кен (2004-01-16 07:59) [3]

> Романов Р.В. © (16.01.04 07:20) [1]
> Все равно ты записываешь информацию в двоичном виде. Компьютер
> умеет работать только с ней.

Поэтому и вопрос, как конвертнуть ?

← →
Романов Р.В. (2004-01-16 08:06) [4]

Ученик © (17.09.02 22:37)
function UniConvert(L, Base : Integer; Chars : PChar) : string;
begin
Result := "";
if StrLen(Chars) >= Base then begin
repeat
Result := (Chars + (L mod Base))^ + Result;
L := L div Base
until L = 0
end
end;

ShowMessage(UniConvert(534534, 2, "01"))

← →
sniknik (2004-01-16 08:08) [5]

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

← →
Кен (2004-01-17 02:28) [6]

> Романов Р.В. © (16.01.04 08:06) [4]

Это не то. Вопрос как в памяти, которая двоичная, разместить переменные которые могут принимать три значения ?
Толи сгруппировать как то, толи не знаю чего. Чтобы покомпактнее было.
Например 3^5 = 245 . То есть в 8 бит можно поместить 5 значений, а не 4, если использовать по 2 бита на значение. Понимаешь о чём речь ?

Но всё равно остаётся "резерв" в виде 256-245. А хочется так, чтобы было идеально, без этой незадействованной части.

← →
Palladin (2004-01-17 11:45) [7]

Удалено модератором

← →
Sergey_Masloff (2004-01-17 12:23) [8]

sniknik © (16.01.04 08:08) [5]
>машину нужно новую (комп), у которой основа не бит а "трит" с >3мя возможными значениями. другого способа нет, в такой >постановке вопроса.
Новую? Все новое это хорошо забытое старое. Такие машины были, кстати все равно битом называлась единица памяти, но троичным. Но это было очень давно, нам в институте в 1988 году про такие рассказывали как про страшную древность, типа конца 60-х.

← →
KSergey (2004-01-17 13:49) [9]

Предлагаю автору перейти на четверичную (четвертичную?) систему - и проблема отпадет сама собой.

← →
Кен (2004-01-18 01:14) [10]

> KSergey © (17.01.04 13:49) [9]
> Предлагаю автору перейти на четверичную (четвертичную?)
> систему - и проблема отпадет сама собой.

Каким образом ?

← →
Palladin (2004-01-18 01:27) [11]

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

← →
Германн (2004-01-18 02:05) [12]

Не знаю "в струю" ли я? Но, почему-то, вспомнилась моя программа из 80-х. Та программа являлась средством получения/обработки данных физического эксперимента. Короче - результатом первичной работы программы должен был быть файл, в котором записаны координаты измеренных точек, т.е. (X,Y), где X и Y типа Real.
Но данные эксперимента получали в одном месте, а анализировали в другом. А средством переноса данных, на тот момент, могли служить только дискеты 5". Причем, у нас была только Искра 1030, которую мы научили работать с 80-ю дорожками, но не было возможности обработать таким образом "первую машину".
Единственным способом облегчить жизнь явилось "изобретение особой упаковки" двух Real в 8 байт. Но тут, разумеется, было учтено, что величины X и Y не могут выйти за "некои" пределы.

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

← →
Кен (2004-01-18 02:52) [13]

> Palladin © (18.01.04 01:27) [11]
> ну нету в современных персональнях компьютерах понятия пол
> бита!
> вот и используй для записи одного значения в своей "тритичной"
> системе 2 бита.

См. выше.

> Германн © (18.01.04 02:05) [12]
> Опять же, имхо, теперь нет необходимости
> в такой упаковке и, кроме того, она только замедлит программу.

Практическия я проблему уже решил упаковав в 2 бита, но меня интересует теоретическая часть. Отнеситесь к этому как к давольно сложной задаче по программированию.
Сложной потому, что сколько 3 в степень не возводи, чётное число не получишь, а значит избыточность всегда будет оставаться. Задача только свести её к минимуму. Как ?

← →
Dima_dvp (2004-01-18 03:59) [14]

На самом деле если есть какой-то избыток в данных (в данном случае отсутствие "11") то всегда его можно получить.
В данном конкретном случае это действительно теория ибо сжатие сэкономит 25% объёма при этом потеряя в скорости чтения/записи данных более 100%.

В общих словах могу сказать про метод сжатия так:
бит 3-чных чисел(сжат.) 3-ичных чисел(не сжат.) 2(4) 1(3) 1 3(8) 1(3) 1 4(16) 2(9) 2 5(32) 3(27) 2 6(64) 3(27) 3 7(128) 4(81) 3 8(256) 5(243) 4 9(512) 5(243) 4 10(1024) 6(729) 5 11(2048) 6(729) 5 12(4096) 7(2187) 6 13(8192) 8(6561) 6 .............

Надеюсь тенденция понятна. В скобках я указал 2 или 3 в степени.
т.е. в скобках и есть обоснование того что в 13 битах поместятся 8 троичных чисел.
Теперь если не понятно - объясню как на примере 5 бит.

В пяти битах у нас храниться число от 2в0 до 2в5-1,
т.е. от 0 до 31.

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

Т.е. 31(dec) = 11111(bin) = 1011(3)

Надеюсь понятно объяснил...

Ещё раз оговорюсь о ненужности этого всего - прикиньте сколько пересчитывать а потом ещё и 3,6,9 и т.д. конструкции склеивать так, чтобы в двоихные байты разместить

← →
KSergey (2004-01-18 06:58) [15]

> Кен © (18.01.04 01:14) [10]
>
> > KSergey © (17.01.04 13:49) [9]
> > Предлагаю автору перейти на четверичную (четвертичную?)
>
> > систему - и проблема отпадет сама собой.
>
> Каким образом ?

А напрячь свои способности по "теоритеческому программированию" - не наше это барское дело? ;)
Я о том, что если перейти к системе с основанием 4, то все ровно ляжет в 2 бита - а значит проблема с "неплотностью" отпадет сама собой.

← →
Palladin (2004-01-18 19:35) [16]

> Кен © (18.01.04 02:52) [13]

Куда выше? Что там выше? Сполшное не понимание, вот что там...

← →
Кен (2004-01-19 01:53) [17]

> Dima_dvp © (18.01.04 03:59) [14]
> Надеюсь понятно объяснил...

Нет. Непонятно. Объяснить я и сам могу. Как сделать то ?

> В данном конкретном случае это действительно теория ибо
> сжатие сэкономит 25% объёма

Нет не 25, а 33,(3), именно из-за этого и проблемы с запихиванием, что число некруглое.

> KSergey © (18.01.04 06:58) [15]
> А напрячь свои способности по "теоритеческому программированию"
> - не наше это барское дело? ;)

А тут только лёгкие задачи интересны ? Над которыми думать ненадо.

← →
ЮЮ (2004-01-19 06:03) [18]

> А тут только лёгкие задачи интересны ? Над которыми думать ненадо.

Если приходится думать об экономии 2х битов из 8ми задействованных, то здесь речь уже идет не об экономии памяти (2К на 1000 объектов - потеря смехотворная), сколько о проблемах алгоритма, для которого роиходится выделять столько памяти, что приходится экономить на крохах.

Вот над алгоритмом и подумай, имхо, это и есть самое интересное (и самое нетривиальное) в программировании

← →
KSergey (2004-01-19 07:12) [19]

> [17] Кен © (19.01.04 01:53)
> А тут только лёгкие задачи интересны ? Над которыми думать
> ненадо.

А кому-то охото за тебя напрягаться? Тебе интересно - ты и думай.

← →
Anatoly Podgoretsky (2004-01-19 08:54) [20]

Кен © (19.01.04 01:53) [17]
А тут только лёгкие задачи интересны ? Над которыми думать ненадо.

Бори лень ума, возможно со временем и трудные задачи станут интересны. Хотя сомневаюсь.

← →
Dima_dvp (2004-01-19 13:09) [21]

> > Dima_dvp © (18.01.04 03:59) [14]
> > Надеюсь понятно объяснил...
>
> Нет. Непонятно. Объяснить я и сам могу. Как сделать то ?

Ну сначала надо определиться с задачей. У тебя просто надо сохранить набор одноразрядных троичных чисел? Сколько их? Может их числдо переменное?

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

Функция должна работать примерно так:

//Предполагаем что изначально числа храняться в массиве (20 штук) - каждый элемент - одно троичное число // a - указатель на массив байтов (каждый байт - для удобства - одно троичное число) function Pack(a: ^Byte) : DWORD; var i: Byte; begin //Изначально у нас пустое число Result := 0; //Известно что результирующее число получаеться как //a[0]*3^0 + a[1]*3^1 + a[2]*3^2 + a[3]*3^3 + .... for i:=0 to 19 do begin Result := Result + a[i]*Pow(3,i); //Pow(3,i) - 3^i - помоему так возводить надо, но могу ошибаться end; end;

Итого на выходе ф-ии DWORD, содержащий в себе 20 троичных чисел.
Распаковывать надо по обратному алгоритму. Попробуй сделать сам, но скажу тебе что всё это примитивный перевод чисел из одной системы счисления в другую - это на информатьике в 9 классе проходят.

← →
alexnmsk (2004-01-19 15:12) [22]

> Кен © (17.01.04 02:28) [6]

> Это не то. Вопрос как в памяти, которая двоичная, разместить
> переменные которые могут принимать три значения ?

Если имеется ввиду хранение переменных, которые могут принимать ТОЛЬКО три значения, то складываем их по принципу
n1*3^0+n2*3^1+n3*3^2+n4*3^3... а затем переводим их третичной системы в обычную. Получаем вполне упакованные зачения. Хотя избыточность в конце массива данных все равно неизбежна (часть байта под переменные не отведешь).

← →
alexnmsk (2004-01-19 15:17) [23]

Прошу прощения. После складывания никакой перевод не нужен, мы уже получаем в значения в удобоваримом формате..

← →
Dima_dvp (2004-01-19 18:13) [24]

alexnmsk (19.01.04 15:12) [22] - а я что-то другое написал?

← →
Кен (2004-01-24 02:57) [25]

Эта формула и так понятна : n1*3^0+n2*3^1+n3*3^2+n4*3^3

Вопрос, что Вы для 50 мегабайт так и будете 3 в степени возводить ? Там степень со ста нулями получится. В High(Intgeger) не впишетесь.

Для байта или нескольких байт это работает. А для большего нужен другой подход.

Как подружить тритичную систему с двоичной ? Найти похожие ветки