About the Series
First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.
Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.
Hole 2: Numbers from a Normal Distribution
I can't believe this hasn't been done yet! You're to generate random numbers, drawing from a normal distribution. Some rules (the majority of them are probably automatically covered by most submission, but some of them are in place to ensure consistency of results between vastly different languages):
You should take two non-negative integers as input: a seed
Sand the amount
Nof numbers to return. The output should be a list of
Nfloating point numbers, drawn from a normal distribution with mean 0 and variance 1. Whenever your submission is given the same seed
Sit should produce the same number. In particular, if it is called once with
(S, N1)and once with
(S, N2), the first
min(N1, N2)entries of the two outputs should be identical. In addition, at least 216 different values of
Sshould produce different sequences.
You may use any built-in random number generator that is documented to draw numbers from an (approximately) uniform distribution, provided you can pass
Son to it and it supports at least 216 different seeds. If you do, the RNG should be able to return at least 220 different values for any given number you request from it.
- If your available uniform RNG has a smaller range, is not seedable, or supports too few seeds, you must either first build a uniform RNG with a sufficiently large range on top of the built-in one or you must implement your own suitable RNG using the seed. This page may be helpful for that.
- If you don't implement an established algorithm for generating normal distributions, please include a proof of correctness. In either case, the algorithm you choose must yield a theoretically exact normal distribution (barring limitations of the underlying PRNG or limited-precision data types).
- Your implementation should use and return either floating-point numbers (at least 32 bits wide) or fixed-point numbers (at least 24 bits wide) and all arithmetic operations should make use of the full width of the chosen type.
- You must not use any built-in functions directly related to normal distribution or Gaussian integrals, like the Error function or its inverse.
You may write a full program or a function and take input via STDIN, command-line argument, function argument or prompt and produce output via return value or by printing to STDOUT (or closest alternative).
N will be non-negative integers, each less than 220. Output may be in any convenient, unambiguous list or string format.
This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.
To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:
# Language Name, N bytes
N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)