From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,CP1252 X-Google-Thread: 103376,3e9f592176b8fb05 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-07-25 08:34:17 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!wn14feed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi.com!sccrnsc04.POSTED!not-for-mail Message-ID: <3F214DF6.6010102@attbi.com> From: "Robert I. Eachus" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.2) Gecko/20021120 Netscape/7.01 X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Random Number Generator Problem References: <30c81431.0307250634.77148b62@posting.google.com> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit NNTP-Posting-Host: 66.31.71.243 X-Complaints-To: abuse@comcast.net X-Trace: sccrnsc04 1059147256 66.31.71.243 (Fri, 25 Jul 2003 15:34:16 GMT) NNTP-Posting-Date: Fri, 25 Jul 2003 15:34:16 GMT Organization: Comcast Online Date: Fri, 25 Jul 2003 15:34:16 GMT Xref: archiver1.google.com comp.lang.ada:40809 Date: 2003-07-25T15:34:16+00:00 List-Id: Brien wrote: > When I run this code, i get 9,233,........,808 (which is 2**63) as > about half of my results. There are two problems here. The first, which you should definitely report to ACT, is that the code for the discrete generator uses (long_)integers. Obviously 2**64 > 2**63, so there is a problem here. The fix is that when generating values of this type, the bounds should be Long_Integer'First and Long_Integer'Last, not 0 and Max_Binary_Modulus. There is a line in the algorithm which folds out of range values into the largest possible value. For normal ranges, this line preserves the unbiased nature of the results. But in this case, half the results (generated as Long_Floats) will be out of range for the (intermediate) Long_Integer type. The second problem is that you may be trying to accomplish something that the Ada RM does not promise. The algorithm as written will generate many more than 2**32 values. (About 2**50 but I'd have to dig out my documentation to get the exact number of possible values.) If you really need the possibility of 2**64 unbiased values, there are few, if any, RNGs outside of cryptography that will do what you want. The GNAT generator IS a cryptographic generator with a few cheats to make it highly efficient--but not useful for cryptographic purposes. I just haven't gotten around to generating a version of the algorithm that will provide 2**64 unbiased values. If you haven't guessed, this will take several days of CPU time (in the background on this machine is fine) to find the necessary constants, plus modifications to the generator code. So, how many values do you really need? And are there other characteristics that you need? It is probably the case that I can give you some code that takes twice as long as the GNAT generator and does what you need. (Notice though that it will take years to generate all of the possible values for the current generator, even on today's fastest CPUs. So I thought I had a few years before this issue became urgent.) -- Robert I. Eachus �In an ally, considerations of house, clan, planet, race are insignificant beside two prime questions, which are: 1. Can he shoot? 2. Will he aim at your enemy?� -- from the Laiden novels by Sharon Lee and Steve Miller.