Упрощение суммирования для достаточно больших m

[kthxbye]

Пусть $a(n)$ - произвольная целочисленная последовательность.

Пусть также $b(n,m)$ - целочисленная последовательность, такая, что

$$b(n,m)=\sum\limits_{k=1}^{n}b(k,m-1)b(n-k,m), b(n,0)=a(n), b(0,m)=1$$

Какие существуют способы вычисления $b(n,m)$ для достаточно больших $m$ (например $m=2^{1000}$)?

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

[zykov]

Тут вроде на свёртку похоже.
Можно через Фурье посчитать, что быстро, т.к. есть быстрый алгоритм Фурье-преобразования.

[kthxbye]

zykov в сообщении #1596467 писал(а):

Тут вроде на свёртку похоже.
Можно через Фурье посчитать, что быстро, т.к. есть быстрый алгоритм Фурье-преобразования.

Благодарю за ответ! Можно чуть подробнее? Если что, я не математик, а просто энтузиаст. Мне желательно иметь код на PARI/GP для сравнения по скорости с моим.

[zykov]

Свёртка (математический анализ)
Дискретное преобразование Фурье
Быстрое преобразование Фурье

-- 04.06.2023, 17:18 --

kthxbye в сообщении #1596454 писал(а):

(например $m=2^{1000}$)?

Впрочем $2^{1000}$ - это перебор.
В какую память это влезет???

[Null]

Пусть $B_m(x)=\sum_{k=0}^{\infty}b(k,m)x^k$ - формальный степенной ряд. Если я ни где не накосячил $B_m(x)=\frac{2}{2-B_{m-1}(x)}$. Пусть $F(u)=\frac{2}{2-u}$. Тогда $F^{m}(u)$($m$ итераций) - дробно-линейная функция и её коэффициенты считаются за $O(\log^3{m})$. А потом подставляем в неё ряд $B_0(x)$.

[kthxbye]

zykov, благодарю за ссылки, буду разбираться!

zykov в сообщении #1596495 писал(а):

Впрочем $2^{1000}$ - это перебор.
В какую память это влезет???

У меня на PARI/GP для $m=2^{1000}$ и $n=1\cdots 50$ считается за две минуты. К сожалению мой алгоритм вычисляет не отдельные значения, а первые $k$ значений, а также работает только для последовательностей $a(n)$ у которых $a(1)=1$. Вот и он:

a(n)=n--; binomial(2*n, n)/(n+1)
f(n)=my(v, v1, v2); v=vector(n+2,i,if(i==1,vector(n+2,j,a(j)),vector(n-i+3,j,(j==1)))); v1=vector(n+1,i,0); v1[1]=a(2)-1; for(i=2,n+1,for(j=2,i,v[j][i-j+2]=v[j-1][i-j+3]-sum(k=1,j-1,v1[j-k]*v[k][i-j+2])); v1[i]=v[i][2]-sum(j=1,i-1,v1[j])-1); v1
b(n,m)=my(v, v1, v2, v3); v=f(n); v1=vector(n+1,i,1); v2=v1; v3=vector(n+1,i,0); v3[1]=1; for(i=1,n,for(j=1,n-i+1,v2[j]=v1[j+1]+sum(q=1,j,(m+1)^-(j-q+1)*v[j-q+1]*v1[q])); v1=v2; v3[i+1]=v1[1];); for(i=1,n,v3[i+1]*=(m+1)^i); v3

Null, благодарю за ответ! Буду пробовать и обязательно поделюсь результатом. Функцию $F(u)$ надо просто возводить в степень или же для подсчета ее коэффициентов есть какой-то хитрый ход?

[Null]

kthxbye в сообщении #1596625 писал(а):

Функцию $F(u)$ надо просто возводить в степень или же для подсчета ее коэффициентов есть какой-то хитрый ход?

$F^{2k+1}(x)=F(F^k(F^k(x)))$
$F^{2k}(x)=F^k(F^k(x))$

[kthxbye]

Null, еще раз благодарю! Вот слепил программку на скорую руку:

a(n)=numbpart(n)
F(x,m)=if(m==0,2/(2-x),F(F(x,m-1)))
B(x)=sum(k=1,10,a(k)*x^k)
b(n,m)=polcoeff(F(B(x+O(x^11)),m),n)

Прога успешно возвращает $b(n,1)$, а вот уже на $b(n,2)$ начинает ошибаться. Кроме того, не проверяя базовых случаев, я сразу забил в прогу $m=2^{1000}$ и она пожаловалась мне на ошибку deep recursion для $F(x)$.

[Null]

Итерации функции надо считать за $O(\log{m})$. Причем в явном виде. Делает ли ваша программа это? Можно свести в возведению матрицы в степень.
Попробуйте $F(u)=\frac{1}{2-u}$. Похоже я накосячил.
$a(0)=1$?

[kthxbye]

Null, вот первые 30 ($m=0\cdots29$) значений $F(x,m)$:

2/(-x + 2)
(-x + 2)/(-x + 1)
(-2*x + 2)/-x
x
2/(-x + 2)
(-x + 2)/(-x + 1)
(-2*x + 2)/-x
x
2/(-x + 2)
(-x + 2)/(-x + 1)
(-2*x + 2)/-x
x
2/(-x + 2)
(-x + 2)/(-x + 1)
(-2*x + 2)/-x
x
2/(-x + 2)
(-x + 2)/(-x + 1)
(-2*x + 2)/-x
x
2/(-x + 2)
(-x + 2)/(-x + 1)
(-2*x + 2)/-x
x
2/(-x + 2)
(-x + 2)/(-x + 1)
(-2*x + 2)/-x
x
2/(-x + 2)
(-x + 2)/(-x + 1)

Т.е. функция зацикливается и ходит по кругу. Вероятно так быть не должно. Либо моя программа вычисляет функцию неправильно, либо проблема в чем-то другом.

Null в сообщении #1596654 писал(а):

Итерации функции надо считать за $O(\log{m})$. Причем в явном виде. Делает ли ваша программа это? Можно свести в возведению матрицы в степень.

Что такое в явном виде? Надо задавать цикл for длины $m$ который программа обязана будет пройти? Что за матрица? Как ее возводить?

Null в сообщении #1596654 писал(а):

$a(0)=1$?

Если внимательно посмотреть на формулу $b(n,m)$, то можно заметить, что $a(0)$ не влияет на расчеты. У меня $a(0)=0$. При этом, конечно, $b(0,0)=1$.