C言語でチェビシェフの多項式を100回目まで作りたい

Question

チェビシェフ多項式の100回目をC言語で作りたいのですが
どこから初めていいのかわかりません。
教えて下さるとうれしいです。
T1(X)＝１
T2(x)＝X
T3(X)＝2x^2-1
T4(x)=4x^3-3x
というのがチェビシェフ多項式です。

Comments

[Penpen7]

「作りたい」というのはどういう意味でしょうか？
値を求めたいのか数式を作りたいのか

Answer 1

多項式の係数を並べた配列 c[N] を用意します。X^i の係数が c[i] なわけね。
そーすっと、

• 多項式に「x を掛ける」は配列c[N]の値をひとつズラす
• 多項式に「2 を掛ける」は配列c[N]の値を全部2倍する
• 多項式から「多項式d[N]を引く」は配列c[i]からd[i]を引く(i=0..N-1)

ことになります。

これだけ用意すれば T(n+1) = 2xT(n) - T(n-1) が計算できます。

Comments

[kazuma-s]

T100(x) = 2^98 x^99 + ... ですから、int64_t c[N]; だと 2^98 はオーバーフローです。
多倍長計算が必要でしょう。

[episteme]

ふぉろーありがとです。
ちょっとやってみた:
1: 1x0
2: 1x1
3: 2x2 -1x0
4: 4x3 -3x1
5: 8x4 -8x2 1x0
6: 16x5 -20x3 5x1
7: 32x6 -48x4 18x2 -1x0
8: 64x7 -112x5 56x3 -7x1
9: 128x8 -256x6 160x4 -32x2 1x0
10: 256x9 -576x7 432x5 -120x3 9x1
11: 512x10 -1280x8 1120x6 -400x4 50x2 -1x0
12: 1024x11 -2816x9 2816x7 -1232x5 220x3 -11x1
13: 2048x12 -6144x10 6912x8 -3584x6 840x4 -72x2 1x0
14: 4096x13 -13312x11 16640x9 -9984x7 2912x5 -364x3 13x1
...早晩パンクしますな。

多倍長計算が必要ではあるけど、2倍する と 引く とがあればいいのでさほどに面倒ではなさげ。

Answer 2

数式を取り扱うには、数式処理用のライブラリが必要になります。まずはその辺りから調査したらいかがでしょうか。私が一つ見つけたのはLeptonでした。
https://mattn.kaoriya.net/software/lang/c/20151014155115.htm
もしくはライブラリを使わなくとも、係数を配列で保存しておいて、漸化式でどんどん式を増やしていけばいいと思います。
何れにせよ、以下のような漸化式を処理すればいいでしょう。
T_{n+1}=2xT_{n}-T_{n-1}(n=1,2,...)
T0=1
T1=x

なお、言語にこだわらなければ、PythonのSympyで容易に多項式を求めることができます。
https://pianofisica.hatenablog.com/entry/2020/05/16/080000#Chebyshev%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%81%E3%82%A7%E3%83%93%E3%82%B7%E3%82%A7%E3%83%95%E5%A4%9A%E9%A0%85%E5%BC%8F
上記サイトから引用したソースコード(チェビシェフ多項式T0からT6を出力する)

import sympy as sp
sp.init_printing()
n=sp.symbols('n', integer=True)
x=sp.var('x')
C_list = []
for n in range(7):
    c = sp.chebyshevt(n,x)
    C_list.append(c)
C_list