Итальянка

[wrest]

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

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

Там ведь даже не умножения, а возведения в квадрат, а это должно быть быстрее чем просто умножение.

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

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

Вольфрам, как я слышал, небыстрый. pari/gp тоже интерпретатор, но вот на подобные вычиcления немного лучше заточен, вот и всё.

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

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

Не не, в программах на pari/gp что я запускал не используется встроенная функция вычисления Фибоначчи, она такие большие числа не умеет.
Использовалось два кода, подсказанный ув. maxal, через производящую функцию, по модулю
fibomod_2(n,m)=lift(polcoef(lift(Mod(x,(x^2-x-1)*Mod(1,10^m))^n),1,x))
и возведением "производящей матрицы" в степень, тоже по модулю:
fibomod_1(n,m)=lift(((Mod([1,1;1,0],10^m))^(n-1))[1,1])

Обе берут на вход n - номер числа Фибоначчи, m - сколько последних цифр вернуть в качестве результата (ведущие нули опускаются).
С кодом fibomod_2(), использующим производящую функцию, надо быть осторожным: переменная x не должна использоваться до этого кода, или надо выполнить команду kill(x) если использовалась.

P.S. Ну а вообще, сермяжная правда конечно в том, что числа Фибоначчи (и вообще ЛРП, но Фибоначчи в особенности) и всё про них украдено задолго до нас. Но сейчас вычисления такого объема , как например предложили вы (стомиллионнозначные числа по тысячезначному модулю), стало доступно на гаджетах (я пользуюсь андроид планшетом, и он по скорости примерно такой же как мой ноутбук) лёжа на диване, и позволяет легко удовлетворить праздный интерес.

[lel0lel]

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

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

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

Там ведь даже не умножения, а возведения в квадрат, а это должно быть быстрее чем просто умножение.

Про три умножения -- это я про алгоритм, который использовался при расчёте выше мной. Он легко переписывается под два умножения, правда именно умножения, поэтому, как вы верно заметили два squaring в алгоритме gmp всё равно будут немного быстрее, скорее всего.

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

Вольфрам, как я слышал, небыстрый. pari/gp тоже интерпретатор, но вот на подобные вычиcления немного лучше заточен, вот и всё.

Да, это влияет, но не сильно, на таких объемах основное -- это количество больших умножений, если его сделать минимальным, то ни интерпретатор, ни железо -- не главное.

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

Не не, в программах на pari/gp что я запускал не используется встроенная функция вычисления Фибоначчи, она такие большие числа не умеет.

Это понятно, я вам отправлял код maxal, там, при вычислении $x^n \bmod Cp(x)$, используется только возведение в квадрат полиномов по полиномиальному модулю (алгоритм Fiduccia), тем не менее это почти тоже, что некоторое количество умножений по модулю. Поэтому я и сказал, что так или иначе, в pari для умножения двух линейных полиномов по модулю полинома второго порядка реализация эквивалентна двум большим умножениям. Отсюда и различие 3/2. Про другие коды сказать не берусь, так как pari не использую, но, с большой вероятностью, это те же два умножения (быть может squaring).

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

всё про них украдено задолго до нас

Это вы зря, полно открытых проблем. Машины считают быстро, это ваша правда. Посчитаю пожалуй "пентаначчи") давно ничего не считал, так, ради интереса: $f_0=f_1=f_2=f_3=0, f_4=1, f_{k+5}=f_{k+4}+f_{k+3}+f_{k+2}+f_{k+1}+f_{k}$. Задача таже. Расчётное время полёта 2 часа 26 минут , но я пожалуй спать

[lel0lel]

Время в секундах, немного раньше планируемого.

In[116]:= AbsoluteTiming[AnyOrderRecurrenceModulo[{0, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, 10^10000000, 10^1000]]

Out[116]= {7474.47, 
297919434044441427313952240882791859235377456519957485683612326523101343187362485727950513984897408395496
758254206776045600872220478373237452374283441317226722846870348022952014396504076758453612303636532822655
484940428198255664630193251812981357182008672955588092292209205401387170080496741712116822345565753287753
952057689414845743494482987594714257798724183449405530685469958729607189120032090941391938738193571965020
989325826484390252837443091721399860062328139936172039093718733375213438541691651031355203405931173528985
527672468556878197950083643100603759034920127037472513136157172439312821183036734091812810198773052715056
796167537718276046473659449129481680288867987158434436222784729602238558415469784467770705947560236441675
070255456452649997533877319135183367080208234025796307848225760647126584074253677577392179807162815590026
358723966740095321659626251879997346875931238743224948041964358907625571889757090877956684833848932495317
91795297759953095409776391702029485
2042506005648324353}

[wrest]

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

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

Если вспомнить про период, то время счета будет 300мс (результат не печатаю, он правильный)
? fibomod_10m(n,m)=n=n%(15*10^(m-1));lift(((Mod([1,1;1,0],10^m))^(n-1))[1,1])
? fibomod_10m(10^(10^7),1000);
? ##
*** last result computed in 306 ms.
?

-- 06.10.2023, 08:52 --

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

Посчитаю пожалуй "пентаначчи")

Вот универсальные ванлайнеры для обсуждаемой темы
1. Считаем n-ое k-наччи (подсмотрено в oeis про пентаначчи):
knacci(n, k)=(matrix(k, k, i, j, i==j-1||i==k)^n)[1, k]
Например 20-е пентаначчи:
? knacci(20,5)
%229 = 26784
?

2. Считаем n-ое k-наччи по модулю m
knaccimod(n,k,m)=lift(((Mod(matrix(k, k, i, j, i==j-1||i==k),m))^(n))[1,k])
Например 20-e 5-наччи по модулю 1000:
? knaccimod(20,5,10^3)
%230 = 784
?

-- 06.10.2023, 08:53 --

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

Время в секундах, немного раньше планируемого.

У меня чуть меньше часа (57 минут).

[wrest]

Для закрытия обощенного вопроса темы хорошо бы ещё научиться вычислять период k-наччи по модулю (ЛРП же периодические все по модулю, если я правильно понимаю).

[wrest]

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

Для закрытия обощенного вопроса темы хорошо бы ещё научиться вычислять период k-наччи по модулю (ЛРП же периодические все по модулю, если я правильно понимаю).

Можно даже не наименьший (главный), если это сложно, а какой-нибудь.

[maxal]

maxal в сообщении #1559683 писал(а):

Строгое изложение теории можно найти в учебнике
Глухов М. M., Елизаров В. П., Нечаев А. А. Алгебра.
См. глава 25 § 9. Вычисление периода и длины подхода ЛРП над конечным полем

[wrest]

maxal
Спасибо, я пас: у меня не хватает образования для этой главы этой книги.
Может, lel0lel или Doctor Boom почитают.

[maxal]

Вот здесь есть код для вычисления периода по простому модулю:
post1559671.html#p1559671

[wrest]

maxal в сообщении #1612699 писал(а):

Вот здесь есть код для вычисления периода по простому модулю:

Да, я видел. Но у нас модуль не простой (пока интересовались последними цифрами десятичной записи, т.е. модулями вида $2^n\cdot 5^n$) и код, ессно, не работает...