On OTP rand module difference between OTP 19 and OTP 20

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

Re: On OTP rand module difference between OTP 19 and OTP 20

Attila Rajmund Nohl
2017-08-31 17:27 GMT+02:00 Loïc Hoguin <[hidden email]>:
> On 08/31/2017 05:13 PM, Attila Rajmund Nohl wrote:
>>
>> 2017-08-31 15:42 GMT+02:00 Loïc Hoguin <[hidden email]>:
[...]

>>> I certainly hope this is not the general policy for OTP. We program
>>> against
>>> the documentation. The documentation *is* our reality.
>>
>>
>> I disagree. Take this example:
>> https://lwn.net/SubscriberLink/732420/9b9f8f2825f1877f/ The printk()
>> function in the Linux kernel was documented to print new logs to new
>> lines unless the KERN_CONT option was passed. In reality it didn't
>> always started new lines and people expected (maybe even relied on)
>> this - and when the code was updated to match the documentation, they
>> were genuinely surprised when their code was broken.
>
>
> This story is not about people following the documentation and then have the
> documentation be "fixed" under their feet without them noticing, it is in
> fact the complete opposite.

The moral of the story: people are programming against
behavior/implementation, not documentation. In these cases fixing the
implementation instead of the documentation has very real possibility
of breaking existing programs. Of course, one can tell its users that
"it's your fault you haven't followed the documentation!" but it
doesn't necessarily make those users happy...
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Loïc Hoguin-3
On 08/31/2017 05:32 PM, Attila Rajmund Nohl wrote:

> 2017-08-31 17:27 GMT+02:00 Loïc Hoguin <[hidden email]>:
>> On 08/31/2017 05:13 PM, Attila Rajmund Nohl wrote:
>>>
>>> 2017-08-31 15:42 GMT+02:00 Loïc Hoguin <[hidden email]>:
> [...]
>>>> I certainly hope this is not the general policy for OTP. We program
>>>> against
>>>> the documentation. The documentation *is* our reality.
>>>
>>>
>>> I disagree. Take this example:
>>> https://lwn.net/SubscriberLink/732420/9b9f8f2825f1877f/ The printk()
>>> function in the Linux kernel was documented to print new logs to new
>>> lines unless the KERN_CONT option was passed. In reality it didn't
>>> always started new lines and people expected (maybe even relied on)
>>> this - and when the code was updated to match the documentation, they
>>> were genuinely surprised when their code was broken.
>>
>>
>> This story is not about people following the documentation and then have the
>> documentation be "fixed" under their feet without them noticing, it is in
>> fact the complete opposite.
>
> The moral of the story: people are programming against
> behavior/implementation, not documentation. In these cases fixing the
> implementation instead of the documentation has very real possibility
> of breaking existing programs. Of course, one can tell its users that
> "it's your fault you haven't followed the documentation!" but it
> doesn't necessarily make those users happy...

Maybe in the Linux kernel. Outside, where there is such a thing as
documentation (comments are not documentation), if the code behaves
differently than the documentation, you open a ticket... And in that
case, yes, for a limited time, you will program against the behavior and
not against the documentation. But it's the exception, not the rule.

--
Loïc Hoguin
https://ninenines.eu
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

zxq9-2
In reply to this post by Attila Rajmund Nohl
On 2017年08月31日 木曜日 17:32:44 you wrote:
> The moral of the story: people are programming against
> behavior/implementation, not documentation. In these cases fixing the
> implementation instead of the documentation has very real possibility
> of breaking existing programs. Of course, one can tell its users that
> "it's your fault you haven't followed the documentation!" but it
> doesn't necessarily make those users happy...

There was once a boy who always rode his bike on the right side of the streets in his neighborhood. Sure, the signs all said "keep left" but, well, everyone just ignores the signs where he lives.

One day a new sign was in its place that said "keep right".

Now what should he do?

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

zxq9-2
In reply to this post by Attila Rajmund Nohl
On 2017年08月31日 木曜日 17:32:44 Attila Rajmund Nohl wrote:

> 2017-08-31 17:27 GMT+02:00 Loïc Hoguin <[hidden email]>:
> > On 08/31/2017 05:13 PM, Attila Rajmund Nohl wrote:
> >>
> >> 2017-08-31 15:42 GMT+02:00 Loïc Hoguin <[hidden email]>:
> [...]
> >>> I certainly hope this is not the general policy for OTP. We program
> >>> against
> >>> the documentation. The documentation *is* our reality.
> >>
> >>
> >> I disagree. Take this example:
> >> https://lwn.net/SubscriberLink/732420/9b9f8f2825f1877f/ The printk()
> >> function in the Linux kernel was documented to print new logs to new
> >> lines unless the KERN_CONT option was passed. In reality it didn't
> >> always started new lines and people expected (maybe even relied on)
> >> this - and when the code was updated to match the documentation, they
> >> were genuinely surprised when their code was broken.
> >
> >
> > This story is not about people following the documentation and then have the
> > documentation be "fixed" under their feet without them noticing, it is in
> > fact the complete opposite.
>
> The moral of the story: people are programming against
> behavior/implementation, not documentation. In these cases fixing the
> implementation instead of the documentation has very real possibility
> of breaking existing programs. Of course, one can tell its users that
> "it's your fault you haven't followed the documentation!" but it
> doesn't necessarily make those users happy...

There was once a boy who always rode his bike on the right side of the streets in his neighborhood. Sure, the signs all said "keep left" but, well, everyone just ignores the signs where he lives.

One day a new sign was in its place that said "keep right".

Now what should he do?

-Craig

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Michael Truog
In reply to this post by Raimo Niskanen-2
On 08/31/2017 05:30 AM, Raimo Niskanen wrote:

> On Thu, Aug 31, 2017 at 10:34:16AM +1200, Richard A. O'Keefe wrote:
>>
>> On 30/08/17 6:42 PM, Raimo Niskanen wrote:
>>> On Wed, Aug 30, 2017 at 11:44:57AM +1200, Richard A. O'Keefe wrote:
>>>> There are applications of random numbers for which it is important
>>>> that 0 never be returned.  Of course, nothing stops me writing
>>> What kind of applications?  I would like to get a grip on how needed this
>>> function is?
>> I'll give you just one example.  There are two ways I know to generate
>> normally distributed random numbers.  One of them goes like this:
>>
>>       sqrt(-2 * ln(randnz()) * cos(pi * random())
>>
>> where random() is in [0,1) but randnz() must be in (0,1).
>>
>> OK, I'll give you another example.  This is part of an algorithm for
>> generating gamma variates, one of the best known.
>>
>>       U <- random()
>>       if U <= r then
>>           z <- -ln(U/r)
>>       else
>>           z <- ln(random()/lambda)
>>       end
>>
>> You will notice that both of the calls to ln will go wrong if
>> random() can return 0.
>>
>> These aren't the only examples, but I have an appointment.
> Thank you!
>
> Should I make a pull request of this?
>
>      https://github.com/erlang/otp/compare/OTP-20.0...RaimoNiskanen:raimo/stdlib/rand-uniformNZ
>
> Is the name uniformNZ good enough?
> Are uniform floats complete enough with this addition?

As I argued in the original pull request for these recent 20.0 random number changes, a uniform distribution is much more intuitive if it is inclusive: [0,1]

For example, if you are dealing with probabilities, it is simpler to think in percentages from 0.00 to 1.00

An example from the python documentation is at https://docs.python.org/3/library/random.html#random.uniform though they have ambiguity about the highest value due to a rounding problem they have.

I have had my own dependency for uniform as [0,1] at https://github.com/okeuday/quickrand/blob/fc5e21ec70ee94dd4ce1c5ee02b55ceea03f9008/src/quickrand.erl#L294-L309 so I have been working around this absence.  Though I would assume other people would benefit from the addition of a [0,1] function in Erlang/OTP.

Best Regards,
Michael



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Fred Hebert-2
In reply to this post by Loïc Hoguin-3
On 08/31, Loïc Hoguin wrote:
>Maybe in the Linux kernel. Outside, where there is such a thing as
>documentation (comments are not documentation), if the code behaves
>differently than the documentation, you open a ticket... And in that
>case, yes, for a limited time, you will program against the behavior
>and not against the documentation. But it's the exception, not the
>rule.
>

I think 'it depends' truly *is* the best way to go about it. Let's see a
few examples:

- A function does what is in the doc, but also does a bit more at the
  same time. Do you fix by removing the additional functionality people
  may now rely on, or by updating the doc to match the implementation?
- The documentation specifies that by sending the atom 'tsl1.3' you can
  set up a TLS 1.3 connection, but the implementation only accepts
  'tsl1.3' and crashes on 'tsl1.3'. Do you not update the documentation
  for what was a typo, or do you add support for 'tsl1.3' as a
  parameter? If anybody relied on that behaviour, they relied on the
  code not working!
- A function for socket handling returns values such as `{error, emfile
  | enfile | econnrefused}`. Someone finds out that the syscalls it
  relays data to also may return `{error, eperm | eaccess}` on top of
  what was specified before. Do you swallow the errors and mask them, or
  update the docs? Or is it not just a bug in the docs?
- A function's doc says it sorts in a stable manner but it does not.  
  Which one should you change? There seems to be no winner on this one.
- A function logs information while it operates on data, but the
  documentation makes no reference to it. Someone working with it in a
  specific environment has issues with that behaviour.*

There's plenty of cases where the doc and the implementation may be
wrong individually. Either as a mistake on either sides, by omission, or
through a bug. Usually you have to take a pragmatic approach wondering
which of the fixes will give the lowest conflict or impact to people
using the code.

Now is the case of the random behaviour similar to specifying a bad type
boundary similar to "not supporting all the errors", to a breach of a
well-established contract, etc.? That's a really hard question, but
saying either "the doc always wins" or "the code always wins"
unequivocally sounds like a real bad policy to me.

Regards,
Fred.

* In adding shell history to Erlang, we got tripped up on disk_log doing
  just that. We added a new option to force it to be silent when needed,
  for example, so both the code and the doc required a fix!
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Loïc Hoguin-3
On 08/31/2017 10:30 PM, Fred Hebert wrote:
> On 08/31, Loïc Hoguin wrote:
>> Maybe in the Linux kernel. Outside, where there is such a thing as
>> documentation (comments are not documentation), if the code behaves
>> differently than the documentation, you open a ticket... And in that
>> case, yes, for a limited time, you will program against the behavior
>> and not against the documentation. But it's the exception, not the rule.
>>
>
> I think 'it depends' truly *is* the best way to go about it.

Well it's a good thing I agreed with this in an email sent almost 6
hours ago then. :-)

--
Loïc Hoguin
https://ninenines.eu
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Richard A. O'Keefe-2
In reply to this post by Attila Rajmund Nohl
Sometimes people program against the documentation.
Sometimes people program against the behaviour.
Sometimes people program against their expectations
and the hell with the docs and the code.

In fact you are never going to please everyone.
My case study:
   The Quintus Prolog documentation had always said
   "do not add or remove clauses of an interpreted
    predicate while it is running; the behaviour is
    not defined."
    In major release 3, as part of implementing modules,
    we defined the behaviour to be "every call acts as if
    it made a snapshot of the predicate on entry and used
    that snapshot; changes to the predicate will affect
    later calls but not earlier ones".
    One customer complained that we had broken his code.
    We not only pointed out that the manual had warned
    against what he was doing, I rewrote his code to
    run 700 times faster.  (I kid you not.)

Of course we lost that customer.

I wish there was a blanket rule I could recommend.
There is one, of course, and that is "test before you
release".  In this particular case, it's quite hard
to test because the bad outcome is extremely rare.
(Although I do have a photocopy of the library of an
old programming language where the Gaussian random
number generator could not possibly have worked,
because 0 turned up once every 2^16 calls.)

There is another rule, which is that changes to the
documentation and changes to the code both need to
be clearly communicated in release nodes, and as a
user, it's my job to *read* the release notes.

The irony here, of course, is that Erlang copied as183
from Prolog, and I wrote the Prolog version of the
Wichmann-Hill 3-cycle generator, and it doesn't take
any care to avoid 0.0, and that's one reason why I was
glad to see it replaced...
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Richard A. O'Keefe-2
In reply to this post by Michael Truog


On 1/09/17 6:35 AM, Michael Truog wrote:
> As I argued in the original pull request for these recent 20.0 random
> number changes, a uniform distribution is much more intuitive if it is
> inclusive: [0,1]

Intuitive?  For integers, I'll grant that.  For reals?  Not so much.
I certainly cannot grant "MUCH more intuitive".
I've had occasion to do (random next * 2 - 1) arcTanh, which of
course breaks down if *either* 0 or 1 is returned by (random next).

> For example, if you are dealing with probabilities, it is simpler to
> think in percentages from 0.00 to 1.00

Actually, when I'm dealing with probabilities, I never think
about them as percentages.  Now the interesting thing here
is this.  Suppose you want to get a true [false] outcome
with probability p [1-p].  Then random next < p  does the
job perfectly, but ONLY if 1 is excluded.

The trick of generating a random integer from 1 to N by
doing (in C): (int)(random() * N) + 1 can of course give
you N+1 if random() can return 1.0, and this is a thing I very
often do.  (Yes, if 0.0 is excluded, the probability of getting
1 is very slightly skewed, but it's _very_ slightly.)

> An example from the python documentation is at
> https://docs.python.org/3/library/random.html#random.uniform though they
> have ambiguity about the highest value due to a rounding problem they have.

Oh, the bit where they say "The end-point value b may or may not be
included in the range."  Worst of both worlds.  You cannot rely on it
being included and you cannot rely on it being excluded.

Let's face it, the usual expectation is that a uniform random number
generator will return a value in the half-open range [0,1).

I have uses for (0.0, 1.0).
Michael Truog has uses for [0.0,1.0], although I wasn't able to tell
from a quick scan of his code what they are.

I could personally live with a warning in the documentation that says
that the random number generator could return 0.0, and here's a little
loop you might use to avoid that, and another suggestion in the code
about how to get the result Michael Truog wants.

I just want it to be obvious that it's dangerous to assume that the
result will not be 0.

By the way, given that a common way to make random floats is to
generate a bitvector, consider
(0 to: 15) collect: [:each | ((each / 15) * 256) truncated].
You will notice that the spacing between the values is *almost*
uniform, but not at the end.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Richard A. O'Keefe-2
In reply to this post by Fred Hebert-2


On 1/09/17 8:30 AM, Fred Hebert wrote:
> I think 'it depends' truly *is* the best way to go about it.

+1.  The universal expert's answer.  (The other is,
"some do, some don't.")  I'm going to nitpick gently.

> - A function does what is in the doc, but also does a bit more at the
>  same time. Do you fix by removing the additional functionality people
>  may now rely on, or by updating the doc to match the implementation?

There is no pressing need to do either.
Perhaps adding a note to the documentation that
"In some releases this function may accept additional
  arguments and appear to do sensible things.  This is
  subject to change."
is all that is required.

> - The documentation specifies that by sending the atom 'tsl1.3' you can
>  set up a TLS 1.3 connection, but the implementation only accepts
>  'tsl1.3' and crashes on 'tsl1.3'. Do you not update the documentation
>  for what was a typo, or do you add support for 'tsl1.3' as a
>  parameter?

You do both, and you add a note to the documentation that
"Earlier releases incorrectly accepted 'tsl1.3' instead of
  'tls1.3'.  This will be corrected in release N+2."

> - A function for socket handling returns values such as `{error, emfile
>  | enfile | econnrefused}`. Someone finds out that the syscalls it
>  relays data to also may return `{error, eperm | eaccess}` on top of
>  what was specified before. Do you swallow the errors and mask them, or
>  update the docs? Or is it not just a bug in the docs?

This one requires serious digging to find out.  I've been there,
though not with sockets.  Discovering that the C program you wrote
for "UNIX" version x reports an error in "UNIX" version y that
doesn't even exist in version x is a pain.  When I was working at
Quintus I spent weeks trawling through Unix manuals carefully
checking the error returns of every system call we used, and tried
to figure out what to do for each.  My aim was to classify errors
as - the program should not have done this (EINVAL &c)
    - the resource doesn't exist (ENOENT, ECHILD, ...) when it should
      or does exist (EEXIST) when it shouldn't
    - the resource named does exist but is the wrong kind of resource
      (ENOTDIR, EISDIR, ENOTBLK, ...)
    - the program doesn't have permission to do this (EPERM, ...)
    - the resource is busy (EBUSY, EDEADLK, ...)
    - some resource ran out (ENOMEM, ENFILE, EMFILE, EFBIG, ENOSPC,...)
    - something went wrong in the system (ENETDOWN, EHOSTDOWN, ...)
I eventually had to stop, but did write a little script using
the C preprocessor to dump all the macros obtained by including
<errno.h> and find all the E[A-Z0-9]+ ones, and check them against
the list of known ones.  It was a lot of work that I hoped POSIX
would render unnecessary in the future.  It didn't.

So this raises the quality-of-documentation issue, "Why did we ever
document this as only raising these specific errors?"

> - A function's doc says it sorts in a stable manner but it does not.
>  Which one should you change? There seems to be no winner on this one.

There is a very clear winner: fix the code.  When quicksort was
invented, it was known to do more comparisons than merge sort.
Hoare's problem was that he needed to sort a bunch of numbers on
a machine with 256 words of data memory, so that (a) he *really*
couldn't afford extra memory, and (b) comparisons were cheap.
Sedgewick's PhD thesis (which I did read once) did a very thorough
examination of quicksort performance and several variations on it,
BUT assumed that a comparison cost 1/4 as much as a memory reference.
Most comparisons of quicksort vs mergesort I've seen were misleading
because they compared numbers rather than strings or richer data
and because they compared a relatively smart quicksort implementation
against a pretty dump merge sort.  You can, for example,
  - do *optimal* sorting for small subfiles
  - not only ping-pong between the two arrays but run alternating
    passes backwards (this gets a bit more leverage out of the cache)
  - do 4-way merge instead of 2-way merge (does as many comparisons
    but is nicer to the memory subsystem)
and you can use a variant of the natural merge like samsort to
exploit existing order.

If you want an efficient algorithm with minimal space overhead,
there's a variant of heapsort that gets NlgN + O(N) comparisons
worst case, which beats quicksort.

> - A function logs information while it operates on data, but the
>  documentation makes no reference to it. Someone working with it in a
>  specific environment has issues with that behaviour.*

The documentation and the code both have to be changed.
The logging has to be made conditional, and the documentation
has to mention it.
>
> * In adding shell history to Erlang, we got tripped up on disk_log doing
>  just that. We added a new option to force it to be silent when needed,
>  for example, so both the code and the doc required a fix!

Ah, so I agreed with you on that one.  For the 2nd half of my concurrent
programming course, I have strongly recommended LYSE, so it's nice to
find myself on your side...

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Richard A. O'Keefe-2
In reply to this post by Raimo Niskanen-2
For what it's worth, here is an extract from the R documentation.

runif(n, min = 0, max = 1)       # min and max have defaults
...
'runif' will not generate either of the extreme values unless
'max = min' or 'max-min' is small compared to 'min',
and in particular not for the default arguments.

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Michael Truog
In reply to this post by Richard A. O'Keefe-2
On 08/31/2017 07:57 PM, Richard A. O'Keefe wrote:

>
> On 1/09/17 6:35 AM, Michael Truog wrote:
>> As I argued in the original pull request for these recent 20.0 random
>> number changes, a uniform distribution is much more intuitive if it is
>> inclusive: [0,1]
>
> Intuitive?  For integers, I'll grant that.  For reals?  Not so much.
> I certainly cannot grant "MUCH more intuitive".
> I've had occasion to do (random next * 2 - 1) arcTanh, which of
> course breaks down if *either* 0 or 1 is returned by (random next).

A uniform distribution should be uniformly distributed.  I understand the woes of floating-point prevent perfect uniform distribution, but we could at least try to pay attention to the limits involved, and if we did, that would make the idea much more intuitive.

My belief is that the [0,1) distribution is the most common because it is the easiest to implement given the IEEE floating point standard format.  However, I would also like to be proven wrong, to have more faith in the current situation.

>> For example, if you are dealing with probabilities, it is simpler to
>> think in percentages from 0.00 to 1.00
>
> Actually, when I'm dealing with probabilities, I never think
> about them as percentages.  Now the interesting thing here
> is this.  Suppose you want to get a true [false] outcome
> with probability p [1-p].  Then random next < p  does the
> job perfectly, but ONLY if 1 is excluded.

I see this as much simpler when it is possible to have random =< p , not that it matters much in this context, only when things get more complex.

>
>
> The trick of generating a random integer from 1 to N by
> doing (in C): (int)(random() * N) + 1 can of course give
> you N+1 if random() can return 1.0, and this is a thing I very
> often do.  (Yes, if 0.0 is excluded, the probability of getting
> 1 is very slightly skewed, but it's _very_ slightly.)
>
>> An example from the python documentation is at
>> https://docs.python.org/3/library/random.html#random.uniform though they
>> have ambiguity about the highest value due to a rounding problem they have.
>
> Oh, the bit where they say "The end-point value b may or may not be
> included in the range."  Worst of both worlds.  You cannot rely on it
> being included and you cannot rely on it being excluded.
>
> Let's face it, the usual expectation is that a uniform random number
> generator will return a value in the half-open range [0,1).
>
> I have uses for (0.0, 1.0).
> Michael Truog has uses for [0.0,1.0], although I wasn't able to tell
> from a quick scan of his code what they are.

I have some examples that can make this desire a bit clearer:

https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L139-L149

     % use Box-Muller transformation to generate Gaussian noise
     % (G. E. P. Box and Mervin E. Muller,
     %  A Note on the Generation of Random Normal Deviates,
     %  The Annals of Mathematical Statistics (1958),
     %  Vol. 29, No. 2 pp. 610–611)
     X1 = random(),
     X2 = PI2 * random(),
     K = StdDev * math:sqrt(-2.0 * math:log(X1)),
     Result1 = erlang:max(erlang:round(Mean + K * math:cos(X2)), 1),
     Result2 = erlang:max(erlang:round(Mean + K * math:sin(X2)), 1),
     sleep(Result2),


https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L204-L210

     X = random(),
     if
         X =< Percent ->
             erlang:exit(monkey_chaos);
         true ->
             ok
     end,

with:
random() ->
     quickrand:strong_float().

These are code segments used for the CloudI service configuration options monkey_latency and monkey_chaos so that normal distribution latency values and random service deaths can occur, respectively (with the more common names as Latency Monkey and Chaos Monkey, but the words switched to make the concepts easier to find and associate).  For the Box-Muller transformation, it really does want a definite range [0,1] and it helps make the monkey_chaos service death easier to understand at a glance.


>
> I could personally live with a warning in the documentation that says
> that the random number generator could return 0.0, and here's a little
> loop you might use to avoid that, and another suggestion in the code
> about how to get the result Michael Truog wants.
>
> I just want it to be obvious that it's dangerous to assume that the
> result will not be 0.
>
> By the way, given that a common way to make random floats is to
> generate a bitvector, consider
> (0 to: 15) collect: [:each | ((each / 15) * 256) truncated].
> You will notice that the spacing between the values is *almost*
> uniform, but not at the end.
>
I agree, but I still think the use of the word uniform here is better suited to the extremes.  We know it is IEEE floating-point, so we know it is inexact.

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Raimo Niskanen-2
In reply to this post by Loïc Hoguin-3
On Thu, Aug 31, 2017 at 03:42:06PM +0200, Loïc Hoguin wrote:

> On 08/30/2017 12:33 PM, zxq9 wrote:
> > On 2017年08月30日 水曜日 10:29:12 Raimo Niskanen wrote:
> >
> >> It is in general safer to change the documentation to match the reality.
> >
> > Wow.
>
> I certainly hope this is not the general policy for OTP. We program
> against the documentation. The documentation *is* our reality.
>
> It also seems it's not even listed in the release notes. We program
> against the documentation, if the documentation has a breaking changes
> it would be great to know about it.

I had no idea that statement would be so flammable. :-)

I simply wanted to point out that from the point of view of a developer of
a mature product like Erlang/OTP it is has happened too many times that
a subtle behaviour change breaks something for a customer.

And that is something that programmers writing new code often do not
appreciate since they simply want the libraries to be "right" where it is
a very reasonable view that the documentation defines what is "right".

I also realize that in this particular case to stop returning 0.0 from
rand:uniform() would also have been a safe choice since that would be
almost impossible to detect and almost certainly cause no harm.

And no, I did not state an OTP policy.  We decide from case to case.

>
> --
> Loïc Hoguin
> https://ninenines.eu

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Raimo Niskanen-2
In reply to this post by Michael Truog
On Thu, Aug 31, 2017 at 10:29:34PM -0700, Michael Truog wrote:

> On 08/31/2017 07:57 PM, Richard A. O'Keefe wrote:
> >
> > On 1/09/17 6:35 AM, Michael Truog wrote:
> >> As I argued in the original pull request for these recent 20.0 random
> >> number changes, a uniform distribution is much more intuitive if it is
> >> inclusive: [0,1]
> >
> > Intuitive?  For integers, I'll grant that.  For reals?  Not so much.
> > I certainly cannot grant "MUCH more intuitive".
> > I've had occasion to do (random next * 2 - 1) arcTanh, which of
> > course breaks down if *either* 0 or 1 is returned by (random next).
>
> A uniform distribution should be uniformly distributed.  I understand the woes of floating-point prevent perfect uniform distribution, but we could at least try to pay attention to the limits involved, and if we did, that would make the idea much more intuitive.

If I try to be philosophical, picking a random number in the range
0.0 to 1.0 of real numbers, the probability of getting a number exactly 0.0
(or exactly 1.0) is infinitely low.  Therefore the range (0.0,1.0) is more
natural.

>
> My belief is that the [0,1) distribution is the most common because it is the easiest to implement given the IEEE floating point standard format.  However, I would also like to be proven wrong, to have more faith in the current situation.

I think that is very possible.

We can not forget the fact that digital floating point numbers will always
be some kind of integer values in disguise.

:

>
> I have some examples that can make this desire a bit clearer:
>
> https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L139-L149
>
>      % use Box-Muller transformation to generate Gaussian noise
>      % (G. E. P. Box and Mervin E. Muller,
>      %  A Note on the Generation of Random Normal Deviates,
>      %  The Annals of Mathematical Statistics (1958),
>      %  Vol. 29, No. 2 pp. 610–611)
>      X1 = random(),
>      X2 = PI2 * random(),
>      K = StdDev * math:sqrt(-2.0 * math:log(X1)),

math:log(X1) will badarith if X1 =:= 0.0.  You need a generator for X1
that does not return 0.0, just as RO'K says.

>      Result1 = erlang:max(erlang:round(Mean + K * math:cos(X2)), 1),
>      Result2 = erlang:max(erlang:round(Mean + K * math:sin(X2)), 1),

If random() for X2 is in [0.0,1.0] then both 0.0 and 1.0 will produce the
same value after math:cos(X2) or math:sin(X2), which I am convinced will
bias the result since that particular value will have twice the probability
compared to all other values.  I think you should use a generator for X2
that only can return one of the endpoints.

Actually, it seems a generator for (0.0,1.0] would be more appropriate
here...

>      sleep(Result2),
>
>
> https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L204-L210
>
>      X = random(),
>      if
>          X =< Percent ->
>              erlang:exit(monkey_chaos);
>          true ->
>              ok
>      end,

In this kind of code, I think that (when thinking integers, since we are
talking about integers in disguise) half open intervals are more correct.

The interval [0.0,0.1] contains say N+1 numbers, the interval [0.0,0.2]
contains 2*N+1 nubers so subtracting the first interval from the second
would get the interval (1.0,2.0) which have N numbers.  So you get a bias
because you include both endpoints.

In this case I believe more in a generator that gives [0.0,1.0) and the
test X < Percent, since that is what I would have written using integers to
avoid off-by-one errors.

>
> with:
> random() ->
>      quickrand:strong_float().
>
> These are code segments used for the CloudI service configuration options monkey_latency and monkey_chaos so that normal distribution latency values and random service deaths can occur, respectively (with the more common names as Latency Monkey and Chaos Monkey, but the words switched to make the concepts easier to find and associate).  For the Box-Muller transformation, it really does want a definite range [0,1] and it helps make the monkey_chaos service death easier to understand at a glance.

Please explain why the Box-Muller transformation needs a definite range
[0.0,1.0].

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Raimo Niskanen-2
In reply to this post by Richard A. O'Keefe-2
On Fri, Sep 01, 2017 at 02:57:49PM +1200, Richard A. O'Keefe wrote:
:
>
> I could personally live with a warning in the documentation that says
> that the random number generator could return 0.0, and here's a little
> loop you might use to avoid that, and another suggestion in the code
> about how to get the result Michael Truog wants.
>
> I just want it to be obvious that it's dangerous to assume that the
> result will not be 0.

That can surely merit a warning, even though the interval is documented.

>
> By the way, given that a common way to make random floats is to
> generate a bitvector, consider
> (0 to: 15) collect: [:each | ((each / 15) * 256) truncated].
> You will notice that the spacing between the values is *almost*
> uniform, but not at the end.

That sounds interesting but I do not understand.  Is that Elixir code?

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Raimo Niskanen-2
In reply to this post by Michael Truog
On Thu, Aug 31, 2017 at 10:29:34PM -0700, Michael Truog wrote:
:

>
> I have some examples that can make this desire a bit clearer:
>
> https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L139-L149
>
>      % use Box-Muller transformation to generate Gaussian noise
>      % (G. E. P. Box and Mervin E. Muller,
>      %  A Note on the Generation of Random Normal Deviates,
>      %  The Annals of Mathematical Statistics (1958),
>      %  Vol. 29, No. 2 pp. 610–611)
>      X1 = random(),
>      X2 = PI2 * random(),
>      K = StdDev * math:sqrt(-2.0 * math:log(X1)),
>      Result1 = erlang:max(erlang:round(Mean + K * math:cos(X2)), 1),
>      Result2 = erlang:max(erlang:round(Mean + K * math:sin(X2)), 1),
>      sleep(Result2),

Why not use rand:normal/3?

It uses the Ziggurat Method and is supposed to be much faster and
numerically more stable than the basic Box-Muller method.

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Hugo Mills-2
In reply to this post by Raimo Niskanen-2
On Fri, Sep 01, 2017 at 10:41:15AM +0200, Raimo Niskanen wrote:

> On Thu, Aug 31, 2017 at 10:29:34PM -0700, Michael Truog wrote:
> > On 08/31/2017 07:57 PM, Richard A. O'Keefe wrote:
> > >
> > > On 1/09/17 6:35 AM, Michael Truog wrote:
> > >> As I argued in the original pull request for these recent 20.0 random
> > >> number changes, a uniform distribution is much more intuitive if it is
> > >> inclusive: [0,1]
> > >
> > > Intuitive?  For integers, I'll grant that.  For reals?  Not so much.
> > > I certainly cannot grant "MUCH more intuitive".
> > > I've had occasion to do (random next * 2 - 1) arcTanh, which of
> > > course breaks down if *either* 0 or 1 is returned by (random next).
> >
> > A uniform distribution should be uniformly distributed.  I understand the woes of floating-point prevent perfect uniform distribution, but we could at least try to pay attention to the limits involved, and if we did, that would make the idea much more intuitive.
>
> If I try to be philosophical, picking a random number in the range
> 0.0 to 1.0 of real numbers, the probability of getting a number exactly 0.0
> (or exactly 1.0) is infinitely low.  Therefore the range (0.0,1.0) is more
> natural.
   Mathematically, there's a distinction. What you've just described
is that in a random variable over the interval [0.0, 1.0], 0.0 and 1.0
happen *almost never* (which is a very specific technical term), and
that values in the open interval (0.0, 1.0) occur *almost surely*.

   Being discrete, the computer implementation based on floating point
numbers ensures that the probability of getting 0.0 or 1.0 in that
case is measurably non-zero, whereas in the ideal version over the
reals, above, it is infinitesimally small. In that distinction lie
most of the problems that people are talking about here, I think.

> > My belief is that the [0,1) distribution is the most common
> > because it is the easiest to implement given the IEEE floating
> > point standard format.  However, I would also like to be proven
> > wrong, to have more faith in the current situation.

> I think that is very possible.

   From my relatively limited practical experience, either I've wanted
[0, 1) or I don't care. Example:

   Red = int(random() * 256)

where I don't want the value 256, because it's out of range for my
8-bit graphics mode, but I do want the probability of 255 to be the
same as every other value. So I want [0, 1) as my range.

   Alternatively:

   P = random(),
   if
      P =< 0.3 -> ...;
      P =< 0.7 -> ...;
      P > 0.7 -> ...
   end

where, in general, I don't care if I could get 0.0 or 1.0 or not,
because the differences are immeasurably small for all practical
purposes.

   I think it's clear to me that _several_ functions are needed for
different cases, with fully-closed, fully-open and half-open
intervals. IMO, the fully-closed and half-open are probably the most
useful (and, modulo any floating-point issues which I'm not qualified
to talk about, [0,1) can be turned into (0,1] with
1-random_halfopen()).

   With a fully-closed interval, it should be possible to write
helpers for generating the other three by simply calling
random_closed() again if you get an undesirable end-point. You can't
easily extend the range of the half-open or open intervals to give you
the closed ones. So I'd say at minimum, there should be a function
giving the closed interval.

    Whether the "test and retry" approach is the best implementation
or not is a matter for discussion, as is the question of whether all
or some of these functions should be in the standard lib, or they are
expected to be hacked together on an as-needed basis.

   Hugo.

--
Hugo Mills             | Anyone who says their system is completely secure
hugo@... carfax.org.uk | understands neither systems nor security.
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                        Bruce Schneier

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Michael Truog
In reply to this post by Raimo Niskanen-2
On 09/01/2017 01:41 AM, Raimo Niskanen wrote:

>> I have some examples that can make this desire a bit clearer:
>>
>> https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L139-L149
>>
>>       % use Box-Muller transformation to generate Gaussian noise
>>       % (G. E. P. Box and Mervin E. Muller,
>>       %  A Note on the Generation of Random Normal Deviates,
>>       %  The Annals of Mathematical Statistics (1958),
>>       %  Vol. 29, No. 2 pp. 610–611)
>>       X1 = random(),
>>       X2 = PI2 * random(),
>>       K = StdDev * math:sqrt(-2.0 * math:log(X1)),
> math:log(X1) will badarith if X1 =:= 0.0.  You need a generator for X1
> that does not return 0.0, just as RO'K says.
>
>>       Result1 = erlang:max(erlang:round(Mean + K * math:cos(X2)), 1),
>>       Result2 = erlang:max(erlang:round(Mean + K * math:sin(X2)), 1),
> If random() for X2 is in [0.0,1.0] then both 0.0 and 1.0 will produce the
> same value after math:cos(X2) or math:sin(X2), which I am convinced will
> bias the result since that particular value will have twice the probability
> compared to all other values.  I think you should use a generator for X2
> that only can return one of the endpoints.
>
> Actually, it seems a generator for (0.0,1.0] would be more appropriate
> here...
>
>>       sleep(Result2),
>>
>> with:
>> random() ->
>>       quickrand:strong_float().
>>
>> These are code segments used for the CloudI service configuration options monkey_latency and monkey_chaos so that normal distribution latency values and random service deaths can occur, respectively (with the more common names as Latency Monkey and Chaos Monkey, but the words switched to make the concepts easier to find and associate).  For the Box-Muller transformation, it really does want a definite range [0,1] and it helps make the monkey_chaos service death easier to understand at a glance.
> Please explain why the Box-Muller transformation needs a definite range
> [0.0,1.0].

That was my understanding after not having modified that routine for a decent amount of time, though I must be mistaken.  I will need to fix this source code and regret not seeing these problems in the Box-Muller transformation source code. Thank you for pointing them out.  At least this shows a need for a (0.0,1.0] function.

Thanks,
Michael
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Michael Truog
In reply to this post by Raimo Niskanen-2
On 09/01/2017 01:54 AM, Raimo Niskanen wrote:

> On Thu, Aug 31, 2017 at 10:29:34PM -0700, Michael Truog wrote:
> :
>> I have some examples that can make this desire a bit clearer:
>>
>> https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L139-L149
>>
>>       % use Box-Muller transformation to generate Gaussian noise
>>       % (G. E. P. Box and Mervin E. Muller,
>>       %  A Note on the Generation of Random Normal Deviates,
>>       %  The Annals of Mathematical Statistics (1958),
>>       %  Vol. 29, No. 2 pp. 610–611)
>>       X1 = random(),
>>       X2 = PI2 * random(),
>>       K = StdDev * math:sqrt(-2.0 * math:log(X1)),
>>       Result1 = erlang:max(erlang:round(Mean + K * math:cos(X2)), 1),
>>       Result2 = erlang:max(erlang:round(Mean + K * math:sin(X2)), 1),
>>       sleep(Result2),
> Why not use rand:normal/3?
>
> It uses the Ziggurat Method and is supposed to be much faster and
> numerically more stable than the basic Box-Muller method.
>
The Box-Muller is simpler and producing 2 results instead of 1 .  I believe I looked at the source code for rand:normal/3 and expected the Box-Muller to be faster only because it creates 2 results, though I should check that.  I will have to investigate it more.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: On OTP rand module difference between OTP 19 and OTP 20

Raimo Niskanen-2
In reply to this post by Michael Truog
On Fri, Sep 01, 2017 at 03:53:37AM -0700, Michael Truog wrote:

> On 09/01/2017 01:41 AM, Raimo Niskanen wrote:
> >> I have some examples that can make this desire a bit clearer:
> >>
> >> https://github.com/CloudI/cloudi_core/blob/a1c10a02245f0f4284d701a2ee5f07aad17f6e51/src/cloudi_core_i_runtime_testing.erl#L139-L149
> >>
> >>       % use Box-Muller transformation to generate Gaussian noise
> >>       % (G. E. P. Box and Mervin E. Muller,
> >>       %  A Note on the Generation of Random Normal Deviates,
> >>       %  The Annals of Mathematical Statistics (1958),
> >>       %  Vol. 29, No. 2 pp. 610–611)
> >>       X1 = random(),
> >>       X2 = PI2 * random(),
> >>       K = StdDev * math:sqrt(-2.0 * math:log(X1)),
> > math:log(X1) will badarith if X1 =:= 0.0.  You need a generator for X1
> > that does not return 0.0, just as RO'K says.
> >
> >>       Result1 = erlang:max(erlang:round(Mean + K * math:cos(X2)), 1),
> >>       Result2 = erlang:max(erlang:round(Mean + K * math:sin(X2)), 1),
> > If random() for X2 is in [0.0,1.0] then both 0.0 and 1.0 will produce the
> > same value after math:cos(X2) or math:sin(X2), which I am convinced will
> > bias the result since that particular value will have twice the probability
> > compared to all other values.  I think you should use a generator for X2
> > that only can return one of the endpoints.
> >
> > Actually, it seems a generator for (0.0,1.0] would be more appropriate
> > here...
> >
> >>       sleep(Result2),
> >>
> >> with:
> >> random() ->
> >>       quickrand:strong_float().
> >>
> >> These are code segments used for the CloudI service configuration options monkey_latency and monkey_chaos so that normal distribution latency values and random service deaths can occur, respectively (with the more common names as Latency Monkey and Chaos Monkey, but the words switched to make the concepts easier to find and associate).  For the Box-Muller transformation, it really does want a definite range [0,1] and it helps make the monkey_chaos service death easier to understand at a glance.
> > Please explain why the Box-Muller transformation needs a definite range
> > [0.0,1.0].
>
> That was my understanding after not having modified that routine for a decent amount of time, though I must be mistaken.  I will need to fix this source code and regret not seeing these problems in the Box-Muller transformation source code. Thank you for pointing them out.  At least this shows a need for a (0.0,1.0] function.

Yes.  That is easily produced by (pointed out earlier in this thread):
    1.0 - rand:uniform()

>
> Thanks,
> Michael

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
123