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 <- buy my book? http://agilesolutionspace.blogspot.com/ twitter: @ckeithray 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> wrote: > > >> On Jan 12, 2018, at 8:22 PM, Nate Cook <natec...@apple.com> wrote: >> >> On Jan 12, 2018, at 6:24 PM, Jonathan Hull via swift-evolution >> <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> >>>> 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> 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>, 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 >>>>>>> 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 > > _______________________________________________ > 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
