Raise Binomials to integer powers
显示 更早的评论
It's needed to raise first-degree binomials (ax+b) (i.e. polynomial vectors [a b]) to integer powers. Is there any fast solution? Polynomial multiplication with convolutions is not fast if the required degree is high..
I know about the Pascal triangle, but I don't know/have an algorithm.
采纳的回答
Polynomial multiplication with convolutions is not fast if the required degree is high.
What about with FFTs, e.g.,
n=3;
p=[1,1];
p_to_the_n = real(ifft(fft(p,n+1).^n))
p_to_the_n =
1 3 3 1
3 个评论
Ilya
2014-6-15
John D'Errico
2014-6-15
编辑：John D'Errico
2014-6-15
Be careful though, as this will return floating point numbers, NOT integers as you might want.
format long g
n=20;
p=[1,1];
p_to_the_n = real(ifft(fft(p,n+1).^n))
p_to_the_n =
Columns 1 through 5
1.00000000003881 20.0000000000111 189.999999999978 1139.99999999998 4844.99999999996
Columns 6 through 10
15504 38760 77520 125970 167960
Columns 11 through 15
184756 167960 125970 77520.0000000001 38760.0000000001
Columns 16 through 20
15504 4844.99999999992 1139.99999999992 189.999999999956 19.9999999999778
Column 21
1.00000000003326
For high enough orders, even rounding might not be sufficient to restore them to integers.
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Polynomials 的更多信息
产品
Translated by 
