
while checking uniform_int.hpp, I spotted 2 weirdnesses in uniform_int.hpp that almost cancel themselves out, but not to the point that a contrived example is impossible. The heart of the problem is this loop : while(mult <= limit) { result += (eng() - bmin) * mult; mult *= result_type(brange)+result_type(1); // <-- overflow possible } where limit = (range+1)/(brange+1) the multiplication is almost always guaranteed not to overflow (that was the motivation to write the loop that way, I guess), except when mult==limit (which is reached when range+1 is a power of brange+1) in that case, the last multiplication assigns (range+1) to mult. And range+1 might in fact overflow. Now, it turns out in cases where range+1 overflows, limit is computed with special anti-overflow code, and there 's a bizarre condition there that looks like a bug : if(_range % result_type(brange)+1 == result_type(brange)) ++limit; instead of expected if(_range % result_type(brange+1) == result_type(brange+1)) ++limit; so in the end, most of the time when range==max, limit is assigned the value : range/(brange+1) instead of (range+1)/(brange+1). So it cancels out the first bug most of the time (maybe that is the reason for the bizarre code). but the limit will still be equal to (range+1)/(brange+1) for brange=1 (I'm not sure how useful a coin-flipper generator would be, but we never know..), and mult can then be made to wrap and reach 0 in the previous loop, which loops forever. I've attached a compilable exemple and suggested patch. I've thought it over carefully, the patch works in all situations. after the test on (mult==limit), it's all safe since mult is guaranteed to be > limit, and thus _range/mult will still be < brange+1, so the recursive call at the end is safe. -- Samuel

Hello, Samuel. [snip math]
so in the end, most of the time when range==max, limit is assigned the value: range/(brange+1) instead of (range+1)/(brange+1). So it cancels out the first bug most of the time (maybe that is the reason for the bizarre code).
Don't you just love obfuscated math?
but the limit will still be equal to (range+1)/(brange+1) for brange=1 (I'm not sure how useful a coin-flipper generator would be, but we never know..),
A while back I implemented a random-path graph algorithm that calculates a random "next vertex" or "successor" during each step in the path. Successor candidates that cause U-turns or cycles are thrown out before the random number generator is called. If each vertex has exactly three neighbors (e.g. when the graph represents a buckyball wireframe), then the random number generator degenerates into a coin-flipper generator. So it's not that farfetched.
and mult can then be made to wrap and reach 0 in the previous loop, which loops forever.
I'll test your theory when I get the chance. Cromwell Enage _______________________________ Do you Yahoo!? Win 1 of 4,000 free domain names from Yahoo! Enter now. http://promotions.yahoo.com/goldrush

le Monday 23 August 2004 23:51, sponage@yahoo.com écrivit :
Don't you just love obfuscated math?
ohh yesss I do ! :-)
graph represents a buckyball wireframe), then the random number generator degenerates into a coin-flipper generator. So it's not that farfetched.
but in my example, the generator is used as a base for generating full length int numbers. So, unless there is a device that's very good at creating 1 bit entropy so fast and so well that people use it as a core source of randomness, the case really is contrived. hmm, well I guess this could happen after all. So the bug might have had a non-zero probability of happening (not much more, though) Anyway, the code is better with the bug fixed :) -- Samuel
participants (2)
-
Cromwell Enage
-
Samuel Krempp