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,583275b6950bf4e6 X-Google-Attributes: gid103376,public X-Google-Thread: fdb77,5f529c91be2ac930 X-Google-Attributes: gidfdb77,public X-Google-Thread: 1108a1,59ec73856b699922 X-Google-Attributes: gid1108a1,public X-Google-ArrivalTime: 2003-05-11 14:57:57 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!arclight.uoregon.edu!wn13feed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi_feed4!attbi.com!sccrnsc04.POSTED!not-for-mail Message-ID: <3EBEC762.3030705@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.java.advocacy,comp.object,comp.lang.ada Subject: Re: Using Ada for device drivers? (Was: the Ada mandate, and why it collapsed and died) References: <9fa75d42.0304230424.10612b1a@posting.google.com> <9fa75d42.0304240446.493ca906@posting.google.com> <3EA7E0E3.8020407@crs4.it> <9fa75d42.0304240950.45114a39@posting.google.com> <4a885870.0304291909.300765f@posting.google.com> <416273D61ACF7FEF.82C1D1AC17296926.FF0BFD4934A03813@lp.airnews.net> <9fa75d42.0305010621.55e99deb@posting.google.com> <0-WcnWfafqsNpiyjXTWcqw@gbronline.com> <1051804573.732603@master.nyc.kbcfp.com> <3EBE9BD4.1050008@attbi.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit NNTP-Posting-Host: 24.62.164.137 X-Complaints-To: abuse@attbi.com X-Trace: sccrnsc04 1052690276 24.62.164.137 (Sun, 11 May 2003 21:57:56 GMT) NNTP-Posting-Date: Sun, 11 May 2003 21:57:56 GMT Organization: AT&T Broadband Date: Sun, 11 May 2003 21:57:56 GMT Xref: archiver1.google.com comp.lang.java.advocacy:63532 comp.object:63211 comp.lang.ada:37200 Date: 2003-05-11T21:57:56+00:00 List-Id: Robert I. Eachus wrote: > My favorite example is a program I wrote in a few hours to demonstrate > the "right" way to generate random permutations in Ada. Hyman Rosen wrote: > I think this is a perfect example of the blind spot of Ada programmers. > You are so enamored of enumerations and perfectly indexed arrays and > lack of buffer overflows that you will probably miss the most likely > and subtle bug of this kind of code, which is that the Shuffle routine > fails to produce each possible permutation with uniform probability! Did you read what I wrote, really? Should I have included the notes in the Shufflling routine which showed why this particular method of generation permutations was unbiased? Okay done: procedure Shuffling (List : in out List_Type; Gen : in Generator) is -- a routine for producing permutations of a list of elements. Note -- that this method is unbiased for any independent sequence. (For -- any two cards the possibility that they will be in a particular -- order is exactly 1/2, this can be extended by iteration to show -- that each sequence has a probablity of 1/N! Note that for large -- lists of elements not all permutations will be generated. There -- are N! permutations of a list of N values, and this may be much -- greater than the number of generator states. Note also that the -- actual number of different possible permutations generated from -- one starting seed is k/GCD(N,k) for a generator with k states. List_Copy : constant List_Type := List; type Rec is record Index : Index_Type; Rand : Float; end record; type Rec_Array is array (Index_Type range <>) of Rec; Temp : Rec_Array(List'Range); function "<" (L, R: Rec) return Boolean is begin return L.Rand < R.Rand; end "<"; procedure Sort is new Sorting(Rec, Index_Type, Rec_Array, "<"); begin for I in Temp'Range loop Temp(I) := (I, NFR.Random(Gen)); end loop; Sort(Temp); -- Sort based on value of random number -- Now rearrange List based on the order of indices in Temp for I in List'Range loop List(I) := List_Copy(Temp(I).Index); end loop; end Shuffling; Again, no subtlety present or wanted. Note that for Ada, the generator you get from Ada.Numerics.Float_Random will usually have more that 2^32 states. If it is the one I wrote that is in Gnat, the GCD mentioned will be one, unless N has a factor that is one of two five digit primes. Oh, and this is the body of a generic where Element_Type, List_Type, and Index_Type are generic parameters. Okay? No? Well if you really need a longer period generator, write me. The other alternative is to combine two generators with independent seeds and periods. Adding typical [0..1) generators and if >1, subtracting 1 works just fine unless one of the generators is biased. In fact, for most tests of randomness, you get more random behavior than either generator alone.