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)
Ответ на: комментарий от AntonI

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

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

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

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

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

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

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

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

Нет уж, Вы анонсировали свое умение работать с рядами - демонстрируйте.

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

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

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

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

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

Нет, это было еще до Вас. Если Вы конечно не Тейлор и ко…

Всё остальное, вы придумали сами.

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

Вопросов больше не имею.

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

Нет, это было еще до Вас. Если Вы конечно не Тейлор и ко…

То есть теперь вы спорите ещё и с Тейлором? :)

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

Могу. Да, не из всех рядов, но могу. Разобрались, почему определить знак – сложнее?

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

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

Видите ли, мне приходилось юзать ряды для построения численных схем высокого порядка точности, и для аналитического представления результатов многомерного интегрирования. Это тяжело и сложно (@bugfixer видел), там одним дефайном не отделаешься - у кластера иногда памяти не хватает.

Я думал Вы и правда носитель какого то сакрального знания, а оказывается Вы обычный балабол:-(

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

Этот ряд имеет значение (сходится)?

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

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

Этот ряд имеет значение (сходится)?

При b>0 очевидно да. Но при малых b может делать это оооочень медленно;-)

Вопрос в том когда (при каких условиях) НУЖНО представлять значение в виде суммы ряда. И когда такое представление имеет смысл. «Условие теоремы это список поражений ее автора» - так вот я этих условий так и не дождался. В общем случае это очевидно не работает, пример я привел.

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

Точно, это же «замечательный» предел, так что и при b = 0 должен сходится.

Тогда какие вопросы? Математик сказал: решение существует. Значит медленно и упорно майним монетки - приближаем тепловую смерть вселенной при t -> ∞.

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

Математик сказал: решение существует.

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

первый замечательный предел

ну вот, спалили контору;-(

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

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

Улыбнуло. Ладно, считайте, что на слабо взять удалось. Придётся что-то выкатить.

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

Можете ограничиться более подробным описанием того что Вы делаете и как. С условиями применимости;-)

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

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

Настоящий математик играет с символами по выдуманным правилам (и хорошо, если выдуманный мир непротиворечив).

Прикладной математик проверяет степень шизофрении, ой, то есть степень оторванности настоящего математика от реальности.

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

С условиями применимости

Нет, я так не играю. В начале было одно условие: представить корень какого-то рационального числа в рациональных числах.

И тут пришел ты и перевернул условие: есть ряд, представь в виде рационального числа.

Естественный ответ: заткнись и считай.

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

представить корень какого-то рационального числа в рациональных числах.

Нет бы продолжить троллить, и спросить про квадратный корень отрицательного числа.

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

В начале было одно условие: представить корень какого-то рационального числа в рациональных числах.

Все уже представлено до Вас, man sqrt. Есть всякие оптимизации

Естественный ответ: заткнись и считай.

«А как дысал, как дысал!» Скучно, девочки… зачем тогда было щеки дуть?!

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

«А как дысал, как дысал!»

«Молчи и считай!» было сказано сразу же на твое предложение посчитать до бесконечности элементы бесконечного счетного множества.

Поэтому ты, глубоко вдохнув, решил перевернуть всё. Выдыхай, бобер!

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

Я тут чуть-чуть наговнокодил. Моих знаний Хаскела сделать быстро красивее не хватает.

import Data.Ratio
import Data.List

data Sum = Sum  [(Rational, Rational)]

takeWhileOneMore p = foldr (\x ys -> if p x then x:ys else [x]) []

eval precision (Sum xs) =
    sum $ map fst $ takeWhileOneMore ((>precision).snd) xs

instance Num Sum where
    Sum xs + Sum ys = Sum $ zipWith (\(a1, b1) (a2, b2) -> (a1+a2, b1+b2) ) xs ys
    Sum xs * Sum ys = Sum zs where
        psx = scanl1 (+) $ map fst xs
        psy = scanl1 (+) $ map fst ys
        psz = zipWith (*) psx psy
        as = zipWith (-) psz (0:psz)
        ds = zipWith4 (\sx sy dx dy -> (abs sx)*dy + (abs sy)*dx + dx*dy) psx psy (map snd xs) (map snd ys)
        zs = zip as ds
    negate (Sum xs) = Sum $ map (\(a, b) -> (-a, b)) xs
    fromInteger i = Sum $ (i%1, 0) : repeat (0, 0)

sqrt' :: Rational -> Sum
sqrt' x = res
    where res = Sum $ zip as $ map (\s -> abs (s - x/s)) ps
          as = a1 : map (\s -> (x/s - s)/2) ps
          ps = scanl1 (+) as
          a1 = fromIntegral (floor $ sqrt $ fromRational x) % 1

Смысл в том, что числа x представляются бесконечной последовательностью пар рациональных (aᵢ, bᵢ) таких, что
x = a₁ + a₂ + a₃ + ...
bᵢ ≥ |aᵢ₊₁ + aᵢ₊₂ + aᵢ₊₃ + ...|
bᵢ -> 0

Ну и пример использования:

Создаем пару чисел s2 = √2 и s3 = √3:

*Main> s2 = sqrt' 2
*Main> s3 = sqrt' 3
Их можно 'вычислить' с любой наперёд заданной точностью как рациональное число, которое, естественно, можно перевести и в Double:
*Main> eval (1%100) s2
17 % 12
*Main> eval (1%1000) s2
577 % 408
*Main> eval (1%1000000) s2
665857 % 470832
*Main> fromRational $ eval (1%100) s2
1.4166666666666667
*Main> fromRational $ eval (1%1000) s2
1.4142156862745099
*Main> fromRational $ eval (1%1000000) s2
1.4142135623746899
С числами можно делать арифметические операции. Ожидаемо x = (√3-√2)*(√3+√2) = 1
*Main> x = (s3-s2)*(s3+s2)
*Main> eval (1%100) x
1019911 % 1019592
*Main> fromRational $ eval (1%100) x
1.0003128702461377
*Main> fromRational $ eval (1%1000) x
1.0003128702461377
*Main> fromRational $ eval (1%1000000) x
1.0000000084681628

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

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

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

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

Спасибо. Но я продолжаю не понимать, в частности потому что не знаю Хаскеля.

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

  1. Когда такое число вычисляется (приводится к float), как производится суммирование? Потому что в рациональных числах это будет очень долго, а во floating point это может оказаться очень неправильно за счет ошибки округления (если ряд знакопеременный).

  2. Для каких именно чисел Вы это используете? Это таки накладывает ограничения на способ порождения ряда - для корней вид членов будет один, для синусов другой и т.д. И я не понял как именно Вы порождаете ряд для корня - раскладываетесь в Тейлора в окрестностях ближайшего квадрата рационального числа? Еще как то?

  3. Если это корни, то не очень понятно зачем (кроме как джаст фор фан, что тоже ответ)? Народ упарывается по всякому - полиномы Эрмита, сферические функции, я раскладывал экспоненту от суммы скалярных произведений на сфере и еще черти чего. Для корней я бы просто ввел корень как корень из рационального числа - они бы прекрасно перемножались, складывать было бы сложнее (так и оставались бы суммой), но в любом случае ИМНО это было бы удобнее ряда. Да и эстетически симпатичнее;-)

Все это фактически элементы CAS, сделанные на коленке и заточенные под решение какой то узкой задачи. Вот хочется эту задачу понять;-)

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

Я же ожидаю, что не с кодером общаюсь, а со спецом по мат. моделированию, физике и вот этим вот всем.

Физика тут я не понял причем, а в остальном будьте проще - у меня в первом семестре по матану был трояк;-)

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

Нет, я так не играю. В начале было одно условие: представить корень какого-то рационального числа в рациональных числах.

Просто ни кто еще "не осилил".  

В связи с этим вспоминается как математики пришли к понятию «производная» /КРАСОТИЩЕ/ и далее пришли к интегральному исчислению.

Скорее всего иррациональные и иные числа все же каким-то образом можно представить в виде рядов, но не методом ПОДГОНКИ …

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

В связи с этим вспоминается как математики пришли к понятию «производная» /КРАСОТИЩЕ/ и далее пришли к интегральному исчислению.

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

ПРОИЗВОДНАЯ ...
anonymous
()
Ответ на: комментарий от anonymous

Просто ни кто еще «не осилил».

Представить в рациональных числах / значение x, когда x * x = -1 /

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

Когда такое число вычисляется (приводится к float), как производится суммирование? Потому что в рациональных числах это будет очень долго, а во floating point это может оказаться очень неправильно за счет ошибки округления (если ряд знакопеременный).

Ну, не так уж и долго. Рациональную дробь для (√3-√2)*(√3+√2) с точностью до 1000000 десятичного знака считает за 3 секунды. Жить можно, хоть и не очень приятно.

Для каких именно чисел Вы это используете?

Мне это не нужно, для моих целей обычно и float хватает.

И я не понял как именно Вы порождаете ряд для корня - раскладываетесь в Тейлора в окрестностях ближайшего квадрата рационального числа? Еще как то?

Это уже не очень важно, на самом деле. По факту я считаю методом Герона. Да, постоянно нужно тащить частичную сумму ряда, но что поделать. Могу переделать и в ряд Тейлора.

Если это корни, то не очень понятно зачем (кроме как джаст фор фан, что тоже ответ)?

Анонимус спрашивал про корень из двух, я сделал корень из двух. Да, это just for fun, на практике мне оно не нужно. Но можно добавить и другие числа. e^pi?

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

Я бы не делал рядами, конечно. Можно интереснее. Тут только пруф оф поинт.

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

Все это фактически элементы CAS, сделанные на коленке и заточенные под решение какой то узкой задачи. Вот хочется эту задачу понять;-)

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

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

Рациональную дробь для (√3-√2)*(√3+√2) с точностью до 1000000 десятичного знака

Сферический конь в вакууме.

считает за 3 секунды. Жить можно, хоть и не очень приятно.

Это безумно долго.

для моих целей обычно и float хватает.

Открою секрет - в 99% случаев этого хватает.

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

Сферический конь в вакууме.

И?

Это безумно долго.

Лет 15 назад в олимпиадном программировании была хорошая оценка. Чтобы уложиться в таймлимит в 1с, программа должна делать до 1000000 итераций. По тем меркам 10^6 значащих цифр за 3 секунды – ок. Попробуйте просто посчитать корень из 2 с такой точностью. Уверяю, длинная арифметика съест очень много времени. Вангую, что у вас получится раз в 10 быстрее, но это мелочь для пруф оф консепт кода.

Открою секрет - в 99% случаев этого хватает.

Спасибо, что сообщил.

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

Сферический конь в вакууме.

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

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

Лет 15 назад

А кто-то не понаслышке знает что такое МК-61 и МК-52…

в олимпиадном программировании

О, Вы олимпиадник? Прикольно.

в таймлимит в 1с, программа должна делать до 1000000 итераций.

Мы нынче в гигагерцах живём. Это от 1000 тактов на циферку. Времени - вагон.

Спасибо, что сообщил.

Вы не поняли. Во вполне себе живых системах цены во float’ах разлетаются. Не благодарите.

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

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

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

Ок, принято. Нет бы сразу так;-)

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

Открою секрет - в 99% случаев этого хватает.

За овер 20 лет я наверное только один раз уперся в то что мне не хватило флоат. Результаты были очень забавные. И еще раз уперся в нехватку дабла - это как раз при суммировании знакопеременного ряда в лоб;-)

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

У коллег, в латтис больцмане, даже в даблах масса течет:-)

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

За овер 20 лет я наверное только один раз уперся в то что мне не хватило флоат. Результаты были очень забавные. И еще раз уперся в нехватку дабла - это как раз при суммировании знакопеременного ряда в лоб;-)

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

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