И Коллатц на что-нибудь сгодится

Помните гипотезу Коллатца? Она заключается в том, что если взять любое целое положительное число, и повторно делить его пополам, если очередной результат чётный, или умножать на 3 и прибавлять 1, если очередной результат нечётный, то рано или поздно получится 1.

Заметим, что зная, сколько раз подряд приходилось делить на 2 после каждого 3n+1, и сколько всего раз это делалось, процедуру можно обратить вспять и получить исходное число из единицы.

И ещё раз заметим, что все эти операции линейные, поэтому если мы возьмём число А, выполним с ним Коллатцеву процедуру с запоминанием типа и количества шагов, а потом исполним её вспять, начиная с числа В, и используя В вместо единицы, то получим произведение АВ. Вычислительная сложность этой операции составляет O(kn), где k - количество шагов исходной процедуры, в которых выполнялось умножение, а n - количество бит в числе В.

Умножать таким образом на большие числа, которые сходятся к единице по Коллатцевой процедуре "весьма быстро", оказывается в несколько раз быстрее, чем это делает библиотека GMP.



( а разгадка проста )