Why do i get a Overflow Exception when trying to run the same method with same parameters?

Question

Was thinking of creating a random number generator which will support uint, long & ulong. I got to making the random uint generator but got stuck on making a min, max generator.

This is what i have

public class Rand : System.Random

public uint UInt32(uint min, uint max)
{
    byte[] array = new byte[4];

    base.NextBytes(array);

    uint result = BitConverter.ToUInt32(array, 0);

    if (result < min | result > max)
    {
        UInt32(min, max); //here i get a StackOverflowException
    }
    return result;
}

Why do i get a StackOverflowException when trying to run the same method with the same parameters?

Have you tried debugging it to see what it's actually doing step by step, observing the variables? You might answer your own question. — rory.ap, Feb 16 '18 at 12:20
if (result < min | result > max) is this correct or should be ||? — Johnny, Feb 16 '18 at 12:22
You generate random number and if it fails to match criteria (min-max range) - you call the same function again. But random number might fail to match this criteria arbitrary number of times, while stack size is not infinite, so often (how often depends on min and max) your recursive call eats up all the stack. That's not how you should generate random number in a range. — Evk, Feb 16 '18 at 12:24
Since bit-patterns are 'predictable' i.e. you could try cutting out the bits that make you exceed your boundaries. To save yourself the looping/recursive calls. No idea how that might effect the "quality" of the generated numbers though. — user6144226, Feb 16 '18 at 12:42

Sergey Kalinichenko · Accepted Answer · 2018-02-16T12:43:59.877

4

Your program's ability to exit from recursive invocations is dependent on the length of the interval [min..max]. The smaller the interval, the higher the probability of hitting StackOverflowException.

Since you are generating 4-byte integers, you have 2³² possible values. Assuming uniform distribution of random values, the probability of hitting the interval between min and max is equal to (max-min)*2^-32. The probability of continuing the recursive invocation is 1-(max-min)*2^-32. If you want your recursive invocations to have a chance of ending within a reasonable number of calls, the interval between min and max should be pretty large in comparison to 2³².

You can avoid stack overflow at the expense of having a rather slow code by converting your recursive code to iterative (your recursive implementation is wrong, too, because it drops the result of recursive invocation, but it's not worth fixing anyway).

edited Feb 16 '18 at 12:43

answered Feb 16 '18 at 12:30

Sergey Kalinichenko

714,442
84
1,110
1,523

What makes the iterative approach (assuming you just mean a while loop) slower? Or do you mean its just slow generally rather than slower than a recursive version would be (if it didn't overflow)? – Chris Feb 16 '18 at 12:40
1

Everything's OK except your last sentence -- you can't (easily) implement `Random(min, max)` by delegating to `Random(int, int)`, let alone for `ulong`. For `ulong` in particular, not even `Sample` will do if you want a decent distribution, as that internally just scales an `int`. There are [other approaches](https://stackoverflow.com/q/677373/4137916), of course. – Jeroen Mostert Feb 16 '18 at 12:41
1

@Chris It does not make it slower, it makes it slow in absolute terms. Recursive code will be just as fast as the iterative one. In fact, it could be restructured for tail call optimization. – Sergey Kalinichenko Feb 16 '18 at 12:42
I will just do what @Lepijohnny once said in the comment section of the post, dunno why he removed it, and put a `& max` and the end of `BitConverter` its good enough. – Demiz Feb 16 '18 at 12:42
1

@JeroenMostert you can do `Random(int, int)` and cast result to `(uint)` in unckecked context. Because int and uint have the same size - that will work fine (negative ints will result in big positive uints). For ulongs that's different story indeed. – Evk Feb 16 '18 at 12:42
@Evk: simply casting the input parameters will not give you correct results, taking range into account (my example of `0, uint.MaxValue` was obviously poorly chosen, as there it *will* work -- edited). You can do it, but not trivially. – Jeroen Mostert Feb 16 '18 at 12:44
@dasblinkenlight: Cool. I thought on rereading that was probably what you meant but thought I would check in case there was something I was missing. :) – Chris Feb 16 '18 at 12:45
@Demiz: using `&max` doesn't look like it will give you an even distribution which I would personally expect from a random number generator... – Chris Feb 16 '18 at 12:47
@Chris i get what you mean but idk what else to do. Its better than nothing. – Demiz Feb 16 '18 at 13:06
1

@Demiz: How about work out the size of your range. Round up to the nearest power of 2. Generate a random number between 0 and your power of 2. Bitmask that. Discard those that are out of range (less than 50% chance to be out of range now). Add min value to your number (to bring it back into the actual range). There may well be better ways to do it but this should at least guarantee you uniformity with a relatively simple algorithm. – Chris Feb 16 '18 at 13:44

Why do i get a Overflow Exception when trying to run the same method with same parameters?

1 Answers1