Skip to content

Instantly share code, notes, and snippets.

@andreasgrv
Last active November 28, 2017 13:34
Show Gist options
  • Save andreasgrv/0983cda38cd9d7f2678d477e877c5473 to your computer and use it in GitHub Desktop.
Save andreasgrv/0983cda38cd9d7f2678d477e877c5473 to your computer and use it in GitHub Desktop.
Approximation of samples from a normal by summing samples of uniform.How close to the max value of the Box Muller transform (https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform clamp at 6.66 standard deviations when using float32) can we get when using a sum of iid uniform samples ?
Got absmax : 2.6663 after 100 iters and 0.00 secs
Got absmax : 2.8621 after 200 iters and 0.00 secs
Got absmax : 3.0409 after 600 iters and 0.00 secs
Got absmax : 3.3918 after 700 iters and 0.00 secs
Got absmax : 3.3950 after 1000 iters and 0.00 secs
Got absmax : 3.6232 after 1100 iters and 0.00 secs
Got absmax : 3.7237 after 2900 iters and 0.01 secs
Got absmax : 3.8769 after 4200 iters and 0.01 secs
Got absmax : 4.0837 after 13400 iters and 0.04 secs
Got absmax : 4.1979 after 71500 iters and 0.17 secs
Got absmax : 4.4566 after 144800 iters and 0.33 secs
Got absmax : 5.2728 after 189900 iters and 0.43 secs
Got absmax : 5.3970 after 18083700 iters and 39.34 secs
Got absmax : 5.5239 after 27797300 iters and 60.38 secs
Got absmax : 5.8969 after 128032600 iters and 277.47 secs
Got absmax : 6.0791 after 1189764100 iters and 2559.42 secs
Got absmax : 6.3850 after 1217149400 iters and 2617.80 secs
Got absmax : 6.3850 after 20032229900 iters and 42742.40 secs <- still running
from timeit import default_timer as timer
import numpy as np
if __name__ == "__main__":
N_SAMPLES = 169 # how many samples to sum per "normal" approx sample
alpha = np.sqrt(12.)/2. # we want our uniform to have std = 1
BATCH = 100
mx = 0 # max of sum of uniforms seen
i = 1
# Largest value that can be sampled using Box Muller transform
# if using 32 bit floats. # can we reach this with this approx?
THRESH = 6.66
start = timer()
while(mx < THRESH):
samples = np.random.uniform(-alpha, alpha, size=(BATCH, N_SAMPLES))
# abs since we want positive or negative above THRESH
mxe = np.max((1./np.sqrt(N_SAMPLES)) * np.abs(samples.sum(axis=1)))
end = timer()
if mxe > mx:
mx = mxe
s = 'Got absmax : %.4f after %d iters and %.2f secs' % (mx, (i*BATCH), end - start)
print(s)
else:
s = 'Got absmax : %.4f after %d iters and %.2f secs' % (mx, (i*BATCH), end - start)
print(s, end='\r')
i += 1
end = timer()
print('Got absmax : %.4f' % mx, 'after %d iters' % (i*BATCH), 'and %.2f secs' % (end - start))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment