Столкнулся со следующей проблемой. Пишу язык высокого уровня для программирования микроконтроллера. Хотелось бы иметь возможность вычисления арифметических и логических выражений. Но в микроконтроллере предусмотрена работа только с целыми числами (даже аппаратного деления нацело нет). Так вот мне пришла в голову следующая идея. Для практических нужд вполне хватит рациональных чисел, а они, как известно, отождествляются с парой целых (числитель, знаменатель). Потому можно в контроллере все числа, с которыми идет работа, представлять парами целых и реализовать арифметику следующим образом:

пусть u,u' - рациональные числа:  

u  <-> (m, n)
u' <-> (m',n')

(предполагается, что в записи рационального числа парой (числитель, знаменатель) знаменатель всегда неотрицателен).

Тогда:

u + u' <-> (mn' + m'n, nn')
u - u' <-> (mn' - m'n, nn')
uu'    <-> (mm', nn')
u/u'   <-> (mn', m'n)
 
u < u'  <-> mn' < m'n

и, что интересно, если ввести сопоставление:

+∞    <-> всякая пара вида (□, 0),  где □ - некоторое натуральнео число > 0
-∞    <-> всякая пара вида (-□, 0),
0     <-> всякая пара вида (0, □),
Undef <-> (0,0),

то получим вполне адекватную расширенную арифметику:

+∞ + u <-> (□,0) + (m,n) = (□,0) <->  +∞
+∞ u   <-> (□,0)(m,n)    = (□,0) <->  +∞
+∞/u   <-> (□,0)/(m,n)   = (□,0) <->  +∞
u/+∞   <-> (m,n)/(□,0)   = (0,□) <-> 0  

+∞ + (-∞) <-> (□,0) + (-□,0) = (0,0) <-> Undef
+∞ 0      <-> (□,0) (0,1)   = (0,0)  <-> Undef

Что вы думаете на этот счет. Какие здесь подводные камни?
П.С. Умножение/сложение в контроллере быстрое (~одного такта).

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

__>Столкнулся со следующей проблемой. Пишу язык высокого уровня для программирования микроконтроллера. Хотелось бы иметь возможность вычисления арифметических и логических выражений. Но в микроконтроллере предусмотрена работа только с целыми числами (даже аппаратного деления нацело нет). Так вот мне пришла в голову следующая идея. Для практических нужд вполне хватит рациональных чисел, а они, как известно, отождествляются с парой целых (числитель, знаменатель).
А почему не с фиксированной точкой? Правда тогда деление будет нужно.

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

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

__>>Столкнулся со следующей проблемой. Пишу язык высокого уровня для программирования микроконтроллера. Хотелось бы иметь возможность вычисления арифметических и логических выражений. Но в микроконтроллере предусмотрена работа только с целыми числами (даже аппаратного деления нацело нет). Так вот мне пришла в голову следующая идея. Для практических нужд вполне хватит рациональных чисел, а они, как известно, отождествляются с парой целых (числитель, знаменатель).
LD>А почему не с фиксированной точкой? Правда тогда деление будет нужно.
И не только. Например, результат деления 1/3 = 0.(3) не может точно быть представлен в формате с фиксированной точкой, а потому точность будет потеряна обрезанием его до какого-нибудь 0.3333333. В дробно-рациональном же представлении все ОК — точность вычислений 100%.

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

__>И не только. Например, результат деления 1/3 = 0.(3) не может точно быть представлен в формате с фиксированной точкой, а потому точность будет потеряна обрезанием его до какого-нибудь 0.3333333. В дробно-рациональном же представлении все ОК — точность вычислений 100%.

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

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

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

__>>И не только. Например, результат деления 1/3 = 0.(3) не может точно быть представлен в формате с фиксированной точкой, а потому точность будет потеряна обрезанием его до какого-нибудь 0.3333333. В дробно-рациональном же представлении все ОК — точность вычислений 100%.

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

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

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

Здравствуйте, _hum_,

__>И еще, кто-нить знает быстрый алгоритм округления рац. дробей (быстрый в смысле моих быстрых операций умножения и сложения/вычитания)?
--
Посмотрите в книге "Hacker's delight".

С уважением,
Геннадий Майко.

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

__>И еще, кто-нить знает быстрый алгоритм округления рац. дробей (быстрый в смысле моих быстрых операций умножения и сложения/вычитания)?
Спуск в дереве Штерна—Броко, например.

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

ГМ>Здравствуйте, _hum_,

__>>И еще, кто-нить знает быстрый алгоритм округления рац. дробей (быстрый в смысле моих быстрых операций умножения и сложения/вычитания)?
ГМ>--
ГМ>Посмотрите в книге "Hacker's delight".

ГМ>С уважением,
ГМ>Геннадий Майко.

Спасибо, гляну.

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

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

__>>И еще, кто-нить знает быстрый алгоритм округления рац. дробей (быстрый в смысле моих быстрых операций умножения и сложения/вычитания)?
WM>Спуск в дереве Штерна—Броко, например.

Посмотрел дерево Штерна—Броко. Довольно интересная вещь, не знал. Но как его использовать для быстрого округления все же не увидел (ведь спуск для больших числителя или знаменателя будет очень долго осуществляться). Можете пояснить свою мысль или указать литературу, где об этом бы говорилось?

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

__>Здравствуйте, watch-maker, Вы писали:

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

__>>>И еще, кто-нить знает быстрый алгоритм округления рац. дробей (быстрый в смысле моих быстрых операций умножения и сложения/вычитания)?
WM>>Спуск в дереве Штерна—Броко, например.

__>Можете пояснить свою мысль или указать литературу, где об этом бы говорилось?

Про свойство дерева можно прочитать в частности в книге «Конкретная математика. Математические основы информатики». Сам алгоритм поиска дробей описан много где: пример, пример (нужно только выкинуть лишнее вроде операций со строками).

__>как его использовать для быстрого округления все же не увидел (ведь спуск для больших числителя или знаменателя будет очень долго осуществляться).
Скорость сходимости в нём зависит от самого значения числа. После пары поворотов в дереве и числитель и знаменатель начинают стремительно расти, а само приближение, соответственно, быстро сходится. Проблема есть именно когда мы идём долго влево или вправо не сворачивая — в этом случае прибавляются слишком малые числа чтобы началось ускорение. Это можно исправить разными способами. Например, отлавливая такие числа и запуская поиск не из корня дерева.
Можно использовать связь дерева Штерна—Броко с цепными дробями — они дают эквивалентный результат, но сходится быстрее. И именно этот алгоритм часто используется на практике (смотри, например, на функцию limit_denominator).
Но, разумеется, для эффективной работы с цепными дробями нужно уметь делить целые числа. В общем-то, операция деления целых чисел при работе с рациональными дробями нужна не меньше чем при реализации арифметики с плавающей или с фиксированной запятой. А скорее нужна даже больше — ведь в арифметике с запятой делить требуется, собственно, только при явном делении двух чисел, а в арифметики с рациональными дробями — практически после каждой операции сложения или вычитания.
В общем, если тебе хочется избежать реализации деления любой ценой, то использование рациональных дробей тебе в этом не поможет (конечно пока у твоего компьютера не бесконечная память или типа того).

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

WM>В общем, если тебе хочется избежать реализации деления любой ценой, то использование рациональных дробей тебе в этом не поможет (конечно пока у твоего компьютера не бесконечная память или типа того).

А что поможет? Есть какие-то системы счисления, в которых легко деление выполнять?

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

__>Для практических нужд вполне хватит рациональных чисел, а они, как известно, отождествляются с парой целых (числитель, знаменатель).
Не хватит. Твои рациональные числа покроют пространство от (2^N-1)/1 и до 1/(2^N-1). N — разрядность твоего процессора.
Если тебе надо выразить число, скажем, 1.23E22 — ты в глубокой жеппе.
То, есть, тебе надо гуглить на тему "floating point emulation". Первое, что приходит на ум, покопайся в исходниках GCC, точнее его библиотеки libgcc

__>Потому можно в контроллере все числа, с которыми идет работа, представлять парами целых и реализовать арифметику следующим образом:
Для рациональных чисел можно ограничиться сложением, умножением и операцией "наибольший общий делитель" — GCD.
Для GCD есть быстрый алгоритм "binary GCD" — он хорошо описан в книге "Handbook of applied cryptograpy", глава 14
По поводу остальных операций — посмотри на реализацию класса "rational" в Бусте (boost.org)

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

__>Здравствуйте, watch-maker, Вы писали:

WM>>В общем, если тебе хочется избежать реализации деления любой ценой, то использование рациональных дробей тебе в этом не поможет (конечно пока у твоего компьютера не бесконечная память или типа того).
__>А что поможет?
Реализация деления. После этого ты уже сможешь выбирать между плавающей и фиксированной запятой, между рациональными и цепными дробями.
Есть хорошие обзоры, есть уже написанные библиотеки. В конце-концов, те, кому лень реализовывать быстрые алгоритмы, берут те же побитовые реализации, которым вообще ничего кроме сложений да битовой логики не нужно. Да, они не очень быстры, но хотя бы легко реализуются.

Ну и раз ты говоришь, что
__>Пишу язык высокого уровня для программирования микроконтроллера.
то посмотри обязательно на книгу, которую тебе посоветовали раньше. Если ты делишь на константу, то как раз от деления можно избавится на этапе компиляции. Если же деление идёт на переменную, то, конечно, придётся делить более-менее честно.

__>Есть какие-то системы счисления, в которых легко деление выполнять?
Конечно есть. Но в них наоборот операции типа сложения превращаются в ад.

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

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

__>>Для практических нужд вполне хватит рациональных чисел, а они, как известно, отождествляются с парой целых (числитель, знаменатель).
DEA>Не хватит.
От целей зависит.

__>>Потому можно в контроллере все числа, с которыми идет работа, представлять парами целых и реализовать арифметику следующим образом:
DEA>Для рациональных чисел можно ограничиться сложением, умножением и операцией "наибольший общий делитель" — GCD.
Что значит "можно ограничиться"? Что делать, когда после очередного сложения знаменатель не влезет в отведённую память?

DEA>Для GCD есть быстрый алгоритм "binary GCD"
Ну нашел НОД, а зачем? Дальше что с ним делать?
Вроде на него часто делят? Но для этого нужно уметь делить!

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

__>>>Для практических нужд вполне хватит рациональных чисел, а они, как известно, отождествляются с парой целых (числитель, знаменатель).
DEA>>Не хватит.
WM>От целей зависит.
Гм. А можно эти цели озвучить, а то они странные какие-то....

WM>Что значит "можно ограничиться"? Что делать, когда после очередного сложения знаменатель не влезет в отведённую память?
Вот от этого тебя плавающая точка и спасет. Точнее, заменит одну проблему на другую — выход за вычислимые пределы на потерю точности.

DEA>>Для GCD есть быстрый алгоритм "binary GCD"
WM>Ну нашел НОД, а зачем? Дальше что с ним делать?
Солить на зиму, вестимо. А еще можно почитать исходники rational в Бусте, как я советовал ранее.

WM>Вроде на него часто делят? Но для этого нужно уметь делить!
Shift-subtract division спасет отца демократии. В Hackers Delight есть очень удобный алгоритм для этого.

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

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

__>>Здравствуйте, watch-maker, Вы писали:

WM>>>В общем, если тебе хочется избежать реализации деления любой ценой, то использование рациональных дробей тебе в этом не поможет (конечно пока у твоего компьютера не бесконечная память или типа того).
__>>А что поможет?
WM>Реализация деления. После этого ты уже сможешь выбирать между плавающей и фиксированной запятой, между рациональными и цепными дробями.
WM>Есть хорошие обзоры, есть уже написанные библиотеки. В конце-концов, те, кому лень реализовывать быстрые алгоритмы, берут те же побитовые реализации, которым вообще ничего кроме сложений да битовой логики не нужно. Да, они не очень быстры, но хотя бы легко реализуются.

WM>Ну и раз ты говоришь, что
__>>Пишу язык высокого уровня для программирования микроконтроллера.
WM>то посмотри обязательно на книгу, которую тебе посоветовали раньше. Если ты делишь на константу, то как раз от деления можно избавится на этапе компиляции. Если же деление идёт на переменную, то, конечно, придётся делить более-менее честно.

__>>Есть какие-то системы счисления, в которых легко деление выполнять?
WM>Конечно есть. Но в них наоборот операции типа сложения превращаются в ад.


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

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

арифметическое_выражение_1 отношение_сравнения арифметическое_выражение_2

где каждое арифметическое_выражение удовлетворяет условиям:

1) содержит только операции +,-,*,/, количество вхождений которых не превышает, скажем так, 100;
2) входящие в него значения не превышают по абсолютной величине, скажем так, 2000;
3) относительная погрешность вычисления выражения не превосходит некоторой заранее известной и не зависящей от этого выражения величины, например 0.01%.


с учетом того, что разрядность регистров — 32, однотактовые операции — умножение, сложение, вычитание, сдвиг на один разряд, сдвиг на 8, 16.

Как я понимаю, условию 3) удовлетворяет именно floating-point arithmetic, но у нее проблемы с делением — не менее 45 тактов (про умножение и сложение не в курсе, но скорее всего приемлемо).
У дробно-рационального подхода проблема с п.3) — даже если бы можно было быстро делить нацело (чего скорее всего нельзя, ибо, насколько я понимаю, в лучшем случая все равно сложность ~ разрядность числа), то непонятно, какое на его основе округление использовать, чтобы гарантировать одинаковую относительную ошибку округления.

Мдаа...Оказывается, тут целая наука вылазит. Кто бы мог подумать...

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

__>Мне бы хотелось уметь быстро (не более 10 тактов/операцию) вычислять логические выражения вида
__>где каждое арифметическое_выражение удовлетворяет условиям:
__>1) содержит только операции +,-,*,/, количество вхождений которых не превышает, скажем так, 100;
__>2) входящие в него значения не превышают по абсолютной величине, скажем так, 2000;
__>3) относительная погрешность вычисления выражения не превосходит некоторой заранее известной и не зависящей от этого выражения величины, например 0.01%.


__>с учетом того, что разрядность регистров — 32, однотактовые операции — умножение, сложение, вычитание, сдвиг на один разряд, сдвиг на 8, 16.

__>Как я понимаю, условию 3) удовлетворяет именно floating-point arithmetic,
Нет. Плавающая запятая довольно быстро может набирать относительную погрешность. Но при правильном алгоритме, который учитывает особенности её работы, можно замедлить скорость её накопления. Так если тебе нужно найти сумму массива, то стоит использовать алгоритм Кэхэна. А если нужно решить простую СЛАУ методом Гаусса, то обязательно нужно выбирать ведущий элемент. Если этого не делать, то при вычислениях ошибка может накапливаться слишком быстро. Хотя сами по себе формулы абсолютно точные.

Пункт 3 — это вообще очень серьёзное требование. А совместно с требованием к скорости — прямо фантастика.

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

DEA>>>Для GCD есть быстрый алгоритм "binary GCD"
WM>>Ну нашел НОД, а зачем? Дальше что с ним делать?
DEA>Солить на зиму, вестимо. А еще можно почитать исходники rational в Бусте, как я советовал ранее.
Да boost::rational вообще отвратительная библиотека. Не стоит на неё ориентироваться

The rational number class is designed for use in conjunction with an unlimited precision integer class. With such a class, rationals are always exact, and no problems arise with precision loss, overflow or underflow.

При использовании в качестве базового типа чисел с бесконечной точностью в boost::rational нельзя контролировать потребление памяти (а она очень быстро заканчивается). А при использовании в качестве базового типа более привычных int32_t она выдаёт неверный результат — не кидает исключение, не находит ближайшее представимое число (как это обычно происходит для float или как это можно делать в python.fractions), а просто выдаёт мусор.

WM>>Вроде на него часто делят? Но для этого нужно уметь делить!
DEA>Shift-subtract division спасет отца демократии. В Hackers Delight есть очень удобный алгоритм для этого.
Конечно. Только если уметь делить, то вся возня с рациональными дробями становится совершенно не нужна. Во всяком случае я именно так понимаю автора темы.

Здравствуйте, watch-maker

Ясно. В этом деле, оказывается, столько нюансов и подводных камней, что лучше самому не сунуться. Да я как бы и не хотел влазить во все эти погрешности, наивно понадеявшись на то, что использование "отложенного деления" в виде пар чисел позволит избежать всей этой мороки. Но, видать, не судьба (хотя меня все-таки мучают подозрения, что мой случай, в котором нужно только в конце-концов сравнить числа, без необходимости конкретного представления этих чисел, все-таки мог дать выигрыш).