Rounding of complementary percentages

round_percents.js

/*!
 * Given a set of numeric values, returns a set of integer percents
 * 
 * Algorithm defined by Rahul Narain, translated to JavaScript.
 * http://math.stackexchange.com/questions/183476/rounding-of-complementary-percentages#186225
 *
 * > round_percents([20.5, 79.5])
 * [21, 79]
 * > round_percents([24.8, 25.2, 0.5, 49.5])
 * [25, 25, 1, 49]
 * > round_percents([3518,3843,5959,6843,3843816,384384,38438])
 * [0, 0, 0, 0, 90, 9, 1]
 */
function round_percents (values) {
	var n = values.length;
	var sum = 0;
	var s = 100;
	var i = 0;
	var p = new Array(n);
	var q = new Array(n);
	var r = new Array(n);
	var k = 0;
	var deservingIndex = 0;
	
	for (i = 0; i < n; i++) {
		sum += values[i];
	}
	// You have n values p1,p2,…,pn which add up to an integer sum s
	// You have n values p1,p2,…,pn
	// You can divide each of them into integral and fractional parts p[i]=q[i]+r[i], where q[i] is an integer and r[i] is a real number in (0,1).
	for (i = 0; i < n; i++) {
		p[i] = s * (values[i] / sum);
		q[i] = Math.floor(p[i]);
		r[i] = p[i] - q[i];
	}
	
	// Clearly r1+r2+⋯+rn must be an integer, say k.
	// The rounded form of each value is either qi or qi+1; that is, we will replace each ri with either zero or one.
	// We are allowed only k ones. 
	for (i = 0; i < n; i++) {
		k += r[i];
	}
	k = Math.round(k);
	
	// A natural way to do this is to define some function f which tells how much each value "deserves" a one.
	while (k > 0) {
		deservingIndex = 0;
		for (i = 0; i < n; i++) {
			if (boostLowValues(i) > boostLowValues(deservingIndex)) {
				deservingIndex = i;
			}
		}
		for (i = 0; i < n; i++) {
			if (largestFraction(i) > largestFraction(deservingIndex)) {
				deservingIndex = i;
			}
		}
		q[deservingIndex] += 1; // give a k
		r[deservingIndex] = 0;  // don't use this remainder again
		k--;
	}
	return q;

	// If you wanted to treat all values equally, you would set f = r[i].
	// For example, if you had values 33.3%, 33.3%, and 33.4%, then k=0.3+0.3+0.4=1, and the values of f are 0.3, 0.3, and 0.4, so you round as 33%, 33%, and 34%.
	function largestFraction (i) {
		return r[i];
	}
	// If you want to give low values a boost, you could try f = r[i] + (s − p[i]) / s.
	// Then a value of, say, 2.xx% need only be at least 2.02% to beat 50.5% and 90.9% in the Who Wants to Be Rounded Up competition
	// .02 + (100 - 2.02) / 100 = .02 + .9798 = .9998
	// .50 + (100 - 50.5) / 100 = .50 + .4850 = .9850
	// .90 + (100 - 90.9) / 100 = .90 + .0890 = .9890
	function boostLowValues (i) {
		return r[i] + (s - p[i]) / s;
	}
}