Итальянка

[wrest]

TOTAL в сообщении #1612231 писал(а):

Легко доказать?

Период равен 1500. Ну и 6000 тоже подходит :)
Ну и вообще, период остатков от деления фибоначчей на $10^n$ равен $1,5\cdot 10^n$ для $n>2$

[TOTAL]

wrest в сообщении #1612234 писал(а):

TOTAL в сообщении #1612231 писал(а):

Легко доказать?

Период равен 1500. Ну и 6000 тоже подходит :)
Ну и вообще, период остатков от деления фибоначчей на $10^n$ равен $1,5\cdot 10^n$ для $n>2$

Эх, а можно было и догадаться. Ведь периоды по модулям $2^3$ и $5^3$ нашёл как $4*3$ и $25*20$. Затем нужно было наименьшее кратное, а я просто перемножил.

[Doctor Boom]

realeugene в сообщении #1612226 писал(а):

классическим алгоритмом вычисления Фибоначчи за логарифмическое время

Ага, его уже до меня придумали
TOTAL
wrest
Собственно, я решал так. Можно показать, что $F(m+n)=F(m)F(n)+F(m-1)F(n-1)$, а также $F(m+1)F(m-1)=F^2(m)\pm 1$. Экспоненциально увеличиваем $m$, постоянно удваивая (по первой формуле), а предыдущие числа Фибоначчи находим по второй. Правда вместо $F(m)$ используем последние цифры $x$ (т.к. нас интересуют только они), и после каждого вычисления берем также последние цифры и т.д. Получаем логарифмическое время

[wrest]

Doctor Boom в сообщении #1612302 писал(а):

Собственно, я решал так.

Ок, тогда наверное у вас есть ответ какие

Doctor Boom в сообщении #1612230 писал(а):

последние 10 цифр?

для

Doctor Boom в сообщении #1612224 писал(а):

$358436853268954357854468657567$ члена последовательности Фибоначчи

Для pari/gp не хватило 4 гигабайт памяти стека для вычисления "обычным" путём, а давать больше я не стал пробовать (где-то в районе 6..8 гигабайт отъедаемых pari/gp обычно начинаются проблемы у моего андроид-планшета).

[Doctor Boom]

wrest
Я пока не считал (вручную через калькулятор очень долго, а прогать лень). Разумеется, вычислять явно это число Фибоначчи дичь, я мог бы дать и стозначный номер члена

[wrest]

Doctor Boom в сообщении #1612328 писал(а):

Разумеется, вычислять явно это число Фибоначчи дичь, я мог бы дать и стозначный номер члена

Ну тогда по задаче

Doctor Boom в сообщении #1612230 писал(а):

последние 10 цифр?

для

Doctor Boom в сообщении #1612224 писал(а):

$358436853268954357854468657567$ члена последовательности Фибоначчи

У меня получается такой ответ: $3131370978$
Как проверите, дайте знать, правильно ли я сосчитал.

[Doctor Boom]

wrest
А вы считали по моему методу или своему?

[wrest]

Doctor Boom в сообщении #1612331 писал(а):

А вы считали по моему методу или своему?

Я обнаружил ещё один

Вернее, метод самый чтотни на есть ваш. Но как именно это в pari считается я не знаю, знаю что очень быстро, можно сказать мгновенно.

[wrest]

Doctor Boom
Из Википедии (ну не только из неё, но из неё проще, можно латех скопировать) узнаём, что $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$
Откуда следуют в частности и формулы вашего метода.
Запрограммировав возведение матрицы в степень напрямую в pari, получаем удивительно быстрый результат.
? Fn_last_m_digits(n,m)=lift(((Mod([1, 1; 1, 0], 10^m))^(n-1))[1,1]);
? Fn_last_m_digits(358436853268954357854468657567,10)
%163 = 3131370978
? ##
*** last result computed in 0 ms.
?
Где-то под капотом pari мгновенно возводит в степень эту матрицу, а наличие встроенной модулярной арифметики ещё больше упрощает этот процесс. Даже не пришлось искать остаток от деления номера на период (т.к. оно и так посчиталось быстрее миллисекунды).
Ну ясно, что таким же образом можно искать остаток от деления чисел Фибоначчи на любое число, а не только $10^m$

[Andrey A]

Период Фибоначчи по $\mod m$ бывает $=x_m,$ либо $2x_m,$ либо $4x_m,$ где $x_m$ — номер наименьшего Фибоначчи кратного $m\left ( F_x \right ).$ Ссылка maxal от 01.09.2018: https://dxdy.ru/post1335875.html#p1335875.
Как вычислить $F_x$ было выше.

[wrest]

Andrey A в сообщении #1612354 писал(а):

Период Фибоначчи по $\mod m$ бывает $=x_m,$ либо $2x_m,$ либо $4x_m,$ где $x_m$ — номер наименьшего Фибоначчи кратного $m\left ( F_x \right ).$

Периоды Пизано также описаны в Википедии (статья "Период Пизано") а методы их вычисления в A001175

[lel0lel]

wrest
В этой теме https://dxdy.ru/topic150059.html maxal привёл пример вычисления в pari/gp периода последовательности чисел трибоначчи по модулю, там есть код и книга по теории.

Для задачи из этой темы должно работать следующее

n=358436853268954357854468657567; Mod(x,(x^2-x-1)*Mod(1,10^10))^n

Это просто отредактированный код maxal для трибоначчи.

Давайте проведём небольшой конкурс железа: посчитаем $F_n\bmod 10^{1000}$ для $n=10^{10^7}$. У меня получилось так (не пользуясь периодичностью)

AbsoluteTiming[AnyOrderRecurrenceModulo[{0, 1}, {1, 1}, 10^10000000, 10^1000]]
{1733.34,
12126777761338423904739066327632362358045016070713179270131387083553035703114480187613454162426779656763622051928
15167257914761446046349926413161948415387172356775381660704544905989363275737166433722255526941465989583746483137
58039086681535986613318166960337210579662349945336412038111890572826810206418771015492680303216188591177740050051
65497589782581480607406094544341193540705720765867327674272181887063446620118751614592592254206946411343936651271
44829594384076832421629176463717100169653234214121130494879951938385686905849399892571130467767322222201018982942
92143463825295465052730850408006648271777134287992114791017442101692797278260849345480148951055375090438022397142
15692879808437222698243931308606631730806646502252465240033265722807533359487045849221225596472327339101087072173
58232069894566897234317203958019684637492402136171609038697139689209157281907967940911211787719700531851223803239
047153240982923932796604356740872797698500591032259930505954326207529447856359183788299560546875}

Один из самых эффективных алгоритмов для вычисления удалённых чисел Фибоначчи: https://my.eng.utah.edu/~pajensen/ACM/Documentation/gmplib.org/manual/Fibonacci-Numbers-Algorithm.html,
я считал не по нему.

[wrest]

lel0lel в сообщении #1612491 писал(а):

Давайте проведём небольшой конкурс железа:

Запустил на ноутбуке одновременно два потока pari/gp. Один через возведение матрицы в степень, другой через производящую функцию. Если через час результата не будет, то я из конкурса выбываю.

upd Счет закончился. Функция с возведением матрицы в степень отработала за 1242 сек, функция с производящей функцией за 1131 сек.
Значения совпадают с тем, что вы привели.

[wrest]

lel0lel в сообщении #1612491 писал(а):

посчитаем $F_n\bmod 10^{1000}$ для $n=10^{10^7}$.

Ну тут получается $\log_2(n)\approx 3,3\cdot 10^7$ ну и сам номер не степень двойки, так что ещё потребуется сколько-то сложений (единиц в двоичной записи номера примерно треть , около $1,2\cdot 10^7$) и наверное можно параллелить сложения, что немного ускорит вычисление.

lel0lel в сообщении #1612491 писал(а):

Один из самых эффективных алгоритмов для вычисления удалённых чисел Фибоначчи:

GMPLib используется в pari, не знаю используется ли конкретно для Фибоначчей. Но кстати в pari втроенная функция вычисления чисел Фибоначчи на вход принимает long (64 бит для 64-битных систем, насклько я понимаю), так что для бОльших номеров надо делать своё.

[lel0lel]

Поздравляю)
Примерно в полтора раза быстрее.

wrest в сообщении #1612560 писал(а):

наверное можно параллелить сложения, что немного ускорит вычисление.

Думаю, что это бессмысленно, так как основное время в такой задаче это умножение по большому модулю. С учётом обмена данными, выиграша скорее всего не будет, а возможно, что будет проигрыш во времени. Вот пободаться с умножением имеет смысл, я считал алгоритмом, в котором каждый бит это три умножения. Его можно переписать, что умножений будет два ( меньше для рекурсий второго порядка не получить)

wrest в сообщении #1612560 писал(а):

GMPLib используется в pari, не знаю используется ли конкретно для Фибоначчей.

Очень может быть, и, кстати, похоже на правду, так как это объясняет различие в полтора раза. У GMPlib в алгоритме два умножения на бит, точнее два squaring.

Если есть желание, посчитайте эту же задачу для "пентаначчи", для рекурсий старших порядков я как-то оптимизировал количество больших умножений на бит, там с pari пободаться есть хорошие шансы)