LINUX.ORG.RU

Математика с фиксированной запятой для C++20

 


0

3

Посоны,

Мы тут сделали библиотеку для математики с фиксированной запятой на С++. Вот так работает:

const auto x = fixed::make::p<2>(1, 11);

Это число с двумя десятичными знаками после запятой представляющее 1.11.

const auto y = fixed::make::p<1>(1, 0);

Это число с одним десятичным знаком после запятой, представляющее 1.0.

const auto z = x + y;

Это сумма двух чисел.

А вот это ошибка компиляции:

fixed::make::p<3, uint8_t>((uint8_t)0, 0);

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

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

Во время выполнения, переполнение тоже контролируется, все операции возвращают std::optional который при переполнении будет пустым.

Библиотека спроектирована так чтобы ни один бит информации ни при каких манипуляциях не терялся бы, либо если бит надо потерять, то это надо сделать явно и число станет неточным, на что тоже есть признак, который можно проверить вызвав fixed::is_accurate(x), и если какие-то биты были потеряны, то функция вернёт false.

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

Ссылка: https://bitbucket.org/alekseyt/fixed

Более полный пример использования: https://bitbucket.org/alekseyt/fixed/src/master/examples/basic.cpp

Заранее спасибо.



Последнее исправление: aleksey_tulinov (всего исправлений: 1)
Ответ на: комментарий от aleksey_tulinov

Точность меняется прямо время компиляции

Наводящий вопрос: 0.5 * 2.2 это 1.1 или 1.10? А почему? И как добиться 1.1 автоматически если precision это параметр типа?

bugfixer ★★★★★
()
Ответ на: комментарий от bugfixer

Для этого нужно оставаться в домене rationals - медленно, но верно.

А как мне рациональным числом представить корень из двух, например?

anonymous
()
Ответ на: комментарий от anonymous

Как сумму бесконечного ряда элементов из домена rationals - бесконечно медленно, но верно.

anonymous
()
Ответ на: комментарий от anonymous

Для этого нужно оставаться в домене rationals - медленно, но верно.

А как мне рациональным числом представить корень из двух, например?

Очевидно это выходит за рамки того что представимо decimals, но в отличие от того что ТС пытается продвинуть rationals хотя бы покрывают деление тоже, а не только сумму / разность / произведение. И не теряют точность пока переполнение или деление на ноль не случится.

bugfixer ★★★★★
()
Ответ на: комментарий от AntonI

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

  1. Если точность не нужна, то информацию о том, что числа получаются неточными можно игнорировать, просто не ассертить на fixed::is_accurate(), а если важна, то ассертить.

  2. Чем лучше - это мы и пытаемся выяснить. Теоретически можно добиться 100% точности, но с оговорками. Терять информацию - терять деньги, это плохо. Но например 1/3 всегда неточно, и если мы так делаем, то информация потеряется. Тут надо решить, что мы делаем, теряем деньги и делаем неточно, или как-то выкручиваемся и делаем точно. Если теряем деньги, то у допущенной неточности появляется цена, мы её знаем, и примерно знаем сколько стоит ошибка.

Вряд ли отвечает на вопросы, да? Общая цель - предотвратить уничтожение информации, получится ли это сделать, и надо ли это делать - надо посмотреть.

aleksey_tulinov
() автор топика
Ответ на: комментарий от bugfixer

0.5 * 2.2 - это 1.10, но приведение 1.10 к 1.1 не теряет точность и число 1.1 получится точным. Это тоже поддерживается.

aleksey_tulinov
() автор топика
Последнее исправление: aleksey_tulinov (всего исправлений: 1)
Ответ на: комментарий от bugfixer

Понижение точности 2 -> 1 делается во время компиляции, но флаг точно число или нет - это рантайм флаг и устанавливается во время выполнения операции.

Если понизить точность с двух знаков до одного знака у числа 1.11, то число 1.1 получится неточным, в рантайме, если понизить точность у числа 1.10, то 1.1 получится точным.

Это просто два разных признака. Один, precision, указывает на точность числа которое используется для вычислений, это компайлтайм параметр. Второй признак, accuracy, указывает на то, точно это число в принципе или не точно, это рантайм параметр.

aleksey_tulinov
() автор топика
Ответ на: комментарий от aleksey_tulinov

Понижение точности 2 -> 1 делается во время компиляции

Невозможно. В лучшем случае вы можете «попросить» сконвертировать и получить признак «а была ли потеря». Даже не смешно насколько это далеко от того чего можно достичь автоматически.

bugfixer ★★★★★
()
Ответ на: комментарий от bugfixer

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

aleksey_tulinov
() автор топика
Ответ на: комментарий от aleksey_tulinov

Больше скажу - у вас в принципе runtime «normalize» невозможен. Покажите мне signature если не верите.

bugfixer ★★★★★
()
Ответ на: комментарий от aleksey_tulinov

Ну да, это так и делается

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

bugfixer ★★★★★
()
Ответ на: комментарий от bugfixer

Как можно на тебя обижаться, ты такой милый. Тебе же дали исходники, возьми и посмотри. Мог бы хотя бы README прочитать для начала.

aleksey_tulinov
() автор топика
Последнее исправление: aleksey_tulinov (всего исправлений: 1)
Ответ на: комментарий от aleksey_tulinov

ты такой милый.

Даже не знаю как реагировать. «Ориентация север»? Где там пресловутый «Владимир»? Он заскучал.

Тебе же дали исходники, возьми и посмотри

Уже говорил - раньше выходных никак. А вообще - вы правда считаете что все прям вот растекаться будут? Типа мы там «шедевр» должны увидеть и головой в пол начать биться?

bugfixer ★★★★★
()
Ответ на: комментарий от aleksey_tulinov

Вряд ли отвечает на вопросы, да?

Совсем не отвечает;-( На первый вопрос Вы видимо ответа не знаете. На второй…

Теоретически можно добиться 100% точности, но с оговорками. Терять информацию - терять деньги, это плохо.

Теоретически есть две, и только две возможности вообще не терять деньги:

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

  2. Если не хотите терять деньги при потере информации - делайте атомарным распределение числа между счетами, так что бы сумма сохранялась. Это работает быстро, но немного странно выглядит - в такой алгебре нет операции деления а есть какая то функция

template <int D> void MyNumber::split(const std::array<float, D-1> fraction, std::array<MyNumber, D> &result) const;
// sum fraction <= 1

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

И слушайте внимательно @bugfixer, он в этой области съел столько собак что любой корейский гурман от зависти умрет.

AntonI ★★★★★
()
Последнее исправление: AntonI (всего исправлений: 1)
Ответ на: комментарий от Waterlaz

А так, видеть числовой тип, который … точно знает накопившуюся ошибку

причем в compile-time ;-) Не, это так не работает…

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

Ну, в compile-time – нет, а вот в runtime – почему бы и нет.

Waterlaz ★★★★★
()
Ответ на: комментарий от bugfixer

«Точно» здесь ключевое слово. Если интересует только оценка сверху - rationals можно обогнать.

Вполне всё делается точно, если под «точно» понимать «точная оценка сверху для данного представления числа»

Waterlaz ★★★★★
()
Ответ на: комментарий от bugfixer

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

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

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

aleksey_tulinov
() автор топика
Ответ на: комментарий от anonymous

Как сумму бесконечного ряда элементов из домена rationals - бесконечно медленно, но верно.

Даа? А говорят, что сумма рациональных чисел всегда рациональное число. Для тех кто в танке - корень из двух это нерациональное число и представить его рациональным числом или их суммой нельзя. Это раз. Ну и два - как ты видишь это в коде, бесконечную сумму? Она мало того, что неверная, так еще и бесконечная…

anonymous
()
Ответ на: комментарий от anonymous

сумма бесконечного ряда

сумма

И поскакали…

anonymous
()
Ответ на: комментарий от anonymous

Даа? А говорят, что сумма рациональных чисел всегда рациональное число. Для тех кто в танке - корень из двух это нерациональное число и представить его рациональным числом или их суммой нельзя.

Для тех, кто в танке, сумма ряда рациональных чисел может быть иррациональна. Шок, сенсация!

Ну и два - как ты видишь это в коде, бесконечную сумму? Она мало того, что неверная, так еще и бесконечная…

В Хаскеле из-за его ленивости вообще легко такое сделать. Но на любом языке можно, на самом деле. Опять же, внезапно :)

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Оасскажите скорее как можно на компутере в лоб посчитать бесконечную сумму за конечное время. Да еще и с приемлемой точностью.

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

Расскажите скорее как можно на компутере в лоб посчитать бесконечную сумму за конечное время. Да еще и с приемлемой точностью.

define посчитать :)

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Расскажите скорее как можно на компутере в лоб посчитать бесконечную сумму за конечное время. Да еще и с приемлемой точностью.

define посчитать :)

Вы меня прямо заинтриговали. А можно с этого места поподробнее? А то походу я что-то очень важное упустил в этой жизни…

bugfixer ★★★★★
()
Ответ на: комментарий от Waterlaz

define посчитать

Последовательность, как и числовой ряд, - упорядоченное счётное (бес)конечное множество. Математики сказали, что про определению «счётное», - молчи и считай!

anonymous
()

А вот это ошибка компиляции:

fixed::make::p<3, uint8_t>((uint8_t)0, 0); Компилятор видит, что в uint8_t нельзя представить три десятичных знака и выдаёт ошибку.

И снова не удержался. Вам очевидно что нолик или единичка в последнем разряде влезет в тот-же uint8_t вне зависимости от precision? И как вы вообще определяете что влезет / что нет в compile time учитывая что мантисса это в общем случае не constexpr?

bugfixer ★★★★★
()
Ответ на: комментарий от Waterlaz

А, ну да - берем какого нить математика, даем ему бумашку с карандашом, он считает, пишем это в дефайн и профит! Заявляем что это прекомпайл-тайм-калкулайшн.

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

А, ну да - берем какого нить математика, даем ему бумашку с карандашом, он считает, пишем это в дефайн и профит! Заявляем что это прекомпайл-тайм-калкулайшн.

Видимо, слишком много сленга в моих сообщениях.

«define посчитать» = что вы понимаете под словом посчитать? Представить его в памяти компьютера в двоичной системе счисления? Этого я сделать не могу, конечно, но что это за двоичный шовинизм? :)

Waterlaz ★★★★★
()
Ответ на: комментарий от bugfixer

Вы меня прямо заинтриговали. А можно с этого места поподробнее? А то походу я что-то очень важное упустил в этой жизни…

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

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Если мы представляем число как сумму бесконечного ряда

Кстати.

Можно ли вывести формулу для получения значения N-ого числа для любого бесконечного ряда, заданного некоими правилами?

Шутка

Попрошу привести формулу для получения N-ого простого числа …

anonymous
()
Ответ на: комментарий от anonymous

Можно ли вывести формулу для получения значения N-ого числа для любого бесконечного ряда, заданного некоими правилами?

В общем случае – нет.

Попрошу привести формулу для получения N-ого простого числа …

Формулу – нет, но алгоритм – совсем другое дело ;)

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

что вы понимаете под словом посчитать?

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

Представить его в памяти компьютера в двоичной системе счисления? Этого я сделать не могу

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

AntonI ★★★★★
()
Последнее исправление: AntonI (всего исправлений: 1)
Ответ на: комментарий от Waterlaz

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

Представить мы можем и анальный секс отрицательной бесконечности с положительной. А использовать в расчётах - нет.

LamerOk ★★★★★
()
Ответ на: комментарий от AntonI

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

Или вы чего-то просто не знаете…

Waterlaz ★★★★★
()
Ответ на: комментарий от LamerOk

Представить мы можем и анальный секс отрицательной бесконечности с положительной. А использовать в расчётах - нет.

Сложно и неэффективно, но использовать можем.

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Теоретически - может быть и можем, с неизбежной потерей точности на выводе конечного резульата(ов). Практически это скорее «не можем».

LamerOk ★★★★★
()
Ответ на: комментарий от AntonI

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

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

Вы сейчас делаете то, что было на заре появления десятичной системы счисления. «Этим же невозможно пользоваться!!! Чтобы узнать, сколько будет 325 я должен три умножить на сто, два умножить на десять и сложить это всё с пятёркой!!!»

Waterlaz ★★★★★
()
Ответ на: комментарий от LamerOk

Теоретически - может быть и можем, с неизбежной потерей точности на выводе конечного резульата(ов). Практически это скорее «не можем».

Если нас на выходе интересует представление в двоичной системе, то, конечно, с потерей точности. Но в 99% случаем нас в конечном счёте интересует ответ да/нет на некоторый вопрос (ну или серия ответов на серию же вопросов). Например, зажечь пиксель с координатами (x, y) или нет? И на некоторые вопросы такого рода мы сможем отвечать даже если число представлено суммой бесконечного ряда.

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

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

Прежде чем лезть в дебри математики, Вам таки наверное стоит научится внимательно читать и понимать написанное. Я специально написал «… с точностью до ошибки округления …» — приведите пожалуйста пример числа, которое нельзя с точностью до ошибки округления представить конечным числом цифр в позиционной системе счисления. Речь разумеется идет о числах лежащих в диапазоне [-MAX:+MAX] где MAX это максимально возможное по модулю число представимое в данной системе счисления и заданной разрядности, разрядность может выбрать сами.

Или вы чего-то просто не знаете…

Расскажите скорее про алгоритм суммирования ЛЮБОГО бесконечного ряда работающий на современных компьютерах конечное (разумное) время и дающий ответ с точностью до ошибки округления. Можете медаль Филдса получить.

AntonI ★★★★★
()
Ответ на: комментарий от Waterlaz

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

ЛЮБОГО бесконечно ряда? Изначально речь шла о ЛЮБЫХ рядах. Давайте алгоритм в студию.

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

Расскажите скорее про алгоритм суммирования ЛЮБОГО бесконечного ряда работающий на современных компьютерах конечное (разумное) время и дающий ответ с точностью до ошибки округления. Можете медаль Филдса получить.

Я не буду его суммировать. Я тут уже который пост подряд толдычу, что моё представление числа – бесконечный ряд. Суммировать я его буду только если мне зачем-то понадобится его двоичное или десятичное представление.

ЛЮБОГО бесконечно ряда? Изначально речь шла о ЛЮБЫХ рядах. Давайте алгоритм в студию.

Где об это шло? Всё вообще началось из корня из двух. Но любой алгоритмически разрешимый ряд представлять могу.

Waterlaz ★★★★★
()
Ответ на: комментарий от AntonI

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

Нет, ВЫ! Можно мы не будем общаться таким тоном? :)

Я специально написал «… с точностью до ошибки округления …» — приведите пожалуйста пример числа, которое нельзя с точностью до ошибки округления представить конечным числом цифр в позиционной системе счисления.

Прекрасно. Так в чём проблема посчитать с заданной точностью сумму ряда (+с некоторыми оговорками об «остаточном члене»)?

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Я не буду его суммировать.

Не суммируйте. Давайте в студию алгоритм оценки суммы ряда на больше/меньше чего то например.

Где об это шло?

Математика с фиксированной запятой для C++20 (комментарий)

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

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

AntonI ★★★★★
()
Ответ на: комментарий от Waterlaz

Можно мы не будем общаться таким тоном? :)

Давайте. Для начала перестаньте ванговать о знаниях собеседника.

Так в чём проблема посчитать с заданной точностью сумму ряда (+с некоторыми оговорками об «остаточном члене»)?

Любого ряда? Вы не поверите… вот уже и оговорки об остаточном члене полезли…

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

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

Я всё ещё на форуме беседую или точную спецификацию/ТЗ делаю? Тем не менее, я сразу сказал, что

«Если мы представляем число как сумму бесконечного ряда, предлагая алгоритм вычисления любого элемента по его номеру, …». То есть уже работаю только алгоритмически вычислимыми последовательностями.

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

В том ведь и дело, что могу. Если числа a и b вычислимы с любой наперёд заданной точностью, то вычислимы и a+b, и a*b.

Waterlaz ★★★★★
()
Ответ на: комментарий от AntonI

Любого ряда? Вы не поверите… вот уже и оговорки об остаточном члене полезли…

Оговорки всегда будут, опять же, не ТЗ пишу. В ieee 754 тоже много оговорок, но то стандарт. Вы же видите, что с бесконечным рядом я могу работать и начинаете юлить, как уж на сковородке.

Waterlaz ★★★★★
()
Ответ на: комментарий от AntonI

Ну давайте ряд sin(a*n)/n^(1+b), b>0.

А давайте лучше корни рациональных чисел, с чего всё и началось.

Предложите алгоритм хотя бы определения знака суммы.

Что совсем не то же самое, что и вычисление суммы с заданной точностью ;-)

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Нет уж, Вы анонсировали свое умение работать с рядами - демонстрируйте. Вы никаких оговорок что умеете только корни не делали. А то дальше выяснится что Вы умеете только квадратные корни от двузначных целых чисел которые являются квадратами целых чисел…

Да, обычно знак определить это гораздо проще чем посчитать сумму с заданной точностью. Но Вы и знак определить оказывается неспособны…

AntonI ★★★★★
()
Последнее исправление: AntonI (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.