LOVESYUK
Пишу тут о том что интересно. А интересно мне про IT, нейросети, стартапы и много ещё чего. Обо мне: основатель двух IT компаний. Люблю писать код и обучать ML модели. Делаю мини-проекты и рассказываю о них тут. with 💙 from @mr_vvv
نمایش بیشتر- مشترکین
- پوشش پست
- ER - نسبت تعامل
در حال بارگیری داده...
در حال بارگیری داده...
Mikhail Kozyulin invites you to add the folder “Физтехи”, which includes 38 chats.
const int L = 1 << 23; // == 2^23
const float a = L / std::log(2);
const float b = L * 127;
float fastExp(float x) {
x = a * x + b;
return std::bit_cast<float>((int)x);
}
Выше упрощенная версия кода, который считает приблизительное значение экспоненты, который я недавно встретил на GitHub.
Я был супер удивлен, что тут умножение + сложение + преобразование типов, и всё — экспонента подсчитана.
В моей голове экспонента всегда была нетривиальной операцией, на которую требуется много тактов. Как же так, давайте разбираться.
Целые и дробные числа хранятся в битах по-разному
Числа в формате int хранятся ожидаемым образом, например, для числа 123:
123: int = 0000000000000000000000000 1111011
Числа в формате float хранятся в виде маски битов:
s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm
s — 1 бит знака. Определяет, положительное число или отрицательное.
e — 8 битов экспоненты. Показывают степень двойки.
m — 23 бита мантиссы. Хранят дробную часть числа.
Само число = (-1)^{s} * 2^{e} * 1.{m}
Например для нашего числа 123:
123: float = 0 00000110 11101100000000000000000
e = 00000110b = 6
m = 0.1110110b = 0.921875
Проверяем: 2^{e} x 1.{m} = 2^6 x 1.921875 = 123. Сходится!
Переводить представления из int в float и обратно несложно, и процессор умеет делать это очень эффективно.
Чтобы понять суть алгоритма, вместо e^{x} будем считать 2^{x}
Считаем быстро 2^{x} если x - int
Заметим, что если мы знаем двоичное представление x, то если мы его засунем в биты экспоненты float, то задача уже решена (e = x, m = 0). Это ключевое наблюдение для понимания алгоритма!
В int представлении все биты числа x у нас хранятся в правом конце числа. Чтобы сдвинуть их в область экспоненты, мы умножим наш int x на 2^23. Тем самым просто допишем 23 нуля справа.
В этих двух идеях и есть вся суть. Как перейти от 2^{x} к e^{х} в других деталях можно разобраться самому или заглянуть в оригинальную статью.
Cчитать экспоненту в десятичной системе мы (человеки) тоже можем с помощью одного умножения (wow!)
Например, чтобы оценить exp(36) мы можем переписать
exp(36) = 10^{36 * log10(e)} = 10^{15.634} ~ 10^16
Эта неожиданная похожесть алгоритмов, получается из-за того что научная запись чисел вроде 5.34e7 очень похожа на то, как хранятся float в компьютере.
P. S. На самом деле степень двойки в экспоненте float сдвинута на 127, чтобы мы могли записывать как большие числа, так и очень маленькие. Мы учитываем этот сдвиг, добавляя b = L * 127
. Я убрал его, чтобы он не отвлекал от основной идеи.
P. P. S. Для тех кто всё понял: почему умножение на 2^32 в коде происходит в float, а не в int и что происходит с мантиссой в этом случае?
@lovesyuk
const int L = 1 << 23; // == 2^23
const float a = L / std::log(2);
const float b = L * 127;
float fast_math_function(float x) {
x = a * x + b;
return std::bit_cast<float>((int)x);
}
Выше упрощенная версия кода который считает приблизительное значение некоторой стандартной математической функции. Из действий тут только умножение + сложение + преобразование типов. А результат получается супер нетривиальный!
Вчера я потратил значительное время чтобы полностью понять как это работает эта магия. Расскажу о ней в следующем посте.
А пока два вопроса:
- Что это за функция?
- Как и почему работает этот магический код?Please note down the new value of pi: 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223176 If you'd like to sign up to hear about future ridiculous maths projects that require volunteers:
https://forms.gle/w44THpNJ3jWUPqHy6Play list of all my previous calculating pi videos:
https://youtube.com/playlist?list=PLhtC92GarkjyYbxI3-4qzIWIRbZaw4wuP&si=DzWXgnv_vYfDgiLZThis calculation was paid-for with surplus funding from a previous Stand-up Maths kick-starter. If you'd like to support future projects, you can join me on Patreon. My Patreon supporters keep me irrational.
https://www.patreon.com/standupmathsWilliam Shanks was voiced by the excellent Ben Moor:
https://www.spesh.com/ben/The amazing voice over was provided by the fantastic Gemma Arrowsmith:
https://www.gemmaarrowsmith.com/And huge thanks to the Pi-by-hand Committee who spent two years working on this project: Alex Genn-Bash Ayliean McDonald -
https://www.youtube.com/@AylieanBen Sparks -
https://www.youtube.com/@SparksMathsChristian Perfect Deanna Judd James Grime -
https://www.youtube.com/@singingbananaKatie Steckles -
https://www.youtube.com/@KatieStecklesMatthew Scroggs -
https://www.youtube.com/@chalkdustmagMax Hughes Nicole Jacobus Sophie Maclean -
https://bit.ly/Sophie_NumberphileThanks to Steve Mould for making sure everything was legit, and only mentioning tau six or so times. CORRECTIONS - None yet, let me know if you spot anything (other than the final 6). - Yes, this video was released the day before Pi Day. It's so teachers have a chance to watch it and prepare their Pi Day lessons for the big day. Filming and editing by Alex Genn-Bash Animations by William Marler Written and 'performed' by Matt Parker Produced by Nicole Jacobus Music by Howard Carter Design by Simon Wright and Adam Robinson MATT PARKER: Stand-up Mathematician Website: http://standupmaths.com/ NEW BOOK:
https://mathsgear.co.uk/products/love-triangle-by-matt-parker-signedFree online chess server. Play chess in a clean interface. No registration, no ads, no plugin required. Play chess with the computer, friends or random opponents.
طرح فعلی شما تنها برای 5 کانال تجزیه و تحلیل را مجاز می کند. برای بیشتر، لطفا یک طرح دیگر انتخاب کنید.