A Simple Puzzle

re: A Simple Puzzle

pr3fix — Sat, 21 Apr 2012 23:07:07 GMT

(max - min) / buckets ?

re: A Simple Puzzle

CodeInChaos — Wed, 29 Feb 2012 10:38:31 GMT

@Ali

The disadvantage of that method is, that you now need to be *very* careful about rounding errors. I would not be surprised if there are values min<=x<max for which the calculated bucket is outside of the array range. Floating point rounding is a tricky beast.

So I prefer Eric's code (with a fix for his bug of course).

---

Since IMO the build in Random class in .net sucks, I'm currently creating my own RNG. A similar issue crept up:

One feature is generating a uniform double that satisfies min<=x<max from a uniform double that satisfies 0<=x<1.

The naive implementation if this is simply: `return min+(max-min)*Uniform()`. Unfortunately if `Uniform()` returns `1-Epsilon`, the result might get rounded to `max`, violating the contract.

So I've added a do-while loop ensured the result is smaller than max.

re: A Simple Puzzle

Olivier — Mon, 27 Feb 2012 09:12:37 GMT

The moral of all this: static typing does not replace testing ;-)

re: A Simple Puzzle

Jagannath — Mon, 27 Feb 2012 05:08:40 GMT

private static int[] CreateHistogram(IEnumerable<double> data, int buckets, double min, double max)

{

int[] results = new int[buckets];

double multiplier = buckets / (max - min);

foreach (double datum in data)

{

int index = (int) ((datum - min) * multiplier);

if (0 <= index && index < buckets)

results[index] += 1;

min = datum;

}

return results;

}

re: A Simple Puzzle

weeble0 — Fri, 24 Feb 2012 19:39:00 GMT

@Ali Ah, sorry, I did misunderstand you.

re: A Simple Puzzle

Ali — Fri, 24 Feb 2012 19:04:41 GMT

@weeble0 I think you misunderstand me, my comment was "first check if the current point is in range, and if it is, only then calculate the index" seems a more natural way to code the algorithm. I wondered if there is some disadvantage I cannot see. (Except that, then there would be no interesting bug/puzzle to talk about)

re: A Simple Puzzle

weeble0 — Fri, 24 Feb 2012 18:55:50 GMT

This all sounds very familiar. This bears some relation to one of Eric's previous posts, "What's the difference? Remainder vs modulus":

blogs.msdn.com/.../what-s-the-difference-remainder-vs-modulus.aspx

In fact, I think in the comments I linked to an instance of a very similar bug.

re: A Simple Puzzle

weeble0 — Fri, 24 Feb 2012 18:45:55 GMT

@Ali I don't think that has anything to do with the bug, does it? Mathematicians would normally write something like (min<=value<max) to more clearly express how value falls inside a range with a lower and an upper bound. Indeed some languages such as Python actually allow that syntax. In languages like C# that don't allow that syntax, (min<=datum && datum<max) is the closest you can get.

re: A Simple Puzzle

Josh Starner — Fri, 24 Feb 2012 18:41:38 GMT

I just watched a presentation by Bret Victor last night called Inventing on Principle, and he talks about an interface that gives algorithm developers immediate insight into the results of their functions. If you haven't seen it, you should watch this section of it: www.youtube.com/watch

Watching the video and then reading this post made me think: Man, if Eric had this tool, he may not have had that bug. :)

re: A Simple Puzzle

bjorg — Fri, 24 Feb 2012 18:29:59 GMT

The only time it goes into the last bucket is when the value is equal to max. Did you mean to use a rounding function when going from double to int instead?

I'm not following your train of thought here. Suppose min is 0, max is 5 and buckets is 10. Multiplier is 2. If one of the data is, say, 4.7 then we multiply by 2 to get 9.4 and then round off to 9, which is the index of the last bucket. But 4.7 is not equal to 5. So I've provided a counterexample to your claim; would you care to clarify the claim? -- Eric