Дилемма 3n+1 на Java. Кэшируем рекурсию

Приветствую всех, сегодня я хочу рассказать про одну из самых интересных неразгаданных загадок математики. Гипотеза Коллатца, или же дилемма 3n+1 прославилась благодаря простоте своей формулировки, при этом оставаясь не доказанной уже более 90 лет.

Краткая формулировка, то бишь немного измененная выдержка из википедии (en и ру):

Берём любое натуральное число n:

1. Если оно чётное, то делим его на 2,

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<BigDecimal, Long> collatzCache = CacheBuilder.newBuilder().build();

Кстати, зависимость maven использовал эту:

<dependency>        <groupId>com.google.guava</groupId>   <artifactId>guava</artifactId>   <version>33.2.1-jre</version>  </dependency>

Однако, для того, чтобы функция начала нормально кэшироваться, мне пришлось переделать бесконечный цикл на рекурсию и кэшировать результат ее вызова в методе 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) я получил следующее время выполнения для различных конфигураций:

Интересный факт, в википедии указано, что по состоянию на апрель 2021 года проверены все натуральные числа до 9.8×10²¹, и каждое из них продемонстрировало соответствие гипотезе Коллатца.

Я прогнал алгоритм на числе 9.8×10²¹+1 и уверенно могу вам сказать: это число тоже соответствует гипотезе Коллатца, путь в единицу из него занимает 505 шага.

Таким образом, вы можете самостоятельно запустить этот код, и, дописав в википедию, что проверили еще парочку миллиардов чисел на соответствие гипотезе, обеспечить математическому сообществу крепкий и здоровый сон)

Код проекта на GitHub: https://github.com/youngmyn/collatz‑theory

Источники:

Самая простая нерешённая задача — гипотеза Коллатца [Veritasium] (youtube.com) — очень классное видео по теме, которое и вдохновило меня на написание этой статьи

Гипотеза Коллатца — Википедия (wikipedia.org) — Русская википедия гипотезы

Collatz conjecture — Wikipedia — Английская википедия гипотезы

Cache (Guava: Google Core Libraries for Java 23.0 API)) — кэш гуава

https://habr.com/ru/articles/673 224/ — классная статья про математический подход к созданию оптимальной реализации lru cache