Comments 37
Вот ещё одна интересная статья про деление, но 8-битное https://specbranch.com/posts/faster-div8/
Глянул по диагонали - да, это очень близко к теме статьи, и что то интересное про полиномы Чебышева
Если зафиксировать X0, то n-ый член последовательности
можно выразить как полином степени 2^n-1 по D, причем из свойств метода Ньютона получаем, что на отрезке [1.0, 2.0] его максимальное отклонение от 1/x очень маленькое. Можем ли мы найти какой-то другой полином, который можно было бы быстрее посчитать, и его отклонение было бы не хуже? Вот со вторым свойством как раз всплывают многочлены Чебышева, и основанный на нем метод Ремеза (про них не так давно была на хабре статья про вычисление синуса) -- такие методы позволяют найти многочлен фиксированной степени с наименьшим отклонением от целевой функции на отрезке. Как этот многочлен потом эффективно вычислять -- отдельный вопрос, вроде как в статье об этом отдельный параграф.
Может, вместо "мерим" лучше употреблять "измеряем"?
И почему зелёный цвет вдруг стал зеленным?
Можно было такое в личку кинуть :)
Можно было до публикации принять к сведению вот это:
https://habr.com/ru/articles/830040/
Спойлер: там есть раздел "Кто виноват — ясно, а делать-то что?"
Очень смешно
Можете пояснить, что хотели сказать? Что вовсе не обязательно грамотно писать статьи? Это сложно?
Вы нашли одну ошибку на статью и одно немного устаревшее слово, я вас поздравляю с этим
отличается в 4-ом разряде. В этом и причина, почему мы не храним второй байт: по сути из первого байта мы используем только старшую тетраду
Правильно пишется: в "4-м". После "по сути" не хватает запятой. В конце предложения ставится точка.
Хотя, для uint16_t он является избыточным для более широких типов uint32_t, uint64_t полная таблица дробей будет заниматься неоправданно много
После "избыточным" не хватает запятой. И чем таблица будет заниматься?
Я знаю, что Вы мне можете написать: мы не экзамене по русскому языку и т.д. Дело Ваше.
Ага, больше я это обсуждать не собираюсь - считайте, что у меня авторская пунктуация во всех предложениях
https://pikabu.ru/story/velik_moguchim_russkiy_yazyika_1746621
Я понял у вас развлечение - погадить в комментариях, ну что ж. Не мои проблемы. Была бы цель исправить ошибки - кинули б в личку, говорят - это просто
Исправлять ошибки должны комментаторы, а не автор?
Говорят, прогнать текст через автокорректор - это просто. Хотя бы через Microsoft Word, там можно нажать F7. Работает, начиная с MS Office 97.
точка там есть (и была)
Очень интересно! Мы делали так - перемножали два быстрых обратных корня - тоже неплохо получалось.
типа формула
А сами множители считаются методом Ньютона?
Примерно да...
ru.wikipedia.org/wiki/Быстрый_обратный_квадратный_корень
https://habr.com/ru/articles/730872/
https://habr.com/ru/companies/infopulse/articles/336110/
Главное помнить, что быстрый обратный корень выдает аппроксимацию, а не точное значение.
На самом деле точное значение для деления это вещь такая...часто её нет и быть не может, например, 1/3 в десятичностой системе, а в двоичной системе все дроби вида 1/n где n - не степень двойки не имеют такого представления. Можно посмотреть мою предыдщую статью, там весь алгоритм построен на том, как аккуратно обращаться с погрешностями. Да и в этой статье, конечно, этот вопрос затронут тоже.
Хотя, для uint16_t он является избыточным для более широких типов uint32_t, uint64_t полная таблица дробей будет заниматься неоправданно много памяти, а значит, реализация и применения метода касательных будет иметь смысл.
Если использовать этот метод для uint64_t, то как его производительность будет соотноситься со встроенной операцией деления?
Невозможно ответить на этот вопрос, не проведя экспериментов. Скорее всего результат будет неплохой - храним все значения для uit16_t , делаем два шага алгоритма , шаг коррекции
Почему нельзя использовать тот же самый метод - использовать те же самые 3 бита для приближения, но увеличить количество итераций, чтобы получить точность уже 64 бита?
Не привожу исходный код измерений для метода divide, потому что он отличается только одной строкой, средний результат: 5.8 секунды — лучше! Причём — значительно!
Удивительно, как компилятор умеет векторизовать такой код, с поиском по таблице и проверками остатка, что он оказывается быстрее стандартного деления (в SIMD ведь нет целочисленного деления? но я удивлюсь, если приведённый вами код окажется быстрее, чем реализация такого типа с делением в вещественных числах)
Поделить нельзя — умножить или алгоритм быстрого деления по методу Ньютона-Рафсона