И Коллатц на что-нибудь сгодится
Aug. 18th, 2022 08:04 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkПомните гипотезу Коллатца? Она заключается в том, что если взять любое целое положительное число, и повторно делить его пополам, если очередной результат чётный, или умножать на 3 и прибавлять 1, если очередной результат нечётный, то рано или поздно получится 1.
Заметим, что зная, сколько раз подряд приходилось делить на 2 после каждого 3n+1, и сколько всего раз это делалось, процедуру можно обратить вспять и получить исходное число из единицы.
И ещё раз заметим, что все эти операции линейные, поэтому если мы возьмём число А, выполним с ним Коллатцеву процедуру с запоминанием типа и количества шагов, а потом исполним её вспять, начиная с числа В, и используя В вместо единицы, то получим произведение АВ. Вычислительная сложность этой операции составляет O(kn), где k - количество шагов исходной процедуры, в которых выполнялось умножение, а n - количество бит в числе В.
Умножать таким образом на большие числа, которые сходятся к единице по Коллатцевой процедуре "весьма быстро", оказывается в несколько раз быстрее, чем это делает библиотека GMP.
Всё это, конечно, очень замечательно, но, в сущности, недалеко ушло от распознавания паттерна цифр в множителе и конструирования оптимального алгоритма умножения. Скажем, умножать Х на 99997999979999799997 обычным образом в столбик ни один нормальный человек не будет: тут сразу видно, что нужно умножить Х на 3 (а умножение на степень 10 у нас бесплатное) и потом выполнить одно вычитание и 3 сложения.
Заметим, что зная, сколько раз подряд приходилось делить на 2 после каждого 3n+1, и сколько всего раз это делалось, процедуру можно обратить вспять и получить исходное число из единицы.
И ещё раз заметим, что все эти операции линейные, поэтому если мы возьмём число А, выполним с ним Коллатцеву процедуру с запоминанием типа и количества шагов, а потом исполним её вспять, начиная с числа В, и используя В вместо единицы, то получим произведение АВ. Вычислительная сложность этой операции составляет O(kn), где k - количество шагов исходной процедуры, в которых выполнялось умножение, а n - количество бит в числе В.
Умножать таким образом на большие числа, которые сходятся к единице по Коллатцевой процедуре "весьма быстро", оказывается в несколько раз быстрее, чем это делает библиотека GMP.
Всё это, конечно, очень замечательно, но, в сущности, недалеко ушло от распознавания паттерна цифр в множителе и конструирования оптимального алгоритма умножения. Скажем, умножать Х на 99997999979999799997 обычным образом в столбик ни один нормальный человек не будет: тут сразу видно, что нужно умножить Х на 3 (а умножение на степень 10 у нас бесплатное) и потом выполнить одно вычитание и 3 сложения.
no subject
Date: 2022-08-18 03:52 pm (UTC)Ну ни фига себе.
no subject
Date: 2022-08-18 04:20 pm (UTC)no subject
Date: 2022-08-18 07:12 pm (UTC)Напомнило алгоритм Бут(с)а, где сложение или вычитание делается только при смене бита множителя с 0 на 1 и наоборот.
no subject
Date: 2022-08-18 08:32 pm (UTC)