16
\$\begingroup\$

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.

\$\endgroup\$
1

3 Answers 3

10
\$\begingroup\$

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

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

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.

Additional notes:

  • 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.
\$\endgroup\$
2
  • \$\begingroup\$ Do you know why this isn't quite as good as the other answer? \$\endgroup\$
    – Simd
    Commented Jun 21 at 9:17
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Commented Jun 21 at 13:48
4
\$\begingroup\$

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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.