Оглавление [Скрыть]
Алгоритм целочисленного отношения
-
Целочисленное отношение и алгоритм
- Целочисленное отношение между действительными числами x1, x2, …, xn — это набор целых чисел a1, a2, …, an, не все из которых равны 0, такой, что
- Алгоритм целочисленных отношений находит целочисленные отношения между заданными действительными числами или определяет, что таких отношений не существует.
-
История алгоритмов
- Для случая n = 2 евклидов алгоритм находит любое целочисленное соотношение между x1 и x2.
- Алгоритм Фергюсона–Форкейда опубликован в 1979 году, но не имеет полных доказательств.
- Алгоритм LLL разработан в 1982 году, имеет полные доказательства.
- Алгоритм HJLS разработан в 1986 году, имеет полные доказательства.
- Алгоритм PSOS разработан в 1988 году, имеет полные доказательства.
- Алгоритм PSLQ разработан в 1992 году, существенно упрощен в 1999 году, признан одним из “Десяти лучших алгоритмов века”.
-
Приложения алгоритмов
- Определение алгебраичности числа x через поиск целочисленного отношения между степенями x.
- Поиск целочисленного отношения между x и математическими константами для выражения x через эти константы.
- Использование численных методов для нахождения приблизительных значений бесконечных рядов, произведений или интегралов, затем поиск целочисленного отношения для выражения в замкнутой форме.
- Пример успеха: формула Бейли–Борвейна–Плуффа для π.
- Нахождение новых тождеств, связанных с дзета-функциями и квантовой теорией поля.
- Определение точек бифуркации логистической карты.
- Объединение с таблицами математических констант и эвристическими методами для приложений, таких как обратный символьный калькулятор и инвертор Plouffe.
- Разложение полиномов высокой степени на множители.