* Re: Ada2005 random @ 2003-04-03 12:27 David C. Hoos, Sr. 2003-04-03 12:39 ` Peter Hermann 0 siblings, 1 reply; 32+ messages in thread From: David C. Hoos, Sr. @ 2003-04-03 12:27 UTC (permalink / raw) To: comp.lang.ada mail to news gateway; +Cc: ica2ph ----- Original Message ----- From: "Peter Hermann" <ica2ph@sinus.csv.ica.uni-stuttgart.de> Newsgroups: comp.lang.ada To: <comp.lang.ada@ada.eu.org> Sent: April 03, 2003 3:56 AM Subject: Re: Ada2005 random > Lutz and all, > > * Peter Hermann wrote: > >> In an application I need a variable discrete random function. > ^^^^^^^^ > with "variable" I meant the following flexibility, e.g. : > a := random(generator1, 1 , 9); > b := random(generator1, 1 , 8); > c := random(generator1, 3 , 7); Such an approach is statistcally dubious, since the same generator is being used for all draws. Normally, one would use a distinct generator for each sequence. > _______________________________________________ > comp.lang.ada mailing list > comp.lang.ada@ada.eu.org > http://ada.eu.org/mailman/listinfo/comp.lang.ada > > ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-03 12:27 Ada2005 random David C. Hoos, Sr. @ 2003-04-03 12:39 ` Peter Hermann 2003-04-03 22:10 ` Randy Brukardt 2003-04-04 8:27 ` 0 siblings, 2 replies; 32+ messages in thread From: Peter Hermann @ 2003-04-03 12:39 UTC (permalink / raw) David C. Hoos, Sr. <david.c.hoos.sr@ada95.com> wrote: > Such an approach is statistically dubious, since the same generator is > being used for all draws. Normally, one would use a distinct > generator for each sequence. agreed: this is of course not a purist's approach although I could live with it in the practice. Using Lutz Do's code (thank you) should do the job. Do you have a better idea how to pick out randomly from a set with an always changing number of members? -- --Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de --Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen --http://www.csv.ica.uni-stuttgart.de/homes/ph/ --Team Ada: "C'mon people let the world begin" (Paul McCartney) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-03 12:39 ` Peter Hermann @ 2003-04-03 22:10 ` Randy Brukardt 2003-04-04 7:43 ` Peter Hermann ` (2 more replies) 2003-04-04 8:27 ` 1 sibling, 3 replies; 32+ messages in thread From: Randy Brukardt @ 2003-04-03 22:10 UTC (permalink / raw) Peter Hermann wrote in message ... >David C. Hoos, Sr. <david.c.hoos.sr@ada95.com> wrote: >> Such an approach is statistically dubious, since the same generator is >> being used for all draws. Normally, one would use a distinct >> generator for each sequence. > >agreed: this is of course not a purist's approach >although I could live with it in the practice. >Using Lutz Do's code (thank you) should do the job. >Do you have a better idea how to pick out randomly from a set with >an always changing number of members? When I wanted to do that, I just borrowed the code from the Ada random number generator. In all of the implementations I've seen, the actual generator is the float one; the integer one just uses some code to return the proper value. I just made a function that did that with variable bounds instead of the generic ones. I needed that for a 'choosing' algorithm, say drawing balls one by one out of a bowl. If you have 8 balls originally, you're choosing 1 out of 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and discarding the useless ones, the second last draw can take a very long time (only 2 out of 8 choices are meaningful). I'm pretty sure that this is a valid technique; certainly the underlying float generator is still random (at least as much as it ever was!), and the use of that result is unbiased. While it would be nice if Ada supported this directly, it's easy enough to write it yourself. Randy Brukardt. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-03 22:10 ` Randy Brukardt @ 2003-04-04 7:43 ` Peter Hermann 2003-04-04 10:21 ` Dale Stanbrough 2003-04-04 12:20 ` Stuart Palin 2 siblings, 0 replies; 32+ messages in thread From: Peter Hermann @ 2003-04-04 7:43 UTC (permalink / raw) Randy Brukardt <randy@rrsoftware.com> wrote: > While it would be nice if Ada supported this directly, it's easy enough that's it. However, it should be well crafted and therefore not necessarily my initial proposal, because with this one I am feeling statistically uncomfortable ;-) As Christoph Grein pointed out, the starting point is A.5.2(50-54). A valuable Ada2005 pret-a-porter user call need to be well thought over. -- --Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de --Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen --http://www.csv.ica.uni-stuttgart.de/homes/ph/ --Team Ada: "C'mon people let the world begin" (Paul McCartney) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-03 22:10 ` Randy Brukardt 2003-04-04 7:43 ` Peter Hermann @ 2003-04-04 10:21 ` Dale Stanbrough 2003-04-04 12:11 ` Stuart Palin ` (3 more replies) 2003-04-04 12:20 ` Stuart Palin 2 siblings, 4 replies; 32+ messages in thread From: Dale Stanbrough @ 2003-04-04 10:21 UTC (permalink / raw) Randy Brukardt wrote: > I needed that for a 'choosing' algorithm, say drawing balls one by one > out of a bowl. If you have 8 balls originally, you're choosing 1 out of > 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and > discarding the useless ones, the second last draw can take a very long > time (only 2 out of 8 choices are meaningful). I'm pretty sure that this > is a valid technique; certainly the underlying float generator is still > random (at least as much as it ever was!), and the use of that result is > unbiased. > > While it would be nice if Ada supported this directly, it's easy enough > to write it yourself. How about for i in reverse 8..2 loop put (random (blah) mod i); end loop; ? dale ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 10:21 ` Dale Stanbrough @ 2003-04-04 12:11 ` Stuart Palin 2003-04-04 14:25 ` Lutz Donnerhacke ` (2 subsequent siblings) 3 siblings, 0 replies; 32+ messages in thread From: Stuart Palin @ 2003-04-04 12:11 UTC (permalink / raw) Dale Stanbrough wrote: > How about > > for i in reverse 8..2 loop > > put (random (blah) mod i); > > end loop; Of the many problems with this bit of code, perhaps the most serious is the bias it introduces to the randomness. Consider if random returned a value 0..10, then taking the result mod 8 would give 2 ways of getting 0..2 but only one way of getting 3..7. Similar skew exist for other cases (except 5). -- Stuart Palin ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 10:21 ` Dale Stanbrough 2003-04-04 12:11 ` Stuart Palin @ 2003-04-04 14:25 ` Lutz Donnerhacke 2003-04-04 21:51 ` Dale Stanbrough 2003-04-05 6:46 ` Martin Krischik 2003-04-13 14:56 ` Robert I. Eachus 3 siblings, 1 reply; 32+ messages in thread From: Lutz Donnerhacke @ 2003-04-04 14:25 UTC (permalink / raw) * Dale Stanbrough wrote: > How about > for i in reverse 8..2 loop > put (random (blah) mod i); > end loop; > ? This is not uniformly distributed. Don't use that! ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 14:25 ` Lutz Donnerhacke @ 2003-04-04 21:51 ` Dale Stanbrough 2003-04-05 18:34 ` Samuel Tardieu 0 siblings, 1 reply; 32+ messages in thread From: Dale Stanbrough @ 2003-04-04 21:51 UTC (permalink / raw) In article <slrnb8r5e4.ov.lutz@taranis.iks-jena.de>, Lutz Donnerhacke <lutz@iks-jena.de> wrote: > * Dale Stanbrough wrote: > > How about > > for i in reverse 8..2 loop > > put (random (blah) mod i); > > end loop; > > ? > > This is not uniformly distributed. Don't use that! If the random numbers are uniformly distributed, why wouldn't a window on that distribution also be uniformly distributed? Could you give an example? Dale ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 21:51 ` Dale Stanbrough @ 2003-04-05 18:34 ` Samuel Tardieu 0 siblings, 0 replies; 32+ messages in thread From: Samuel Tardieu @ 2003-04-05 18:34 UTC (permalink / raw) >>>>> "Dale" == Dale Stanbrough <dstanbro@bigpond.net.au> writes: Dale> If the random numbers are uniformly distributed, why wouldn't a Dale> window on that distribution also be uniformly distributed? "mod" does not create a window. Dale> Could you give an example? Suppose that random numbers are uniformly distributed over the set {0,1,2}. Apply "mod 2" to that, you get {0,1,0}. The probability of getting a 0 is twice the one of getting a 1. Sam -- Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/sam ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 10:21 ` Dale Stanbrough 2003-04-04 12:11 ` Stuart Palin 2003-04-04 14:25 ` Lutz Donnerhacke @ 2003-04-05 6:46 ` Martin Krischik 2003-04-07 21:07 ` Randy Brukardt 2003-04-13 14:56 ` Robert I. Eachus 3 siblings, 1 reply; 32+ messages in thread From: Martin Krischik @ 2003-04-05 6:46 UTC (permalink / raw) On Fri, 04 Apr 2003 10:21:44 +0000, Dale Stanbrough wrote: > Randy Brukardt wrote: > > > for i in reverse 8..2 loop Should that not be: for i in reverse 2 .. 8 loop on in full: for i in reverse Integer range 2 .. 8 loop > > put (random (blah) mod i); > > end loop; With Regards Martin -- Martin Krischik mailto://Martin@krischik.com http://ada.krischik.com ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-05 6:46 ` Martin Krischik @ 2003-04-07 21:07 ` Randy Brukardt 0 siblings, 0 replies; 32+ messages in thread From: Randy Brukardt @ 2003-04-07 21:07 UTC (permalink / raw) Martin Krischik wrote in message ... >On Fri, 04 Apr 2003 10:21:44 +0000, Dale Stanbrough wrote: > >> Randy Brukardt wrote: >> >> >> for i in reverse 8..2 loop > >Should that not be: > >for i in reverse 2 .. 8 loop Yes, of course. Randy. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 10:21 ` Dale Stanbrough ` (2 preceding siblings ...) 2003-04-05 6:46 ` Martin Krischik @ 2003-04-13 14:56 ` Robert I. Eachus 2003-04-13 21:58 ` Mark Biggar 3 siblings, 1 reply; 32+ messages in thread From: Robert I. Eachus @ 2003-04-13 14:56 UTC (permalink / raw) Dale Stanbrough wrote: > Randy Brukardt wrote: > > >>I needed that for a 'choosing' algorithm, say drawing balls one by one >>out of a bowl. If you have 8 balls originally, you're choosing 1 out of >>7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and >>discarding the useless ones, the second last draw can take a very long >>time (only 2 out of 8 choices are meaningful). I'm pretty sure that this >>is a valid technique; certainly the underlying float generator is still >>random (at least as much as it ever was!), and the use of that result is >>unbiased. >> >>While it would be nice if Ada supported this directly, it's easy enough >>to write it yourself. If you need a permutation, the best way to do it is to generate a set of random (float) values, associate them with the data to be permuted and the sort on this key. I have seen a lot of code that attempts to permute a list by going through the list and exchanging elements. For lists of length greater than two this can easily be shown to be biased. For example there are 3! = 6 possible permutions of a list of three elements, the usual version of the swapping algorithm has 3^3 = 27 possible outcomes, another (worse) variation has 2^3 = 8 different outcomes. In either case the number of outcomes is not evenly divisible by the number of different permutations. Even if you do this, there is another potential problem. For a set of size N, there are N! possible permutations. For example for a deck of cards, there are 52! possible permutations. If you are generating bridge hands, there are 52!/(13!)^4 different possible deals. Now if you are taking the (pseudo-)random sequence from a single generator, there will be at most as many different possible hands as there are possible starting seeds for the generator. For the generator that I wrote, which AFAIK is still used by GNAT, if you use the time based version of Reset, there are more than 2^32 possible starting values, but of course, they won't all occur in a particular year. If you really, really care about making it possible to generate a large fraction of all possible permutations, the way to do it is to take several generators with seeds generated based on different random data, then shuffle the deck more than once. This program should serve as an example of how to do this. (Note, I don't claim this is "right" since I don't use two generators, and shuffle twice.) with Ada.Numerics.Float_Random; package Statistics is subtype Generator is Ada.Numerics.Float_Random.Generator; type Direction is (Ascending, Descending); generic type Element_Type is private; type Index_Type is (<>); type List_Type is array (Index_Type range <>) of Element_Type; with function "<" (L, R : Element_Type) return Boolean is <>; procedure Sorting (List : in out List_Type); -- General-purpose sorting procedure generic type Element_Type is private; type Index_Type is (<>); type List_Type is array (Index_Type range <>) of Element_Type; procedure Shuffling (List : in out List_Type; Gen : in Generator); -- Permute the contents of List randomly end Statistics; ------------------------------------------------------------------------ with Ada.Numerics.Float_Random; package body Statistics is package NFR renames Ada.Numerics.Float_Random; -- generic -- type Element_Type is private; -- type Index_Type is (<>); -- type List_Type is array (Index_Type range <>) of Element_Type; -- with function "<" (L, R : Element_Type) return Boolean is <>; procedure Sorting (List : in out List_Type) is -- Quicksort Part : Element_Type; First : Index_Type; Last : Index_Type; begin -- Don't break on short lists; if List'Length <= 1 then return; elsif List'Length = 2 then if List(List'Last) < List(List'First) then Part := List(List'First); List(List'First) := List(List'Last); List(List'Last) := Part; end if; return; end if; -- now it is safe to assume that List'First and List'Last -- are in range. First := List'First; Last := List'Last; -- choose partition value Part := List(First); -- partition list Main_Loop: loop if Part < List(Last) then Last := Index_Type'PRED(Last); exit Main_Loop when Last=First; else List(First) := List(Last); First := Index_Type'SUCC(First); exit Main_Loop when Last=First; while List(First) < Part loop First := Index_Type'SUCC(First); exit Main_Loop when Last=First; end loop; List(Last) := List(First); Last := Index_Type'PRED(Last); exit Main_Loop when Last=First; end if; end loop Main_Loop; List(First) := Part; -- at this point First = Last. Sorting(List(List'First..Index_Type'PRED(Last))); Sorting(List(Index_Type'SUCC(Last)..List'Last)); end Sorting; -- generic -- type Element_Type is private; -- type Index_Type is (<>); -- type List_Type is array (Index_Type range <>) of Element_Type; procedure Shuffling (List : in out List_Type; Gen : in Generator) is 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; end Statistics; --------------------------------------------------------------------------- with Ada.Numerics.Float_Random; with Statistics; with Text_IO; use Text_IO; procedure Bridge_Hands is -- a procedure to produce random (but sorted) bridge hands for duplicate. package NFR renames Ada.Numerics.Float_Random; Gen: NFR.Generator; function Rand(G: in NFR.Generator := Gen) return Float renames NFR.Random; type Direction is (North, East, South, West); type Suits is (Spades, Hearts, Diamonds, Clubs); type Ranks is (Ace, King, Queen, Jack, Ten, Nine, Eight, Seven, Six, Five, Four, Three, Deuce); Display_Suit: constant array(Suits) of Character := "SHDC"; Display_Rank: constant array(Ranks) of Character := "AKQJT98765432"; subtype Dealer_Name is String(1..5); Display_Dealers: constant array(0..3) of Dealer_Name := ("North", "East ", "South", "West "); subtype Vulnerability is String(1..11); Display_Vulnerability: constant array(0..3) of Vulnerability := ("None ","North/South","East/West ","Both "); package Int_IO is new Text_IO.Integer_IO(Integer); Number_of_Hands: Integer; type Card is record Suit: Suits; Rank: Ranks; end record; type Card_Array is array (Natural range <>) of Card; Deck: Card_Array(0..51); subtype Hand is Card_Array(0..12); Hands: array(Direction) of Hand; function By_Rank(L,R: Card) return Boolean is begin return L.Rank < R.Rank; end By_Rank; pragma INLINE(By_Rank); procedure Sort_Hand is new Statistics.Sorting(Card, Natural, Card_Array, By_Rank); procedure Shuffle is new Statistics.Shuffling(Card, Natural, Card_Array); procedure Deal is begin for I in Hand'Range loop for J in Hands'Range loop Hands(J)(I) := Deck(I*4 + Direction'POS(J)); end loop; end loop; for I in Hands'Range loop Sort_Hand(Hands(I)); -- sort cards by rank, but not by suit. end loop; end Deal; function Cards(D: in Direction; S: in Suits) return String is Temp: String(1..26) := (others => ' '); Index: Natural := 3; begin Temp(1) := Display_Suit(S); for I in Hand'Range loop if Hands(D)(I).Suit = S then Temp(Index) := Display_Rank(Hands(D)(I).Rank); Index := Index + 2; end if; end loop; if Index = 3 then Temp(3..5) := "---"; end if; return Temp; end Cards; begin -- Use time-dependant random numbers: NFR.Reset(Gen); -- Initialize deck. for I in Deck'Range loop Deck(I) := (Suits'VAL(I/13), Ranks'VAL(I mod 13)); end loop; Text_IO.Put_Line("Enter number of hands, default is 32:"); begin Int_IO.Get(Number_of_Hands); exception when others => Number_of_Hands := 32; end; for I in 0..Number_of_Hands - 1 loop Text_IO.New_Page; Text_IO.New_Line(3); Text_IO.Put_Line(" Board: " & Integer'IMAGE(I+1)); Text_IO.Put_Line(" Dealer: " & Display_Dealers(I mod 4)); Text_IO.Put_Line(" Vulnerability: " & Display_Vulnerability((I + I/4) mod 4)); New_Line(3); Shuffle(Deck, Gen); Deal; Text_IO.Put_Line(" NORTH"); Text_IO.New_Line; Text_IO.Put_Line(" " & Cards(North,Spades)); Text_IO.Put_Line(" " & Cards(North,Hearts)); Text_IO.Put_Line(" " & Cards(North,Diamonds)); Text_IO.Put_Line(" " & Cards(North,Clubs)); New_Line(2); Text_IO.Put_Line(" WEST " & " EAST"); Text_IO.New_Line; Text_IO.Put_Line(" " & Cards(West,Spades) & " " & Cards(East,Spades)); Text_IO.Put_Line(" " & Cards(West,Hearts) & " " & Cards(East,Hearts)); Text_IO.Put_Line(" " & Cards(West,Diamonds) & " " & Cards(East,Diamonds)); Text_IO.Put_Line(" " & Cards(West,Clubs) & " " & Cards(East,Clubs)); New_Line(2); Text_IO.Put_Line(" SOUTH"); Text_IO.New_Line; Text_IO.Put_Line(" " & Cards(South,Spades)); Text_IO.Put_Line(" " & Cards(South,Hearts)); Text_IO.Put_Line(" " & Cards(South,Diamonds)); Text_IO.Put_Line(" " & Cards(South,Clubs)); end loop; end Bridge_Hands; ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-13 14:56 ` Robert I. Eachus @ 2003-04-13 21:58 ` Mark Biggar 0 siblings, 0 replies; 32+ messages in thread From: Mark Biggar @ 2003-04-13 21:58 UTC (permalink / raw) Robert I. Eachus wrote: > Dale Stanbrough wrote: > >> Randy Brukardt wrote: >> >> >>> I needed that for a 'choosing' algorithm, say drawing balls one by one >>> out of a bowl. If you have 8 balls originally, you're choosing 1 out of >>> 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and >>> discarding the useless ones, the second last draw can take a very long >>> time (only 2 out of 8 choices are meaningful). I'm pretty sure that this >>> is a valid technique; certainly the underlying float generator is still >>> random (at least as much as it ever was!), and the use of that result is >>> unbiased. >>> >>> While it would be nice if Ada supported this directly, it's easy enough >>> to write it yourself. > > > If you need a permutation, the best way to do it is to generate a set of > random (float) values, associate them with the data to be permuted and > the sort on this key. I have seen a lot of code that attempts to > permute a list by going through the list and exchanging elements. For > lists of length greater than two this can easily be shown to be biased. > > For example there are 3! = 6 possible permutions of a list of three > elements, the usual version of the swapping algorithm has 3^3 = 27 > possible outcomes, another (worse) variation has 2^3 = 8 different > outcomes. In either case the number of outcomes is not evenly divisible > by the number of different permutations. The way I usualy do random array shuffle has no bias for i in reverse 2..n loop j := random(1..i); swap(x(i), x(j)); end loop; that translates to "randomly select with out replacement until the unselected set is empty" and in the 3 item case results in exactly 6 outcomes (first iteration select 1 of 3, second iteration select 1 of 2 for 6 outcomes). -- Mark Biggar mark@biggar.org mark.a.biggar@attbi.com ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-03 22:10 ` Randy Brukardt 2003-04-04 7:43 ` Peter Hermann 2003-04-04 10:21 ` Dale Stanbrough @ 2003-04-04 12:20 ` Stuart Palin 2003-04-07 7:26 ` Jean-Etienne Doucet 2 siblings, 1 reply; 32+ messages in thread From: Stuart Palin @ 2003-04-04 12:20 UTC (permalink / raw) Randy Brukardt wrote: <snip> > I needed that for a 'choosing' algorithm, say drawing balls one by one > out of a bowl. If you have 8 balls originally, you're choosing 1 out of > 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and > discarding the useless ones, the second last draw can take a very long > time (only 2 out of 8 choices are meaningful). I'm pretty sure that this > is a valid technique; certainly the underlying float generator is still > random (at least as much as it ever was!), and the use of that result is > unbiased. Depending on the size of the set, and the nature in which the size changes you could create an initial set and then use one of the many 'shuffling' algorithms readily available (make sure you use one that truly preserves the randomness statistics - ISTR there is a subtle point in one of the most obvious algorithms). You can then simply draw your random selection by moving through the list. There are probably many 'themes' on this idea that you can play around with, depending on your needs. (For instance if your 'set' is a linked list, you could make it a doubly linked list, the secondary link being a random order). -- Stuart Palin ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 12:20 ` Stuart Palin @ 2003-04-07 7:26 ` Jean-Etienne Doucet 2003-04-07 8:09 ` Lutz Donnerhacke 0 siblings, 1 reply; 32+ messages in thread From: Jean-Etienne Doucet @ 2003-04-07 7:26 UTC (permalink / raw) [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #1: Type: text/plain, Size: 1555 bytes --] Randy Brukardt wrote: | | I needed that for a 'choosing' algorithm, say drawing balls one by one | out of a bowl. If you have 8 balls originally, you're choosing 1 out of | 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and | discarding the useless ones, the second last draw can take a very long | time (only 2 out of 8 choices are meaningful). I'm pretty sure that this | is a valid technique; certainly the underlying float generator is still | random (at least as much as it ever was!), and the use of that result is | unbiased. | For this kind of problems, I use the Ada.Numerics.Float_Random generator, along with the function: function Rand (N : Positive) return Positive is -- gives a random integer in the range 1 .. N begin return Integer(Float(N) * Random(Gen) + 0.5); end Rand; It can be used for ranges other than 1 .. N: function Rand (Min, Max : Integer) return Integer is -- gives a random integer in the range Min .. Max begin return Rand(Max - Min + 1) + Min - 1; end Rand; It works as well for enum types: type Enum is (...); function Random_Enum return Enum is -- gives a random Enum value begin return Enum'Val(Rand(Enum'Pos(Enum'Last) + 1) - 1); end Random_Enum; I've never had a problem with this. _______________________________________________________________________________ Jean-Etienne Doucet / LAAS-CNRS / Toulouse, France E-mail: doucet@laas.fr "S'il n'y a pas de solution, c'est qu'il n'y a pas de probl�me." (Les Shadoks) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-07 7:26 ` Jean-Etienne Doucet @ 2003-04-07 8:09 ` Lutz Donnerhacke 0 siblings, 0 replies; 32+ messages in thread From: Lutz Donnerhacke @ 2003-04-07 8:09 UTC (permalink / raw) * Jean-Etienne Doucet wrote: > For this kind of problems, I use the Ada.Numerics.Float_Random generator, > along with the function: If performance is not an issue, you are right. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-03 12:39 ` Peter Hermann 2003-04-03 22:10 ` Randy Brukardt @ 2003-04-04 8:27 ` 2003-04-04 12:14 ` Peter Hermann [not found] ` <6lk1m-lm3.ln1@beastie.ix.netcom.com> 1 sibling, 2 replies; 32+ messages in thread From: @ 2003-04-04 8:27 UTC (permalink / raw) Peter Hermann wrote: > David C. Hoos, Sr. <david.c.hoos.sr@ada95.com> wrote: > >>Such an approach is statistically dubious, since the same generator is >>being used for all draws. Normally, one would use a distinct >>generator for each sequence. > > > agreed: this is of course not a purist's approach > although I could live with it in the practice. > Using Lutz Do's code (thank you) should do the job. > Do you have a better idea how to pick out randomly from a set with > an always changing number of members? > Pick a random number from Integer and do a "mod" operation. Rodrigo ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 8:27 ` @ 2003-04-04 12:14 ` Peter Hermann 2003-04-04 14:26 ` Lutz Donnerhacke [not found] ` <6lk1m-lm3.ln1@beastie.ix.netcom.com> 1 sibling, 1 reply; 32+ messages in thread From: Peter Hermann @ 2003-04-04 12:14 UTC (permalink / raw) Rodrigo Garc?a <rodrigo.garcia.ARROBA.epfl.ch> wrote: > Pick a random number from Integer and do a "mod" operation. Rodrigo, well: you won the first round :-) instantiation of discrete_random with an actual generic parameter having a huge range of values, such as integer or natural or positive and then mod,abs should sufficiently satisfy my statistic conscience. -- --Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de --Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen --http://www.csv.ica.uni-stuttgart.de/homes/ph/ --Team Ada: "C'mon people let the world begin" (Paul McCartney) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 12:14 ` Peter Hermann @ 2003-04-04 14:26 ` Lutz Donnerhacke 0 siblings, 0 replies; 32+ messages in thread From: Lutz Donnerhacke @ 2003-04-04 14:26 UTC (permalink / raw) * Peter Hermann wrote: > Rodrigo Garc?a <rodrigo.garcia.ARROBA.epfl.ch> wrote: >> Pick a random number from Integer and do a "mod" operation. > well: you won the first round :-) No. > instantiation of discrete_random with an actual generic parameter > having a huge range of values, such as integer or natural or positive > and then mod,abs should sufficiently satisfy my statistic conscience. Using "mod" destroys the uniformness of your random data an therefore will not meet most of the assumed randomness preconditions. ^ permalink raw reply [flat|nested] 32+ messages in thread
[parent not found: <6lk1m-lm3.ln1@beastie.ix.netcom.com>]
* Re: Ada2005 random [not found] ` <6lk1m-lm3.ln1@beastie.ix.netcom.com> @ 2003-04-05 7:29 ` Pascal Obry 2003-04-05 9:00 ` tmoran 0 siblings, 1 reply; 32+ messages in thread From: Pascal Obry @ 2003-04-05 7:29 UTC (permalink / raw) Dennis Lee Bieber <wlfraed@ix.netcom.com> writes: > Might do for the short run, but I can see a failure in the long > run... > > For simplicity, say "Integer" covers 0..8, and the selection run 0..7 > (necessitating use of a mod 8)... The result will be that selection 0 > will have 2/9 chances with 1..7 having 1/9, rather than all having a > 1/8 chance. Ok, but integer has a range of -(2 ** 31) .. +(2 ** 31 - 1) so the difference could be something around +/- (x / (2 ** 31 - 1)) ! Not so bad for a simple program I would say. Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://perso.wanadoo.fr/pascal.obry --| "The best way to travel is by means of imagination" --| --| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595 ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-05 7:29 ` Pascal Obry @ 2003-04-05 9:00 ` tmoran 2003-04-05 17:02 ` Pascal Obry 0 siblings, 1 reply; 32+ messages in thread From: tmoran @ 2003-04-05 9:00 UTC (permalink / raw) > Ok, but integer has a range of -(2 ** 31) .. +(2 ** 31 - 1) so the difference > could be something around +/- (x / (2 ** 31 - 1)) ! A small error if x is small, but rather large if x is, say, 3/8 * 2**31 If the generator's range = a*x+b, then (random mod x) will take values < b a+1 times and values >= b only a times. If a is small, a/(a+1) will differ substantially from 1.0 Also, there's no guarantee that the generator's range is Integer or that it is 32 bits wide. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-05 9:00 ` tmoran @ 2003-04-05 17:02 ` Pascal Obry 0 siblings, 0 replies; 32+ messages in thread From: Pascal Obry @ 2003-04-05 17:02 UTC (permalink / raw) tmoran@acm.org writes: > > Ok, but integer has a range of -(2 ** 31) .. +(2 ** 31 - 1) so the difference > > could be something around +/- (x / (2 ** 31 - 1)) ! > A small error if x is small, but rather large if x is, say, 3/8 * 2**31 Right, reading original question it seems that x was supposed to be small. Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://perso.wanadoo.fr/pascal.obry --| "The best way to travel is by means of imagination" --| --| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595 ^ permalink raw reply [flat|nested] 32+ messages in thread
* Ada2005 random @ 2003-04-02 13:27 Peter Hermann 2003-04-02 13:44 ` Lutz Donnerhacke ` (3 more replies) 0 siblings, 4 replies; 32+ messages in thread From: Peter Hermann @ 2003-04-02 13:27 UTC (permalink / raw) In an application I need a variable discrete random function. Due to good reason I am reluctant to use my own very old http://www.csv.ica.uni-stuttgart.de/ftp/pub/ada/ica/misc/randomph.txt Instead, I would prefer to use generic type Result_Subtype is (<>); package Ada.Numerics.Discrete_Random is which offers a function Random (Gen : Generator) return Result_Subtype; but does not offer something like function Random (Gen : Generator; from : Result_Subtype := Result_Subtype'first; to : Result_Subtype := Result_Subtype'last) return Result_Subtype; which may or may not make sense in that raw disguise. Anyway in Ada95, I have to roll my own code or let me send one ;-) Does an AI exist for Ada95 or Ada2005? Did I miss something? -- --Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de --Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen --http://www.csv.ica.uni-stuttgart.de/homes/ph/ --Team Ada: "C'mon people let the world begin" (Paul McCartney) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-02 13:27 Peter Hermann @ 2003-04-02 13:44 ` Lutz Donnerhacke 2003-04-03 9:56 ` Peter Hermann 2003-04-04 3:50 ` Steve ` (2 subsequent siblings) 3 siblings, 1 reply; 32+ messages in thread From: Lutz Donnerhacke @ 2003-04-02 13:44 UTC (permalink / raw) * Peter Hermann wrote: > In an application I need a variable discrete random function. > > Due to good reason I am reluctant to use my own very old > http://www.csv.ica.uni-stuttgart.de/ftp/pub/ada/ica/misc/randomph.txt > > Instead, I would prefer to use > generic > type Result_Subtype is (<>); > package Ada.Numerics.Discrete_Random is > > which offers a > function Random (Gen : Generator) return Result_Subtype; > > but does not offer something like > function Random (Gen : Generator; > from : Result_Subtype := Result_Subtype'first; > to : Result_Subtype := Result_Subtype'last) > return Result_Subtype; > which may or may not make sense in that raw disguise. What's wrong with the following? subtype Specialized_Result_Subtype is Result_Subtype range from .. to; package Specialized_Random is new package Ada.Numerics.Discrete_Random (Specialized_Result_Subtype); ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-02 13:44 ` Lutz Donnerhacke @ 2003-04-03 9:56 ` Peter Hermann 2003-04-03 10:13 ` Lutz Donnerhacke 0 siblings, 1 reply; 32+ messages in thread From: Peter Hermann @ 2003-04-03 9:56 UTC (permalink / raw) Lutz and all, > * Peter Hermann wrote: >> In an application I need a variable discrete random function. ^^^^^^^^ with "variable" I meant the following flexibility, e.g. : a := random(generator1, 1 , 9); b := random(generator1, 1 , 8); c := random(generator1, 3 , 7); ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-03 9:56 ` Peter Hermann @ 2003-04-03 10:13 ` Lutz Donnerhacke 0 siblings, 0 replies; 32+ messages in thread From: Lutz Donnerhacke @ 2003-04-03 10:13 UTC (permalink / raw) * Peter Hermann wrote: > Lutz and all, >> * Peter Hermann wrote: >>> In an application I need a variable discrete random function. > ^^^^^^^^ > with "variable" I meant the following flexibility, e.g. : > a := random(generator1, 1 , 9); > b := random(generator1, 1 , 8); > c := random(generator1, 3 , 7); procedure random(g : in out Generator; min, max : X; rand : out X) --# derives rand from g, min, max and --# g from g; --# pre max > min; --# post rand in min .. max; is absmax : X; begin absmax := X'Last - (X'Last - X'First) mod (max - min); --# check absmax > X'First; loop random(g, rand); -- ... random (g : in out Generator; r : out X) ... exit when rand <= absmax; end loop; return (rand - X'First) mod (max - min) + min; end random; Ok, it's the C approach ;-) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-02 13:27 Peter Hermann 2003-04-02 13:44 ` Lutz Donnerhacke @ 2003-04-04 3:50 ` Steve 2003-04-04 14:30 ` Lutz Donnerhacke 2003-04-04 4:33 ` Christoph Grein 2003-04-05 0:14 ` Jeffrey Carter 3 siblings, 1 reply; 32+ messages in thread From: Steve @ 2003-04-04 3:50 UTC (permalink / raw) The following code almost does what you asked for. The problem is that without the delays the selected random number is always the same. I think this is because a new generator is created for each call, and the "seed" value (based on time) is the same unless I include delays. with Ada.Integer_text_Io; with Ada.Text_Io; procedure CLA_Test2 is function Check( low, high : Integer ) return Integer is subtype check_range is integer range low .. high; package ranged_random is new Ada.Numerics.Discrete_Random( check_range ); gen : ranged_random.Generator; begin ranged_random.reset( gen ); return ranged_random.Random( gen ); end Check; begin Ada.Integer_Text_Io.Put( Check( 1, 10 ) ); Ada.Text_Io.New_Line; Delay 1.0; Ada.Integer_Text_Io.Put( Check( 1, 10 ) ); Ada.Text_Io.New_Line; Delay 1.0; Ada.Integer_Text_Io.Put( Check( 1, 10 ) ); Ada.Text_Io.New_Line; Delay 1.0; Ada.Integer_Text_Io.Put( Check( 1, 10 ) ); Ada.Text_Io.New_Line; Delay 1.0; end CLA_Test2; I would probably go with creating my own routine using the float package. Steve (The Duck) "Peter Hermann" <ica2ph@sinus.csv.ica.uni-stuttgart.de> wrote in message news:b6eog4$8jl$1@news.uni-stuttgart.de... > In an application I need a variable discrete random function. > > Due to good reason I am reluctant to use my own very old > http://www.csv.ica.uni-stuttgart.de/ftp/pub/ada/ica/misc/randomph.txt > > Instead, I would prefer to use > generic > type Result_Subtype is (<>); > package Ada.Numerics.Discrete_Random is > > which offers a > function Random (Gen : Generator) return Result_Subtype; > > but does not offer something like > function Random (Gen : Generator; > from : Result_Subtype := Result_Subtype'first; > to : Result_Subtype := Result_Subtype'last) > return Result_Subtype; > which may or may not make sense in that raw disguise. > > Anyway in Ada95, I have to roll my own code or let me send one ;-) > > Does an AI exist for Ada95 or Ada2005? > Did I miss something? > > -- > --Peter Hermann(49)0711-685-3611 fax3758 ica2ph@csv.ica.uni-stuttgart.de > --Pfaffenwaldring 27 Raum 114, D-70569 Stuttgart Uni Computeranwendungen > --http://www.csv.ica.uni-stuttgart.de/homes/ph/ > --Team Ada: "C'mon people let the world begin" (Paul McCartney) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 3:50 ` Steve @ 2003-04-04 14:30 ` Lutz Donnerhacke 2003-04-05 3:02 ` Steve 0 siblings, 1 reply; 32+ messages in thread From: Lutz Donnerhacke @ 2003-04-04 14:30 UTC (permalink / raw) * Steve wrote: > The following code almost does what you asked for. No. > The problem is that without the delays the selected random number is > always the same. This should lead you to the error. > I think this is because a new generator is created for each call, and the > "seed" value Ack > (based on time) is the same unless I include delays. Nobody says, that the time is included in the seed. And more important: Even if the random seed is generated from the time, the generation of random values from the seed does have completely different statistical properties than generating a seed from the time. Therefore your code is wrong, wrong, and wrong. Don't use it! ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 14:30 ` Lutz Donnerhacke @ 2003-04-05 3:02 ` Steve 0 siblings, 0 replies; 32+ messages in thread From: Steve @ 2003-04-05 3:02 UTC (permalink / raw) "Lutz Donnerhacke" <lutz@iks-jena.de> wrote in message news:slrnb8r5nt.ov.lutz@taranis.iks-jena.de... [snip] > Nobody says, that the time is included in the seed.... Actually they did (or at least based on a time-dependent state): LRM A.5.2(34) Sets the state of the specified generator to one that is an unspecified function of the value of the parameter Initiator (or to a time-dependent state, if only a generator parameter is specified). The latter form of the procedure is known as the time-dependent Reset procedure. In my example a new "Generator" (presumably containing a seed value) is created each time the routine is called. This is likely to give different results than propagting the generator through a sequence of calls to Random. > And more important: Even > if the random seed is generated from the time, the generation of random > values from the seed does have completely different statistical properties > than generating a seed from the time. > > Therefore your code is wrong, wrong, and wrong. Don't use it! BTW: Just because I gave an example of how it "might" be done, doesn't mean I think it's a good method. The fact that a new "generator" is created with each call is somewhat dubious. Steve (The Duck) ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-02 13:27 Peter Hermann 2003-04-02 13:44 ` Lutz Donnerhacke 2003-04-04 3:50 ` Steve @ 2003-04-04 4:33 ` Christoph Grein 2003-04-06 15:44 ` 2003-04-05 0:14 ` Jeffrey Carter 3 siblings, 1 reply; 32+ messages in thread From: Christoph Grein @ 2003-04-04 4:33 UTC (permalink / raw) See RM A.5.2(51) for a generator returning values in 0 .. M-1 for variable M. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-04 4:33 ` Christoph Grein @ 2003-04-06 15:44 ` 0 siblings, 0 replies; 32+ messages in thread From: @ 2003-04-06 15:44 UTC (permalink / raw) Christoph Grein wrote: > See RM A.5.2(51) for a generator returning values in 0 .. M-1 for > variable M. Without any kind of doubt, that's the rightest solution! Rodrigo PS: In fact, it reminds me when I learned how to get random numbers in BASIC, where the only random function returns float values between 0 and 1. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: Ada2005 random 2003-04-02 13:27 Peter Hermann ` (2 preceding siblings ...) 2003-04-04 4:33 ` Christoph Grein @ 2003-04-05 0:14 ` Jeffrey Carter 3 siblings, 0 replies; 32+ messages in thread From: Jeffrey Carter @ 2003-04-05 0:14 UTC (permalink / raw) Peter Hermann wrote: > In an application I need a variable discrete random function. PragmARC.Universal_Random from the PragmAda Reusable Components has what you want. http://home.earthlink.net/~jrcarter010/pragmarc.htm -- Jeff Carter "English bed-wetting types." Monty Python & the Holy Grail ^ permalink raw reply [flat|nested] 32+ messages in thread
end of thread, other threads:[~2003-04-13 21:58 UTC | newest] Thread overview: 32+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2003-04-03 12:27 Ada2005 random David C. Hoos, Sr. 2003-04-03 12:39 ` Peter Hermann 2003-04-03 22:10 ` Randy Brukardt 2003-04-04 7:43 ` Peter Hermann 2003-04-04 10:21 ` Dale Stanbrough 2003-04-04 12:11 ` Stuart Palin 2003-04-04 14:25 ` Lutz Donnerhacke 2003-04-04 21:51 ` Dale Stanbrough 2003-04-05 18:34 ` Samuel Tardieu 2003-04-05 6:46 ` Martin Krischik 2003-04-07 21:07 ` Randy Brukardt 2003-04-13 14:56 ` Robert I. Eachus 2003-04-13 21:58 ` Mark Biggar 2003-04-04 12:20 ` Stuart Palin 2003-04-07 7:26 ` Jean-Etienne Doucet 2003-04-07 8:09 ` Lutz Donnerhacke 2003-04-04 8:27 ` 2003-04-04 12:14 ` Peter Hermann 2003-04-04 14:26 ` Lutz Donnerhacke [not found] ` <6lk1m-lm3.ln1@beastie.ix.netcom.com> 2003-04-05 7:29 ` Pascal Obry 2003-04-05 9:00 ` tmoran 2003-04-05 17:02 ` Pascal Obry -- strict thread matches above, loose matches on Subject: below -- 2003-04-02 13:27 Peter Hermann 2003-04-02 13:44 ` Lutz Donnerhacke 2003-04-03 9:56 ` Peter Hermann 2003-04-03 10:13 ` Lutz Donnerhacke 2003-04-04 3:50 ` Steve 2003-04-04 14:30 ` Lutz Donnerhacke 2003-04-05 3:02 ` Steve 2003-04-04 4:33 ` Christoph Grein 2003-04-06 15:44 ` 2003-04-05 0:14 ` Jeffrey Carter
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox