Comments 11
А какое примерно отношение максимального числа к количеству ключей в кэше? Может проще иметь хеш-таблицу ключей, которые на предыдущем шаге привели к 1? Тогда храниться все будет в разы компактнее => больше ключей поместится в память, => можно будет быстрее исследовать больший диапазон. А после того, как мы достигли верхней границы, пробегаемся по ключам и считаем уже для них последовательности сведения к 1 (здесь можно и с кешированием полных путей) - то есть такая двухступенчатая ракета ;)
Ответ на этот вопрос сложнее чем кажется, варьируется сильно от диапазона и стратегии хранения ключей в кэше.
В статье есть ссылка, про исследование кэша на оптимальность: https://habr.com/ru/articles/673224/
В случае с хэш-таблицей, у меня есть подозрение, что на больших числах кэш все равно будет переполняться и сильно тормозить. Нужна стратегия чистки памяти, в моем случае soft references помогли
А если проверять на чётность не всё число, а только последнюю цифру, то не экономичнее выйдет по ресурсам?
В статье есть про это строчка:
Но затем заменил на более лаконичное:
private static boolean isEven(BigDecimal n) {return !n.testBit(0);}А, или вы про передачу в сам метод только последней цифры?
У четных чисел, представленных в двоичной системе, нулевой бит равен 0. Что значит проверять последнюю цифру?
Не очень понятно, зачем так извращаться, тем более с Guava, если программа на С без оптимизаций справляется за 11 секунд (в однопоточном режиме).
Интересный факт, в википедии указано, что «По состоянию на июль 2023 года проверены все натуральные числа до 10¹⁰⁰ (десять в сотой степени), и каждое из них продемонстрировало соответствие гипотезе Коллатца.»
Число 10¹⁰⁰ взято с потолка. Ссылки на источник в википедии нет. Да и не скоро появятся компьютерные мощности для такой проверки. В английской вики указано 2⁶⁸ ≈ 3*10²⁰ на июль 2020. В русской (версия от 06.08.2023) 9,8*10²¹ на апрель 2021. Это больше похоже на правду.
Дилемма 3n+1 на Java. Кэшируем рекурсию