たくさんの数の平均を求める方法について

どうもこんにちは
研究でシミュレート用のプログラムを書いています

大量の数を入力し、その平均値を求めるコードを書いているのですが、
誤差ができるだけ小さくなる方法はないでしょうか
入力する数はdouble型の実数値あるいはint型の整数値で、
個数は1億程度です。
最初は1つずつ足していたのですが、整数型の場合はオーバーフローしてしまい、実数型の場合も徐々に加算する値が相対的に小さくなり、誤差が大きくなっていきました。
100万個ずつに区切って平均を求め、それを後で合計する方法も考えましたが、あまりきれいな方法になりません

なにかいい方法はないでしょうか

No.4 回答者： usokoku 回答日時： 2009/10/04 17:31

２番です。

３番の方の「情報落ち」の意味で「桁落ち」という言葉を使っています。

加算だけならば、整数の固定長100桁１０進演算専用ライブラリをご自身で作っても、半日ぐらいでできるでしょう。１０進ですとそのままテキストかできますので、計算時間が多少かかってもよい場合(せいぜい１０回程度しか使わないで捨てるソフト)なら、考慮の対象に入れてもよいでしょう。

この回答への補足

計算時間が多少かかるのは避けたいのです。

補足日時：2009/10/04 21:25

この回答へのお礼

締め切りました。

お礼日時：2010/05/12 21:59

No.2 回答者： usokoku 回答日時： 2009/10/03 16:45

C言語での変数の書式を知らないので、変なことを書いている場合があります。

ひとつの場合は、指数部が存在しない変数の場合には、
求めた和を保存する配列を作っておいて、
値を加える前の数値を保存しておいて、オーバーフローの割り込みが発生したときに、それまでの値を配列に保存します。そして加える値を最初の値として計算して行きます。
最後の計算として、配列の値を2のn乗で割って、オーバーフローしない桁に直して足します。

もうひとつの場合、指数部が存在する場合には、
求めた和を保存する配列を複数個作っておいて、
指数部が同じ値同士をたして行きます。指数部で桁落ちが発生するような状態になったときに、配列に保存します。
桁落ちの発生する範囲が指数部の値によって異なりますので、指数部の値によって配列を変える必要があります。ただ、この指数部の範囲が大きく変わるような状態での和を求めることは、「平均値」と呼べるものではなくなってしまう可能性が大きいです。

別法としては、指数部の持たない整数等に型変換をして、指数部が存在しない方法で計算して行く方法があります。

MS-DOSの時代ですと、多倍精度演算が各種公開されていました。当時の公開ライブラリを探すとよいものがあるかもしれません。また、多倍精度演算専用言語もあるようです。
http://search.yahoo.co.jp/search?p=%E5%A4%9A%E5% …
http://www.vector.co.jp/vpack/filearea/dos/prog/c/
どのような言語系をお使いかわかりませんが、ちょっと手直しをする程度で使えるはずです。

この回答への補足

計算量が極端に多くなる処理は使えないのです。
変数もintやdoubleなど基本のものしか使えません。
すいません。

補足日時：2009/10/04 21:23

この回答へのお礼

締め切りました。

お礼日時：2010/05/12 21:58

No.1 回答者： episteme 回答日時： 2009/10/03 16:21

処理系によっては倍長(たいてい64bit)整数をサポートしています。

# long long とか __int64 とか

この回答への補足

int64 は使用できないのです。

補足日時：2009/10/04 21:22

この回答へのお礼

締め切りました。

お礼日時：2010/05/12 21:58