Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

generate random number without using any built in function in perl?

by anurag_perl (Novice)
on May 08, 2013 at 19:12 UTC ( #1032666=perlquestion: print w/ replies, xml ) Need Help??
anurag_perl has asked for the wisdom of the Perl Monks concerning the following question:

Hi Everybody, So far in perl, for random number generation we use rand function. But, Can anyone explain on how to generate a random number without using perl built rand function. The generation of random number can be any number or without repetitive number or within a range? with best time complexity. Regards, Anurag Hi EveryBody, I've posted this thread to collect few methods on how you choose the logic to generate the random number. But I see people being frustated saying why do you need to use?? This is a research I'm doing on my own to collect information. Regards, Anurag

Comment on generate random number without using any built in function in perl?
Re: generate random number without using any built in function in perl?
by moritz (Cardinal) on May 08, 2013 at 19:31 UTC
Re: generate random number without using any built in function in perl?
by hdb (Prior) on May 08, 2013 at 19:48 UTC
Re: generate random number without using any built in function in perl?
by kennethk (Monsignor) on May 08, 2013 at 20:08 UTC

    Not to be obtuse, but why can't you use rand? This smacks of an XY Problem. There are a myriad of ways to generate pseudom random series, and the appropriate solution depends very strongly on the intended purpose. 'Best time complexity' is solved by xkcd://221, which is probably not what you mean. Most Linux boxes have /dev/random at their disposal for truly high quality randomness, but this is overkill for nearly every application, and denies the possibility of playback.

    ~$ perl -e 'open $rnd, "<", "/dev/random"; read $rnd, $value, 4; prin +t "Value = ", unpack ("H*", $value), "\n"' Value = 0de13803
    Equivalent functionality can be garnered on other systems with TrulyRandom. These are very slow, though still 'Best time complexity'.

    Describe your application, and the quality of the guidance we can provide will improve dramatically.


    #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

      In all obtuseness, shouldn't the comment in the xkcd code be "guaranteed to have been random"?

      Not to be obtuse, but why can't you use rand? This smacks of an XY Problem.

      Yes, I fully agree.

      To the OP: please tell us why you can't (or don't want to) use the Perl random number generator, which is, I think, of a high quality and has been well tested over many years, and would want to go for something else, which is likely to work much less properly unless you are willing to commit huge amount of time to test how well it performs.

      I once made a very basic pseudo random number generator, because I did not have any library available to do that for me in the environment that I was using. It ended up working for the purpose that I had, because the requirement was really not demanding. But trying to do that, you figure out that this is a very difficult problem, and sometimes very clever ideas fail miserably. (I knew it was quite difficult before I started, but I did not realize how much more difficult than I thought it was.)

      I would suggest that you take a look at Donald Knuth's "The Art of of Computer Programming", Volume 2, Seminumerical Algorithms, Chapter 3, Random Numbers. Once you've read through the 190 pages (in the edition that I own) devoted to random numbers, I think that you will agree that you probably don't want a "quick fix" solution to such a complicated problem. Using a well tested library is far safer in probably more than 99.99% of the cases.

Re: generate random number without using any built in function in perl?
by InfiniteSilence (Curate) on May 08, 2013 at 20:21 UTC

    This is probably bad if you don't have an Internet connection, but oh well..

    perl -MHTML::TreeBuilder -e 'use LWP::Simple; my $page = get(qq|http:/ +/www.random.org/integers/?num=100&min=1&max=100&col=5&base=10&format= +html&rnd=new|); my $parser = HTML::TreeBuilder->new_from_content($pag +e); print $parser->look_down(qq|class|,qq|data|)->as_text;'

    Celebrate Intellectual Diversity

Re: generate random number without using any built in function in perl?
by tobyink (Abbot) on May 08, 2013 at 21:27 UTC

    OK, here's an example. It's not anything like a useful random number generator for cryptographic purposes, but looks fairly random at a first glance...

    use v5.12; { my $seed = time; sub myrand { do { $seed *= $seed; $seed =~ s/[^0-9]//g; my $midpoint = int(length($seed) / 2); $seed = substr($seed, 0, $midpoint) . substr($seed, $midpo +int); $seed = substr($seed, 0, 9); } until ($seed > 10_000_000); my $r = reverse substr($seed, 0, 6); my $lim = @_ ? shift : 1; $lim * ($r/1_000_000); } } # 50 random numbers less than 10... say myrand(10) for 1..50;
    package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name
Re: generate random number without using any built in function in perl?
by BrowserUk (Pope) on May 08, 2013 at 22:42 UTC

    #! perl -slw use strict; use Data::Dump qw[ pp ]; use threads; use threads::shared; my $rand :shared = chr(0)x4; async( sub { use bytes; my $tid = shift; --vec( $rand,$tid,8) while 1; }, $_ )->detach for 0 .. 3; our $M //= 24; our $N //= 1e4; my %stats; ++$stats{ unpack( 'V', $rand ) % $M } for 1 .. $N; pp \%stats; __END__ C:\test>rand { "0" => 499, 1 => 380, 2 => 296, 3 => 450, 4 => 373, 5 => 395, 6 => 465, 7 => 445, 8 => 423, 9 => 465, 10 => 446, 11 => 515, 12 => 433, 13 => 424, 14 => 441, 15 => 423, 16 => 364, 17 => 308, 18 => 403, 19 => 373, 20 => 516, 21 => 368, 22 => 352, 23 => 443, }

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: generate random number without using any built in function in perl?
by davido (Archbishop) on May 08, 2013 at 23:40 UTC

    There are a number of well-documented Pseudo Random Number Generation algorithms available for the searching on the 'net. Each has strengths and weaknesses, and all will produce pseudo-random numbers (even Perl's rand produces pseudo-random numbers).

    There are varying qualities of pseudo-random number generators; some are adequate for general purpose use (Perl's rand, for example). Some are suitable for Monte Carlo simulations (Mersenne Twister, for example), and some are suitable for cryptographic purposes (A block cypher in counter mode, or ISAAC, for example).

    All of these need to be seeded somehow. Perl's built-in PRNG seeds using a combination of time, process ID, and some bit twiddling, if I'm not mistaken. Porting one of the well-known algorithms to Perl is only half the problem (and in the case of many of the common algorithms, one that's already been solved on CPAN). The other half of the problem is seeding. Perl's method of seeding is again adequate for "general purpose" use. But for more stringent uses, there are more robust techniques; reading from /dev/urandom (non-blocking), or /dev/random (blocking), or through Windows API calls (Windows XP or newer). Seeding in a way that is portable across a bunch of systems is best handled through a module like Dana Jacobsen's Crypt::Random::Seed, which abstracts away the platform specifics, allowing it to be portably useful. On systems where no "standard" entropy pool is available, degrades gracefully to Crypt::Random::TESHA2 (short for Timer Entropy => SHA2).

    So to summarize, if I were to write a random number generator that avoided rand, I would first ask what it will be used for. Then I will evaluate the many well-known PRNG algorithms to determine which one meets those needs. After porting its code to Perl (or better, after finding it on CPAN), I would then go looking at how strong of a seed I need, and would probably end up using Dana's module regardless, since it's so convenient and provides options for non-blocking sources.

    Finally, I would use tests such as FIPS140-2 to evaluate the quality of the randomness. Of course there are as many types of randomness tests as there are types of PRNGs, so you have to pick ones that test for your use case (ie, statistical use might test differently than crypto use).

    The last thing I would do, however, is try to invent my own PRNG algorithm. There's at least 40 years of prior art available to learn from.


    Dave

      Why use pseudo-random when you can have random? :)


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

        It's an interesting concept. If I understand (and please correct me if I'm wrong), you're using the unpredictability of the relationship between a few asynchronous threads as an entropy source, and then reducing that entropy to, in this case, a range of 0 .. 23, though it could just as easily be full bytes, or something else.

        When I run it with threaded Perl 5.14.2 on Ubuntu 13.04 (the only threaded Perl I have built at the moment), my distributions are not nearly so nice as yours. I keep seeing things like:

        { "0" => 3810, "2" => 5960, "16" => 230 }

        I have no idea why there's a difference. I fiddled with different numbers of threads, but that didn't produce appreciable improvements toward getting a smoother distribution.

        I also wonder if you need to consider modulo bias. Well, actually looking at the code again, I don't wonder, I'm pretty sure modulo bias can be an issue if $M is set to a number that doesn't divide evenly into 2^32.

        Initially I intended to test your code with A Perl adaptation of the FIPS-140-2 test, and A randomness dispersion test, but it doesn't take that sharp of an instrument to spot clusters when there are only three numbers drawn out of a possible 24 given thousands of picks.

        Any thoughts why this works for you and not for me?


        Dave

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1032666]
Approved by tobyink
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (8)
As of 2014-09-23 10:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (218 votes), past polls