#!/usr/bin/perl -l

use constant SLICE => 10000;
use constant BIGSLICE => SLICE * SLICE;

# $result = randbigint( $low, $high )
# $result = randbigint( $high )
# $result = randbigint
#    Return a (possibly BigInt) integer between $low and $high.
#    Return a (possibly BigInt) integer between 1 and $high.
#    Return a (possibly BigInt) integer between 0 and 1.
sub randbigint {
    use integer;
    my ( $low, $high ) = @_;

    # Set the default alternatives.
    $low  = 0 unless defined $low;
    $high = 1 unless defined $high;

    # Make sure that they're in order.
    ($low,$high) = ($high,$low) if $low > $high;

    while ( 1 ) {
        # Some versions of rand provide only 15 bits of randomness.
        # That means that asking for a large random number is never
        # fair; only 2**15 of the numbers will ever be chosen.
        #
        # If the range is small enough, we just select a random element.
        # A range of SLICE (10000) is enough smaller than 2**15 to be
        # reasonably fairly chosen, while still big enough to be useful.
        my $diff = $high - $low + 1;
        return $low + int ( rand $diff ) if $diff < SLICE;

        # Otherwise, we'll divide the range into SLICE subranges
        # and select one of them, and repeat the loop to select from
        # the chosen subrange.
        #
        # If the range has less than BIGSLICE (100000000) elements,
        # we correct for the unfairness that occurs when there
        # are two different subrange sizes.  If it is bigger,
        # the unfairness is negligible.

        # Note: the "use integer" at the top of this function
        # has a special purpose.  It ensures that the results of
        # a division are truncated to an integer, whether the
        # arguments are normal Perl numbers (truncated because of
        # the "use integer") or they are BigInts (truncated
        # because BigInts always use integer divide).  This is
        # necessary.  If the int() function were used instead,

        # it would ruin the value when it was applied to a BigInt
        # rather than a scalar.

        my $interval = int( rand( SLICE ) );
        my $intlow = $low + $diff * $interval / SLICE;
        my $inthigh = $low + $diff * ($interval+1) / SLICE - 1;
        my $intmax = ($diff + SLICE - 1) / SLICE;

        # accept new bounds if any of these is true:
        #       (A) the range is big enough to ignore unfairness
        #       (B) the subrange is full size
        #       (C) the subrange is small size
        #           but the "extra" number in the subrange
        #           wasn't chosen.
        ($low, $high) = ( $intlow, $inthigh )
             if $diff > BIGSLICE
                || ($inthigh - $intlow + 1) == $intmax
                || rand( $intmax ) >= 1.0;
    }
}

print randbigint(1000);

use Math::BigInt;
$x = new Math::BigInt("999999999999999999999999999999999");
print randbigint($x), "\n", randbigint($x, 2 * $x);