My problem is due to the fact that I am manipulating a set of amounts that span over some intervals of time (start date/end date) and that are rounded to cents. I have to multiply each of them by some fraction (percentage), and I have to round the results to cents. Then I have to match the sum of what I calculated to the total amount (the sum of all chunks) multiplied by the same fraction (to make sure that precision loss didn't cause a lot of damage to the "big picture"), and if I have an error, I put it into the last (or first?) calculated value. Then I have to "balance" all the amounts for every start date I have (and, probably, for an end date too).
Example: $A_i$ is a monetary amount that is associated to a date $D_i$, $i\in [1, n]\subset\mathbb{N}$. I need to calculate commissions for every amount. I know the commission rate $cr$. Every commission amount should be rounded. So, I have $n$ commission amounts $CA_i$. The problem is that after rounding off the amounts, I get that ($\lceil x\rceil$ is the rounded value of $x$ in what follows): $$\sum_{i=1}^n \lceil A_i*cr\rceil \neq \left\lceil\biggl(\sum_{i=1}^n A_i\biggr)*cr\right\rceil$$
Let's assume that I correct this error by adding the difference to $AC_n$. Now, I might have another problem: let $\{d_j\}_{1\leq j\leq m}$ be the set of all (distinct) dates $D_i$. So, I have that $$\sum_{k=1}^? \lceil B_k cr\rceil \neq \left\lceil\biggl(\sum_{k=1}^? B_k\biggr)*cr\right\rceil$$ where $B_k = \{A_i \text{ such that } D_i = d\}$, for some date $d\in \{d_k\}$. In other words, if I group the rounded results by date, there will still be an error compared to the total commission for this date. So, I should balance across every date (not forgetting about the total amount!)
This balancing is a very intuition-based approach, which might work or not. I've been looking for some formalization on the internet, but All I got was either the classic numerical analysis (after some brief introduction to floating point representation errors and rounding errors, it immediately goes to linear equations etc.) or just "Don't use floating point to represent money" articles. Are there any accessible sources on the specific topic of monetary calculations?
Asked By : Igor
Answered By : Yuval Filmus
Let me illustrate one problem which could happen, and one way to solve it. You want to distribute a given amount of cents $N$ into $k$ piles, in proportions $p_1,\ldots,p_k$, where $p_1,\ldots,p_k \geq 0$ and $p_1 + \cdots + p_k = 1$. The problem is that $Np_i$ need not be an integer. As a simple example, you might want to divide $20$ cents into $1/3:2/3$ proportions. The fractional solution is $$ 6\frac{2}{3}:13\frac{1}{3}. $$ It seems fair to round this to $7:13$ since $2/3 > 1/3$. More generally, compute $m_i = \lfloor N p_i \rfloor$ and $r_i = Np_i - m_i$. Here $m_i$ is the initial allocation and $r_i$ is the fractional one that you want to round. You need to add up some amount $R = N - \sum_i m_i$ of cents to make the total exactly $N$. Sort the $r_i$ in non-increasing order, and give one cent to the first $R$ parts according to this order (break ties arbitrarily). This is just a generalization of the example above.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47165
0 comments:
Post a Comment
Let us know your responses and feedback