Дилемма 3n+1 на Java. Кэшируем рекурсию
Приветствую всех, сегодня я хочу рассказать про одну из самых интересных неразгаданных загадок математики. Гипотеза Коллатца, или же дилемма 3n+1 прославилась благодаря простоте своей формулировки, при этом оставаясь не доказанной уже более 90 лет.
Краткая формулировка, то бишь немного измененная выдержка из википедии (en и ру):
Берём любое натуральное число n:
Если оно чётное, то делим его на 2,
Если нечётное, то умножаем на 3 и прибавляем 1.
Над полученным числом выполняем те же самые действия, и так далее.
Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.
Пример:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (пришли в единицу за 7 шагов)
9 → 28 → 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (тут потребовалось уже 19 шагов)
Я далеко не математик, но интуитивно понял, что главная проблема здесь в том, что мы не знаем, до каких пор будет расти число, поскольку множитель 3 больше делителя 2, на который мы делим число в случае его четности. Поэтому мы не можем использовать типичную для подобных задач индукцию, и утверждать, что каждое k число будет меньше предыдущего, поэтому мы рано или поздно придем в единицу.
Собственно говоря, доказывать гипотезу Коллатца я и не собирался, но грех не запрограммировать такую простую задачку.
Я написал условия «в лоб»:
public static long coll_func(BigDecimal n){
BigDecimal copyNum = n;
long stepsCounter = 0;
while(!n.equals(BigDecimal.valueOf(1))){
stepsCounter++;
if(n.remainder(BigDecimal.valueOf(2)).equals(BigDecimal.valueOf(0))){
n = n.divide(BigDecimal.valueOf(2));
}
else{
n = n.multiply(BigDecimal.valueOf(3)).add(BigDecimal.valueOf(1));
}
}
return stepsCounter;И это работало! Действительно, запустив из main эту функцию в цикле, я мог увидеть количество шагов, которое понадобится, чтобы прийти в единицу для различных чисел.
Но сильно бросается в глаза тот факт, что для приведенных в примере цепочек имеется достаточно большая общая часть:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
9 → 28 → 14 → 7 → 22 → 11 → 34 → 17→ 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
То есть программа каждый раз пересчитывает эти значения по новой, а мне бы хотелось этого избежать. Я захотел сделать кэш, чтобы при заходе в 10ку, программа понимала: блин, а где‑то я это уже видела, и просто добавляла к текущим 13 шагам 6 из кэша, получая 19.
Я нашел на просторах интернета информацию о кэше Guava и решил использовать его. Выяснил, что можно настроить автоудаление по времени, максимальный размер, уровень многопоточной изоляции и многое другое.
Делается это при создании объекта CacheBuilder (до вызова .build () можно настроить разные опции кэша):
Cache collatzCache = CacheBuilder.newBuilder().build(); Кстати, зависимость maven использовал эту:
com.google.guava
guava
33.2.1-jre
Однако, для того, чтобы функция начала нормально кэшироваться, мне пришлось переделать бесконечный цикл на рекурсию и кэшировать результат ее вызова в методе main.
Выглядеть это стало следующим образом:
public static long collatzFunc(BigDecimal n, long stepsCounter) {
if (n.equals(BigDecimal.ONE)) return stepsCounter;
if (isEven(n))
n = n.divide(BigDecimal.valueOf(2));
else
n = n.multiply(BigDecimal.valueOf(3)).add(BigDecimal.ONE);
Long stepsInCache = collatzCache.getIfPresent(n);
if (stepsInCache != null)//If the function has a value in the cache, we get it from there.
return stepsInCache + stepsCounter + 1;
else return collatzFunc(n, stepsCounter + 1);//otherwise, simple recursive call
}
Метод isEven проверяет BigDecimal на четность, изначально я использовал
private static boolean isEven(BigDecimal n) {
return n.remainder(BigDecimal.valueOf(2)).equals(BigDecimal.ZERO);
}Но затем заменил на более лаконичное:
private static boolean isEven(BigDecimal n) {return !n.testBit(0);}Метод main (проверяем гипотезу на числах от 1 до diapason-1 и выводим число с самым долгим путем в единицу):
public static void main(String[] args) {
long maxSteps = 0;
long maxHardNumber = 0;
for (long i = 1; i < diapason; i++) {
long l = collatzFunc(BigDecimal.valueOf(i), 0);
collatzCache.put(BigDecimal.valueOf(i), l);
if (l > maxSteps) {
maxSteps = l;
maxHardNumber = i;
}
}
System.out.println("The most hard humber is " + maxHardNumber + ". We need " + maxSteps + " steps to make 1");
}Проведя такого рода оптимизацию, я начал экспериментировать с размером кэша и способами его чистки, в следствии чего мне удалось найти метод softValues, который задает значениям из кэша Strength.SOFT и это лучшим образом влияет на производительность! Сборщик мусора удаляет значения из такого кэша только тогда, когда ему требуется память.
Таким образом мой кэш создавался следующей строчкой:
CacheBuilder.newBuilder().softValues().build();(в то время, как первоначальное решение с циклом проверяло первые 100 млн натуральных чисел за 27 минут 44 секунды, решение с кэшем и softValues справилось всего за 7 минут 19 секунд. Прирост более чем в 3,7 раз, неплохо)
Также интересно, что ни одна из реализаций алгоритма, даже на относительно слабом железе не уходит в туман и не падает от OutOfMemory, спокойно проверяя миллионы 19-значных чисел, причем справляясь за адекватное время.
На самом деле самым противным на отрезке [1,100 000 000) стало число 63 728 127: чтобы привести его в единицу, пришлось сделать 949 шагов. А если подумать, то 949 шагов — это не очень много, поэтому вычисления для компьютера не сложны и не вызывают переполнения памяти.
На отрезке [1, 50 000 000) я получил следующее время выполнения для различных конфигураций:
Конфигурация | Время выполнения, сек. |
Кэш с фиксированным максимальным размером в 10 000 000, где по истечению лимита элементы вытесняются по принципу FIFO (first in, first out) | 159 |
Кэш без указания максимального размера, с модом softValues | 78 |
Без кэша, цикл | 501 |
Без кэша, рекурсия | 387 |
Интересный факт, в википедии указано, что «По состоянию на июль 2023 года проверены все натуральные числа до 10¹⁰⁰ (десять в сотой степени), и каждое из них продемонстрировало соответствие гипотезе Коллатца.» Гипотеза Коллатца — Википедия (wikipedia.org)
Я прогнал алгоритм на числе 10¹⁰⁰+1 и уверенно могу вам сказать: это число тоже соответствует гипотезе Коллатца, путь в единицу из него занимает 2308 шага.
Таким образом, вы можете самостоятельно запустить этот код, и, дописав в википедию, что проверили еще парочку миллиардов чисел на соответствие гипотезе, обеспечить математическому сообществу крепкий и здоровый сон)
Код проекта на GitHub: https://github.com/youngmyn/collatz‑theory
Источники:
Самая простая нерешённая задача — гипотеза Коллатца [Veritasium] (youtube.com) — очень классное видео по теме, которое и вдохновило меня на написание этой статьи
Гипотеза Коллатца — Википедия (wikipedia.org) — Русская википедия гипотезы
Collatz conjecture — WikipediaГипотеза Коллатца — Википедия (wikipedia.org) — Английская википедия гипотезы
Cache (Guava: Google Core Libraries for Java 23.0 API)) — кэш гуава
https://habr.com/ru/articles/673 224/ — классная статья про математический подход к созданию оптимальной реализации lru cache
