Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cryptic genetic variation in software: hunting a buffered 41-year-old bug

cryptogenomicon.wordpress.com

Post reply on HN
Print view View original

11–20 of 50 posts

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#11

Post by vishnugupta »

matthewcanty wrote: post #4

That was a really interesting read, and very well written. I wonder if anyone can clear this up though... I find the terminology of open and closed intervals contradictory to their meaning. Does anyone know why they are described like this? `Closed` makes me think shut or not-including - however it includes its endpoints. `Open` makes me think inclusive - yet does not include its endpoints.

The way I wrap my head around this is "open" == "no defined beginning or end point" and "closed" == "precisely defined beginning/end point".

To take your thinking a bit further the interval is "shut" precisely because it's closed exactly at that point. And the interval is thrown "open" by not including the point.

BTW; Rudin's classic text (1) covers the fascinating topic of neighborhoods which builds on the concept of intervals. It took me a while to completely understand the concept but after that understanding limits was relatively easier; even otherwise "neighborhood" as a concept is interesting in itself.

[1] http://www.math.boun.edu.tr/instructors/ozturk/eskiders/guz1...

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#12

Post by ZoFreX »

imurray wrote: post #7

It would be safest for most rand() functions to omit both zero and one, unless a user was really sure they wanted otherwise. If we were generating real numbers, we'd never see precisely zero or one. The fact that we do is an artifact of limited precision. These boundary cases cause problems in common computations like u.log(u) or (1-u).log(1-u).

It's pretty common in practice to want [0,1) (that is, 0 <= x < 1) from your random number generator. Never generating 0 would be a problem when the range is small and discrete - generating random letters for example.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#13

Post by entropy_ »

masklinn wrote: post #9
saurik wrote: post #6

Earlier quoted context omitted.

The analogy I've always used is that the closed interval has what amounts to a lid or a cap on it, while the open interval does not. Another (sort of related) way of looking at it is that the closed interval has a maximum (or minimum) value, whereas the open interval, despite only missing a single value, suddenly has this feeling of continuation, because without that final value it now asymptotes to the end and you w…

The so-called "french notation" is interesting and — I think — clearer: a closed interval is [a, b] and an open interval is ]a, b[.

I learned Math in a french-system school and yes, that's definitely a much better notation in my opinion. The difference between [] and () is not immediately clear, whereas [a,b] versus ]a,b[ makes it obvious that one includes a and b while the other does not. It also makes it easy to remember "open" and "closed" and what they mean in terms of whether or not the interval bounds are included or excluded

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#14

Post by bainsfather »

imurray wrote: post #7

It would be safest for most rand() functions to omit both zero and one, unless a user was really sure they wanted otherwise. If we were generating real numbers, we'd never see precisely zero or one. The fact that we do is an artifact of limited precision. These boundary cases cause problems in common computations like u.log(u) or (1-u).log(1-u).

Interesting suggestion, but I'm not sure I agree with you.

You could use that argument about any of the random numbers that your rng returns. "Hey, 0.023 is infinitesimally unlikely to occur, so let's exclude that as well".

Generally when I use a real-valued rng, the numbers generated are meant to be 'representative' of what I should get from the distribution. And when I get e.g. 0.023, it kind-of means "0.023 and/or numbers near to 0.023". If I excluded 0.023 from the possible results of the rng, then I would have a 'hole' in my distribution 'in the region of' 0.023.

Maybe what you want is to go from the possible rnds:

0.000, 0.001, 0.002, 0.003, ... , 0.999

to:

0.0005, 0.0015, 0.0025, ... , 0.9995

whereas with your suggestion, you are under-representing the boundary numbers near to 0 and/or near to 1. Generally not a problem I guess, but what you are doing is, imo, 'wrong in theory', even though your high-precision floats will probably cover it up ok in almost all cases.

I agree with you about 0 and 1 causing problems when they are fed into other functions - e.g. generating Gaussian rngs by using InverseCumulativeGaussian(0.0) - a bug I wasted some time hunting down in my company's rng library. My view was that the developer who wrote the library did not understand the maths of what he was doing, rather than that the 0to1 random number generator was at fault.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#15

Post by vkolencik »

kovrik wrote: post #3
saurik wrote: post #2

(Also posted 20 hours ago, also no comments.) (It occurs to me that if there are ever comments on this post, my comment will sound really confusing: let it be clear that this article is #1 currently, was posted 40 minutes ago, and there are no comments yet. ;P) https://news.ycombinator.com/item?id=8453042

Well, this article is so thorough, detailed and well-written, that I don't know what to say other than "Wow, that was cool and very interesting!". More stories like that?

I especially like the clever analogy with genetics. Douglas Hofstadter said something along the lines of analogy being more powerful when the two concepts it connects are otherwise very distant from each other.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#16

Post by StavrosK »

saurik wrote: post #6
matthewcanty wrote: post #4

That was a really interesting read, and very well written. I wonder if anyone can clear this up though... I find the terminology of open and closed intervals contradictory to their meaning. Does anyone know why they are described like this? `Closed` makes me think shut or not-including - however it includes its endpoints. `Open` makes me think inclusive - yet does not include its endpoints.

The analogy I've always used is that the closed interval has what amounts to a lid or a cap on it, while the open interval does not. Another (sort of related) way of looking at it is that the closed interval has a maximum (or minimum) value, whereas the open interval, despite only missing a single value, suddenly has this feeling of continuation, because without that final value it now asymptotes to the end and you w…

Even though this is also the way I think of it, this underscored to me the fact that you can make up plausible explanations for anything; even for words that are opposites and are trying to explain the same thing.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#17

Post by picomancer »

db48x wrote: post #10
matthewcanty wrote: post #4

That was a really interesting read, and very well written. I wonder if anyone can clear this up though... I find the terminology of open and closed intervals contradictory to their meaning. Does anyone know why they are described like this? `Closed` makes me think shut or not-including - however it includes its endpoints. `Open` makes me think inclusive - yet does not include its endpoints.

It's a good question. A close reading of the Wikipedia page " rel="nofollow">https://en.wikipedia.org/wiki/Interval_%28mathematics%29#Ter... tells me that an open interval has no definite maximum or minimum. This no doubt sounds strange, but it surely comes down to the slightly odd behavior of real numbers. In an open interval like (0, 1), there is no single real number which is less than one but is greater than all…

> real numbers. In an open interval like (0, 1), there is no single real number which is less than one but is greater than all other real numbers less than one.

The rational numbers are like this too.

All the rational numbers between 0 and 1 also increase arbitrarily close to 1 with no largest element. You can prove this by simple contradiction: For every rational number x Actually real numbers can be defined (axiomatized) in terms of the least upper bound property -- every set of real numbers that's bounded above has a least upper bound. So you could actually have a set S of rational numbers that gets arbitrarily close to something like sqrt(2) from below. S then has no rational least upper bound -- for every rational number x greater than or equal to every element of S, there is another rational number y greater than or equal to every element of S but smaller than x.

Note that a set of real numbers need not contain its upper bound -- as you noted, a bounded open interval doesn't contain its upper bound.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#18

Post by cgio »

entropy_ wrote: post #13
masklinn wrote: post #9

Earlier quoted context omitted.

The so-called "french notation" is interesting and — I think — clearer: a closed interval is [a, b] and an open interval is ]a, b[.

I learned Math in a french-system school and yes, that's definitely a much better notation in my opinion. The difference between [] and () is not immediately clear, whereas [a,b] versus ]a,b[ makes it obvious that one includes a and b while the other does not. It also makes it easy to remember "open" and "closed" and what they mean in terms of whether or not the interval bounds are included or excluded

I don't know if it's very intuitive given that a and be are still inside the ][. Maybe a]..[b would make it clearer?

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#19

Post by jdpage »

matthewcanty wrote: post #4

That was a really interesting read, and very well written. I wonder if anyone can clear this up though... I find the terminology of open and closed intervals contradictory to their meaning. Does anyone know why they are described like this? `Closed` makes me think shut or not-including - however it includes its endpoints. `Open` makes me think inclusive - yet does not include its endpoints.

From a real analysis standpoint... the definition of a 'closed set' in an N-dimensional metric space (of which Euclidean space, i.e. normal space, is an example) is as follows: a set C is 'closed' if and only if, given any sequence of elements (x_n) converging on x, such that (x_n) is a subset of C, it follows that x is also in C.

Under this definition, 'closed' makes sense in the larger context, since in mathematics, if an operation is 'closed' on a set, that means that applying the operation to elements of the set always yields another element of the same set.

Open is a bit more awkward. A set O is 'open' if and only if the complement of O (i.e. the set of all points not in O) is closed. So open is kind of the opposite of closed, hence the convention. Of course, it isn't really the opposite of closed, since there are sets which are neither closed nor open.

tt;dr (too technical; didn't read) in maths, 'closed' usually means 'I can do stuff inside this set without falling out of it'. In the case of intervals, the 'stuff' in question is taking a limit of a convergent sequence.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#20

Post by mbq »

Thumbs up for not using rand, but the assuming that MT is a golden bullet is not exactly scientific; one should just test few RNGs, it may come in that the code exploits some ultra-hidden hole in MT or that some much faster RNG works equally well. Also reproducibility of a stochastic code means that the code results lead to the same conclusions regardless of the seed, not that you get bit to bit identical output for the same seed. In case one assumes (only) the latter, it may end up in seed cherry picking, not-optimizing code because it would "break reproducibility" or not investigating the natural deviation of the results.
Post reply on HN