Raise Binomials to integer powers

8 次查看（过去 30 天）
Ilya
Ilya 2014-6-13
编辑： Ilya 2014-6-17
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.

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2014-6-13
编辑：Matt J 2014-6-13
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 个评论
显示 1更早的评论
John D'Errico
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.
Ilya
Ilya 2014-6-17
编辑：Ilya 2014-6-17
That's a valuable remark! I suspected this, but didn't know exactly that it might be so bad even with integers!

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Polynomials 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by