これはプログラミングの質問よりも複雑さの理論の質問であることを私は知っています。ここに間違ったことを書いていないことを願っています。間違った場所である場合はお詫びしますが、誰かが答えを持っていることを願っています。そして、それは複雑性理論の質問であることによって、どういうわけかプログラムミンに関連しています。
私は線形反復シーケンスを研究していますが、シーケンスのn番目の値を取得するには、コンパニオンマトリックスの累乗を取得する必要があることが表示されたので、累乗を取得するための既知のアルゴリズムがあるかどうか疑問に思いました。この種のマトリックスの高速な方法で..
コーディングの例を示すことはできませんが、もう少し説明してみましょう。
k次の同次線形反復シーケンス：
s（n + k）= a（k-1）s（n + k-1）+ a（k-2）s（n + k-2）+ .. .. + a（0）
for n = 0,1、..ここで、s（i）はシーケンスのi番目の値であり、a（i）は代数フィールドの係数です。
Aは、次の場合の上記のシーケンスのコンパニオン行列です：
（0 0 0 0 ... 0 a（0））
（1 0 0 0 ... 0 a（1））
（0 1 0 0 ... 0 a （2））
（.. .. .. .. .. .. .. .. ..）
（0 0 0 0 ... 1 a（k-1））
さらに、理論では、シーケンスは次のとおりです
。s（n）= s（0）A ^ n for n = 0,1、..
これで、助けてくれてありがとう。