Skip to content

Instantly share code, notes, and snippets.

@ibarland
Created October 9, 2022 17:37
Show Gist options
  • Save ibarland/5fdb7a78b37aac678c0b4c3b8b6e2207 to your computer and use it in GitHub Desktop.
Save ibarland/5fdb7a78b37aac678c0b4c3b8b6e2207 to your computer and use it in GitHub Desktop.
Q: What % of randomly-chosen doubles in [0,1) aren't associative (x+y+z != z+x+y e.g.). A: About 15%.
import java.util.*;
class AdditionNotAssociative {
static int M = 6; // 3! orderings to add x,y,z
static int[] errsForPermutation = new int[M]; // Global
static int N = 1000;
static String N_LEN_SPEC = "%" + Integer.toString(N).length() + "d";
static Random rng = new Random(0);
static int VERBOSE = 3;
public static void main( String... args ) {
for (int i=0; i<N; ++i) {
checkAssociativity(i, rng.nextDouble(), rng.nextDouble(), rng.nextDouble() );
}
if (VERBOSE > 2) System.out.printf("\n");
// report results:
int totalDiscrepancies=0;
for (int i=1; i<M; ++i) {
totalDiscrepancies += errsForPermutation[i];
if (VERBOSE > 1) System.out.printf("perm %1d: %4.1f%% non-associative ("+N_LEN_SPEC+"/"+N_LEN_SPEC+")\n",
i, 100.0*errsForPermutation[i]/N, errsForPermutation[i], N );
}
if (VERBOSE > 1) System.out.printf(" ----- ---- ----\n");
if (VERBOSE > 0) System.out.printf("total: %4.1f%% non-associative ("+N_LEN_SPEC+"/"+N_LEN_SPEC+")\n",
100.0*totalDiscrepancies/((M-1)*N), totalDiscrepancies, (M-1)*N );
}
static void checkAssociativity( int i, double x, double y, double z ) {
//checkOneOrdering(i,0, x,y,z, x,y,z); // pointless, 'course.
checkOneOrdering(i,1, x,y,z, x,z,y);
checkOneOrdering(i,2, x,y,z, y,x,z);
checkOneOrdering(i,3, x,y,z, y,z,x);
checkOneOrdering(i,4, x,y,z, z,x,y);
checkOneOrdering(i,5, x,y,z, z,y,x);
}
static void checkOneOrdering( int i, int j,
double x0, double y0, double z0,
double x1, double y1, double z1 ) {
double sum0 = x0+y0+z0;
double sum1 = x1+y1+z1;
if (sum0 != sum1) {
if (VERBOSE > 2) System.out.printf(" sample#"+N_LEN_SPEC+" perm %1d: %f+%f+%f == %g != %g == %f+%f+%f (difference %g).\n",
i,j, x0,y0,z0,sum0, sum1,x1,y1,z1, Math.abs(sum1-sum0) );
++errsForPermutation[j];
}
}
}
import java.util.*;
class AddNotAssoc {
public static void main( String... args ) {
int N = 1000;
int errs=0;
Random rng = new Random(0);
double x,y,z;
for (int i=0; i<N; ++i) {
x = rng.nextDouble();
y = rng.nextDouble();
z = rng.nextDouble();
if (x+y+z != x+z+y) { ++errs; System.out.printf(" sample#%6d: %f,%f,%f\n", i, x,z,y); }
if (x+y+z != y+x+z) { ++errs; System.out.printf(" sample#%6d: %f,%f,%f\n", i, y,x,z); }
if (x+y+z != y+z+x) { ++errs; System.out.printf(" sample#%6d: %f,%f,%f\n", i, y,z,x); }
if (x+y+z != z+x+y) { ++errs; System.out.printf(" sample#%6d: %f,%f,%f\n", i, z,y,x); }
if (x+y+z != z+y+x) { ++errs; System.out.printf(" sample#%6d: %f,%f,%f\n", i, z,x,y); }
// NOTE: yes, the same triple can count as multiple `errs`.
// But that's arguably correct, as they are three distinct tuples that might each arise.
}
System.out.printf("%4.1f%% non-associative (%d/%d)\n", 100.0*errs/(5*N), errs, 5*N );
}
}
import java.util.*;
class AddNotAssocIndependent {
public static void main( String... args ) {
int N = 1000;
int errs=0;
Random rng = new Random(0);
double x,y,z;
for (int i=0; i<N; ++i) {
x = rng.nextDouble();
y = rng.nextDouble();
z = rng.nextDouble();
if ( x+y+z != x+z+y
|| x+y+z != y+x+z
|| x+y+z != y+z+x
|| x+y+z != z+x+y
|| x+y+z != z+y+x) {
++errs;
System.out.printf(" sample#%6d: %f,%f,%f\n", i, z,x,y);
}
}
System.out.printf("%4.1f%% non-associative (%d/%d)\n", 100.0*errs/N, errs, N );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment