🚀 go-pugleaf

leo@mxb.meshnet.or.jp wrote:
> 
> 教えてください。
> 
> 以下のようなプログラムを高速化するにはどうしたらいいでしょうか？
> 
>         long            i,j,n,nn;
>         double  nrm,sigma;
>         double  cosTable[],x[],y[];
> 
>         for( j=1 ; j<n ; j++ )
>         {
>                 for(sigma=i=0 ; i<n ; i++)
>                     sigma += x[i] * cosTable[(( 2 * i + 1 ) * j)%nn] ;
>                 y[j] = nrm * sigma;
>         }
> 

(1)  処理そのものを見直す。
     →元の式にたちかえって、数式を変形するだけで処理が減らないかどうか、
       考えてみる。
(2)  ＦＰＵの高速なマシンならば、極力整数を利用しない。
     →整数演算より小数演算の方が速いマシンも存在する。そうしたマシンでは
       コサインのテーブルよりコサインそのものをＦＰＵに計算させたほうが、
       かえって速いことさえある。整数←→小数の変換に手間取るマシンも存在
       する。
(2)' 小数演算を決して使わない。
     →ＦＰＵの付属していないマシンの場合、小数の演算もすべてソフトウェア
       でＦＰＵの代わりに実現しているわけで、当然ながら大量の演算を必要と
       する。オーバーフローや有効桁数などに気を付けながら、たとえば1000倍
       の数値として全演算を行ってしまう。
(3)  アセンブラですべてを書き換える。
     →コンパイラよりも、ずっと上手にアセンブラを使える状況でない限り、
       逆に遅くなってしまうことさえある。
(4)  高速なマシンを利用する。
     →当然ながら、今より速くなる。

  他にも方法はあることでしょうが、まぁ、このくらいをあげておきます。

  小手先のテクニックなんぞより、(1) が、大きな効果を生むことでしょう。
すでに数式が極限まで簡略化されており、それでも高速化しなければならない
としたら、小手先のテクニックが有効となります。

----- Takeshi  Shigihara
      Office   cygnus@masternet.or.jp
      Home     cygnus@po.jah.ne.jp -----

テトリスのソースからデジタル信号処理まで変な分野しかしらない。
ようめい＠明治大学です。

> for( j=1 ; j<n ; j++ )
> {
> for(sigma=i=0 ; i<n ; i++) sigma += x[i] * cosTable[(( 2 * i + 1 ) *
>j)%nn] ;
>
> y[j] = nrm * sigma;
> }


式からすると離散コサイン変換（ＤＣＴ）ですよね？
これは離散フーリエ変換（ＤＣＴ）と同じで高速フーリエ変換（ＦＦＴ）を使えば高
速化できたと思います。確かＤＣＴの厚い本によく載っています。

それと、cosTable[]を求めるときも全てのcosを計算するのではなく、z変換を用いて
差分式に変換するのが良いでしょう。最初だけcos()を求めてあとは差分を計算すれ
ば高速でcosTableを求められます。（差分の場合、誤差がでますけれど。）
この辺も、僕が全く理解不能な「デジタル信号処理うんぬん」とか「Ｚ変換うんぬ
ん」とか書いてある本によく載っています。でもこれらの本は理論ばかり書いてあっ
て実際のことはあまり書いてないのでよくわからないです．