The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-BigInt-Random-OO-0.03
River stage zero No dependents
++
/ Math::BigInt::Random::OO

NAME

Math::BigInt::Random::OO - generate uniformly distributed Math::BigInt objects

SYNOPSIS

  use Math::BigInt::Random::OO;

  # Random numbers between 1e20 and 2e30:

  my $gen = Math::BigInt::Random::OO -> new(min => "1e20",
                                            min => "2e30");
  $x = $gen -> generate();      # one number
  $x = $gen -> generate(1);     # ditto
  @x = $gen -> generate(100);   # 100 numbers

  # Random numbers with size fitting 20 hexadecimal digits:

  my $gen = Math::BigInt::Random::OO -> new(length => 20,
                                            base => 16);
  @x = $gen -> generate(100);

ABSTRACT

Math::BigInt::Random::OO is a module for generating arbitrarily large random integers from a discrete, uniform distribution. The numbers are returned as Math::BigInt objects.

DESCRIPTION

Math::BigInt::Random::OO is a module for generating arbitrarily large random integers from a discrete, uniform distribution. The numbers are returned as Math::BigInt objects.

CONSTRUCTORS

CLASS -> new ( ... )

Returns a new Math::BigInt::Random::OO random number generator object. The arguments are given in the "hash style", as shown in the following example which constructs a generator for random numbers in the range from -2 to 3, inclusive.

  my $gen = Math::BigInt::Random::OO -> new(min => -2,
                                            max =>  3);

The following parameters are recognized.

min => NUM

Specifies the minimum possible output value, i.e., the lower bound. If `max' is given, but `min' is not, then `min' is set to zero.

max => NUM

Specifies the maximum possible output value, i.e., the upper bound. If `max' is given, but `min' is not, then `max' must be non-negative.

length => NUM

Specifies the length of the output value, i.e., the number of digits. Use this option to ensure that all random numbers have the same number of digits. If the base is not given explicitly with the `base' option, then a base of 10 is used. The following two constructors are equivalent

  Math::BigInt::Random::OO -> new(length => $n, base => $b);

  $min = Math::BigInt -> new($b) -> bpow($n - 1);
  $max = Math::BigInt -> new($b) -> bpow($n) -> bsub(1));
  Math::BigInt::Random::OO -> new(min => $min, max => $max);

For instance, if the length is 4 and the base is 10, the random numbers will be in the range from 1000 to 9999, inclusive. If the length is 3 and the base is 16, the random numbers will be in the range from 256 to 4095, which is 100 to fff hexadecimal.

This option is ignored if the `max' option is present.

base => NUM

Sets the base to be used with the `length' option. See also the description for the `length' option.

length_bin => NUM

This option is only for compatibility with Math::BigInt::Random. The following two cases are equivalent

  $cls -> new(length_bin => $n);
  $cls -> new(length => $n, base => 2);
length_hex => NUM

This option is only for compatibility with Math::BigInt::Random. The following two cases are equivalent

  $cls -> new(length_hex => $n);
  $cls -> new(length => $n, base => 16);
OBJECT -> generate ( COUNT )
OBJECT -> generate ( )

Generates the given number of random numbers, or one number, if no input argument is given.

  # Generate ten random numbers:

  my @num = $gen -> generate(10);

TODO

  • Add a way to change the core uniform random number generator. Currently, CORE::rand() is used, but it would be nice to be able to switch to, e.g., Math::Random::random_uniform_integer().

  • Add functionality similar to the `use_internet' parameter argument in Math::BigInt::Rando::random_bigint(). This could be implemented using, e.g., Net::Random.

  • Add more tests.

NOTES

To fully understand how Math::BigInt::Random::OO works, one must understand how Perl's CORE::rand() works.

Details on CORE::rand()

CORE::rand() is Perl's own function for generating uniformly distributed pseudo-random integers. The core of CORE::rand() is an internal function, let's call it RAND(), which generates uniformly distributed pseudo-random integers greater than or equal to 0 and less 2**RANDBITS. CORE::rand() is implemented equivalently to

                     K * RAND()
  CORE::rand(K) = ---------------
                   2 ** RANDBITS

One may think of the output of RAND() as a integer consisting of RANDBITS bits, where each bit is 0 or 1 with a 50% chance of each. To get a random integer with all RANDBITS bits, one must use

  CORE::rand(2 ** RANDBITS)

Similarely, to get the first N bits, where N must be less than or equal to RANDBITS, use

  int CORE::rand(2 ** N)

The commonly used idiom for generating a random integer in Perl,

  int CORE::rand(K)

only returns uniformly distributed numbers when K is a power of two no lager than RANDBITS.

You can see the number of RANDBITS in your Perl with

  use Config;
  print $Config{randbits};

or on the command line with

  perl -MConfig -wle 'print $Config{randbits}'

or, in new versions of Perl, also

  perl -V:randbits

More on Math::BigInt::Random::OO -> generate()

The goal is to generate a uniformly distributed random integer X greater than or equal to Xmin and less than or equal to Xmax. The core of the generate() method is an algorithm that generates a uniformly distributed non-negative random integer U < 2**N, where N is the smallest integer so that 2**N is larger than the range R = Xmin - Xmax. Equivalently, N = 1 + int(log(R)/log(2)). If the generated integer U is larger than R, that value is rejected and a new U is generated. This is done until U is less than or equal to R. When a U is accepted, X = U - Xmin is returned.

A uniformly distributed non-negative random integer U < 2**N is generated by combining smaller uniformly distributed non-negative random integer V < 2**M, where M less than or equal to RANDBITS. Each of the smaller random integers is generated with CORE::rand().

Here is an example: Assume RANDBITS is 15, which is not uncommon, and the range is 10,000,000,000. The smallest power of two larger than 10,000,000,000 is 2**34 = 17,179,869,184. Since 34 is 4 + 15 + 15, a uniformly distributed non-negative random integer U < 17,179,869,184 is generated by combining three uniformly distributed non-negative random integers, U2 < 2**4, U1 < 2**15, and U0 < 2**15.

The following Perl code handles this special case, and produces a uniformly distributed random integer U greater than or equal to R:

  $R = Math::BigInt->new('10_000_000_000');   # range

  do {
      $U2 = Math::BigInt->new(int CORE::rand 2**4);
      $U1 = Math::BigInt->new(int CORE::rand 2**15);
      $U0 = Math::BigInt->new(int CORE::rand 2**15);
      $U  = (($U2 * 2**15) + $U1) * 2**15 + $U0;
  } until $U <= $R;

Problems with Math::BigInt::Random

I wrote this module partly since Math::BigInt::Random v0.04 is buggy, and in many cases slower, and partly because I prefer an object-oriented interface. The bugs in Math::BigInt::Random v0.04 are

  • When the range (the maximum value minus the minimum value) is smaller than 1048575 (fffff hexadecimal), the maximum value will never be returned.

  • When Perl has been compiled with a number of RANDBITS less than 20, certain values will never occur.

  • When the range is not a power of two, certain values are more likely to occur than others.

The core of this two last problems is the use of int(rand(X)), which only returns uniformly distributed numbers when X is a power of two no larger than RANDBITS.

In addition, the function Math::BigInt::Random::random_bigint() generates only one random integer at a time, and in doing so, there is some overhead. In Math::BigInt::Random::OO, this overhead is placed in the new() constructor, so it is done only once, independently of how many random numbers are generated by the generator() method.

CAVEATS

  • Some versions of Perl are compiled with the wrong number of RANDBITS. This module has way to detect if this is the case.

  • Some versions of CORE::rand() behave poorly. For intance, in some implementations

      rand(1 << $Config{randbits}) % 2

    alternates between 0 and 1 deterministically.

BUGS

There are currently no known bugs.

Please report any bugs or feature requests to bug-math-bigint-random-oo at rt.cpan.org, or through the web interface at http://rt.cpan.org/Public/Bug/Report.html?Queue=Math-BigInt-Random-OO I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

  perldoc Math::BigInt::Random::OO

You can also look for information at:

SEE ALSO

Math::BigInt::Random(3), Math::Random(3), Net::Random(3).

AUTHOR

Peter John Acklam, <pjacklam@cpan.org>

COPYRIGHT & LICENSE

Copyright 2010 by Peter John Acklam <pjacklam@cpan.org>

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.0 or, at your option, any later version of Perl 5 you may have available.