There seems to be a lot of boilerplate. Is it possible to condense? Especially with other issues like broadcasting (see #6902) or dtype (see #6869), it seems like this could easily blow up with so many functions implementing nearly the same thing but with 32-bit or 64-bit int.

Also, is there a way to test / demonstrate the issue with the random stream that is apparently rampant in the current implementation of random_integers? That would be quite useful (at least for my sake, given that I have been looking at this for so long) to illustrate why these changes are necessary.

@gfyoung You can implement both the dtype and broadcasting using the added functions. You need both 32 and 64 to implement both intp and int with the same functions, the same functions added to randomkit (which uses unsigned) can also be used for unsigned. To do a efficient job with smaller integer types more functions need to be added to randomkit for efficient implementation, i.e., there are two int16 in one int32 sample.

Not clear on what you consider boiler plate besides the documentation...

@charris : Regarding dtype and broadcasting, that actually wasn't my question. I'm not worried about ability to implement. No, no, I know both are certainly possible, broadcasting to say the least given how many times it has been done already in mtrand.pyx.

My concern was that won't you have to implement everything at least twice now in your versions? Maybe I'm getting my semantics / definitions wrong, but your two functions are boilerplate given how similar they are to each other.

Also, you say "you need" to implement the functions separately for 32-bit and 64-bit. Again, is there a way to test or illustrate the shortcomings? Also, why is it that you are using the 32-bit Mersenne Twister for npy_uint64? From what I remember, @rkern said on my PR that this should not be done, and that there is a completely separate algorithm for 64-bit.

I unfortunately can't pull down the branch right now to try it myself, but how does the change address the failed method call in #6812 with np.iinfo(np.int64).max? Do you have to call random_int64, or does random_intp suffice?

That's not what I said. What I said was that just changing unsigned long to unsigned long long in the core PRNG would not help you. Instead, I suggested exactly what @charris implemented here, to create rk_uint64 that generates a uint64 from two draws from the core PRNG.

@gfyoung You need 64 bit random numbers in order to generate 64 bit random numbers. OTOH, it is inefficient to use 64 bit numbers to generate 32 random numbers. The two functions are similar, but not the same. Note that rk_random_uint64 will use 32 or 64 bit random samples depending on the size of the range, and we need to preserve that in order to retain backwards compatibility.

It would help if you would make specific comments about specific lines/functions. It it difficult to respond to generalities.

@rkern: Oh, sorry! You're right. Memory failed me there. By the way in the original code (i.e master branch), doesn't rk_ulong do exactly that, which is called from rk_interval, which in turn is called by random_integers? If not, then how was it then that my added test in #6824 passed both on my machine (32-bit) and on 64-bit Linux on Travis?

@charris: Apologies that I haven't been able to give more specific pointers. While I realize this is WIP, my comments have been directed at the overall organization and structure of the code. My concern was directed towards the future additions of dtype and broadcasting, which would have to be added in both functions. I'm just trying to understand why you organized the code the way you did, if that's okay.

Also, if you could address the question regarding the np.iinfo(np.int64).max call, that would be great as well!

@gfyoung If we go the dtype route, it only needs to be added to one function, which will call the appropriate others, which may be hidden (or not). But we do need the others, as they will all differ in lower level details.

I don't see an np.iinfo(np.int64).max call here, what are you referring to?

@charris : Ah, I see. Just add it to random_integers and then branch out to the appropriate calls in randomkit.c. For efficiency purposes, that's fair.

The np.iinfo(np.int64).max call I'm referring to is in the first comment of @jreback issue #6812, which technically is not the failing mem_overlap test failure as you described in your PR description.

Generally speaking, the high-inclusive random_integers(low, high) is considered an API mistake. It's only here because it was in Numeric's RandomArray. I'd prefer to expand only randint() to other dtypes instead.

@rkern : That's interesting that you point that out. What happens if people wanted to generate numbers that included the maximum possible integer (e.g. np.iinfo(np.int64).max)?

That just means that we have to be careful about dealing with the high argument that is input, but it should be manageable.

@rkern : Oh, that was actually more of a theoretical question than a question directly related to the changes here. In any case, I'm not sure that I follow your comment regarding only implementing dtype for just randint and not random_integers since randint calls random_integers currently.

As an aside, perhaps once all of the refactoring has been done, it could be worthwhile to deprecate randint and random_integers with just one function that accepts a is_half_open argument defaulted to True. I'm not sure it's within the scope of this PR, but just throwing that out there.

It's the other way around. random_integers() calls randint().

@rkern : They have been reversed (#6885). Also, I had a question for you about the two draws from the PRNG, which I think got lost in the discussion, so I'll paste it here:

By the way in the original code (i.e master branch), doesn't rk_ulong do exactly that, which is called from rk_interval, which in turn is called by random_integers? If not, then how was it then that my added test in #6824 passed both on my machine (32-bit) and on 64-bit Linux on Travis?

@rkern OK, things can be fixed up. To be clear, randint is the preferred function. ISTM that in that case we should deprecate random_integers or at least document that randint should be used instead. Perhaps the proposed dtype argument should only be added to randint as well to encourage that.

@gfyoung rk_ulong() does make two draws when unsigned long is 64 bits wide. That's what that #if ULONG_MAX <= 0xffffffffUL test is controlling.

Regarding the nitty-gritty details of the various method semantics: I do think it would indeed be nice if there were some way to sample a uniform uint64, though it's a bit tricky to get the API right because it's a weird corner case that most users probably won't care about. I also agree that the current random_integers/randint situation is confusing. An additional extra-confusing aspect that hasn't been mentioned yet in this thread is that the stdlib random module also has functions for sampling from both half-open and closed intervals, and it also uses the name randint for one of those functions, but they do it backwards from us -- their randint is our random_integers, and our randint is their randrange.

Proposal: soft deprecate both randint and random_integers (by "soft deprecate" I mean: document that you shouldn't use them, mayyyybe emit a warning when they're used, but don't make any plans to actually remove them), and replace them both with a new method randrange([start,] stop, [step, closed=False, dtype=int]). Rationale: the randrange name is more transparent to users who already know range and more consistent with the stdlib; the new closed= kwarg (as suggested by @gfyoung) provides an elegant way to sample from the full fixed-width integer range without cluttering up the top-level documentation and forcing users to understand the subtleties of how the half-open convention interacts with fixed-width integers just to get started.

If that sounds good to y'all then someone should post it to the list I guess...

Two things that might benefit from further refinement: (a) the closed= name is somewhat jargony for parts of our user base, maybe there's something even better? (include_max=?), (b) do we want to take advantage of the addition of this new method to clean up the default integer type?

I'd suggest fixing the technical issues with the existing function of interest first and then do the renaming for clarity separately.

As for the rangerange() proposal itself, I'd actually omit step= as a foolish consistency with random.randrange() which is itself a foolishly consistent with range(). This should be a fairly primitive function, so making it do more things with more options is a pessimization in terms of usability, IMO. As for closed=, there isn't a problem with specifying the full range with the open-interval convention; the caller is not restricted to passing in fixed-width integers.

@charris : There are still several documentation issues that should probably be fixed (see the comments I made that have not been collapsed yet in an outdated diff info). OTOH cool to see that there was a speed-up here.

An indication of just how much a jump backward in a loop costs.

In [13]: timeit np.random.randint(0, 128, size=10**6, dtype=np.uint64)
100 loops, best of 3: 3.8 ms per loop

In [14]: timeit np.random.randint(0, 65, size=10**6, dtype=np.uint64)
100 loops, best of 3: 15.5 ms per loop

If the jump overhead was zero, then the second timing would be 2x the first, but as there is a jump back before the second draw that has to account for the extra time. That suggests that the speed could be increased by perhaps about a factor of two by unrolling the loop a bit.

OK, I'm going to put this in so that the appveyor failures can show.