Here's C++ code. The key is the linear-time selection implemented by nth_element. (This code is untested.) vector<int> quant(const vector<double> &x, int goalsum) { vector<pair<double, int>> a(x.size()) ; // [i] -> (fractionalpart, index) vector<int> r(x.size()) ; size_t total_error = (size_t)goalsum ; for (size_t i=0; i<x.size(); i++) { int f = (int)floor(x[i]*goalsum) ; r[i] = f ; a[i] = make_pair(f-x[i], i) ; total_error -= f ; } nth_element(a.begin(), a.begin()+total_error, a.end()) ; for (size_t i=0; i<total_error; i++) r[a[i].second]++ ; return r ; } On Tue, Feb 2, 2016 at 5:13 PM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 2, 2016, at 7:53 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Is the MMA algorithm a faithful implementation of Conway and Sloane's algorithm?
The MMA algorithm is O(n log n) due to Ordering[], but there's a well-known linear-time algorithm; certainly Conway and Sloane's algorithm is linear-time?
-tom
from C&S: "The only substantial amount of computation needed is for the sort in Step 3, which takes O(n log n) steps"
My Mma code is doing pretty much exactly what I subsequently saw in your beautifully terse description:
"round, determine total error (say, +e), "e" values to round the other way selecting those with the least individual error”.
How do you identify the “e” elements with least individual error without doing a sort?
-Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --