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

質問

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

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

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

回答No.3

Tacosan · ベストアンサー

情報落ちを避ける方法は存在します.
誰が考案した方法なんだったっけ....

参考URL：

http://www.cc.kyoto-su.ac.jp/~yamada/pB/float.html#johouot

お礼

回答ありがとうございます。

この処理も試してみようと思います。
桁数に極端な差がある場合は厳しいかもしれませんが。。。

回答No.2

usokoku

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

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

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

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

MS-DOSの時代ですと、多倍精度演算が各種公開されていました。当時の公開ライブラリを探すとよいものがあるかもしれません。また、多倍精度演算専用言語もあるようです。
http://search.yahoo.co.jp/search?p=%E5%A4%9A%E5%80%8D%E7%B2%BE%E5%BA%A6%E6%BC%94%E7%AE%97%E3%80%80%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA&search.x=1&fr=top_ga1_sa&tid=top_ga1_sa&ei=UTF-8&aq=&oq=
http://www.vector.co.jp/vpack/filearea/dos/prog/c/
どのような言語系をお使いかわかりませんが、ちょっと手直しをする程度で使えるはずです。

お礼

締め切りました。

補足

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

回答No.1

επιστημη（@episteme）

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

お礼

締め切りました。

補足

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