Comments 60
Забавно. Начал с отказа от плавающей запятой а в конечном итоге изобрел велосипед — та же плавающая запятая но названная плавающей чертой.
Не то же самое. Но по факту, это числитель и логарифм знаменателя (который всегда является степенью 2).
А использование целочисленной артфметики дает выигрыш на современных процессорах?
Arduino на AVR'ках это далеко не все микроконтроллеры.
Так что не надо так категорично.
Статья очень хорошая — позволяет задуматься, а всё ли мы правильно делаем? Может тут рядом, в другой структуре данных, лежит сокращение вычислений графики. А это мегаватты в год для всей планеты. Может Земля помедленнее нагреваться будет… :)
И слова «общий множитель» вроде тоже упоминались, но сейчас я не могу найти ничего на эту тему, компании уже лет 15 как не существует…
PS: Люди были разные и в разные периоды времени, так что скорее всего правда.
Он будет очень удобен для случаев, когда нормализация фпс (например, держат его всегда близко к 60)Это где сейчас нужен самописный трассирующий рендеринг со стабильным 60 фпс?
Жаль что пока что недоступен исходный код. Возникли идеи:
- А что если не ограничивать размерность рациональных чисел? Т.е. числитель и знаменатель будут BigInteger. Конечно, это сильно уменьшит производительность, но повысит точность.
- Можно вообще попробовать реализовать движок рендера на основе аналитических вычислений.
Попробовал сейчас с телефона через сафари и хром (даже специально его поставил). Не работает ни там, ни там. Что интересно, ошибка полностью совпадает с десктопной — даже в хроме.
Итак, вот первое интересное свойство рациональной арифметики — деление и умножение имеют одинаковые затраты, поэтому в отличие от обычного рендеринга с плавающей запятой, в котором деления обычно избегают, откладывают или скрывают под задержками медленных запросов получения текстур, в рациональной арифметике этих операций бояться не нужно.
Прочитал первый абзац. А разве числа с плавающей запятой (в машине) иррациональны?
Вместо этого в IT рациональным числом называется вполне конкретная конструкция из числителя и знаменателя.
Ну в смысле зачем всё это? Хочется ведь или быстрее сделать (что маловероятно, т.к. на ровном месте получили кучу делений), или качественней.
P.S. Для нормализации — можете не делить на два, а использовать цепные дроби для приближения (см. в википедии подробности). Будет медленнее, чем по степеням двойки работать, но точнее.
По поводу квадратного корня: диофантово уравнение тут решается простейшим способом, но только в ограниченном числе случаев (и в этих случаях примитивный целочисленный корень из числителя и знаменателя как раз и даст правильное решение!). Проблема в том, что требуется не точное равенство, а приближенное, ведь для иррационального результата требуется найти лучшее рациональное приближение, а не заявить об отсутствии результата.
На самом деле нужно просто взять обычный (т.е. без битовых хаков) алгоритм вычисления квадратного корня, и выполнить его в рациональных числах.
1) Эти дроби дают наилучшие подходящие дроби, т.е. приближение к точному числу. То есть процесс «приближения», можно производить простым отбрасыванием хвоста дроби. Например, 16/19 = 0 + 1 / (1 + 1 / (5 + 1 / 3) ) ), что приблизительно равно 5 /6 (эта наилучшая дробь приближение с знаменателем меньше 19).
2) Эти дроби не зависят от системы исчисления и отлично приближают иррациональные числа как Pi, e. e — вообще расскладывается в красивую дробь [1, 1, 2, 1, 1, 4, 1, 1, 8, ...]
3) Эти дроби поддерживают квадратный корень и превращаются в бесконечные циклические дроби. Например, золотое сечение = 1 + 1 / ( 1 + 1 / ( 1 +… ) )
Минусы тоже есть:
— Это не 2 числа, а цепочка целых чисел
— Сложно реализовать в компактном виде
Они дают приближение с заданной точностью и удобное представление фракталов IFS.
Еще и удобны для функционального программирования и для ray marching.
Вот если бы была аппаратная поддержка рекурсий(наподобие SIMD) или мат.аппарт, тогда бы появилась самое эффективное сжатие и рендер.
число, которое можно выразить как соотношение двух целых чисел, например 1/2 или 355/113355/113 — это и есть рациональное приближение числа пи. А напрямую работать с непрерывными дробями не получится.
Чтобы англоязычные комментарии оставались и были доступны habr.com, даже без оригинала статьи? Потому что не вижу публичной формы связи с автором на его блоге.
Я быстро реализовал оставшиеся обычные операции (abs, sign, mod, fract, floor, sqrt, и т.д.), которых теоретически было достаточно для получения красивых рациональных рендеров.
Как например реализовать быстрое вычисление sin/cos на собственном типе данных? Через таблицы?
Интересно как выглядит сцена с двумя полигонами разного цвета лежащими в одной и той же плоскости при рендере основанном на плавающей черте? Будут ли видны какие либо артефакты присущие double precision?
Трансцендентальность — это кое-что другое :)
Моё текущее наивное решение (плохое) брало целочисленный квадратный корень от числителя (с соответствующим округлением), а затем делало то же самое со знаменателем.
Недавно видел что в одной растовой библиотеке реализовали таким образом (со ссылкой на алогритм). Возможно, вам будет любопытно взглянуть
// Reference:
// Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.13
fn sqrt(&self) -> Self {
if self.is_zero() || self.is_one() {
return self.clone();
}
let guess = BigUint::one() << (self.bits() / 2 + 1);
let mut u = guess;
let mut s: BigUint;
loop {
s = u;
let q = self / &s;
let t: BigUint = &s + q;
u = t >> 1;
if u >= s {
break;
}
}
s
}
Отсюда: https://cel.archives-ouvertes.fr/cel-01500109/document
Что-то я тупанул, мы ведь про дроби говорим, а не про целые… Но думаю имеет смысл взять ту же идею, просто методом Ньютона поискать нужное значение.
Можно ли рендерить реалистичные изображения без чисел с плавающей запятой?