Идея алгоритма состоит в повышении точности машинного представления чисел в выбранном диапазоне, за счет снижения точности за его пределами.

Грубо, в интервал [-a..a] попадает 90% всех чисел и их нужно представлять с высокой степенью точности. Оставшиеся 10% попадают в интервал [-10a..10a]. Их тоже надо регистрировать, но требования к точности минимальны. Память ограничена.

Еще грубее. С помощью одного байта можно представить числа из диапазона -128..127 с точностью до целых. Как одним байтом закодировать числа интервала [-10..10] с точностью до 0.125, а числа интервалов [-128..-10, 10..127] с точностью +-5?

http://en.wikipedia.org/wiki/G.711
и рядом по ссылкам

Здравствуйте, horry, Вы писали:

H>Идея алгоритма состоит в повышении точности машинного представления чисел в выбранном диапазоне, за счет снижения точности за его пределами.

H>Грубо, в интервал [-a..a] попадает 90% всех чисел и их нужно представлять с высокой степенью точности. Оставшиеся 10% попадают в интервал [-10a..10a]. Их тоже надо регистрировать, но требования к точности минимальны. Память ограничена.

H>Еще грубее. С помощью одного байта можно представить числа из диапазона -128..127 с точностью до целых. Как одним байтом закодировать числа интервала [-10..10] с точностью до 0.125, а числа интервалов [-128..-10, 10..127] с точностью +-5?

Может я чего не понимаю, но по-моему этот алгоритм называется арифметическая прогрессия Ссылка на школьный учебник математики не помню какого класса. То есть в данном случае байт придется разбить на 3 части, и применить там 3 прогрессии с разными начальными условиями. Вроде все....

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, horry, Вы писали:

H>>Идея алгоритма состоит в повышении точности машинного представления чисел в выбранном диапазоне, за счет снижения точности за его пределами.

H>>Грубо, в интервал [-a..a] попадает 90% всех чисел и их нужно представлять с высокой степенью точности. Оставшиеся 10% попадают в интервал [-10a..10a]. Их тоже надо регистрировать, но требования к точности минимальны. Память ограничена.

H>>Еще грубее. С помощью одного байта можно представить числа из диапазона -128..127 с точностью до целых. Как одним байтом закодировать числа интервала [-10..10] с точностью до 0.125, а числа интервалов [-128..-10, 10..127] с точностью +-5?

А>Может я чего не понимаю, но по-моему этот алгоритм называется арифметическая прогрессия Ссылка на школьный учебник математики не помню какого класса. То есть в данном случае байт придется разбить на 3 части, и применить там 3 прогрессии с разными начальными условиями. Вроде все....

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

Здравствуйте, horry, Вы писали:

H>Еще грубее. С помощью одного байта можно представить числа из диапазона -128..127 с точностью до целых. Как одним байтом закодировать числа интервала [-10..10] с точностью до 0.125, а числа интервалов [-128..-10, 10..127] с точностью +-5?

Можно сделать плавно. 1. Нормализуем диапазон [0...max] к [0...1] и берем корень некой степени v'=pow(v,1/p);
2. Приводим снова диапазону [0...max]. 3. Для декодирования — то же самое, но надо брать v'=pow(v,p); 4. Для отрицательных чисел — аналогично. Чем больше p, тем точнее представлены малые значения. Для небольших диапазонов обычно используется предварительно вычисленные таблицы подстановки. Так работает, например, преобразование из sRGB в linear RGB и обратно.

Здравствуйте, horry, Вы писали:

H> Если бы это было так просто, я бы и сам догадался. От арифметической прогрессии до этого алгоритма как пешком до южного полюса. Сгущений частот-то на интервале может быть несколько.

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

Здравствуйте, horry, Вы писали:

H>Идея алгоритма состоит в повышении точности машинного представления чисел в выбранном диапазоне, за счет снижения точности за его пределами.

H>Грубо, в интервал [-a..a] попадает 90% всех чисел и их нужно представлять с высокой степенью точности. Оставшиеся 10% попадают в интервал [-10a..10a]. Их тоже надо регистрировать, но требования к точности минимальны. Память ограничена.

H>Еще грубее. С помощью одного байта можно представить числа из диапазона -128..127 с точностью до целых. Как одним байтом закодировать числа интервала [-10..10] с точностью до 0.125, а числа интервалов [-128..-10, 10..127] с точностью +-5?

Я бы сделал что-то вроде этого.

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

Плюс такого представления -- монотонность, т.е. число + 0x0000...001 всегда равно следующему числу.
Еще один плюс -- это то, что действуют обычные правила перевода положительных чисел в отрицательные и наоборот, т.е. если иметь тип int, скажем, для такого представления, то -i будет действительно -i.

Ну на примере с одним байтом и двумя диапазонами чисел.

0 0 abcdef = 0abcdef / m (дробное в двоичной записи)
0 1 abcdef = 64 / m + ( 0abcdef ) * n (в двоичной записи)
1 1 abcdef = 1abcdef / m, где первая единица означает, что это отрицательное знаковое число из 7 двоичных бит, например, 1111111 = -1, 1111110 = -2 и т.д.
1 0 abcdef = — 64 / m + ( 1abcdef ) * n (то, что в скобках после плюса на самом деле отрицательное)

Тогда
10000000 = -64 / m — 64 * n
10000001 = -64 / m — 63 * n
...
10111111 = -64 / m — 1 * n
11000000 = -64 / m
11000001 = -63 / m
...
11111111 = -1 / m
00000000 = 0 / m
00000001 = 1 / m
...
00111111 = 63 / m
01000000 = 64 / m + 0 * n
01000001 = 64 / m + 1 * n
...
01111111 = 64 / m + 63 * n

Осталось только подобрать m и n по вкусу!
Например, m=8 и n=2 дает числа [-8..8] с точностью 1/8, а остальные из [-136, 134] -- с точностью +-2.

Только надо помнить, что сложение, вычитание и т.п. чисел БУДЕТ ВЕРНЫМ, но в пределах одного диапазона. Лучше все это хозяйство оформить как класс и автоматически отслеживать действия над такими числами.

В более общем виде можно выделить k бит под идентификацию диапазона и делать 2^k-1 "прыжков".

Здравствуйте, vadimcher, Вы писали:

V>Я бы сделал что-то вроде этого.

V>Старший бит -- знак, затем несколько бит (один, например) -- диапазон, а далее представление числа, которое трансформируется согласно диапазону, в котором число находится.

Поздрвляю! Ты изобрел представление чисел с плавающей точкой.

Здравствуйте, horry, Вы писали:

H>Грубо, в интервал [-a..a] попадает 90% всех чисел и их нужно представлять с высокой степенью точности. Оставшиеся 10% попадают в интервал [-10a..10a]. Их тоже надо регистрировать, но требования к точности минимальны. Память ограничена.

H>Еще грубее. С помощью одного байта можно представить числа из диапазона -128..127 с точностью до целых. Как одним байтом закодировать числа интервала [-10..10] с точностью до 0.125, а числа интервалов [-128..-10, 10..127] с точностью +-5?

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

Варианты впихивания:

1) [0.0, 10.0) в 6 бит, точность 10/64 = 0.15625; [10.0, 128.0) в 6 бит, точность 118/64 = 1.84375
2) [0.0, 8.0) в 6 бит, точность 8/64 = 0.125; [8.0, 128.0) в 6 бит, точность 120/64 = 1.875

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

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, vadimcher, Вы писали:

V>>Я бы сделал что-то вроде этого.

V>>Старший бит -- знак, затем несколько бит (один, например) -- диапазон, а далее представление числа, которое трансформируется согласно диапазону, в котором число находится.

MS>Поздрвляю! Ты изобрел представление чисел с плавающей точкой.

(с) Читайте внимательнее, а потом "выпендривайтесь".

Здравствуйте, horry, Вы писали:

H>Идея алгоритма состоит в повышении точности машинного представления чисел в выбранном диапазоне, за счет снижения точности за его пределами.

H>Грубо, в интервал [-a..a] попадает 90% всех чисел и их нужно представлять с высокой степенью точности. Оставшиеся 10% попадают в интервал [-10a..10a]. Их тоже надо регистрировать, но требования к точности минимальны. Память ограничена.

H>Еще грубее. С помощью одного байта можно представить числа из диапазона -128..127 с точностью до целых. Как одним байтом закодировать числа интервала [-10..10] с точностью до 0.125, а числа интервалов [-128..-10, 10..127] с точностью +-5?

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

В итоге, нашел сам. Алгоритм называется "Интервальное кодирование".

Спасибо всем, кто хотя бы пытался ответить на мой вопрос.

H>К сожалению, читать заголовок темы, видимо, не любит никто. Народ, мне нужно было не направление, в котором надо двигаться для решения задачи и даже не наполовину готовые самопальные алгоритмы, а название и ссылка на один-единственный существующий алгоритм (устроило бы даже только название, ссылка для проверки).
H>В итоге, нашел сам. Алгоритм называется "Интервальное кодирование".
H>Спасибо всем, кто хотя бы пытался ответить на мой вопрос.

Ну уж, тогда, ссылочкой поделитесь, please

Здравствуйте, horry, Вы писали:

H>К сожалению, читать заголовок темы, видимо, не любит никто. Народ, мне нужно было не направление, в котором надо двигаться для решения задачи и даже не наполовину готовые самопальные алгоритмы, а название и ссылка на один-единственный существующий алгоритм (устроило бы даже только название, ссылка для проверки).

H>В итоге, нашел сам. Алгоритм называется "Интервальное кодирование".

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

Ну а во-вторых, про арифметическое кодирование я тебе, кажется, писал Разве это не то же самое, что "интервальное кодирование", которое ты "в итоге, нашел сам"? Проясни-ка ситуацию

Здравствуйте, vadimcher, Вы писали:

MS>>Поздрвляю! Ты изобрел представление чисел с плавающей точкой.

V>(с) Читайте внимательнее, а потом "выпендривайтесь".

Было бы интересно услышать в чём разница... А то так сразу не очевидно.

Здравствуйте, a18, Вы писали:

H>>К сожалению, читать заголовок темы, видимо, не любит никто. Народ, мне нужно было не направление, в котором надо двигаться для решения задачи и даже не наполовину готовые самопальные алгоритмы, а название и ссылка на один-единственный существующий алгоритм (устроило бы даже только название, ссылка для проверки).
H>>В итоге, нашел сам. Алгоритм называется "Интервальное кодирование".
H>>Спасибо всем, кто хотя бы пытался ответить на мой вопрос.

a18>Ну уж, тогда, ссылочкой поделитесь, please

Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Скачал с www.compression.ru.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, horry, Вы писали:

H>>К сожалению, читать заголовок темы, видимо, не любит никто. Народ, мне нужно было не направление, в котором надо двигаться для решения задачи и даже не наполовину готовые самопальные алгоритмы, а название и ссылка на один-единственный существующий алгоритм (устроило бы даже только название, ссылка для проверки).

H>>В итоге, нашел сам. Алгоритм называется "Интервальное кодирование".

А>Во-первых, ты сам виноват. Из сформулированного тобой условия ясно следует, что ты испытываешь проблемы с размещением готовой информации в 1 байте. На этот вопрос тебе и отвечали. Понять, что в действительности хотелось, можно только раза с третьего, к тому же дополнительно включив телепатию. Так что учись правильно формулировать вопросы перед тем, как предъявлять претензии

Повторно отсылаю к заголовку темы. Какая телепатия нужна для того, чтобы понять из "Подскажите название алгоритма и ссылку на его описание", что нужно подсказать название алгоритма?

А>Ну а во-вторых, про арифметическое кодирование я тебе, кажется, писал Разве это не то же самое, что "интервальное кодирование", которое ты "в итоге, нашел сам"? Проясни-ка ситуацию

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

Здравствуйте, Константин, Вы писали:

К>Здравствуйте, vadimcher, Вы писали:

MS>>>Поздрвляю! Ты изобрел представление чисел с плавающей точкой.

V>>(с) Читайте внимательнее, а потом "выпендривайтесь".

К>Было бы интересно услышать в чём разница... А то так сразу не очевидно.

Сколькими способами в представлении чисел с плавающей точкой можно представить число 0, например? Многими.
В предложенном выше способе -- одним.

Задача была отобразить целые числа от -128 до 127 на [-128, 127] или похожий интервал так, чтобы в середине все шло часто, а по краям -- редко. Я это и сделал. Причем монотонно.

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

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

ЗЫ Для тех, кому интересно, здесь есть немного строгой теории неравномерного кодирования, а здесь описаны различные алгоритмы кодирования, применяемые в архиваторах (по состоянию на 2002 год). И вообще вся книжка достаточно толково написана -- кратко и по делу. С примерами.