> On 7/04/2017, at 10:42 AM, Bardur Arantsson <

[hidden email]> wrote:

>

> On 2017-04-07 00:35, Richard A. O'Keefe wrote:

>> For what it's worth, there are rounding algorithms that work on a whole bunch of numbers

>> at once, ensuring that the total of the rounded numbers is equal to the total of the

>> unrounded numbers.

>

> REFERENCES TO LITERATURE, PLEASE!

>

> (I'm not being sarcastic -- this would be very useful to almost anyone

> dealing with monetary amounts... anywhere.)

I first saw mention of such an algorithm in a journal about 40 years ago.

I have a more recent memory of a paper by Knuth in a volume of his

collected papers that I cannot at the moment locate, but I believe this

is the article:

Two-Way Rounding

Author: Donald E. Knuth

Published in:

· Journal

SIAM Journal on Discrete Mathematics archive

Volume 8 Issue 2, May 1995

Pages 281 - 290

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

table of contents doi>10.1137/S0895480194264757

Ah, FOUND IT.

Selected Papers on Design of Algorithms

Donald E. Knuth

CSL Lecture Notes Number 191

CSLI Publications, Stanford, California.

ISBN-13: 978-1-57586-582-9

ISBN-10: 1-57686-582-3

Chapter 16, pp 219-234 "Two-Way Rounding"

"Given n real numbers 0 <= x1 < 1, ..., 0 <= xn < 1,

and a permutation \sigma of {1,...,n}, we can always

find integers x'1 \in {0,1}, ..., x'n \in {0,1}

so that the partial sums x'1+...+x'k and

x'\sigma[1]+...+x'\sigma[k] differ from the

unrounded values x1+...+xk and

x\sigma[1...+x\sigma[k] by at most n/(n+1)

for 1 <= k <= n. The latter bound is the best possible."

Section 1, An Application

"Sometimes it is desirable to round "spreadsheet" data to

larger units while preserving row and column totals and

the grand total."

This application to matrices has been studied by others.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.421.2051&rep=rep1&type=pdfRounding of Sequences and Matrices, with Applications

"We show that any real matrix can be rounded to an integer matrix in

such a way that the rounding errors of all row sums are less than one,

and the rounding errors of all column sums as well as all sums of

consecutive row entries are less than two.

Such roundings can be computed in linear time."

http://people.mpi-inf.mpg.de/~doerr/papers/unbimatround.pdfUnbiased Matrix Rounding

"We show several ways to round a real matrix to an integer one

such that the rounding errors in all rows and columns as well as

the whole matrix are less than one. ... our roundings also have a

rounding error of less than one in all initial intervals of rows

and columns. Consequently, arbitrary intervals have an error of

at most two. ... The same result can be obtained via (dependent)

randomized rounding. This has the additional advantage that the

rounding is unbiased."

Here's a bunch of less formal discussions of the 1D case.

http://stackoverflow.com/questions/32544646/round-vector-of-numerics-to-integer-while-preserving-their-sumhttp://stackoverflow.com/questions/792460/how-to-round-floats-to-integers-while-preserving-their-sumhttps://explainextended.com/2009/09/21/rounding-numbers-preserving-their-sum/https://biostatmatt.com/archives/2902_______________________________________________

Haskell-Cafe mailing list

To (un)subscribe, modify options or view archives go to:

http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.