counter

Visual Basicサンプル

任意精度の計算(多バイト計算:円周率π)


多バイトデータの加減乗除算、逆数、平方根、10進数変換などを行なうモジュール

download mp.NET.zip (VB.Netバージョン)
基数は256。FFTはNUMERICAL RECIPESのfour1による。
download mp4g.NET.zip (VB.Netバージョン)
基数は256。FFTは大浦氏のfft4g_hによる。
download mp4g10.NET.zip (VB.Netバージョン)
基数は10進数、デフォルトで10000。FFTは大浦氏のfft4g_hによる。


以下の機能を備えたVB.Netのモジュールです。ここで「桁」とは基数でまとめて数えるものとします。基数が256の場合「1桁」と「1バイト」は同じになります。基数が10000の場合「1桁」は10進数では4桁になります。詳しくはzipファイルに含まれているドキュメントをご覧ください。



ここまでは、


NUMERICAL RECIPES in C++(英語版)
The Art of Scientific Computing / Second Edition
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery
CAMBRIDGE UNIVERSITY PRESS
ISBN0-521-75033-4


に記載されたC++によるアルゴリズムを移植、ないし参考にしたものです。mp.NET.zipmp4g.NET.zipは、基数が256で10進数ではありませんので、計算結果を表示するために基数変換が必要です。このため、以下の機能が加えてあります。mp4g10.NET.zipには、この機能は不要です。



基数と乗算精度について

これらの演算、変換は、Byte型(1バイト整数)あるいはShort型(2バイト整数)を基にしてコーディングしました。しかし、インテルのIA32アーキテクチャを考えれば、さらに長い4バイトの整数型を使えば演算効率は改善するように思われます。しかし、Byte型やShort型でなければならない理由が、乗算のフーリエ変換で用いる浮動小数点Double型(仮数部53ビット)の精度にあります。


整数データひとつを「桁」と考える、つまり、Byte型なら1バイト(基数256)で1桁、2バイト整数型なら2バイト(基数65536)で1桁と考えることにします。N桁×N桁の乗算では、フーリエ変換の過程で、基数の2乗にNを掛けた数値を正確に浮動小数点型の変数に格納できなければなりません。さらに、計算過程の丸め誤差に備えて、多少(4〜5bit程度)の余裕が必要です。


このようなことを考慮すると、53bitの精度を持つDouble型を用いてフーリエ変換を行なう場合、Byte型で完全な精度で掛け算が可能なのは、基数10で桁数を数えて(普通の10進数で。以下同じ。)10の10乗桁ぐらいまでになります。ところが2バイト整数型を用いる場合は、掛け算可能な桁数が10の6乗桁程度と、大幅に減ってしまいます。さらに、4バイト整数型の場合は、1桁同士の1回の掛け算の結果(最大64bitになり得る)でさえ、Double型に正確に格納することはできません。


このような理由から、まず、256を基数としてByte型を用いたモジュールを用意しました。パーソナルコンピュータ程度であれば精度は事実上無限です。しかし、速度が遅いことが気になるところです。そこで、10進数を基数としてShort型を用いたモジュールを用意しました。基数を10000とした場合、基数が256の場合より数倍速くなります。代わりに、掛け算は400万桁(基数10000)程度、10進数では1600万桁程度までしか安全ではないと思われます。最近のパーソナルコンピュータの速さとメモリ容量をめいっぱい発揮させるためには、基数を1000とするのが最適かもしれません。


乗算のフーリエ変換について

乗算に用いるフーリエ変換は、mp.NET.zipに採用したNUMERICAL RECIPESの場合、長さ1の自明な変換まで分割しています。つまり「基数4」や「基数8」に最適化した変換は用いていません。その点で低速ですが、大変コンパクトなルーチンにまとまっており、教育的には非常に良いものと思います。


「基数4」で最適化されたルーチンを京都大学の大浦氏が公開されているので、移植したものがmp4g.NET.zipmp4g10.NET.zipです。乗算が約3倍高速になっています。その代わり高速フーリエ変換のソースコードは相当に長いものになっています。


改定日 内 容
2004/09/15 高速フーリエ変換を用いた乗算ルーチンの、浮動小数点数から整数への変換を、0.5の加算とMath.Floor関数の組み合わせによる丸め操作をやめて、Visual Basicの組み込み関数Clngによる丸め操作に変更。下記の円周率の計算についてもモジュールの差し替え。比較的短いバイト長(数千から数万バイト)の演算では高速化の効果が大きい。長いバイト長(数十万バイト以上)では効果は小さくなる。
2004/09/16 大浦氏の高速フーリエ変換のルーチンを移植したものを追加。比較的短いバイト長(数千から数万バイト)の演算ではオーバーヘッドが大きく、高速化は目立たない。長いバイト長(数十万バイト以上)で約3倍の高速化を達成。
2004/09/17 基数を10の累乗(最小10、最大10000)としたモジュールを追加。10000とした場合、256よりも2.5倍程度高速。結果を10進数に変換する必要がないので、実効的にはさらに速いと考えられる。

円周率(π)の計算を行なうプロジェクトと実行ファイル

download mppi.NET.zip (VB.Netバージョン)


上述のモジュールを用いて、任意桁数の円周率(π)を求めるコンソール・アプリケーションの例を示します。完備したプロジェクトになっていますので、修正してはコンパイルして、いろいろ試してみてください。また、binフォルダーにコンパイル済み(Release版)のMpPI.exeファイルがありますので、.Net Frameworkさえあれば、とりあえず実行してみることができます。計算結果は、コンソールに表示する以外に、ファイルに保存することもできます。


Borwein兄弟による二次収束のアルゴリズム、上述のNUMERICAL RECIPES in C++に掲載されたプログラムを移植したものです。詳細はdocumentsフォルダーに収められたWordファイルをご覧ください。速さは求めていません。1万桁の計算に866MHzのPentium III M、RAM 392MBで約11秒を要します。10万桁では約450秒になります。この秒数には10進数文字列への変換は含まれていません。桁数が多くなるほど変換が円周率の計算そのものに比べて大きなウェイトを占めるようになります。


ガウス・ルジャンドルのアルゴリズムを用いたプロジェクトも作ってみました。アルゴリズムの名前として、SalaminとBreantによる算術幾何平均(AGM)の公式、とも呼ばれるようです。かなり速くなっています。

download mppiGL.NET.zip (VB.Netバージョン)


1万桁の計算は同じ環境で約8秒、10万桁では約310秒です。やはり10進数文字列への変換は含まれていません。


いずれのアルゴリズムも、同種のプログラムに比べるとかなり低速です。その理由は先にも述べましたが、乗算のルーチンで用いている高速フーリエ変換が、あまり最適化されていない、教育目的のものを用いているためです。


いずれのアルゴリズムでも、100万桁まで同じ結果が得られること、ちゃんと正解であることを確認しました。結果のテキストファイルもzipで固めて提供します。最初の整数部分「3.」で始まって、以下100万桁の小数部「1415.... 」が続きます。ASCII形式で数字以外の文字コードは一切含みませんので解凍後のファイルサイズは1,000,002バイトです。

download mypi1M.zip (計算結果のテキストファイル)


どうしても、Windowsで動く他の円周率計算のプログラムに比べて、速さの見劣りが激しいので、京都大学の大浦氏が作成された高速フーリエ変換のC言語のルーチン(同氏が東京大学在学中に開発されたもの)を移植したところ、3倍高速になりました。大浦氏が「NUMERICAL RECIPES」のルーチンとの速度比を測定された結果をほぼ一致しており、満足しています。.Net Frameworkのマネージコード(C++やC#のポインタを使わないコード)の範囲では、これ以上の高速化は困難かと思われるので、ここで一区切りとします。1万桁の計算は約6秒を要し、それほど速くなっていないように見えますが、オーバーヘッドが目立っているためです。10万桁では約120秒です。念押しですが、10進数文字列への変換は含まれていません。

download mppiGL4g.NET.zip (VB.Netバージョン)


さらにしつこく、基数を10進数ベースとするように改良しました。デフォルトで10000としたところ2.5倍程度速くなりました。1〜1.5万桁で約4〜5秒、10〜12万桁で約60秒となっています。10進数ベースなので基数変換の処理は不要です。したがって上記の基数256のものに比べて、実効的にはさらに高速と言えます。

download mppiGL4g10.NET.zip (VB.Netバージョン)