N 個の整数があるとします。ここで、N は巨大になる可能性がありますが、各 int は 0 からキャップ M の間であることが保証されています。ここで、M は符号付き 32 ビット フィールドに簡単に収まります。
これらの N 個の整数の平均を計算したい場合、それらすべてを同じ符号付き 32 ビット空間で常に合計および除算することはできません。N が大きすぎると、分子がオーバーフローする危険性があります。この問題の 1 つの解決策は、計算に 64 ビット フィールドを使用してより大きな N を保持することですが、この解決策はスケーリングしません。代わりに M が大きな 64 ビット整数である場合、同じ問題が発生します。
同じビット空間で正の整数のリストの平均を計算できるアルゴリズム (できれば O(N)) を知っている人はいますか? 2 つの整数を使用してより大きな整数をシミュレートするような安価なことはしません。