For a range of 0..<(2<<b) (size being 2<<b) and mod m, its less pronounced for small m. Worst case would be a mod greater than 2^(b-1), in which case some values are twice as likely as others.
The increased probability I believe is (floor(s/m)+ 1) / floor(s/m) for s % m != 0 For me, its not so much about being statistically correct as leading people down the right path in terms of comprehension and readability. I find it much easier to think of the classic example program of “pick a number between 1 and 100” as (1…100).random() vs say Int(UInt64.random()%100) + 1 which (with all that complexity) still isn’t a uniform distribution! Thats completely ignoring some of the finer issues you get with floating point numbers as you certain transforms of a [0,1] distribution -DW > On Jan 13, 2018, at 7:41 PM, C. Keith Ray via swift-evolution > <swift-evolution@swift.org> wrote: > > Could someone measure how bad the "random(32 bits) mod m" problem actually > is? It's prominent when the number of bits is close to m, eg 4 bits and m == > 3. Is it bad when bits == 32 and m is less than 2^16? Or bits == 64 and m is > less than 2^32? > > C. Keith Ray > https://leanpub.com/wepntk <https://leanpub.com/wepntk> <- buy my book? > http://agilesolutionspace.blogspot.com/ > <http://agilesolutionspace.blogspot.com/> > twitter: @ckeithray > http://www.thirdfoundationsw.com/keith_ray_resume_2014_long.pdf > <http://www.thirdfoundationsw.com/keith_ray_resume_2014_long.pdf> > > On Jan 13, 2018, at 6:15 PM, Jonathan Hull via swift-evolution > <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: > >> >>> On Jan 12, 2018, at 8:22 PM, Nate Cook <natec...@apple.com >>> <mailto:natec...@apple.com>> wrote: >>> >>> On Jan 12, 2018, at 6:24 PM, Jonathan Hull via swift-evolution >>> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: >>> >>>> I think we have different definitions of consistency. I am fine with the >>>> ergonomics of (0…100).random() as a convenience, but it really worries me >>>> here that everything is special cased. Special cased things are fine for >>>> individual projects, but not the standard library. We should make sure >>>> that the design is flexible and extensible, and that comes in part from >>>> having a consistent interface. >>>> >>>> Also, as I said before, we really shouldn’t be doing these crazy >>>> contortions to avoid ‘random() % 100’. Instead we should look for that >>>> pattern and issue with a warning + fixit to change it to random(in:). I >>>> think that will be much more effective in actually changing the behavior >>>> in the long run. >>> >>> I’m not sure what contortions you’re describing—from what I’ve seen, the >>> proposal author is going to revise the proposal to have these ways of >>> generating individual values: >> >> Mainly avoiding ‘random(using:)’ as a thing we can count on generically >> because of the fear of it being used with mod. This makes random(using:) on >> Bool a one-off special case instead of a thing I can call on anything >> adhering to a protocol. >> >> >>> In extensions to FixedWidthInteger and BinaryFloatingPoint: >>> static func random(in: Range/ClosedRange<Self>, using: >>> RandomNumberGenerator) -> Self >>> >>> In an extension to Bool: >>> static func random(using: RandomNumberGenerator) -> Self >>> >>> If someone still needs a full-width random value as a building-block for >>> generating random instances of other types, they should use the `next()` >>> method directly on a RandomNumberGenerator. In the example code you sent, >>> you could switch to using a RandomNumberGenerator instead of your >>> RandomSourceValue, or base your RandomSourceValue generation on a >>> RandomNumberGenerator instead of whatever random generator you’re using now. >>> >>>> Finally, tying everything to Range is extremely limiting. I understand if >>>> we don’t want to add other types to the standard library, but I should be >>>> able to build on what we add to do it myself without having to reinvent >>>> the wheel for each type. It is important to have a consistent story for >>>> these things (including multi-dimensional types) so that they can >>>> interoperate. >>>> >>>> We really should be looking at GamePlayKit more for design inspiration. >>>> There are several use-cases there that are being blatantly ignored in this >>>> discussion. For example, what if I want to randomly generate a game world >>>> (e.g. The square from The Battle For Polytopia” formerly “SuperTribes”)? >>>> Or what if I want an effect where it randomly fades in letters from a >>>> String. (…).random() will be completely inadequate for these things. >>> >>> The goal at this point is to build into the standard library the basis for >>> all kinds of other use cases. Your library is one such example of something >>> that can be built on top of the protocol and methods that are being >>> proposed, as are a variety of other tasks, as I tried to show in the >>> playground. >>> >>> What’s being proposed now is deliberately short of solving every need—the >>> additions would handle the hard stuff (correct and safe generation of >>> integers and floating-points, along with shuffling collections) and lay the >>> groundwork for other libraries to take things farther (by establishing the >>> RandomNumberGenerator, a default generator, and a pattern for their use). >> >> I think we are mostly in agreement on this. I don’t need the proposal to >> solve every need. I would just really like to see something that those >> other things can be built on. I don’t expect other types to conform out of >> the box, but I want the types that I add conformance to to be able to >> interoperate with machinery that others build around randomness. >> >> For example, if we instead went with Letanyan’s mental model of having to >> define a space to select a random element from using a generator, that would >> be perfectly fine for me, since we can conform Range to that protocol… and >> then we can operate generically on objects which conform to it. >> >> >>> Speaking of GameplayKit, you can make GKRandomSource conform to >>> RandomNumberGenerator in an extension, making all the GK... sources >>> generators. If you’re already depending on those random sources, you’d >>> still have access to them with the proposed model. >> >> Agreed. I was thinking someone was removing the ‘using:’ variant from the >> proposal for some reason. >> >> Thanks, >> Jon >> >> >>> >>> Nate >>> >>>> Thanks, >>>> Jon >>>> >>>> >>>> >>>>> On Jan 12, 2018, at 5:11 AM, Letanyan Arumugam <letanya...@gmail.com >>>>> <mailto:letanya...@gmail.com>> wrote: >>>>> >>>>> Nate’s design follows a consistent idea of getting a random value from >>>>> some set of values. Adding the static method random() to a type >>>>> essentially creates an implicit set which you yourself said leads to >>>>> inconsistency (Double/Int). Secondly I don’t see why random(in:) should >>>>> be added when it is just a different spelling for what is already >>>>> provided. If my second statement is incorrect and there’s something I’m >>>>> missing please correct me? >>>>> >>>>> I think that consistency outweighs the random trapping inconsistency, >>>>> however I would actually be fine if random returned an optional. Though >>>>> the way random is used would likely lead to less opportunities for a trap >>>>> than the other methods you mention. >>>>> >>>>> >>>>> Letanyan >>>>> >>>>>> On 12 Jan 2018, at 04:39, Alejandro Alonso <aalonso...@outlook.com >>>>>> <mailto:aalonso...@outlook.com>> wrote: >>>>>> >>>>>> If anything, Nate’s design is inconsistent as properties like `.first` >>>>>> and `.last` return an optional, and methods like `.min()` and `.max()` >>>>>> return an optional as well. Having `.random()` on ranges be an exception >>>>>> and return non optionals are inconsistent with other collection >>>>>> facilities, and with other collections that aren’t ranges that return >>>>>> optionals on `.random()`. >>>>>> >>>>>> - Alejandro >>>>>> >>>>>> On Jan 11, 2018, 12:06 PM -0600, Letanyan Arumugam via swift-evolution >>>>>> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>, wrote: >>>>>>> This is really cool and seems very powerful. However I don’t think we >>>>>>> should sacrifice consistency for extendability. Especially when the >>>>>>> extendability would not be what most people need. >>>>>>> >>>>>>> What I am basically trying to say is that. I think the proposals >>>>>>> current design direction fits better in a Random library rather than >>>>>>> the Standard Library. And Nate’s design more directly addresses the >>>>>>> motivating points of the proposal. >>>>>>> >>>>>>> Letanyan >>>>>>> >>>>>>>> >>>>>>>> Sure. Small disclaimer that this was originally written back in the >>>>>>>> Swift 1~2 days, so it is overdue for a simplifying rewrite. >>>>>>>> >>>>>>>> Also, I should point out that the term “Source” has a special meaning >>>>>>>> in my code. It basically means that something will provide an >>>>>>>> ~infinite collection of values of a type T. I have what I call a >>>>>>>> “ConstantSource” which just wraps a T and gives it back when asked. >>>>>>>> But then I have a bunch of other “sources" which let you create >>>>>>>> repeating patterns and do deferred calculations and things like that. >>>>>>>> Finally I have a “RandomSource” which is part of what started this >>>>>>>> discussion. You set up a RandomSource with a set of constraints, and >>>>>>>> then it gives you random values of T that adhere to those constraints >>>>>>>> (e.g. colors with a range of hues but the same saturation) whenever >>>>>>>> you ask for them. >>>>>>>> >>>>>>>> This is really useful for doing things like graphic effects because, >>>>>>>> for example, I can ask for a source of colors and a source of line >>>>>>>> widths and then get out a large variety of interesting patterns from >>>>>>>> the same algorithm. I can make simple stripes with ConstantSources, >>>>>>>> or I can make repeating patterns of lines with repeating sources, or I >>>>>>>> can have random colors which look good together by using a >>>>>>>> RandomSource. I can take a BezierPath and make it look hand-drawn by >>>>>>>> breaking it into a bunch of lines and then offset the points a small >>>>>>>> amount using a RandomSource of CGVectors. >>>>>>>> >>>>>>>> Not sure how useful this concept of randomness (and pattern) is to >>>>>>>> others, but I find it immensely useful! Not sure of the best way to >>>>>>>> implement it. The way I do it is a type erased protocol with private >>>>>>>> conforming structs and then public initializers on the type-erasing >>>>>>>> box. The end result is that I can just say: >>>>>>>> >>>>>>>> let myConst = Source(1) //ConstantSource with 1 as a value >>>>>>>> let myPattern = Source([1, 2]) //OrderedSource which repeats 1, then 2 >>>>>>>> over and over forever >>>>>>>> let myMeta = Source([myConst, myPattern]) //Will alternate between >>>>>>>> sub-sources in order. Can be nested. >>>>>>>> //…and so on. >>>>>>>> >>>>>>>> It is quite extensible and can make very complex/interesting patterns >>>>>>>> very easily. What I like about it is that (well controlled) random >>>>>>>> values and patterns or constant values can be interchanged very easily. >>>>>>>> >>>>>>>> The RandomSource has a RandomSourceCreatable Protocol that lets it >>>>>>>> take random bits and turn them into objects/structs of T adhering to >>>>>>>> the given constraints. This is way more complex under the hood than >>>>>>>> it needs to be, but it works well in practice, and I haven’t gotten >>>>>>>> around to cleaning it up yet: >>>>>>>> >>>>>>>> public protocol RandomSourceCreatable { >>>>>>>> associatedtype ConstraintType = Self >>>>>>>> >>>>>>>> >>>>>>>> ///This should be implimented by simple types without internal >>>>>>>> components >>>>>>>> >>>>>>>> static func createRandom(rnd value:RandomSourceValue, >>>>>>>> constraint:RandomSourceConstraint<ConstraintType>)->Self >>>>>>>> >>>>>>>> ///This should be implimented by complex types with multiple axis of >>>>>>>> constraints >>>>>>>> >>>>>>>> static func createRandom(rnd value:RandomSourceValue, >>>>>>>> constraints:[String:RandomSourceConstraint<ConstraintType>])->Self >>>>>>>> >>>>>>>> >>>>>>>> ///Returns the proper dimension for the type given the constraints >>>>>>>> >>>>>>>> static func dimension(given >>>>>>>> contraints:[String:RandomSourceConstraint<ConstraintType>])->RandomSourceDimension >>>>>>>> >>>>>>>> >>>>>>>> ///Validates the given contraints to make sure they can create valid >>>>>>>> objects. Only needs to be overridden for extremely complex types >>>>>>>> static func validateConstraints(_ >>>>>>>> constraints:[String:RandomSourceConstraint<ConstraintType>])->Bool >>>>>>>> >>>>>>>> >>>>>>>> ///Convienience method which provides whitelist of keys for implicit >>>>>>>> validation of constraints >>>>>>>> static var allowedConstraintKeys:Set<String> {get} >>>>>>>> } >>>>>>>> >>>>>>>> Most of these things also have default implementations so you only >>>>>>>> really have to deal with them for complex cases like colors or points. >>>>>>>> The constraints are given using a dictionary with string keys and a >>>>>>>> RandomSourceConstraint value, which is defined like this: >>>>>>>> >>>>>>>> public enum RandomSourceConstraint<T> { >>>>>>>> case none >>>>>>>> case constant(T) >>>>>>>> case min(T) >>>>>>>> case max(T) >>>>>>>> case range (T,T) >>>>>>>> case custom ( (RandomSourceValue)->T ) >>>>>>>> //A bunch of boring convenience code here that transforms values so I >>>>>>>> don’t always have to switch on the enum in other code that deals with >>>>>>>> this. I just ask for the bounds or constrained T (Note: T here refers >>>>>>>> to the type for a single axis as opposed to the generated type. e.g. >>>>>>>> CGFloat for a point) >>>>>>>> } >>>>>>>> >>>>>>>> I have found that this handles pretty much all of the constraints I >>>>>>>> need, and the custom constraint is useful for anything exotic (e.g. >>>>>>>> sig-figs). The RandomSource itself has convenience inits when T is >>>>>>>> Comparable that let you specify a range instead of having to create >>>>>>>> the constraints yourself. >>>>>>>> >>>>>>>> I then have conformed many standard types to RandomSourceCreatable so >>>>>>>> that I can create Sources out of them. Here is CGPoint for reference: >>>>>>>> >>>>>>>> extension CGPoint:RandomSourceCreatable { >>>>>>>> >>>>>>>> >>>>>>>> public static func dimension(given >>>>>>>> contraints:[String:RandomSourceConstraint<CGFloat>])->RandomSourceDimension >>>>>>>> { >>>>>>>> >>>>>>>> return RandomSourceDimension.manyWord(2) >>>>>>>> } >>>>>>>> >>>>>>>> public typealias ConstraintType = CGFloat >>>>>>>> public static var allowedConstraintKeys:Set<String>{ >>>>>>>> return ["x","y"] >>>>>>>> } >>>>>>>> >>>>>>>> >>>>>>>> public static func createRandom(rnd value:RandomSourceValue, >>>>>>>> constraints:[String:RandomSourceConstraint<CGFloat>])->CGPoint { >>>>>>>> let xVal = value.value(at: 0) >>>>>>>> let yVal = value.value(at: 1) >>>>>>>> >>>>>>>> //Note: Ints have a better distribution for normal use cases of points >>>>>>>> let x = CGFloat(Int.createRandom(rnd: xVal, constraint: >>>>>>>> constraints["x"]?.asType({Int($0 * 1000)}) ?? .none))/1000 >>>>>>>> let y = CGFloat(Int.createRandom(rnd: yVal, constraint: >>>>>>>> constraints["y"]?.asType({Int($0 * 1000)}) ?? .none))/1000 >>>>>>>> return CGPoint(x: x, y: y) >>>>>>>> } >>>>>>>> } >>>>>>>> >>>>>>>> Notice that I have a RandomSourceValue type that provides the random >>>>>>>> bits of the requested dimension. When I get around to updating this, I >>>>>>>> might do something closer to the proposal, where I would just pass the >>>>>>>> generator and grab bits as needed. The main reason I did it the way I >>>>>>>> did is that it lets me have random access to the source very easily. >>>>>>>> >>>>>>>> The ‘asType’ method converts a constraint to work with another type >>>>>>>> (in this case Ints). >>>>>>>> >>>>>>>> Colors are a bit more complicated, mainly because I allow a bunch of >>>>>>>> different constraints, and I also have validation code to make sure >>>>>>>> the constraints fit together properly. I also ask for different >>>>>>>> amounts of randomness based on whether it is greyscale or contains >>>>>>>> alpha. Just to give you a sense, here are the allowed constraint keys >>>>>>>> for a CGColor: >>>>>>>> public static var allowedConstraintKeys:Set<String>{ >>>>>>>> return ["alpha","gray","red","green","blue", "hue", >>>>>>>> "saturation", "brightness"] >>>>>>>> } >>>>>>>> >>>>>>>> and here is the creation method when the keys are for RGBA (I have >>>>>>>> similar sections for HSBA and greyscale): >>>>>>>> >>>>>>>> let rVal = value.value(at: 0) >>>>>>>> let gVal = value.value(at: 1) >>>>>>>> let bVal = value.value(at: 2) >>>>>>>> let aVal = value.value(at: 3) >>>>>>>> let r = CGFloat.createRandom(rnd: rVal, constraint: >>>>>>>> constraints["red"] ?? .range(0,1)) >>>>>>>> let g = CGFloat.createRandom(rnd: gVal, constraint: >>>>>>>> constraints["green"] ?? .range(0,1)) >>>>>>>> let b = CGFloat.createRandom(rnd: bVal, constraint: >>>>>>>> constraints["blue"] ?? .range(0,1)) >>>>>>>> let a = CGFloat.createRandom(rnd: aVal, constraint: >>>>>>>> constraints["alpha"] ?? .constant(1.0)) >>>>>>>> >>>>>>>> return self.init(colorSpace: CGColorSpaceCreateDeviceRGB(), >>>>>>>> components: [r,g,b,a])! >>>>>>>> >>>>>>>> >>>>>>>> The end result is that initializing a source of CGColors looks like >>>>>>>> this (either parameter can be omitted if desired): >>>>>>>> >>>>>>>> let colorSource:Source<CGColor> = Source(seed: optionalSeed, >>>>>>>> constraints:["saturation": .constant(0.4), "brightness": >>>>>>>> .constant(0.6)]) >>>>>>>> >>>>>>>> Anyway, I hope this was useful/informative. I know the code is a bit >>>>>>>> messy, but I still find it enormously useful in practice. I plan to >>>>>>>> clean it up when I find time, simplifying the RandomSourceValue stuff >>>>>>>> and moving from String Keys to a Struct with static functions for the >>>>>>>> constraints. The new constraints will probably end up looking like >>>>>>>> this: >>>>>>>> >>>>>>>> let colorSource:Source<CGColor> = Source(seed: optionalSeed, >>>>>>>> constraints:[.saturation(0.4), .brightness(0.4...0.6)]) >>>>>>>> >>>>>>>> Thanks, >>>>>>>> Jon >>>>>>>> >>>>>>>> >>>>>>>> _______________________________________________ >>>>>>>> swift-evolution mailing list >>>>>>>> swift-evolution@swift.org <mailto:swift-evolution@swift.org> >>>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>>>>>> <https://lists.swift.org/mailman/listinfo/swift-evolution> >>>>>>> >>>>>>> _______________________________________________ >>>>>>> swift-evolution mailing list >>>>>>> swift-evolution@swift.org <mailto:swift-evolution@swift.org> >>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>>>>> <https://lists.swift.org/mailman/listinfo/swift-evolution> >>>>> >>>> >>>> _______________________________________________ >>>> swift-evolution mailing list >>>> swift-evolution@swift.org <mailto:swift-evolution@swift.org> >>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>> <https://lists.swift.org/mailman/listinfo/swift-evolution> >> >> _______________________________________________ >> swift-evolution mailing list >> swift-evolution@swift.org <mailto:swift-evolution@swift.org> >> https://lists.swift.org/mailman/listinfo/swift-evolution >> <https://lists.swift.org/mailman/listinfo/swift-evolution> > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution
