Pull to refresh

Comments 60

Забавно. Начал с отказа от плавающей запятой а в конечном итоге изобрел велосипед — та же плавающая запятая но названная плавающей чертой.

Вообще-то мантисса и степень — это не то же самое, что числитель и знаменатель.

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

знаменателя (который всегда является степенью 2)
Почему вы так решили? В статье сказано, что знаменатель может быть любым, и именно в этом суть.
Имел в виду — в числах с плавающей точкой «знаменатель» всегда степень 2 (ну по крайней мере, на ЭВМ с двоичной архитектурой). В статье — да, конечно

А использование целочисленной артфметики дает выигрыш на современных процессорах?

Я так понимаю посыл был не терять точность, как бывает при действительных числах
На современных не факт, т.к. плавающая математика давно аппаратно реализована, а вот для встроенных решений (микроконтроллеров), которые не умеют в числа с плавающей точкой (точнее умеют конечно, но программно и медленно) – ну это просто первое что пришло мне в голову, когда увидел заголовок. Не особо понятно правда, зачем это может понадобиться на практике
Некоторые микроконтроллеры имеют FPU. Например STM32 F3, F4, L4 и F7 имеют 32-хбитный FPU, а F76x/F77x имеют 64-хбитный FPU.
Arduino на AVR'ках это далеко не все микроконтроллеры.
а на STM32H7 400Мгц, FPU достаточно быстрый, я получал около 150Mflops при вычислении сетки Mobilenetv2 и это без асма и оптимизации под архитектуру ядра, просто взял универсальный для всех контроллеров код в стандарте мисра си и скомпилировал просто распределив грамотно память под разные блоки (в этой сетке ещё помимо команд FPU, очень много команд загрузок и тасования данных, паддинга и тд так что считаю что такой бенчмарк чуток более адекватный чем просто сколько FMA в секунду на голом громадном цикле на всю ширину D и I кеша вычислит).
По идее да, ведь даже с учётом АЛУ специально для чисел с плавающей запятой операции с целочисленными быстрее. А ведь ещё есть те же FX от амд, у которых на два целочисленных блока один для float.
Это с неупакованными быстрее. А у вот такой «плавающей черты» скорость будет ниже чем у программной плавающей запятой.
Товарищ проработал вопрос иного представления данных. Вы тыкаете в то, что аппаратной поддержки такой структуры данных нет. Ок. А если реализовать эту математику на ПЛИС, например? Или специальные GPU, которые вместо float будут с такими структурами данных работать? Моё субъективное мнение, что аппаратная реализация «плавающей черты» может оказаться эффективнее, чем плавающая точка. Хотя бы по количеству транзисторов…
Так что не надо так категорично.

Статья очень хорошая — позволяет задуматься, а всё ли мы правильно делаем? Может тут рядом, в другой структуре данных, лежит сокращение вычислений графики. А это мегаватты в год для всей планеты. Может Земля помедленнее нагреваться будет… :)
На современных процессорах всё зависит от оптимизаций. Вычисления с плавающей точкой так же быстры, как целочисленные вычисления. Но если учесть, что в случае целочисленных операций придётся дополнительно делать битовые сдвиги и прочие преобразования, то производительность целочисленных вычислений окажется ниже.
На современных процессорах всё зависит от оптимизаций. Вычисления с плавающей точкой так же быстры, как целочисленные вычисления
Про ARM не забываем. Там все не так радужно
По идее, на gpu от amd может быть выгода, но это тестировать надо.
UFO just landed and posted this here
В наше время — наверное пофик, но много лет назад, несколько человек рассказывали мне красивую старинную легенду упоминали что Discreet Flame/Inferno и некоторые другие из старых силиковских софтов считали все в int именно из-за отсутствия нормальных числодробилок.
И слова «общий множитель» вроде тоже упоминались, но сейчас я не могу найти ничего на эту тему, компании уже лет 15 как не существует…

PS: Люди были разные и в разные периоды времени, так что скорее всего правда.
Автор, осталось дело за малым: оптимизировать алгоритм, добавив проверку наличия проблемных мест (где недостаточно точности упрощённого алгоритма) и повторять только там расчёты с увеличенной детализацией или же вообще классические с плавающей запятой. В итоге это может дать вам более совершенный — гибридный алгоритм рендеринга с динамической глубиной точности. Он будет очень удобен для случаев, когда нормализация фпс (например, держат его всегда близко к 60) важнее наличия мелких артефактов рендеринга.
Он будет очень удобен для случаев, когда нормализация фпс (например, держат его всегда близко к 60)
Это где сейчас нужен самописный трассирующий рендеринг со стабильным 60 фпс?
Еще и на CPU, так как GPU вроде оптимизирован под дробные числа.
Я выше написал — подобная реализация очень зашла бы на микроконтроллерах, которые не имеют аппаратного ускорения вычислений с плавающей точкой. Не могу правда придумать сходу, зачем там правдоподобная графика с рейтрейсингом, но саму по себе математику для расчетов не связанных с графикой вполне можно было бы применить. Было бы круто, если бы кто-то собрал бенчмарк какой-нибудь
Не зашла бы: плавающая запятая пишется точно так же, но проще.
Пишется может проще, а работает быстрее? Я давно с МК не работал, но когда-то приходилось преобразования Фурье считать в целых числах (по точности особых требований не было) потому что программный флоат был слишком медленным для реалтайма
Возможно, что и работает тоже быстрее. Одно только вычисление НОД в каждой операции чего стоит…

Жаль что пока что недоступен исходный код. Возникли идеи:


  • А что если не ограничивать размерность рациональных чисел? Т.е. числитель и знаменатель будут BigInteger. Конечно, это сильно уменьшит производительность, но повысит точность.
  • Можно вообще попробовать реализовать движок рендера на основе аналитических вычислений.
Хм, а у меня там все красное и ничего не работает.
Работает только в относительно свежем хромом на пк и ноутах. В телефонке может не запуститься.

Попробовал сейчас с телефона через сафари и хром (даже специально его поставил). Не работает ни там, ни там. Что интересно, ошибка полностью совпадает с десктопной — даже в хроме.

Нужна ещё дискретная (и достаточно мощная) видеокарта. На ноуте с GeForce демка запускается без ошибок и примерно с 1-2 FPS. Возможно, требуется накатить дрова на видеокарту с сайта производителя, поверх универсального недоразумения, пихаемого мелкомягкими по умолчанию.
Сокращение на НОД без целочисленного деления все равно не обходится :(.
А откуда взялась задача обойтись без целочисленного деления?
Это я вскользь прокоментировал эту фразу:
Итак, вот первое интересное свойство рациональной арифметики — деление и умножение имеют одинаковые затраты, поэтому в отличие от обычного рендеринга с плавающей запятой, в котором деления обычно избегают, откладывают или скрывают под задержками медленных запросов получения текстур, в рациональной арифметике этих операций бояться не нужно.

Прочитал первый абзац. А разве числа с плавающей запятой (в машине) иррациональны?

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

Вместо этого в IT рациональным числом называется вполне конкретная конструкция из числителя и знаменателя.
Ну почему, с флотами вполне можно работать как с точными числами, пока есть гарантия, что округления не съедят значащий разряд мантиссы, ведь любой флоат по определению является рациональным числом.
Имея произвольный «флот» вы не можете, без анализа алгоритма его получения, сказать съело ли в нем что-то округление или же нет.
Разумеется. Но исходная задача может быть такая, что диапазон входных данных дает нам гарантии отсутствия потерь на округлении. Но да, это далеко не на всех задачах возможно и нужен детальный анализ алгоритмов. Но возможность-то есть! =)
Если в задаче используется только сложение, вычитание и умножение — то да.
Но тогда можно просто использовать fixed-point, будет больше бит чем мантисса, и быстрее.
Где сравнение быстродействия и где хоть один пример качества рендеринга выше, чем в float-реализации?

Ну в смысле зачем всё это? Хочется ведь или быстрее сделать (что маловероятно, т.к. на ровном месте получили кучу делений), или качественней.

P.S. Для нормализации — можете не делить на два, а использовать цепные дроби для приближения (см. в википедии подробности). Будет медленнее, чем по степеням двойки работать, но точнее.
Так это же перевод статьи. Если уж и писать предложения по улучшению алгоритма, так лучше сразу автору оригинала.
Мда, это я не заметил. Тогда получается, что и переводить не стоило.
Вообще-то автор переизобрел библиотеку gmp.

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


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

Автору очень хочется порекомендовать изучить Непрерывные Дроби!
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/113
355/113 — это и есть рациональное приближение числа пи. А напрямую работать с непрерывными дробями не получится.
Возможно на хабре можно ввести ссылки на переводы в англоязычной версии хабра?
Чтобы англоязычные комментарии оставались и были доступны habr.com, даже без оригинала статьи? Потому что не вижу публичной формы связи с автором на его блоге.
Вот этот момент вызывает интерес:
Я быстро реализовал оставшиеся обычные операции (abs, sign, mod, fract, floor, sqrt, и т.д.), которых теоретически было достаточно для получения красивых рациональных рендеров.

Как например реализовать быстрое вычисление sin/cos на собственном типе данных? Через таблицы?
Ряд тейлора до 3-го члена. Корень имеется рекурсивная функция f(x) = (f(x) + x/f(x)) / 2

И что может дать такая запись? Чтобы вычислить f(x) нам нужно знать значение f(x), причем не с предыдущего шага, а с этого же… Пока это больше на бесконечную рекурсию без результата похоже

Уточнение. Рациональное число — это число которое можно представить в виде деления целого числа на натуральное число.
Интересно было бы взглянуть на 32-битную формулу 1-4-27 где не все комбинации длины знаменателя, а через один

Интересно как выглядит сцена с двумя полигонами разного цвета лежащими в одной и той же плоскости при рендере основанном на плавающей черте? Будут ли видны какие либо артефакты присущие 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
}

image
image


Отсюда: https://cel.archives-ouvertes.fr/cel-01500109/document




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

Sign up to leave a comment.

Articles