Добрался наконец-то до умножения. Решил его сделать хитро, отдельно выделив умножение на небольшие целые, с целью оптимизации в первую очередь операций по переводу из разных систем счисления.
Такое умножение можно заменить несколькими операциями сложения и сдвига, думал, что получится быстрее. Но нет, быстрее не получилось, почти одинаково: видимо, лишнее сравнение и косвенный вызов процедуры съедают весь выигрыш. Впрочем, на больших размерностях эффект должен быть более заметен.
Тестирование проводил на нечетных числах, так как умножение на четные быстро обнуляет один из операндов на ограниченном по точности типе.
В результате Pascal в релизе показал 680 млн. 64-битных умножений в секунду, а мое умножение 128-битного на 64-битное - всего около 170 млн. Примерно в 4 раза медленнее. Хотя должно бы быть теоретически медленнее всего чуть больше двух раз. Такова плата за универсальность.
А вот умножение 128 на 128 бит дает 88 млн. умножений в секунду, что уже в 8 раз медленнее чисто 64-битного умножения, что странно. Ведь такая 128-битная операция требует лишь три 64-битных умножения и два сложения. Надо внимательнее посмотреть на свой код, видимо, там можно что-нибудь оптимизировать, я даже догадываюсь, что 😁.
Оценить, насколько хорошо работает PascalABC.NET с его BigInteger достаточно сложно. Дело в том, что он имеет "бесконечную" точность, рассчитывая полное произведение, в том время как мой тип старшую часть, выходящую за 128 бит, теряет. В результате множитель в процессе теста на BigInteger постоянно и очень быстро растет, а вместе с тем растет и вычислительная сложность каждого умножения.
В результате я замерял его производительность так: сначала замерил время выполнения N умножений, отбрасывая после каждого все то, что выходило за пределы 128 бит. с помощью побитового AND.
Затем замерил время N операций AND, и вычел одно время из другого.
В результате BigInteger показал 5.5 млн. умножений в секунду, или в 16 раз медленнее моего варианта 128 на 128 бит. Я считаю, что очень неплохо, с учетом того BigInteger считал полное умножение, получая 256 бит результата, что требует еще одного 64-битного умножения и кучи сложений.
Поначалу я предполагал, что в BigInteger используется универсальный алгоритм умножения, например, методом Фурье, но, судя по всему, там используют разные алгоритмы в зависимости от длины операндов. И на относительно коротких умножениях они используют обычный вариант длинного умножения.
