Привет!

Этот пост станет продолжением нескольких последних постов, в которых мы исследовали проблему, вынесенную в заголовок. Если вы не уверены, о чем я говорю, я настоятельно рекомендую вам взглянуть на них, прежде чем продолжить.

В прошлый раз мы остановились на том, что нашли общую формулу для завершения одной монеты при наличии нескольких n монет.

К сожалению, здесь есть две довольно большие проблемы.

  1. Несмотря на то, что это выглядит (и является) довольно кратким, получение значений для все более и более высоких чисел n становится все более трудным, поскольку время вычислений постепенно увеличивается. В конце концов, каждое n зависит от всех предыдущих значений функции.
  2. Конечная цель — найти предел функции. Но, учитывая крайнюю рекурсивность, это очень сложно.

На данный момент я не знаю способа решить любую из этих проблем «отслеживаемым» способом. Вместо этого я решил использовать мощность своего компьютера, чтобы вычислить необходимые значения и посмотреть, есть ли предел, который мы могли бы логически определить количественно (при условии, что он вообще существует).

Если вас не интересует кодирование, не стесняйтесь пропустить этот раздел.

Вот GitHub. Прошу прощения за имена файлов.

Генерировать значения довольно просто — закодируйте функцию, создайте место для хранения значений для будущего использования и укажите начальное значение. Самая трудная часть этого — действительно первый шаг. Ниже приведены проблемы, которые у меня были, и то, как я их решил.

  1. Первоначально при создании значения, поскольку оно было рекурсивным, я запускал функцию каждый раз, когда мне нужно было значение функции. Например, пытаясь получить f(7), я бы вычислил f(1) до f(6). При вычислении от f(2) до f(6) я бы вычислил все значения функции ниже, чем их соответствующие n. Это заставит программу работать очень медленно, для получения значения f(40) потребуется около 15 минут. Чтобы сделать это быстрее, я просто использовал уже имеющуюся у меня хэш-карту со всеми значениями и использовал их при поиске более низких значений вместо их фактического вычисления.
  2. Теперь я мог добраться примерно до f(350). Кроме того, я получал почти нулевые значения. Я обнаружил, что проблема заключается в том, что программа достигает двойного предела функции nCr (n! › limit). Итак, вместо вычисления n! а затем разделить на r! и (n-r)!, я умножал и делил одновременно.
  3. Это исправление заставило меня достичь f (1020), после чего все снова сломалось. Оказалось, что я снова достигал двойного предела, поэтому вместо того, чтобы вычислять 2 ^ n, а затем нырять число на это значение, я просто делил число на 2 n раз.
  4. Это дало мне еще три значения, после чего я начал получать «бесконечность» для всех значений. Источником этой проблемы было то, что программа снова достигла двойного предела в функции nCr. Само конечное значение на этот раз было выше предела, поэтому мне пришлось переписать всю программу. Помимо f(1020), я вычислил все необходимые компоненты в логах и в конце возвел в степень.
  5. Теперь не было никакого реального предела тому, как высоко я мог подняться, если только логарифм значения nCr не оказался выше двойного предела, но это было бы при астрономическом n. Теперь проблема заключалась в том, насколько он был медленным. Первые несколько тысяч значений заняли бы несколько минут, но чтобы получить f(10000), я запустил программу на ночь. Все, что выше, наверняка сломает мой компьютер. Я проследил, что медленная составляющая (еще раз) является функцией nCr. Я понял, что во время моей программы я буду вычислять (n)C(r), а затем (n)C(r+1). Вместо того, чтобы умножать одни и те же числа с минимальными изменениями, я нашел простую формульную константу между ними.

С этим последним исправлением я мог получить более f(10000) за считанные минуты. Однако теперь проблема была не в скорости, а в точности.

Как вы можете знать или не знать, числа типа double хранят только 16 знаков после запятой. После этого значащие цифры в основном исчезают. Учитывая, что я теперь имел дело с журналами, каждое десятичное число имело значение. Я уже мог сказать, что программа становится довольно неточной после f(10000) (скоро я объясню, откуда я это узнал).

Итак, войдите в BigDecimal, библиотеку, которая дает вам бесконечную точность за счет времени. Некоторый рефакторинг и помощь библиотеки Cornell позволили мне получить столько знаков после запятой, сколько я хотел. Кроме того, мне больше не приходилось иметь дело с журналами, так как BigDecimal может хранить значения сколь угодно большими, что дало еще большую точность. Подавляющее большинство файлов в репозитории взяты из этой библиотеки, и в основном только файл запуска (realtesting.java) является моим.

Последние несколько изменений я сделал просто для удобства, а именно экспортировал консоль со всеми напечатанными значениями в блокнот и использовал этот самый блокнот для вычисления дополнительных значений, если это необходимо, вместо повторного вычисления этих значений (в основном внешняя хэш-карта). В репозитории есть все точки, которые я рассчитал в файле README, поэтому, если хотите, можете их использовать. С 24 десятичными знаками я получил около f (45000) за 36 часов. Я обнаружил, что 24 знака после запятой достаточно точны, но вы можете увеличить их до нужного значения.

На самом деле нет никакого способа сделать это быстрее, не жертвуя точностью или увеличивая вычислительную мощность. Однако я обнаружил, что получение большего количества очков на самом деле не приближает меня к конечной цели.

Чтобы объяснить это и то, как я понял, что двойные значения неточны, нам нужно поговорить о том, как сами значения функций. Даже не пройдя сотню точек, вы можете сказать, что функция сходится к некоторому значению. Примерно на 1000 становится очевидным, что он начинается с 0,7213. Кроме того, он колеблется между 0,721340 и 0,721355, постепенно сходясь.

Говоря о подпрыгивании, график большинства точек (больше и предел памяти был достигнут) показывает, что функция очень похожа на демпфирование гармонического движения. Самая большая разница заключается в том, что период функции медленно увеличивается до точки, где каждый пик в два раза превышает значение предыдущего.Вот ссылка на график первых 10 000 точек( двойной) с лучшим обзором и маркировкой всех гребней и впадин. Хотя это и не точное удвоение, но очень близко к нему. Более того, деление вершины на соответствующую впадину почти точно дает sqrt(2). Другими словами, умножение экстремумов на sqrt(2) покажет следующие экстремумы. Я предполагаю, что повышенная точность и расширение домена до всех неотрицательных действительных чисел создадут идеальное удвоение периода.

График также показывает, что мы на самом деле стремимся к пределу. Хотя нам нужно добиться значительного прогресса, чтобы приблизиться к этому пределу, поскольку даже с десятками тысяч дополнительных точек мы все равно знаем только 0,7213. Мы подходим ближе, но, как объяснялось ранее, для достижения следующего экстремума требуется вдвое больше очков, и этот экстремум чуть ближе к пределу, чем предыдущий. В значениях функции также нет видимой закономерности (по крайней мере, в десятичной форме).

Несмотря на все проблемы, сам график довольно сумасшедший. Из нашей задачи с бесконечными игральными костями мы создали несколько синусоидальную функцию, период которой постепенно удваивается, что является безумием. Поскольку это затухание, скорее всего, существует сходящийся предел.

Это отмечает весь прогресс, которого я достиг в решении этой проблемы. На самом деле мы могли бы сделать больше — найти дробное значение каждого из этих очков, перейти от двухгранных монет к теоретическому трехгранному кубику (и т. д.), — но я не думаю, что они приблизят нас к нашей цели. цель.

Итак, пока не будет достигнуто больше прогресса, я перестану писать об этой проблеме, и мы перейдем к другой.

До свидания!