Уважаемые участники форума!
Не могли вы поделиться общей информацией, связанной с принципами перевода алгоритма, оперирующего с действительными числами, на целочисленную арифметику. К примеру, алгоритм выполняет какие-то операции над действительными числами, но хотелось, чтобы все операции проводились в целочисленной форме. Данная проблема возникает при использовании целочисленных процессоров и переноса на них различных математических моделей. Общие сведения про форматы хранения дробных чисел типа Q14, Q15 имеются, но хотелось бы капнуть глубже... В большей степени интересует решение систем, интерполяция...

Интересно. С pentium'ами об этом люди уже забыли. Я посмотрю, что у меня осталось с прошлых лет. Напишу чего-нибудь. Но, по-моему, есть инфа только про операции сложения, умножения и т.п. А решение систем и интерполяция - это уже алгоритмы, которые пользуются сложением и т.п. Сами они ни сколько не меняются.

Даже вроде бы есть специальный раздел математики, который занимается целочисленными вычисленниями.

Цитата

Даже вроде бы есть специальный раздел математики, который занимается целочисленными вычисленниями.

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

Цитата

Я посмотрю, что у меня осталось с прошлых лет.

Буду очень признателен...

Цитата

Буду очень признателен...

Не осталось ничего ни на бумаге, ни в компе. Однако, я думаю, что ты и так всё это знаешь. Вот немного теории нашёл. http://old.sgu.ru/kafedra/teorin/Lekciya_55.htm.
А методу перевода работающей проги на другую платформу я предлагал в другой теме. Если на C++, то надо операторы перегружать. На asm придётся переписывать код.

Напиши поподробнее о программе, которую переводишь.

Цитата(val @ 22.9.2003, 11:53)

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

Давайте разложим все по полкам. Знаете, что такое математическое программирование? Это раздел прикладной математики, который занимается решением задач оптимального управления, т.е. задач на отыскание наилучшего в заранее оговоренном смысле способа осуществления целенаправленного динамического процесса. Данный процесс, как правило, может быть описан дифференциальными, интегральными и иными соотношениями, зависящими от параметров, подлежащих определению. Данные соотношения называют целевыми функционалами (функциями), а параметры - управляемыми переменными. Как правило, на целевые функции накладывают ряд условий и ограничений, существенно осложняющие поиск оптимального решения.
В задачах математического программирования в качестве дополнительного условия на значения управляемых параметров может быть наложено условие целочесленности (иногда дискретности). В этом случае имеет место задача целочисленного (дискретного) программирования. Методы и алгоритмы решения таких задач составляют раздел "Целочисленное программирование".

Однако целочисленные вычисления встречаются не только в методах оптимизации. Существуют способы выполнения различного рода преобразований (в т.ч. Фурье, вейвлет), выполняемых в целочисленном виде. Это делают по разным причинам. Где-то специально для внедрения ПО в специализированное вычислительное устройство. Где-то эта необходимость продиктована целочисленной (или дискретной) природой исходных данных, и за счет целочисленных вычислений (над целочисленными данными!) стараются добиться высокой точности либо быстродействия.

val
Постарайся найти книгу Маклеллан, Рейдер. Применение теории чисел в цифровой обработке сигналов. В магазине искать бесполезно, разве что в "Старой книге", так что дуй в библиотеку. Эта книга тебе точно поможет.

Цитата

так что дуй в библиотеку

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

Цитата

анализ показал, что строгой методики конвертации плавующей запятой в фиксированную пока не разработано

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

Цитата

зато вычисления с фиксированной запятой значительно быстрее и проще, как следствие более короткий код

C этой точки зрения интересно будет посмотреть, что сделано в системе MATLAB. В его состав входит такой Fixed-Point Blockset, позволяющий моделировать эффекты, возникающие в системах, которые используют арифметику с фиксированной точкой.
http://www.matlab.ru/fixedpoint/default.asp (на странице важные ссылки!)

Цитата

Ты какие алгоритмы сейчас ищешь? И с каким представлением числа работаешь?

У меня есть программа, написанная на С++, с использованием классов, типов с плавующей запятой, статических и динимических структур данных. Такой код неуспевает в 100 раз.
Я уже избавился от классов и динимических структур данных, осталость избавиться от плавующей запятой. Нужна методика конвертации кода с плавующей запятой с фиксированную...

Совет не универсальный, но...
Предположим, в текущей постановке задачи какие-то данные
принимают диапазон [-1..1] и с плавающей точкой. А на твоей системе
быстро выполняются действия с 32-разрядным int'ом (+-2000000000).
Так вот, домножай твои данные на эти 2 миллиарда и - вперед,
с fixed point.
Ситуации бывают, конечно, всякие, например, когда промежуточные
результаты получаются гораздо больше по модулю, чем входные данные.
Что же, тогда домножай входные данные менее чем на два миллиарда.
Все это, конечно, тривиально и не всегда применимо.
Floating point на то и изобрели, чтобы поменьше зависеть
от такого рода особенностей.

Это сообщение отредактировал(а) Crait - 24.9.2003, 16:03

Цитата

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

А вот хороший способ борьбы с переполнениями - воспользоваться китайской теоремой об остатках. Строишь свою арифметику в остаточных классах и вперед! Подробности есть в упомянутой книге МакКлеллана и Рейдера, а также у Кнута (2-й том, у него называется, кажись, "модулярные вычисления").

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