random numbers API

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

random numbers API

Florian Bösch
Motivation: Web Applications enter the arena of interactive content creation/consumption (games, productivity software, etc.). A good PRNG would be desirable in many situations.

Web Applications that desire to use random numbers have a 4 problems with the existing Math.random function.

1) The implementation is not "high quality" in that the generated random numbers tend to be statistically poor compared to other higher quality PRNGs.

2) The API does not support seeding whereas the same sequence of random numbers can be generated twice if so desired.

3) It is based on floating points which due to machine differences even in the presence of seeding could generate different numbers.

4) Alternative implementations in JS suffer even in the presence of sophisticated JITing VMs from the fact that mathematics is done in doubles (in the case of addition, subtraction, division and multiplication) and by converting double -> int -> double (in the case of bitshifts and modulo division). This makes it both harder to implement a reliable PRNG and it makes it slow.

I would propose an alternative native code random number API that has the following characteristic:

- The returned value is based on integers ranging from 0 up to a specified limit.
- It is initializable with a seed
- It makes a guarantee that no matter on what machine the random number is generated, that the sequence of random numbers to the same seed is identical.
- It selects a suitable PRNG algorithm to that end that satisfies a high standard of statistical qualities of PRNGs and exhibits good runtime performance.

It could look something like this for example:

var prng = new PRNG(seed);
var x = prng.random(limit);
Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Anne van Kesteren-4
On Fri, Nov 16, 2012 at 7:13 AM, Florian Bösch <[hidden email]> wrote:
> Motivation: Web Applications enter the arena of interactive content
> creation/consumption (games, productivity software, etc.). A good PRNG would
> be desirable in many situations.

Did you discuss this with TC39?


--
http://annevankesteren.nl/

Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Frederick.Hirsch
In reply to this post by Florian Bösch
The W3C Web Cryptography working group [1]  has a draft that seems to include a method to generate cryptographically random values [2].

I'm not sure how well that relates to what your use case requires but it might be worth looking at.

regards, Frederick

Frederick Hirsch
Nokia





On Nov 16, 2012, at 10:13 AM, ext Florian Bösch wrote:

Motivation: Web Applications enter the arena of interactive content creation/consumption (games, productivity software, etc.). A good PRNG would be desirable in many situations.

Web Applications that desire to use random numbers have a 4 problems with the existing Math.random function.

1) The implementation is not "high quality" in that the generated random numbers tend to be statistically poor compared to other higher quality PRNGs.

2) The API does not support seeding whereas the same sequence of random numbers can be generated twice if so desired.

3) It is based on floating points which due to machine differences even in the presence of seeding could generate different numbers.

4) Alternative implementations in JS suffer even in the presence of sophisticated JITing VMs from the fact that mathematics is done in doubles (in the case of addition, subtraction, division and multiplication) and by converting double -> int -> double (in the case of bitshifts and modulo division). This makes it both harder to implement a reliable PRNG and it makes it slow.

I would propose an alternative native code random number API that has the following characteristic:

- The returned value is based on integers ranging from 0 up to a specified limit.
- It is initializable with a seed
- It makes a guarantee that no matter on what machine the random number is generated, that the sequence of random numbers to the same seed is identical.
- It selects a suitable PRNG algorithm to that end that satisfies a high standard of statistical qualities of PRNGs and exhibits good runtime performance.

It could look something like this for example:

var prng = new PRNG(seed);
var x = prng.random(limit);

Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Florian Bösch
In reply to this post by Anne van Kesteren-4
On Fri, Nov 16, 2012 at 4:22 PM, Anne van Kesteren <[hidden email]> wrote:
Did you discuss this with TC39?
I did not, sorry if this is the wrong place for it. 

Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Florian Bösch
In reply to this post by Frederick.Hirsch
On Fri, Nov 16, 2012 at 4:24 PM, <[hidden email]> wrote:
The W3C Web Cryptography working group [1]  has a draft that seems to include a method to generate cryptographically random values [2].
It does include a random number generator. However it does not include seeding and consequentially no guarantees about the algorithm and repeatability.
Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

David Bruant-5
Le 16/11/2012 16:30, Florian Bösch a écrit :
On Fri, Nov 16, 2012 at 4:24 PM, <[hidden email]> wrote:
The W3C Web Cryptography working group [1]  has a draft that seems to include a method to generate cryptographically random values [2].
It does include a random number generator. However it does not include seeding and consequentially no guarantees about the algorithm and repeatability.
That'd be a nonsense to add seeding in my opinion. If you want security, you don't want to take the risk of people seeding and loose all security property. If it's for debugging purposes, the seeding should be part of a devtool, not of the web-facing API.

David
Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Florian Bösch
On Fri, Nov 16, 2012 at 5:20 PM, David Bruant <[hidden email]> wrote:
That'd be a nonsense to add seeding in my opinion. If you want security, you don't want to take the risk of people seeding and loose all security property. If it's for debugging purposes, the seeding should be part of a devtool, not of the web-facing API.
I agree that in the crypographic context seeding might not make sense (or even guarantees about repeatability). 

The purpose of the proposal of a fast, reliable, statistically sound, repeatable, seedable PRNG in JS however is not to do cryptography. It would be to be able to perform procedural computation repeatably regardless of machine, VM, optimization and vendor differences. An example: Say you wanted to do a procedural universe consisting of 1 million stars. At 3 cartesian coordinates per star and at each component having 8 bytes, you'd get 22MB of data. If you want to share this galaxy with anybody you'll have to pass them this 22mb blob. If you want multiple people in the same galaxy, you have to pass them that blob.

It takes about 0.7 seconds in C to generate 3 million statistically sound random numbers for longs. The seed to the galaxy is just a few bytes. So why do we have to transfer 22mb for the web?
Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Boris Zbarsky
In reply to this post by Florian Bösch
On 11/16/12 7:13 AM, Florian Bösch wrote:
> 4) Alternative implementations in JS suffer even in the presence of
> sophisticated JITing VMs from the fact that mathematics is done in
> doubles (in the case of addition, subtraction, division and
> multiplication) and by converting double -> int -> double (in the case
> of bitshifts and modulo division). This makes it both harder to
> implement a reliable PRNG and it makes it slow.

I would be interested in some specific data here.  Do you have an
example of a PRNG that is actually being slow?

-Boris

Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

David Bruant-5
In reply to this post by Florian Bösch
Le 16/11/2012 17:35, Florian Bösch a écrit :
On Fri, Nov 16, 2012 at 5:20 PM, David Bruant <[hidden email]> wrote:
That'd be a nonsense to add seeding in my opinion. If you want security, you don't want to take the risk of people seeding and loose all security property. If it's for debugging purposes, the seeding should be part of a devtool, not of the web-facing API.
I agree that in the crypographic context seeding might not make sense (or even guarantees about repeatability). 

The purpose of the proposal of a fast, reliable, statistically sound, repeatable, seedable PRNG in JS however is not to do cryptography. It would be to be able to perform procedural computation repeatably regardless of machine, VM, optimization and vendor differences. An example: Say you wanted to do a procedural universe consisting of 1 million stars. At 3 cartesian coordinates per star and at each component having 8 bytes, you'd get 22MB of data. If you want to share this galaxy with anybody you'll have to pass them this 22mb blob. If you want multiple people in the same galaxy, you have to pass them that blob.
If you want repeatable, you actually don't want random (as your title suggests) but PRNG very specifically ("pseudo" being themost important part). In that case, I feel writing your own PRNG will be almost as fast as a native one with nowadays crazy JIT. Just write an algorithm that you're satisfied and pass around the algo and any parametrization you want. I feel it would solve your use case.

It takes about 0.7 seconds in C to generate 3 million statistically sound random numbers for longs.
Do you have measurements of how much the same algo takes in JS?

David
Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Florian Bösch
I'll see that I can come up with a test suite that verifies statistical and runtime behavior of an array of algorithms implemented in JS, it'll probably take a while.


On Fri, Nov 16, 2012 at 6:02 PM, David Bruant <[hidden email]> wrote:
Le 16/11/2012 17:35, Florian Bösch a écrit :
On Fri, Nov 16, 2012 at 5:20 PM, David Bruant <[hidden email]> wrote:
That'd be a nonsense to add seeding in my opinion. If you want security, you don't want to take the risk of people seeding and loose all security property. If it's for debugging purposes, the seeding should be part of a devtool, not of the web-facing API.
I agree that in the crypographic context seeding might not make sense (or even guarantees about repeatability). 

The purpose of the proposal of a fast, reliable, statistically sound, repeatable, seedable PRNG in JS however is not to do cryptography. It would be to be able to perform procedural computation repeatably regardless of machine, VM, optimization and vendor differences. An example: Say you wanted to do a procedural universe consisting of 1 million stars. At 3 cartesian coordinates per star and at each component having 8 bytes, you'd get 22MB of data. If you want to share this galaxy with anybody you'll have to pass them this 22mb blob. If you want multiple people in the same galaxy, you have to pass them that blob.
If you want repeatable, you actually don't want random (as your title suggests) but PRNG very specifically ("pseudo" being themost important part). In that case, I feel writing your own PRNG will be almost as fast as a native one with nowadays crazy JIT. Just write an algorithm that you're satisfied and pass around the algo and any parametrization you want. I feel it would solve your use case.


It takes about 0.7 seconds in C to generate 3 million statistically sound random numbers for longs.
Do you have measurements of how much the same algo takes in JS?

David

Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

Joshua Bell-3
On Fri, Nov 16, 2012 at 9:20 AM, Florian Bösch <[hidden email]> wrote:
I'll see that I can come up with a test suite that verifies statistical and runtime behavior of an array of algorithms implemented in JS, it'll probably take a while.


Thank you!

As a side benefit, having a library of tested PRNGs implemented in JS with a "good" license would be quite handy.

 

On Fri, Nov 16, 2012 at 6:02 PM, David Bruant <[hidden email]> wrote:
Le 16/11/2012 17:35, Florian Bösch a écrit :
On Fri, Nov 16, 2012 at 5:20 PM, David Bruant <[hidden email]> wrote:
That'd be a nonsense to add seeding in my opinion. If you want security, you don't want to take the risk of people seeding and loose all security property. If it's for debugging purposes, the seeding should be part of a devtool, not of the web-facing API.
I agree that in the crypographic context seeding might not make sense (or even guarantees about repeatability). 

The purpose of the proposal of a fast, reliable, statistically sound, repeatable, seedable PRNG in JS however is not to do cryptography. It would be to be able to perform procedural computation repeatably regardless of machine, VM, optimization and vendor differences. An example: Say you wanted to do a procedural universe consisting of 1 million stars. At 3 cartesian coordinates per star and at each component having 8 bytes, you'd get 22MB of data. If you want to share this galaxy with anybody you'll have to pass them this 22mb blob. If you want multiple people in the same galaxy, you have to pass them that blob.
If you want repeatable, you actually don't want random (as your title suggests) but PRNG very specifically ("pseudo" being themost important part). In that case, I feel writing your own PRNG will be almost as fast as a native one with nowadays crazy JIT. Just write an algorithm that you're satisfied and pass around the algo and any parametrization you want. I feel it would solve your use case.


It takes about 0.7 seconds in C to generate 3 million statistically sound random numbers for longs.
Do you have measurements of how much the same algo takes in JS?

David


Reply | Threaded
Open this post in threaded view
|

Re: random numbers API

David Bruant-5
In reply to this post by Florian Bösch
Le 16/11/2012 18:20, Florian Bösch a écrit :
> I'll see that I can come up with a test suite that verifies
> statistical and runtime behavior of an array of algorithms implemented
> in JS, it'll probably take a while.
I don't think you need to go through such lengths.
If you do have the galaxy use case, implement it with the same C
algorithm you used to get the 0.7s measurement and see if JS perf is
actually a problem.

David