Skip to content

Instantly share code, notes, and snippets.

@kennytm
Created June 13, 2011 13:49
Show Gist options
  • Save kennytm/1022794 to your computer and use it in GitHub Desktop.
Save kennytm/1022794 to your computer and use it in GitHub Desktop.
Interval arithmetic test.
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)
+/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment