# Input

Integer $$\n > 1\$$

# Output

Ten 64 bit floating point numbers between $$\-n\$$ and $$\n\$$, inclusive, whose sum is the least accurate.

# Details and examples.

These examples are not claimed to be optimal.

You should compute the sum by adding from the left in the standard way. That is something equivalent to:

def summation(arr):
s = 0.0
for number in arr:
s += number
return s


Let us take $$\n = 5\$$. If we set

arr = [4.3493796784913545, 3.2747531416897555, 4.71214376118673,
3.4576694043748524, 2.1095432625442436,4.1930918879466414,
4.655820988880924,3.963317721412073,1.741782502464112,
2.4878467468497014]


the absolute difference between the true sum of arr and summation(arr) is 1.4210854715202004e-14

Let us take $$\n = 50\$$. If we set

arr = [-43.935697899733654, -20.806237147982237,
-42.89988984590284,-48.297453753937226,
-21.681676863344716,-35.08820277346858,
-35.68720096633298,-44.75778960194057,
-42.38178899301877,-36.76765210663521]


the absolute difference between the true sum of arr and summation(arr) is 1.7053025658242404e-13.

Let us take $$\n = 500\$$. If we set

arr = [362.9079020899155,
435.66223234982647, 451.79491575664764,
337.92343925762145, 342.71383494046484,
193.03803553674948, 445.01116265158157,
-32.1151835637149, 72.74845296300403,
21.538615141686755]


the absolute difference between the true sum of arr and summation(arr) is 1.3642420526593924e-12.

# Scoring

Your score will be the absolute difference between the sum of the array you compute and the true sum for $$\n = 5000\$$. Larger scores are better.

Python has math.fsum() which will do exact summation.

• Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Code Golf Meta, or in Code Golf Chat. Comments continuing discussion may be removed. Commented Jun 26 at 23:13

# Rust, score $$\\frac{24}{2^{40}}\$$≈2.1827872842550278e-11

fn f(n: u32) -> [f64; 10] {
let a = n as f64;
let b = f64::to_bits(a);
let mut s: f64 = 0.;
std::array::from_fn(|_| {
let v = (0..).map(|i|f64::from_bits(b-i)).take_while(|j|s+j==s+a).last().unwrap();
s+=a;
v
})
}


Try it on the Rust Playground

• [Brute-forced range in $\left[N-6\epsilon,N\right]$ and this is optimal](gcc.godbolt.org/z/zehdsz6vv)
– l4m2
Commented Jun 21 at 6:48
• Is this code still optimal if the array length is changed?
– Simd
Commented Jun 21 at 8:05
• @Simd this should be length-agnostic.
– att
Commented Jun 23 at 6:52

# Python, Score: 1.9099388737231493e-11 2.1827872842550278e-11

Credit to @att and @Neil who got the correct optimal solution before me, and who's code looks much nicer than mine

import struct

def float_to_bitstring(f):
s = struct.pack('>d', f)
i = struct.unpack('>q', s)[0]
return bin(i)[2:].zfill(64)

def greedy(max_n, arr):
n_bitstr = float_to_bitstring(max_n)
sum_bitstr = float_to_bitstring(sum(arr)+max_n)
n_exp = int(n_bitstr[1:12],2)
sum_exp = int(sum_bitstr[1:12],2)
dif = sum_exp - n_exp
exp = n_exp
mant = int(n_bitstr[12:], 2)
desired_end = int('1'+(dif-1)*'0', 2)
if mant >= desired_end:
exp = bin(exp)[2:].zfill(11)
mant -= desired_end
mant -= mant % (2 * desired_end)
mant += desired_end
mant = bin(mant)[2:].zfill(52)
else:
exp = bin(exp-1)[2:].zfill(11)
mant = bin(desired_end)[2:].rjust(52, '1')
return struct.unpack('>d', struct.pack('>q', int(exp + mant, 2)))[0]

def func(n):
arr = [n]
for i in range(9):
arr.append(greedy(n, arr))
return arr


Try it online!

Defines a function func which takes input n and outputs the desired list of floats. Note that floats are natively 64 bit in python.

Output for n=5000 is [5000, 4999.999999999999, 4999.999999999999, 4999.999999999998, 4999.999999999998, 4999.999999999998, 4999.999999999996, 4999.999999999996, 4999.999999999996, 4999.999999999996]

### Explanation

Floating point addition accumulates error through rounding. The most this rounding can ever be off by is one power of 2 less than the least significant bit of the resulting sum. It's not too complicated to construct a number which will accumulate that maximum error, in fact there are many such numbers, so specifically we want to construct the largest such number. This is because as our sum gets larger we can round off larger numbers. In this way this is a sort of greedy algorithm.

• I don't think adding a negative number is ever optimal in this challenge since we always want our error to accumulate in the same direction, and a bigger overall number leads to bigger errors.
• Please pay no mind to this very dirty python code.
• Edit: In my haste I neglected to account for the fact that the sum gets bigger when you add to it. A simple fix which brings my answer into a tie with the others.
• Do you know why this isn't quite as good as the other answer?
– Simd
Commented Jun 21 at 9:17
• I see now, I'm only looking at the best error for the current sum, but I should be looking at the best error for the result of the next sum Commented Jun 21 at 13:48

# Python 3, score 2.1827872842550278e-11

from fractions import Fraction

def error(i):
return float(Fraction(sum(i)) - sum(map(Fraction, i)))

def inaccurate(n):
e = .5 ** 55
while n - e == n: e *= 2
i = [n]
for _ in range(9):
j = i + [n - e * 2]
i = i + [n - e]
if error(j) > error(i): e *= 2; i = j
return i


Try it online!

• Should this work for different length arrays as well?
– Simd
Commented Jun 21 at 10:42
• @Simd I don't see why not; I didn't write it with a specific length in mind.
– Neil
Commented Jun 21 at 11:44