Fre00042 ＦＦＴによる乗算アルゴリズムってどんなんです？

#0000 sci1003  8808070116

最近πを２億桁以上計算するアルゴリズムが話題になりましたが，その中で
ＦＦＴ（高速フーリエ変換）を使った多倍長数の乗算が行われているそうで
すね．興味があったので，昔の教科書などを引っ張り出してみましたが，Ｆ
ＦＴはスペクトル解析を高速に行う，くらいのことしか書いてありません．

たぶん，２つの多倍長数を｛ａn｝，｛ｂn｝という信号列とみなして，各々
フーリエ変換して｛Ａk｝，｛Ｂk｝を作り，｛Ａｋ・Ｂk｝を逆フーリエ変換
してやるのではないか，と単純に考えたのですが，それでは得られる結果は
ａnとｂnのコンボリューション（たたみ込み）に相当するものになってしま
う気がします．

いったい，ＦＦＴを利用した乗算とは，どのようなアルゴリズムなのか，そ
のよい参考文献などご存じの方がいらしたら，教えてくださいまし．

sci1003　RUKAS




#0001 sci1599  8809242254


ＦＦＴを利用した乗算フログラムの概略は、
ｂｉｔ　１９８８年１０月号にあります。
たぶん蛇足でしょうが、レスポンスが他に無いので、
念のため。　ＯＫＡＤＡ




#0002 sci1003  8809250130


わっ，ＯＫＡＤＡさん，どうもありがとうございます．１０月号というと，いま
出てるやつですね．さっそく明日買ってこなくちゃ．
それにしても，自分でも忘れていた基調発言によくぞ目を止めていただきまして，
ありがたや，ありがたや．．．

RUKAS