Interval arithmetic test.

gistfile1.d

import std.typecons, std.algorithm, std.conv, std.stdio;

ulong getMask(ulong v) {
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v |= v >> 32;
    return v;
}

struct SignExtendedNumber {
    ulong value;
    alias value this;
}

struct IntRange {
    SignExtendedNumber imin, imax;

    string toString() const {
        return text("[", imin.value, ", ", imax.value, "]");
    }

    void unionWith(IntRange other) {
        if (imin.value > other.imin.value)
            imin.value = other.imin.value;
        if (imax.value < other.imax.value)
            imax.value = other.imax.value;
    }
}
alias ulong uinteger_t;

IntRange theAlgorithm(IntRange a, IntRange b)
{
    // Replace this
    uinteger_t aDiffMask = getMask(a.imin.value ^ a.imax.value);
    uinteger_t bDiffMask = getMask(b.imin.value ^ b.imax.value);
    IntRange result;
    result.imin.value = (a.imin.value ^ b.imin.value) & ~(aDiffMask | bDiffMask);
    result.imax.value = (a.imax.value ^ b.imax.value) | (aDiffMask | bDiffMask);
    return result;
}

IntRange[ulong] cached;
IntRange bruteForce(IntRange a, ulong b) {
    if (auto ptr = b in cached)
        return *ptr;
    IntRange r;
    r.imin.value = r.imax.value = a.imax.value ^ b;    // <--
    foreach (c; a.imin.value .. a.imax.value) {
        auto d = c ^ b;                 // <--
        r.unionWith(IntRange(SignExtendedNumber(d), SignExtendedNumber(d)));
    }
    cached[b] = r;
    return r;
}
IntRange bruteForce(IntRange a, IntRange b) {
    auto r = bruteForce(a, b.imax.value);
    foreach (d; b.imin.value .. b.imax.value)
        r.unionWith(bruteForce(a, d));
    return r;
}

void assertContains(IntRange estimated, IntRange exact, IntRange a, IntRange b) {
    assert(estimated.imin.value <= exact.imin.value && estimated.imax.value >= exact.imax.value,
           text(estimated, " does not contain ", exact, " = ", a, " * ", b));
}

void main() {
    uint exactCount = 0, totalCount = 0;

    // it takes 5 minutes to compute limit = 128, 10 seconds to compute 64.
    ulong limit = 64;

    foreach (aLow; 0 .. limit)
    foreach (aHi; aLow .. limit) {
        cached = null;
        foreach (bLow; aLow .. limit)
        foreach (bHi; bLow .. limit) {
            auto a = IntRange(SignExtendedNumber(aLow), SignExtendedNumber(aHi));
            auto b = IntRange(SignExtendedNumber(bLow), SignExtendedNumber(bHi));

            auto exact = bruteForce(a, b);
            auto estimated = theAlgorithm(a, b);

            assertContains(estimated, exact, a, b);
            if (estimated == exact)
                exactCount ++;
            else {
                //writeln(a, " * ", b, " = ", exact, " not ", estimated);
            }
            totalCount ++;
        }
    }

    writeln(100.0*exactCount/totalCount, "% (", exactCount, "/", totalCount, ")");
}

/+
Precision of '&' w.r.t. the number of bits:
 1 = 100%     (7/7)
 2 = 96.9231% (63/65)
 3 = 92.4%    (693/750)
 4 = 88.4154% (8838/9996)
 5 = 85.5994% (124215/145112)
 6 = 83.8136% (1850538/2207920)

Precision of '|' w.r.t. the number of bits:
 1 = 100%     (7/7)
 2 = 98.4615% (64/65)
 3 = 96.5333% (724/750)
 4 = 94.3577% (9432/9996)
 5 = 92.5244% (134264/145112)
 6 = 91.2318% (2014325/2207920)

Precision of '^' w.r.t. the number of bits:
 1 = 100%     (7/7)
 2 = 89.2308% (58/65)
 3 = 79.2%    (594/750)
 4 = 72.9892% (7296/9996)
 5 = 69.7447% (101208/145112)
 6 = 68.1575% (1504864/2207920)
+/