Hundredsoft

多桁の除算や平方根計算を実装したサンプルの16進・２進・10進電卓です。
整数だけですがおよそ100万桁まで計算できます。




乗算は、実数FFTとKaratsuba法を組み合わせています。
この内、実数FFTには、京大の大浦博士のDFTコード(fftsg.c)の一部をFPU化して使っています。
VC++だと拡張倍精度の long double が使えないため、できるだけFPUを使って精度を高めています。
精度が上がると一度に乗算できる桁数が上がり、応答性が向上します。
このときの精度については 「(*1)FFT多倍長乗算器のVLSI設計」 を参考に、最大値どうしの乗算が最大の誤差を与えると仮定し、１度に行えるFFT乗算桁数を決定しています。
また、２進→１０進変換にもFFT乗算が必要になります。
これには神奈川工科大学 平山博士の「(*2)分割統治法による多倍長演算の高速化」を参考にしました。


(*1) 矢崎俊志, 阿部公輝: 「FFT 多倍長乗算器のVLSI 設計」, 日本応用数理学会論文誌, Vol.15, No.3, pp.385-401 (2005-9)

(*2) 平山弘: 「分割統治法による多倍長演算の高速化 (数式処理における理論と応用の研究)」, 数理解析研究所講究録 (2000), 1138: 247-255

---

Tags: プログラムメモ