Re: random numbers API

[David Bruant]

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

Re: random numbers API

[Joshua Bell]

On Fri, Nov 16, 2012 at 9:20 AM, Florian Bösch  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  wrote:
>
>>  Le 16/11/2012 17:35, Florian Bösch a écrit :
>>
>> On Fri, Nov 16, 2012 at 5:20 PM, David Bruant  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
>>
>
>

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  wrote:

>  Le 16/11/2012 17:35, Florian Bösch a écrit :
>
> On Fri, Nov 16, 2012 at 5:20 PM, David Bruant  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
>

Re: random numbers API

[David Bruant]

Le 16/11/2012 17:35, Florian Bösch a écrit :
On Fri, Nov 16, 2012 at 5:20 PM, David Bruant > 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

Re: random numbers API

[Boris Zbarsky]

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

Re: random numbers API

[Florian Bösch]

On Fri, Nov 16, 2012 at 5:20 PM, David Bruant  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?

Re: random numbers API

[David Bruant]

Le 16/11/2012 16:30, Florian Bösch a écrit :
On Fri, Nov 16, 2012 at 4:24 PM, > 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

Re: random numbers API

[Florian Bösch]

On Fri, Nov 16, 2012 at 4:24 PM,  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.

Re: random numbers API

[Frederick.Hirsch]

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


[1] http://www.w3.org/2012/webcrypto/

[2] http://www.w3.org/TR/WebCryptoAPI/#Crypto-method-getRandomValues


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);

Re: random numbers API

[Florian Bösch]

On Fri, Nov 16, 2012 at 4:22 PM, Anne van Kesteren  wrote:

> Did you discuss this with TC39?
>
I did not, sorry if this is the wrong place for it.

Re: random numbers API

[Anne van Kesteren]

On Fri, Nov 16, 2012 at 7:13 AM, 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.

Did you discuss this with TC39?


-- 
http://annevankesteren.nl/

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);