正確なシングルパスペニー計算

Question

部門1..nに割り当てる必要のあるコストCがあります。別の計算では、各部門のシェアが生成されます。これは、小数点以下5桁を超える0〜1の数値です。すべての部門のシェアの合計は正確に1ですが、必ずしも等しいとは限りません。

目標は、各部門に請求する正確なドルとセントを計算することです。法案の合計は、コストCと正確に一致する必要があります。数ペニー未満またはそれ以上にすることはできません。さらに、各部門のシェアは小数ペニーを必要としてはなりません。さらに、最後の部門に残りを単にダンプすることは公平ではありませんが、以前の時間枠を振り返る必要はありません。各部門のシェアをペニーに単純に丸めると、ほとんどの場合、数ペニーのオーバー/アンダーになります。

大雑把に単純化した例：C = 33.34、それぞれが正確に0.2500シェアを持つ4つの部門。 33.34 * 0.25 = 8.335なので、2つの部門が8.33を支払わなければならず、2つが8.34を支払わなければならないことがわかります。 1つの正しい割り当ては、d1 = 8.33、d2 = 8.34、d3 = 8.33、d4 = 8.34です。丸めると、すべての部門が8.34を支払うため、0.02ドルの超過が発生します。これにさらに多くの部門と多くのコストを掛けると、100ドルの差異が生じます。

1パスでこれを行います。つまり、ループしたくないので、0.02だけ離れていることを確認し、再度ループして、値が適切になるまで微調整します。これを1パスで行いたいです。このアルゴリズムに名前があるかどうかも知りたいです。

Answer 1

Perlの場合：

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

use List::AllUtils qw( sum );

print Dumper allocate(10_000, .23, .37, .4);
print Dumper allocate(33.34, .25, .25, .25, .25);
print Dumper allocate(100, 1/3, 1/3, 1/3);

sub allocate {
    my ($C, @shares) = @_;

    my @alloc;

    while ( my $share = shift @shares ) {
        push @alloc, sprintf '%.2f', $C * $share;
        $C -= $alloc[-1];
        my $denom = sum @shares;
        
 Perlの場合：

$VAR1 = [
          '2300.00',
          '3700.00',
          '4000.00'
        ];
$VAR1 = [
          '8.34',
          '8.33',
          '8.34',
          '8.33'
        ];
$VAR1 = [
          '33.33',
          '33.34',
          '33.33'
        ];


出力：

<*> /= $denom for @shares;
    }

    return \@alloc;
}

出力：

<*>

Answer 2

フロートを使用しないでください。固定小数点の10進数を使用するか、スケーリングファクターで除算してドルで値を取得できるようにintを使用します。

決して、決して、決してフロートを使用してお金を計算しません。

Answer 3

「running total」と呼んでいます次のように実装します。

1. 部門＃1が負担するシェアを計算します（丸めエラーが発生する場合があります）
2. ステップ1で計算した金額を第1部に支払います
3. dept＃1とdept＃2が共同で負っている共有を計算します
4. ステップ3で計算した金額から、ステップ2で実際に支払った金額を差し引いて、部門1で支払います。
5. その他depts #s 1、2、および3が共同で負っている金額について

これにより、部門で発生するエラーが最大で1つの丸めエラー（複数の丸めエラーの合計ではない）になり、最終的な合計が正しいことが保証されます。