Implement rand(::Range{BigInt})

[rfourquet]

This is a rebase of #8255, with minor modifications.
The travis test doesn't pass on linux because functions only available in GMP 6 are used, but isn't version 6 a requirement now? (cf. #7957).

[ivarne]

No, currently we require GMP (>= 5.0) in the README. Not sure about the situation in other parts of Julia, but from the discussion in #7957 it seems likely that we can bump the requirement. Packagers on Linux systems seem to have problems with updating dependencies, so we should probably be carefull.

[rfourquet]

OK, so GMP 6 may not be a requirement for Julia 0.4 in the end? in this case I would see if I can implement this using only GMP 5.

[nalimilan]

If you need it I guess we'll deal with that dependency when building packages, but if that's not really needed it would be easier for packagers not to use it. :-)

[ViralBShah]

I think that given julia 0.4 is going to release after a few months, we can go with GMP 6 as a dependency. All the distros will have it by then.

[ivarne]

I changed the title to WIP, so that it is clear that it can't be merged before we update GMP requirement.

[ViralBShah]

@nalimilan Would it be crazy to require GMP 6 for julia 0.4?

[nalimilan]

Absolutely not, it's already in the upcoming Fedora 21 (but generally speaking, raising requirements should only happen with relatively strong reasons).

[rfourquet]

So there was a solution in GMP5, which is no less efficient despite having to copy data instead of generating it directly into the BigInt.
Removing WIP as there are no more GMP requirements.

[rfourquet]

Here is the link to the doc of mpz_import, if someone wanted to check the wrapping code.
The Travis failure seems to be unrelated (it happens in parallel.jl/sharedarray.jl).

[ViralBShah]

@rfourquet Can you squash these commits?

[ViralBShah]

Also, in the squashed commits, can you give a slightly more detailed explanation of the commits?

[tkelman]

opened #9176 for the travis failure - it actually looks like it's in bitarray

[rfourquet]

This is squashed now, with some explanations added in the commit.

[ViralBShah]

A few points as I look through this and other related code:

1. Let's have the GMP 6 code in there, but with a version check. If there is no easy way to check the GMP version, let's have it in there, but commented out. Is there a significant reason to use the new API - performance or memory?
2. The names could be a little more consistent so that the relationships are clearer. How about renaming RangeGenerator to AbstractRangeGenerator, RandIntGen to RangeGeneratorInt, and RandIntGenBigInt to RangeGeneratorBigInt? Could inrange then just be rand_int_gen?
3. I notice that the range length is an unsigned integer, and we specialize for both UInt32 and UInt64. What if we just use Int, which is essentially what we use in most places? I don't think we need to have every possible combination and the full range - if we can keep things simpler, unless there is a good reason for it.

[rfourquet]

1. There is a way to get the GMP version, I didn't thought of that. For small ranges, I couldn't detect significative speed differences between the two versions, but on bigger ranges the GMP5 version is visibly slower (e.g. 30% slower for rand(1:big(2)^10000)).
2. I mostly agree with your changes, but I don't feel the need (yet) of "Abstract" in AbstractRangeGenerator. I was unsure for the name inrange, but it reads nicely in rand(mt, inrange(r)), where r is a range. But when squashing I wanted to change it to rangegen. I would prefer that the name has "range" in it, unlike rand_int_gen.
3. I started a refactoring to simplify this (a bit similar to rand of AbstractArray #8649). But there was opposition to removing the full range. The UInt32 version could maybe be removed if that doesn't make things slower for small types.

[rfourquet]

Updated:

1. the code for the two versions of GMP is there. I named a constant GMP_VERSION in gmp.jl, but if I call it simply VERSION , this message is issued during compilation "Warning: imported binding for VERSION overwritten in module GMP"... aren't they in a different namespace?
2. I kept the name RangeGenerator, and used also RangeGenerator as the constructor (instead of inrange).

[ViralBShah]

It seems that the Windows 64-bit has failed. The worker running the random test is the one that never came back - but there are no error messages.

https://ci.appveyor.com/project/StefanKarpinski/julia/build/1.0.133/job/yhkll194gvedibs9

@tkelman How do we figure this one out? Can you try this branch?

[ViralBShah]

@rfourquet The PR looks good otherwise.

[tkelman]

@ViralBShah sure I'm building this branch now, will let you know what I see

[tkelman]

This does seem to freeze or go into an infinite loop of some kind:

  | | |_| | | | (_| |  |  Version 0.4.0-dev+1904 (2014-12-01 14:28 UTC)
 _/ |\__'_|_|_|\__'_|  |  rf/rand-bigrange/e209872* (fork: 1 commits, 1 day)
|__/                   |  x86_64-w64-mingw32

julia> T = UInt32;

julia> s = big(typemax(T)-1000) : big(typemax(T)) + 10000
4294966295:4294977295

julia> using Base.Test

julia> @test rand(s) != rand(s)

[tkelman]

On master at fd531ed that same sequence of inputs gives ERROR: stack overflow

[rfourquet]

Thanks @tkelman. The stack overflow on master is expected, but I don't see anything that could cause the freeze, I believe it happens in the while true in rand(rng::AbstractRNG, g::RangeGeneratorBigInt).
I'm not familiar with endianness, so I may have put the wrong endianness argument to mpz_import: is the processor big endian? Could you show the value of Base.GMP.GMP_VERSION, and of Base.Random.RangeGenerator(s) in the example above?

[tkelman]

julia> Base.GMP.GMP_VERSION
v"6.0.0"

julia> Base.Random.RangeGenerator(s)
Base.Random.RangeGeneratorBigInt(4294966295,11000,1,0x00003fff)

[tkelman]

I'm not sure about endianness (I don't think it's that different on Windows?) but I have seen in the past that GMP and MPFR tend to use C longs in many of their API's, and I do know that long is only 32 bits on Win64. But I'll defer to you on whether that would make a difference to this code.

[rfourquet]

The other AppVeyor build seems to succeed on a pentium 4 32-bits machine... I read again the code without finding any bug. Would you accept to make another test after adding prints around line 457:

print(limbs, " ")
ccall((:__gmpz_limbs_finish, :libgmp), Void, (Ptr{BigInt}, Clong), &x, g.nlimbs)
println(x)

and then run

T = UInt32; s = big(typemax(T)-1000) : big(typemax(T)) + 10000;  println(rand(s)); rand(s)

?

[tkelman]

https://gist.github.com/2e22f8b016fda3d35c76

That was terminated by me with ctrl-C, didn't show any signs of stopping. Make sure you're not assuming Int and Clong are the same anywhere, on Win64 they're different.

[ViralBShah]

The code seems to use Clong everywhere in ccall, and I assume that Ints passed are converted appropriately by ccall.

[rfourquet]

Thanks a lot! The manual says indeed that ccall converts arguments to what is declared in ccall argument types.
So the first call to rand works (0x00000722 == UInt32(1826)), but then in the second call we find that 0x000006ac == 326417516204 % UInt32 but with 326417516204 = UInt64(0x4c)<<32 + 0x000006ac. So my guess is that for some reason, mpz_limbs_finish assumes that limbs are not of type Culong but UInt64, and that when reading the first limb, it reads beyond the passed array (UInt32[0x000006ac] of size 1), which contains 0x4c after the end position, interpreting those two UInt32 as one UInt64 limb.
In gmp.jl, the data field is Ptr{Culong} so I had assumed that it's enforced that limbs are Culong (default value in gmp.h), but if a local GMP installation is used, it can be different, and I think that this particular installation has configured GMP with #define _LONG_LONG_LIMB. I will see if there is a way to detect the size of the limbs.

[rfourquet]

I pushed a new commit replacing the use of Culong (for limbs) by an auto-detected Limb type. If this fixes the problem above, I'll squash it.

[ViralBShah]

Since you are squashing, could you also update the comments with a bit about the type of Limb? Should be good to merge after that.

[rfourquet]

@ViralBShah I added some comment above the Limb definition in gmp.jl, is this fine?

[rfourquet]

Referencing squashed commit to record discussion.

[ViralBShah]

Thanks - this got done nicely.

[tkelman]

Good catch @rfourquet. I don't think we're specifically asking for this configuration item but it's probably buried somewhere in config.log.

[rfourquet]

@tkelman and it was a good configuration as far as tests are concerned!
I fixed the limbs field and put the check suggested in 8b0921c#commitcomment-8799280 at https://github.com/JuliaLang/julia/compare/rf/rand-bigrange-fixup. I thougth it didn't deserve a new PR but wanted someone to check before meging.