2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 
Сообщение24.07.2007, 11:10 
Аватара пользователя
Почему бы просто не вычислить $F_n$ для заданного $n$ ?
Код:
? fibonacci(600)
%1 = 110433070572952242346432246767718285942590237357555606380008891875277701705731473925618404421867819924194229142447517901959200


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

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

 
 
 
 
Сообщение24.07.2007, 11:19 
Аватара пользователя
А зачем нужны эти числа Фибоначчи? Польза от них хоть какая есть?

 
 
 
 
Сообщение24.07.2007, 11:22 
Аватара пользователя
PSP писал(а):
А зачем нужны эти числа Фибоначчи? Польза от них хоть какая есть?

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

 
 
 
 Re: Как можно подтвердить принадлежность числа к Числам Фибо
Сообщение24.07.2007, 12:30 
dask писал(а):
Как можно подтвердить принадлежность числа к Числам Фибоначчи?
Посчитайте $\frac{log(F\sqrt{5})}{log\frac{1+\sqrt{5}}{2}}$ и округлите. Это номер одного из двух окружающих $F$ чисел Фибоначчи. Потом посчитайте это число и сравните с $F$.

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

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

 
 
 
 
Сообщение24.07.2007, 19:48 
Аватара пользователя
незваный гость писал(а):
С другой стороны, вычисление остатка по простому модулю могло бы позволить подсчитать $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}$ (по той же формуле) и т.д. По сути - это будет вариант дихотомии (двоичного поиска) на числах Фибоначчи.

 
 
 
 
Сообщение24.07.2007, 19:57 
Аватара пользователя
:evil:
maxal писал(а):
Тут надо учитывать, что в периоде чисел Фибоначчи по простому модулю некоторые остатки могут повторяться.

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

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

 
 
 
 
Сообщение24.07.2007, 20:39 
незваный гость писал(а):
Мне кажется, дихотомию проще применять несколько иначе, оценив верхнюю и нижнюю границу (например, через количество цифр).
Количество чисел Фибоначчи с данным количеством цифр по данному основанию ограничено константой, только надо уметь за приемлемое время узнавать номера этих чисел (то есть брать логарифм достаточно точно) с не более чем константной ошибкой. Думаю, хороший алгоритм сделает это за $\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)$.

 
 
 
 Re: Как можно подтвердить принадлежность числа к Числам Фибо
Сообщение24.07.2007, 21:50 
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$.


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

 
 
 
 Re: Как можно подтвердить принадлежность числа к Числам Фибо
Сообщение24.07.2007, 22:41 
Аватара пользователя
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}$$
Понятно, что произведение матриц такого вида опять же является матрицей такого вида.

 
 
 
 Re: Как можно подтвердить принадлежность числа к Числам Фибо
Сообщение24.07.2007, 22:48 
maxal писал(а):
Нетрудно видеть, что $k=O(\log\log n)$ (если точнее, то что-то типа $k=\lceil\log_2 \log_{\phi} n\sqrt{5}\rceil$).
О, я вот здесь ошибся. Но в любом случае оценка по длине действительно неэффективна, проще сразу дихотомия.

 
 
 
 
Сообщение24.07.2007, 23:15 
Аватара пользователя
:evil:
maxal писал(а):
P.S. Лучше работать не напрямую с числами Фибоначчи, а с матрицами вида …

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

 
 
 
 Re: Как можно подтвердить принадлежность числа к Числам Фибоначч
Сообщение25.12.2009, 03:59 
Аватара пользователя
Еще один вариант теста:
число $m$ является числом Фибоначчи тогда и только тогда, когда либо $5m^2+4$, либо $5m^2-4$ является полным квадратом.

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group