Месть Leetcode. Умножение строк. Болтаюсь на 85% с результатом 4ms.

Как водится, ссылка: https://leetcode.com/problems/multiply-strings/

На вход подаются две строки до 200 цифр включительно (от старших разрядов к младшим), нужно вернуть их произведение в виде строки, не используя библиотек арифметики повышенной точности. Отрицательных чисел нет. Лидирующих нулей нет. Хотя, последнее моему решению - без разницы...

Попробовал вначале умножать поциферно. Делим большую из двух строк пополам и умножаем половинки "по-школьному" накрест подстроками (string_view), делая до 4-х рекурсивных умножений. Потом складываем результаты с нужными сдвигами. Всего две операции - mul и add (принимающий сдвиг второго операнда, например, 1234 + 56 * 100 реализуется 1-й операцией). Алгоритм квадратичной сложности от количества цифр множителей. Решение приняли, но сказали, что я - помощник джуниор лузера (лучший прогон 89ms, побил всего 11% решателей).
Ладно, принял это к сведению, добавил оптимизацию Карацубы с разными порогами (тут уже пришлось реализовать ещё и вычитание sub), из которых от 4-х цифровой выдал 50ms и почётное звание джуниор лузера (побито 12% решателей).

Тогда я понял, что кавалерийский подход не сработает, ведь эти твари наверняка копируют в "свои" решения код питоновских библиотек и gnu mp. Я поделил входные строки на участки по N десятичных цифр таким образом, чтобы их произведение влезло в базовый тип. Например, если базовый тип - unsigned short (16 бит), то операнды могут быть по 2 цифры, а их произведение будет не более 4-х и тоже влезет в шорт. И стал передавать в арифметические функции вектора из цифр. Дело пошло побыстрее.

22ms на 32-битных "цифрах" 10000-ной системы счисления позволили мне претендовать на звание мидл лузера, обогнавшего 18% решателей.

И 64-битные "цифры" 1000000000-ной системы счисления позволили уложиться в 4 миллисекунды, Карл! Лишь для того, чтобы увидеть жалкие 85% позади. Это сеньор лузер.

Как обойтись малой кровью, т. е. не копируя к себе в решение GMP?
Подумал о Тум-Куке, но 200/9 - это всего 23 больших "цифры", прекалькуляция не оправдает себя.
Подумывал снизить константный множитель, например, выкинуть к лешему вектора (вектор - это целых три указателя и копирование содержимого). Но литкод использует рантайм от C++'17, в котором нет ни спанов, ни std::array. Реализовывать самому? Гонять обычные массивы? Или auto_ptr/shared_ptr с массивом? Говорят, они с массивами не дружат, но это можно обойти. Наколхозить свой аллокатор на опстеках? Кэшировать результаты операций? Переделать рекурсию в чудовищный цикл со своим стеком? Что тут ещё можно сделать?

Код сюда не влезает. Последний вариант кода (без отладочной печати и комментариев) - здесь: https://pastebin.com/GMrQnqSr

Всё, нашёл способ. У них же GNU C++, в котором есть замечательный __int128.
Шинкуем входные множители по 19 цифр, и вместо 23-х мегацифр получаем 11, а при нашей асимптотике это в 3 раза снижает количество умножений одиночных мегацифр.

Runtime 0ms, beats 100%. И даже расход памяти заметно снизился.

Можно ещё провести оптимизацию по памяти (нам же не нужен вектор 128-битных чисел, хватит и 64-битных), но будет больше мороки в самих операциях: тайпкасты, вычисление переносов...