|
|
●概要 乗算が高速化されれば、除算の高速化となるが、高速除算は、一般には、逆数法が用いられる。つまり、A / B は、A * (1 / B) とするのである。これは、FFT乗算が可能な環境で、且つ逆数を高速に求められることが前提となる。 ●逆数演算基本原理 ニュートン法で求めるのが普通。 y = x-1 - a とおくと、漸化式は、 xn+1 = 2 * xn - a * xn2 となる。幸い、漸化式に除算が含まれないので、FFT乗算と、加減算で実現できる。2 * xn は、多倍長*Integer で行い、a * xn2 を、二回のFFT乗算で行う。 実際にニュートン法で逆数を求めて確認した。 ●ニュートン漸化式 ニュートン法の原理は専門書に依られたい。逆数を求めるニュートン法には、高次収束もあり、どの方法が適しているかを検討する。 ○基本式 Xn+1 = 2 * Xn - A * Xn2 である。二次収束と言うべきか。ループごとに初期値精度の倍づつ、精度が向上する。つまり、15桁であれば、30、60、120・・・などとなる。 収束を見るには、上式を変形する。 d = 1 - A * Xn と置けば、 Xn+1 = Xn * ( 1 + d) となり、d がいかに 0 に近づくかの問題となる。演算では、d の指数部を収束判定に使用する。 ○高次収束 上記は、2次収束と呼ばれるが、3次から5次などの収束もある。次数倍づつ精度があがるので、良さそうに見えるが、実際には、収束回数が減った分、演算数が増加するので、ほぼチャラとなってしまう。つまり、回数 * 演算数 = ほぼ同じ になる。今回は、2次収束とした。 ●初期値 初期値は何でも良いと言う訳ではなく、その後収束を決定付ける大切な要素である。多倍長の場合は、一般には、CPUネイティブ除算で、逆数を求め初期値にする。.NET の場合は、Double による初期値なので、15桁程度の精度となる。一般に、初期値の精度の次数倍づつ精度が上がるとされている。 今回、技術的な検討をした結果、多段初期値方式(例によって筆者の勝手な命名)とした。 ●演算方法 基本逆数方式(初期値がDouble)と多段初期値方式について、その演算方法を紹介する。
|