Как можно подтвердить принадлежность числа к Числам Фибоначч

[dask]

Как можно подтвердить принадлежность числа к Числам Фибоначчи?
К примеру при n = 600, Fn = 110433070572952242346432246767718285942590237357555606380008891875277701705731473925618404421867819924194229142447517901959200

[maxal]

Почему бы просто не вычислить $F_n$ для заданного $n$ ?

? fibonacci(600)
%1 = 110433070572952242346432246767718285942590237357555606380008891875277701705731473925618404421867819924194229142447517901959200

Добавлено спустя 5 минут 34 секунды:

А если $n$ неизвестно, то можно вычислить максимальное число Фибоначчи, не превосходящее заданного числа $m$, и сравнить его с $m$. При этом порядковый номер числа Фибоначчи можно прикинуть по формуле $\log_{\phi} m$, где $\phi = \frac{1+\sqrt{5}}{2}$.

[PSP]

А зачем нужны эти числа Фибоначчи? Польза от них хоть какая есть?

[maxal]

PSP писал(а):

А зачем нужны эти числа Фибоначчи? Польза от них хоть какая есть?

Конечно! См., например: http://ilib.mccme.ru/plm/ann/a06.htm

[tolstopuz]

dask писал(а):

Как можно подтвердить принадлежность числа к Числам Фибоначчи?

Посчитайте $\frac{log(F\sqrt{5})}{log\frac{1+\sqrt{5}}{2}}$ и округлите. Это номер одного из двух окружающих $F$ чисел Фибоначчи. Потом посчитайте это число и сравните с $F$.

[незваный гость]

Ок, можно поставть вопрос по-другому? Дано (большое) x. Надо с минимальными вычислительными затратами определить, является ли оно числом Фибоначчи.

С этой точки зрения, алгоритмы вычисляющие логарифмы не вполне пригодны: их вычислительная сложность очень велика. С другой стороны, вычисление остатка по простому модулю могло бы позволить подсчитать $n$ используя китайскую теорему об остатках (а дальше, имеея гипотезу о $n$, можно вычислить $F_n$ за ${\rm O}(n^{\phi})$ шагов. Или я вру где-нибудь?

[maxal]

незваный гость писал(а):

С другой стороны, вычисление остатка по простому модулю могло бы позволить подсчитать $n$ используя китайскую теорему об остатках (а дальше, имеея гипотезу о $n$, можно вычислить $F_n$ за ${\rm O}(n^{\phi})$ шагов. Или я вру где-нибудь?

Тут надо учитывать, что в периоде чисел Фибоначчи по простому модулю некоторые остатки могут повторяться. Поэтому определить $n$ однозначно сразу не получится (придется перебрирать варианты).

На самом деле, $n$ вычислять необязательно. Вместо этого можно воспользоваться формулой $F_{m+n} = F_{m+1} F_{n} + F_{m} F_{n-1}$ и удваивать индекс чисел Фибоначчи до тех пор, пока не будет получено число $F_{2^k}$ большее заданного, затем вычислить $F_{2^{k-1} + 2^{k-2}$ (по той же формуле) и т.д. По сути - это будет вариант дихотомии (двоичного поиска) на числах Фибоначчи.

[незваный гость]

maxal писал(а):

Тут надо учитывать, что в периоде чисел Фибоначчи по простому модулю некоторые остатки могут повторяться.

Да, я это имел в виду, и мне это не нравилось с самого начала.

Мне кажется, дихотомию проще применять несколько иначе, оценив верхнюю и нижнюю границу (например, через количество цифр).

[tolstopuz]

незваный гость писал(а):

Мне кажется, дихотомию проще применять несколько иначе, оценив верхнюю и нижнюю границу (например, через количество цифр).

Количество чисел Фибоначчи с данным количеством цифр по данному основанию ограничено константой, только надо уметь за приемлемое время узнавать номера этих чисел (то есть брать логарифм достаточно точно) с не более чем константной ошибкой. Думаю, хороший алгоритм сделает это за $\rm{O}(\log\log n)$, а плохой - за $\rm{O}(\log n)$, все равно следующий шаг сложнее. А дальше $\rm{O}(\log n)$ шагов с несколькими умножениями многократной точности, которые делаются где-то за $\rm{O}(\log n\log\log n)$. Итого $\rm{O}((\log n)^2\log\log n)$.

[dask]

maxal писал(а):

На самом деле, $n$ вычислять необязательно. Вместо этого можно воспользоваться формулой $F_{m+n} = F_{m+1} F_{n} + F_{m} F_{n-1}$ и удваивать индекс чисел Фибоначчи до тех пор, пока не будет получено число $F_{2^k}$ большее заданного, затем вычислить $F_{2^{k-1} + 2^{k-2}$ (по той же формуле) и т.д. По сути - это будет вариант дихотомии (двоичного поиска) на числах Фибоначчи.

Все же получается последовательный перебор. Мне понравилась идея:

tolstopuz писал(а):

Посчитайте $\frac{log(F\sqrt{5})}{log\frac{1+\sqrt{5}}{2}}$ и округлите. Это номер одного из двух окружающих $F$ чисел Фибоначчи. Потом посчитайте это число и сравните с $F$.

Как вариант, сделать в два этапа: определится с предполагаемой областью вхождения, а заданную область пройтись одним из вариантов перебора?

[maxal]

dask писал(а):

maxal писал(а):

На самом деле, $n$ вычислять необязательно. Вместо этого можно воспользоваться формулой $F_{m+n} = F_{m+1} F_{n} + F_{m} F_{n-1}$ и удваивать индекс чисел Фибоначчи до тех пор, пока не будет получено число $F_{2^k}$ большее заданного, затем вычислить $F_{2^{k-1} + 2^{k-2}$ (по той же формуле) и т.д. По сути - это будет вариант дихотомии (двоичного поиска) на числах Фибоначчи.

Все же получается последовательный перебор.

Где же это последовательный?
$F_{2^k}$ (и все промежуточные степени) вычисляется за $O(k)$ арифметических операций. Каждое последующее число Фибоначчи при дихотомии - за O(1) операций каждое, и весь поиск займет $O(k)$ шагов.
Нетрудно видеть, что $k=O(\log\log n)$ (если точнее, то что-то типа $k=\lceil\log_2 \log_{\phi} n\sqrt{5}\rceil$). Вот и получается, что суммарная сложность такого поиска равна $O(\log\log n)$ арифметических операций.
Если умножение чисел длины $m$ производить за $O(m\log m)$ машинных операций (понятно, что сложение и сравнение также вписываются в эту оценку), то суммарную сложность можно оценить величиной $O(\log n(\log\log n)^2)$ машинных операций.
Никаких логарифмов вычислять не нужно, вся работа сводится к операциям сложения, умножения и сравнения целых чисел (примерно той же длины что и $n$).

Добавлено спустя 15 минут 34 секунды:

Так как придется хранить всего лишь $O(k)$ чисел, то расход памяти в данном алгоритме можно оценить как $O(\log n\log\log n)$ битов.

Добавлено спустя 17 минут 1 секунду:

P.S. Лучше работать не напрямую с числами Фибоначчи, а с матрицами вида

$$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\F_n & F_{n-1}\end{pmatrix}$$

Понятно, что произведение матриц такого вида опять же является матрицей такого вида.

[tolstopuz]

maxal писал(а):

Нетрудно видеть, что $k=O(\log\log n)$ (если точнее, то что-то типа $k=\lceil\log_2 \log_{\phi} n\sqrt{5}\rceil$).

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

[незваный гость]

maxal писал(а):

P.S. Лучше работать не напрямую с числами Фибоначчи, а с матрицами вида …

Мне (для несколько иной задачи) показалось удобнее работать с парой $(L_n, F_n)$, где $L_n$ — числа Лукаса. Но это дело вкуса.

[maxal]

Еще один вариант теста:
число $m$ является числом Фибоначчи тогда и только тогда, когда либо $5m^2+4$, либо $5m^2-4$ является полным квадратом.