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,ASCII-7-bit X-Google-Thread: 103376,10c4b1e7e98e6a93 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-26 19:47:13 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!cox.net!news-east.rr.com!chnws02.ne.ipsvc.net!cyclone.ne.ipsvc.net!24.128.8.70!typhoon.ne.ipsvc.net.POSTED!not-for-mail Message-ID: <3CF19E8E.9090304@attbi.com> From: "Robert I. Eachus" Organization: Eachus Associates User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020314 Netscape6/6.2.2 X-Accept-Language: en,pdf MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Problems with Ada.Real_Time on GNAT? References: <28d8936a.0205161133.3c9064b7@posting.google.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Date: Mon, 27 May 2002 02:42:57 GMT NNTP-Posting-Host: 24.61.239.24 X-Complaints-To: abuse@attbi.com X-Trace: typhoon.ne.ipsvc.net 1022467377 24.61.239.24 (Sun, 26 May 2002 22:42:57 EDT) NNTP-Posting-Date: Sun, 26 May 2002 22:42:57 EDT Xref: archiver1.google.com comp.lang.ada:24844 Date: 2002-05-27T02:42:57+00:00 List-Id: file13 wrote: > Hi guys. There was a silly little contest on a web BBS where people > were asked to write a program in any language (rules in the source). > I decided to represent for us Ada folks and produced this on GNAT 3.14 > on Windows 2000 > > http://www.qlippoth.com/shuffle.adb Normally I would fault you on your approach. Randomizing a list this way is biased. This can easily be seen by the fact that if N=3, there are 3**3 = 27 possible random sequences, and 3! = 6 random permutations. So some permutations must occur more often than others. (In this case, the permutations 132, 213, and 231 will occur more often than 123, 312, and 321.) One million is a large enough sample that this won't be a problem. (But notice that the bias is still there-- 1000000! does not evenly divide 1000000**1000000. ;-) The way to avoid the problem for small arrays is to generate N random floats (or integers) do an index sort of that list, and use that as the result. But at 1000000 values, float random variates over [0.0..1.0) don't have enough potential different values to avoid a significant number of collisions. Using (32-bit) integer variates will help, but again the bias is probably not an issue for N > 100. Just don't use the technique in this program to shuffle a deck of cards. ;-) Incidently I did compare the two techniques in this case, and the sorting method was slower, but not significantly so. (I used a quicksort, this is a case where a radix sort might be better.)