[Mathematica] 10^100 Число Фибоначчи

[coll3ctor]

Доброго времени суток, друзья.
Конечно, само число Фибоначчи по номеру 10^100 найти нереально (оно не поместится на экран), поэтому я хотел бы найти хотя бы последние 10 знаков
FromDigits к генерации числа Фибоначчи заданного номера так же ничего не дало. Думаю, здесь нужно использовать какое то св-во чисел, что-то типа 80, 180, 280 - у них есть какая то закономерность...

У кого какие идеи?

[venco]

Считать в матричном виде по модулю $10^{10}$.

[coll3ctor]

venco, по модулю? Это как понять? или это из св-в числа Фибоначчи?

матричный вид, это я понимаю так: (написал функцию)

fibonacArtur[n_Integer?NonNegative] := 
 MatrixPower[{{0, 1}, {1, 1}}, n - 1]

MatrixPowerMod использовать ? - к сожалению подобной функции нету (наряду с PowerMod для чисел).

[venco]

Ну, напишите возведение в степень по модулю вручную, матрицы маленькие, должно быть несложно.

[nnosipov]

coll3ctor в сообщении #579063 писал(а):

поэтому я хотел бы найти хотя бы последние 10 знаков

Что так скромно? Найдите хотя бы 1000.

[coll3ctor]

а другой путь к решению этой задачи есть?

[nnosipov]

coll3ctor в сообщении #583365 писал(а):

а другой путь к решению этой задачи есть?

Матрицы не нравятся? Работайте с многочленами. Принципиально иного пути нет.

[arseniiv]

Последние сто цифр равны 5690012597958236757558633467085120672027553533794679994830406632999597604793962091207504272460937501, если найдены верно.

Вот наипрямейшая реализация, которую можно сильно улучшить. Срабатывает у меня за доли секунды.

MatrixPowerMod[m_, 0, n_] := Mod[IdentityMatrix[Length[m]], n]
MatrixPowerMod[m_, p_Integer?Positive, n_] :=
  Block[
    {t = MatrixPowerMod[m, Floor[p/2], n]},
    If[
      EvenQ[p],
      Mod[t.t, n],
      Mod[t.t.m, n]
    ]
  ]

(* Как использовано: *)
Block[
  {$RecursionLimit = 1024},
  MatrixPowerMod[{{0, 1}, {1, 1}}, 10^100, 10^100][[2, 2]]
]

Как видно, если рекурсию преобразовать в цикл, будет проще работать с этой махиной — не будет $RecursionLimit::reclim (а было — стандартных 256 итераций не хватает).

-- Пн июн 11, 2012 17:16:34 --

Кстати, возможно, я номер числа перепутал и он должен быть на 1 больше-меньше.

-- Пн июн 11, 2012 17:19:03 --

Первое определение в MatrixPowerMod нужно для модулей не из $\mathbb Z_{>1}$.

[coll3ctor]

arseniiv
Великолепно! Крайне интересно! Спасибо! А не объясните пожалуйста что да как ?

[arseniiv]

Ну, тут для возведения в степень используется алгоритм за $O(\log n)$, вроде лучше с натуральным показателем и не сделать (точно не помню).

Этот алгоритм основан на свойствах степени (верно для любого моноида), выписанных в таком виде:
$\begin{array}{l} M^{2n} = M^n M^n, \\ M^{2n + 1} = M^{2n} M, \\ M^0 = I. \end{array}$

Остаётся только вовремя произведения брать по модулю.

Кстати, можно было написать немного лучше + нагляднее: вместо

If[
  EvenQ[p],
  Mod[t.t, n],
  Mod[t.t.m, n]
]

написать

Mod[If[EvenQ[p], t.t, t.t.m], n]

-- Пн июн 11, 2012 18:18:39 --

(Мне кажется, для умножения по модулю должны быть алгоритмы и получше.)

[coll3ctor]

arseniiv
1. А зачем оператор Block?
2. Почему если мы берём матрицу для поиска чисел Фибоначчии в степень 10^100 и получаем именно 100 чисел последних? Это какое то свойство $\mod$ - самой операции?

[arseniiv]

coll3ctor в сообщении #583550 писал(а):

1. А зачем оператор Block?

Чтобы завести локальную переменную t.

coll3ctor в сообщении #583550 писал(а):

2. Почему если мы берём матрицу для поиска чисел Фибоначчии в степень 10^100 и получаем именно 100 чисел последних? Это какое то свойство $\mod$ - самой операции?

Ага. Остаток от деления на 10000 совпадает с последними четырьмя цифрами числа. Соответственно, взятие числа по модулю $10^{100}$ оставляет только сто младших его разрядов, остальные выбрасывая.

[coll3ctor]

arseniiv
Спасибо! Всё очень понятно и да, решение можно улучшить, но и это очень изящно и продуктивно.

(Оффтоп)

благодаря вам получил около 10 лишних баллов на зачёт, только оттуда

И да, тему клоз.