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

Интересный факт, в википедии указано, что «По состоянию на июль 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