Last active
November 28, 2017 13:34
-
-
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 ?
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
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 |
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
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