Я тоже удивлён, потому что взял numpy и померял за сколько на моём десктопе четырёхлетней давности умножаются матрицы размером 1500*1500. Получилось 39 миллисекунд, а в статье всё больше секунды даже на фортране. Хотя казалось бы для архитектуры Эльбруса эта задача идеально подходит.
import numpy as np
import time
size = 1500
a = np.random.rand(size, size)
b = np.random.rand(size, size)
start_time = time.time()
c = a @ b
end_time = time.time()
print(f"Время матричного умножения: {end_time - start_time:.4f} секунд")
Для бивекторов место i, j, k = e_1, e_2, e_12 можно использовать i, j, k = e_12, e_13, e_23. В итоге правила умножения для i j k точно такие же и всё остальное тоже идентично.
Огромное спасибо за статью! Очень не хватало высокоуровневого математического взгляда на происходящее, в рунете релевантной информации почти нет, да и на английском немного.
Возможно, дальнейшее развитие теории геометрической алгебры позволит создать какие-то аналоги типизации или физической размерности, но пока геометрические вычисления становятся подобны коду на языке ассемблера, в котором соблюдение семантической целостности остаётся полностью на совести программиста.
Классы, которые я решил выделить - скаляр, плоскость, идеальная плоскость, бивектор, бивектор с компонентами с e_w, бивектор с компонентами без e_w, кватернион, мотор, транслятор, тривектор, точка, вектор и точка в начале координат и мнимая единица (тут коллизия в названий, вектор это тривектор где e_xyz = 0, у точки e_xyz = 1, а у тривектора e_xyz произвольный).
В разделение нормализованный/не нормализованный я не стал лезть, потому что из-за погрешности вычислений произведение двух нормализованных элементов уже не совсем нормализованное.
Мне очень понравилось, что отдельные типы для точек и плоскостей реально содержат только по 3-4 переменных и код получается такой же эффективный без лишних элементов и вычислений. И система типов языка программирования начинает помогать, потому что теперь она чётко знает, что, например, при вращении плоскости кватернионом получится именно плоскость, а при вращении точки - снова точка.
Вдобавок, если для мультивекторов использовать sandwich произведения, то из-за погрешности вычислений некоторые элементы в результирующем мультивекторе могут оказаться ненулевыми, хотя математически там всё должно сократиться. И тут меня спасает то, что для кодогенерации я использовал символьные вычисления и всё это сокращается.
Из минусов - для N типов потребуется сгенерировать N^2 бинарных операций и примерно половина из них дают ненулевой результат. Вполне возможно что в итоговой программе большая часть операций не пригодится.
P.S. с размерностью действительно есть нюансы, потому что если элемент описывает одновременно и вращение и перемещение, то в нём хранятся и расстояние с какой-то размерностью и углы (вернее, скорее синусы и косинусы), но суть в том что они безразмерные. Как это строго математически описать - не очень понятно.
P.P.S. В Вашей статье очень понравилась идея, почему e_a e_b = -e_b e_a. Обычно это постулируют, хотя оказалось что к этому можно прийти из логических рассуждений и желаемых свойств.
P.P.P.S. Ещё вы написали, что пространство CL(0, 3, 0) распадается на линейное пространство над двумя кватернионами, но не будет ли возможен совершенно аналогичный "распад" кватернионов на линейное пространство над двумя комплексными числами? Если это так, то логичнее с комплексных чисел начинать и для кватерниона просто будет частный случай более общего.
Прикольно, в игре TIS-100 надо программировать систолический массив вычислителей размером 4х3. Я думал это автор игры придумал на основе fpga, а оказывается оно и в реальности есть.
В шейдерах можно и флоаты. Допустим, камера рядом с объектом и объект с камерой где-то далеко от центра координат. Тогда в матрицах и объекта и камеры появляюстя большие числа. Но поскольку камера и объект рядом, произведение этих матриц даст матрицу, в которой больших чисел нет (MV) и которую можно безболезненно передавать в шейдер (или вообще сразу MVP передать).
Т.е., произведение M*V лучше с большой точностью считать, а дальше можно в шейдере.
P.S. Я сильно подозреваю что двойной кватернион это то же самое что и мотор в геометрической алгебре. Он же описывает одновременно и позицию и поворот? Вот с ними при уделении от центра координат у меня тоже не очень хорошо получается, потому что поворот описывается косинусами-синусами в интервале [-1, +1], а линейные координаты растут.
Например, радиус Земли около 6 тысяч километров = 6 * 10^6 и семь знаков точности от float значат, что координаты дадут точность плюс-минус метр.
И это я говорю про хранение, а если делать какую-то логику вычислений, то может потребоваться точность на порядки выше.
Допустим, автосимулятор - размер трассы 10км и делается 1000 шагов физики в секунду. 10км = 10_000_000 мм - а вот и предел точности - миллиметр. И если за шаг физики автомобиль смещается на расстояние порядка миллиметра - это фиаско, смещаться он будет куда попало из-за погрешности округления. При 1000 шагов в секунду 1 мм за шаг это 1м/с = 3.6 км/ч - вполне наблюдаемая ненулевая скорость, на которой машину будет колбасить.
Eщё учтём, что если используется интегрирование Верле, когда новая позиция рассчитывается на основе текущей и предыдущей, то ошибка в позиции будет отклонять заодно и скорость. Типичный порядок скорости для гонок пусть будет 30 метров в секунду и 30 мм за шаг. За каждый шаг физики из-за округления будет вылазить погрешность в 3%, и таких шагов - тысяча в секунду. И даже если взять 100 шагов в секунду вместо тысячи, что откровенно мало, погрешность в 0.3% за каждый шаг это ужасно.
Заметьте - это будет, даже если вычисления идеально точные и округление один раз при сохранении во float.
Только проблема в том, что если в промежуточных вычислениях тоже float - погрешность будет ощутимо расти на каждой промежуточной операции.
Я в своём физическом движке всерьёз задумываюсь про добавление DoubleDouble - потому что иногда даже Double не хватает. Например, можно тензор инерции считать не относительно центра масс, а относительно центра координат. И это математически очень просто и красиво получается - тензоры можно перевести в глобальные координаты, там поскладывать и потом перевести обратно в локальную форму. Причём сложение инерции в глобальной СО - это просто поэлеметное сложение 16 чисел.
Но есть нюанс - инерция это m * r^2, и вот это r^2 может заметно повлиять точность, если тело далеко от центра координат. Да, можно в локальной системе отсчёта такое делать и будет точно, я просто привожу пример когда математически красивый и простой код упирается в точность double и начинаются хаки вокруг.
На мой взгляд очень давно не хватает разделения на nullable / non-nullable типы на уровне байткода jvm (и его верификации), кажется это позволит JIT работать эффективнее и код будет более строгий. Сейчас пытаются сделать value типы и видно, что возможность вернуть null там сильно мешает, всё равно придётся переделать.
При прочтении с первого раза толком не понял, что происходит. Есть какие-то формулы, но что-то ход мысли я не смог уловить (и заодно не понял, при чём тут геометрическая алгебра). В голосовалке пока не участвовал, вечером попробую второй раз прочитать.
Поищите моноколёсников (в телеграмме есть чаты по разным городам и странам), можно будет вживую моноколёса посмотреть и порасспрашивать про ту или иную модель. Колеса сильно разные по ощущениями от езды, размеру и особенностям, лучше попробовать прежде чем покупать.
А оно уже так, причём довольно давно. Я долго думал, что администрация перекосов не замечает, но потом пришёл к выводу, что они об особенностях рейтинга, просмотров и т.п. знают и их это полностью устраивает.
Вот по-этому для меня как автора хабр мёртв. Я больше не вижу смысла публиковать здесь технические статьи.
А дальше целая цепочка.
Уходят авторы уникального контента, потом уходят читатели, которые хотят увидеть что-то интересное (я уверен, что таких тоже много), дальше хабр окончательно превращается в один из кучи сайтов с кликбейтными нейросгенерированными статьями. Дальше желание компаний платить за корпоративный аккаунт тоже пропадает.
И к чему это наезд на Сербию? Я родился в гражданином РФ, прожил в РФ 27 лет, пару лет назад переехал жить в Белград - и всё, теперь мне на хабр не заходить?
Иногда ставлю минусы, если читаю статью и она не нравится, но сейчас глянул список твоих недавних постов - большую часть я даже не видел. Ну ещё я тебя как автора заблочил когда-то. Блоки типа "читают сейчас" блокировку не учитывают и я иногда всё-таки оказываюсь в статьях авторов, которых заблочил.
Плюсы я тоже ставлю, если нравится.
Хабр когда-то на почту (кажется, на новый год в начале 24 года) присылал метрику, сколько плюсов и минусов я поставил за год, плюсов там больше, так что на мой взгляд я всё норм делаю.
Я тоже не понимаю, на мой взгляд те статьи совсем лишние. И контента много-много не надо. Хочется, чтобы хороший контент не надо было разыскивать изощрёнными способами и он не тонул в потоках нехорошего.
Например, я сейчас открыл ваши статьи - они интересные, одну про прямоугольные тайловые миры я плюсанул когда-то, а остальные увидел впервые, хотя хабр я раньше чуть ли не каждый день заходил.
Я тоже удивлён, потому что взял numpy и померял за сколько на моём десктопе четырёхлетней давности умножаются матрицы размером 1500*1500. Получилось 39 миллисекунд, а в статье всё больше секунды даже на фортране. Хотя казалось бы для архитектуры Эльбруса эта задача идеально подходит.
Для бивекторов место i, j, k = e_1, e_2, e_12 можно использовать i, j, k = e_12, e_13, e_23. В итоге правила умножения для i j k точно такие же и всё остальное тоже идентично.
Огромное спасибо за статью! Очень не хватало высокоуровневого математического взгляда на происходящее, в рунете релевантной информации почти нет, да и на английском немного.
Можно и сейчас, и с типами сильно удобнее. Мне правда не хватило выразительной мощи системы типов в Scala и я пошёл по пути кодогенерации для какого-то подмножества типов и ограничился только одной алгеброй - проективной для 3д: https://github.com/Kright/ScalaGameMath/tree/master/pga3d/shared/src/main/scala/com/github/kright/pga3d
Классы, которые я решил выделить - скаляр, плоскость, идеальная плоскость, бивектор, бивектор с компонентами с e_w, бивектор с компонентами без e_w, кватернион, мотор, транслятор, тривектор, точка, вектор и точка в начале координат и мнимая единица (тут коллизия в названий, вектор это тривектор где e_xyz = 0, у точки e_xyz = 1, а у тривектора e_xyz произвольный).
В разделение нормализованный/не нормализованный я не стал лезть, потому что из-за погрешности вычислений произведение двух нормализованных элементов уже не совсем нормализованное.
Мне очень понравилось, что отдельные типы для точек и плоскостей реально содержат только по 3-4 переменных и код получается такой же эффективный без лишних элементов и вычислений. И система типов языка программирования начинает помогать, потому что теперь она чётко знает, что, например, при вращении плоскости кватернионом получится именно плоскость, а при вращении точки - снова точка.
Вдобавок, если для мультивекторов использовать sandwich произведения, то из-за погрешности вычислений некоторые элементы в результирующем мультивекторе могут оказаться ненулевыми, хотя математически там всё должно сократиться. И тут меня спасает то, что для кодогенерации я использовал символьные вычисления и всё это сокращается.
Из минусов - для N типов потребуется сгенерировать N^2 бинарных операций и примерно половина из них дают ненулевой результат. Вполне возможно что в итоговой программе большая часть операций не пригодится.
В целом я очень доволен, поверх геометрической алгебры написал физический движок и он работает!
Вот мини-демонстрация: https://www.youtube.com/watch?v=wqt0ylxBqnU и часть кода для сил, инерции, движения и т.п.: https://github.com/Kright/ScalaGameMath/tree/master/pga3dphysics
Ещё заметил, что вы довольно лихо используете экспоненту, а я с ней какое-то время мучился, выводя эффективное вычисление экспоненты и логарифма и аккуратно обходя всякие случаи типа деления на ноль. Сложность вывода сильно зависит от количества генераторов в алгебре. Вот, например, экспонента: https://github.com/Kright/ScalaGameMath/blob/master/pga3d/shared/src/main/scala/com/github/kright/pga3d/Pga3dBivector.scala#L228
P.S. с размерностью действительно есть нюансы, потому что если элемент описывает одновременно и вращение и перемещение, то в нём хранятся и расстояние с какой-то размерностью и углы (вернее, скорее синусы и косинусы), но суть в том что они безразмерные. Как это строго математически описать - не очень понятно.
P.P.S. В Вашей статье очень понравилась идея, почему e_a e_b = -e_b e_a. Обычно это постулируют, хотя оказалось что к этому можно прийти из логических рассуждений и желаемых свойств.
P.P.P.S. Ещё вы написали, что пространство CL(0, 3, 0) распадается на линейное пространство над двумя кватернионами, но не будет ли возможен совершенно аналогичный "распад" кватернионов на линейное пространство над двумя комплексными числами? Если это так, то логичнее с комплексных чисел начинать и для кватерниона просто будет частный случай более общего.
Прикольно, в игре TIS-100 надо программировать систолический массив вычислителей размером 4х3. Я думал это автор игры придумал на основе fpga, а оказывается оно и в реальности есть.
А кажется это оно и есть.
Когда в одном double хранится какое-то число и в ещё одном - поправка к нему.
И кроме суммирования можно при желании ещё остальных арифметических операций надобавлять. Я вот такое нашёл, но не очень понятно что там с лицензией: https://github.com/Hellblazer/Utils/blob/master/src/main/java/com/hellblazer/utils/math/DoubleDouble.java
В шейдерах можно и флоаты.
Допустим, камера рядом с объектом и объект с камерой где-то далеко от центра координат.
Тогда в матрицах и объекта и камеры появляюстя большие числа. Но поскольку камера и объект рядом, произведение этих матриц даст матрицу, в которой больших чисел нет (MV) и которую можно безболезненно передавать в шейдер (или вообще сразу MVP передать).
Т.е., произведение M*V лучше с большой точностью считать, а дальше можно в шейдере.
P.S. Я сильно подозреваю что двойной кватернион это то же самое что и мотор в геометрической алгебре. Он же описывает одновременно и позицию и поворот? Вот с ними при уделении от центра координат у меня тоже не очень хорошо получается, потому что поворот описывается косинусами-синусами в интервале [-1, +1], а линейные координаты растут.
Вот тут в тесте можно примерные числа глянуть (причём мне тут точности double недостаточно оказывается)
https://github.com/Kright/ScalaGameMath/blob/master/pga3dPhysics/src/test/scala/com/github/kright/pga3dphysics/Pga3dInertiaLocalTest.scala#L26
Я даже задумываюсь над тем, чтобы мотор обратно разложить на перемещение + вращение и в таком виде везде хранить
Нельзя, местами даже double не хватает.
Например, радиус Земли около 6 тысяч километров = 6 * 10^6 и семь знаков точности от float значат, что координаты дадут точность плюс-минус метр.
И это я говорю про хранение, а если делать какую-то логику вычислений, то может потребоваться точность на порядки выше.
Допустим, автосимулятор - размер трассы 10км и делается 1000 шагов физики в секунду.
10км = 10_000_000 мм - а вот и предел точности - миллиметр. И если за шаг физики автомобиль смещается на расстояние порядка миллиметра - это фиаско, смещаться он будет куда попало из-за погрешности округления. При 1000 шагов в секунду 1 мм за шаг это 1м/с = 3.6 км/ч - вполне наблюдаемая ненулевая скорость, на которой машину будет колбасить.
Eщё учтём, что если используется интегрирование Верле, когда новая позиция рассчитывается на основе текущей и предыдущей, то ошибка в позиции будет отклонять заодно и скорость. Типичный порядок скорости для гонок пусть будет 30 метров в секунду и 30 мм за шаг. За каждый шаг физики из-за округления будет вылазить погрешность в 3%, и таких шагов - тысяча в секунду. И даже если взять 100 шагов в секунду вместо тысячи, что откровенно мало, погрешность в 0.3% за каждый шаг это ужасно.
Заметьте - это будет, даже если вычисления идеально точные и округление один раз при сохранении во float.
Только проблема в том, что если в промежуточных вычислениях тоже float - погрешность будет ощутимо расти на каждой промежуточной операции.
Я в своём физическом движке всерьёз задумываюсь про добавление DoubleDouble - потому что иногда даже Double не хватает. Например, можно тензор инерции считать не относительно центра масс, а относительно центра координат. И это математически очень просто и красиво получается - тензоры можно перевести в глобальные координаты, там поскладывать и потом перевести обратно в локальную форму. Причём сложение инерции в глобальной СО - это просто поэлеметное сложение 16 чисел.
Но есть нюанс - инерция это m * r^2, и вот это r^2 может заметно повлиять точность, если тело далеко от центра координат. Да, можно в локальной системе отсчёта такое делать и будет точно, я просто привожу пример когда математически красивый и простой код упирается в точность double и начинаются хаки вокруг.
На мой взгляд очень давно не хватает разделения на nullable / non-nullable типы на уровне байткода jvm (и его верификации), кажется это позволит JIT работать эффективнее и код будет более строгий.
Сейчас пытаются сделать value типы и видно, что возможность вернуть null там сильно мешает, всё равно придётся переделать.
При прочтении с первого раза толком не понял, что происходит. Есть какие-то формулы, но что-то ход мысли я не смог уловить (и заодно не понял, при чём тут геометрическая алгебра).
В голосовалке пока не участвовал, вечером попробую второй раз прочитать.
При наличии рук и желания некоторые делают бескамерку. С завода - обычно с камерой.
Поищите моноколёсников (в телеграмме есть чаты по разным городам и странам), можно будет вживую моноколёса посмотреть и порасспрашивать про ту или иную модель. Колеса сильно разные по ощущениями от езды, размеру и особенностям, лучше попробовать прежде чем покупать.
А оно уже так, причём довольно давно. Я долго думал, что администрация перекосов не замечает, но потом пришёл к выводу, что они об особенностях рейтинга, просмотров и т.п. знают и их это полностью устраивает.
Судя по тому, как мою статью администрация убрала в чулан и запретила редактировать - нет, не хочет. Площадку разворот устраивает.
Вот по-этому для меня как автора хабр мёртв. Я больше не вижу смысла публиковать здесь технические статьи.
А дальше целая цепочка.
Уходят авторы уникального контента, потом уходят читатели, которые хотят увидеть что-то интересное (я уверен, что таких тоже много), дальше хабр окончательно превращается в один из кучи сайтов с кликбейтными нейросгенерированными статьями. Дальше желание компаний платить за корпоративный аккаунт тоже пропадает.
И к чему это наезд на Сербию? Я родился в гражданином РФ, прожил в РФ 27 лет, пару лет назад переехал жить в Белград - и всё, теперь мне на хабр не заходить?
Как это относится к теме моей статьи?
Я зарегистрировался на Хабре в 2013 году. 906 закладок за 12 лет, это примерно 80 за год, или одна за четыре-пять дней.
Всего количество статей, новостей и т.п. на Хабре судя по айдишникам шагнуло за 870000
Иногда ставлю минусы, если читаю статью и она не нравится, но сейчас глянул список твоих недавних постов - большую часть я даже не видел. Ну ещё я тебя как автора заблочил когда-то. Блоки типа "читают сейчас" блокировку не учитывают и я иногда всё-таки оказываюсь в статьях авторов, которых заблочил.
Плюсы я тоже ставлю, если нравится.
Хабр когда-то на почту (кажется, на новый год в начале 24 года) присылал метрику, сколько плюсов и минусов я поставил за год, плюсов там больше, так что на мой взгляд я всё норм делаю.
Я по пунктам расписал проблемы и их причины. Я привёл конкретные примеры. Где проходит грань между жалобой и мнением?
Чем моя статья по смыслу отличается от следующих статей, которые не в чулане?
Рак, убивающий Хабр, ака «подпишитесь на мой телеграм-канал» https://habr.com/ru/articles/788186/
"Как AI захватывает Хабр, и почему это всех бесит" https://habr.com/ru/articles/878400/
"Чудесное совпадение или плагиат в квадрате" https://habr.com/ru/articles/841698/
"Хабр умирает?" https://habr.com/ru/articles/278325/
"Почему умер Хабр. Что делать и куда бежать" https://habr.com/ru/articles/278341/
@Exosphere, @Boomburum почему эта статья оказалась в чулане и я не могу её редактировать?
Я тоже не понимаю, на мой взгляд те статьи совсем лишние.
И контента много-много не надо. Хочется, чтобы хороший контент не надо было разыскивать изощрёнными способами и он не тонул в потоках нехорошего.
Например, я сейчас открыл ваши статьи - они интересные, одну про прямоугольные тайловые миры я плюсанул когда-то, а остальные увидел впервые, хотя хабр я раньше чуть ли не каждый день заходил.