Created
October 9, 2022 17:37
-
-
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%.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 ); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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