Re: [computer-go] [OT] All-integer scalable distribution algorithm.
while neither a normal distribution nor integer based, the following is relatively fast and may be useful for you (you might need to slide things around so that you get the maximum value where you want it and ignore the rest) check out the poisson distribution: http://en.wikipedia.org/wiki/Poisson_distribution there is helpfully an algorithm from knuth around the middle of the article that is quick. i take it that you want to go from a uniform distribution to something weighted more on one side than the other, for a finite number of possible values? if there's no strong reason that you want it to be half-normal, then there are a ton of distributions that can serve that need and might be easier to deal with in code. i suggested the poisson because it's something like the binomial, which itself is quite a bit like the normal, only very heavily based in a finite number of trials. (i'd prefer the binomial, but that might mean precomputing a lot of little tables ahead of time). s. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] [OT] All-integer scalable distribution algorithm.
In message [EMAIL PROTECTED], Mike Hill [EMAIL PROTECTED] writes Folks... First, let me say how much pleasure my reading of this list has given me. I love that folks are out there cranking on this problem. Truly, it's one of the great problems. I have a rather strange request. I am a statistical idiot, in both senses of 'statistical'. After scrolling through a half-dozen stat tutorials online, I find myself completely unable to grasp how I'd get the effect I want even if I wanted to use floats, which I don't. As you will soon be aware, I don't even have the language to figure out how to describe my problem. Seeing as how there are so many MC algorithm workers on the list, I thought I'd turn to you for some guidance. The essence of my idea is that I want a psuedo-random algorithm which takes as a parameter a 'degree-of-randomness' value. Something along these lines: int choose( int range, int degree-of-randomness) Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. Am I making *any* sense? If so, you may need some sort of psychiatric help, or alternatively, you could do me the favor of explaining how to ask for what I want or even how to actually get it. :) So if you specify a range of 3 and a degree-of-randomness of 100, you get a uniform distribution of the range 0..3. If you specify a range of 3 and a degree-of-randomness of 0, you want something with a maximum at 0, looking like the right half of a Gaussian, a zero steepness [?], and an unspecified variance. Are you aware that, if it has any variance at all, its tail will extend beyond 3? I think the maths will be easy enough, once you have made it clear what you want (or why you want it). Maybe this would provide what you want: take a random number in the range 0..1 raise it to the power (100/degree-of-randomness) multiply the result by range Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] [OT] All-integer scalable distribution algorithm.
Folks... First, let me say how much pleasure my reading of this list has given me. I love that folks are out there cranking on this problem. Truly, it's one of the great problems. I have a rather strange request. I am a statistical idiot, in both senses of 'statistical'. After scrolling through a half-dozen stat tutorials online, I find myself completely unable to grasp how I'd get the effect I want even if I wanted to use floats, which I don't. As you will soon be aware, I don't even have the language to figure out how to describe my problem. Seeing as how there are so many MC algorithm workers on the list, I thought I'd turn to you for some guidance. The essence of my idea is that I want a psuedo-random algorithm which takes as a parameter a 'degree-of-randomness' value. Something along these lines: int choose( int range, int degree-of-randomness) Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. Am I making *any* sense? If so, you may need some sort of psychiatric help, or alternatively, you could do me the favor of explaining how to ask for what I want or even how to actually get it. :) Cheers, and thanks, Hill ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] [OT] All-integer scalable distribution algorithm.
It sounds like you're frustrated, so here's a few lines of C code that'll do about what you describe. Note that the use of large values for the standard deviation will make the code go very slow from repetitive looping. The divide by 10 is to make it not be too slow with a degree of randomness of 100. randn returns a normally distributed random number. float standard_deviation = degree_of_randomness/10; double r; do{ r = abs(randn(seed))*standard_deviation; }while (r = (range+1)) return floor(r); 1. Get a random, normally distributed, variable (using your favorite API to do that) 2. If it's negative, make it positive Use your favorite function for generating a normally distributed random variable. If it's negative, make it positive. Multiply it by some On Tue, 2007-11-06 at 22:03 -0500, Mike Hill wrote: Folks... First, let me say how much pleasure my reading of this list has given me. I love that folks are out there cranking on this problem. Truly, it's one of the great problems. I have a rather strange request. I am a statistical idiot, in both senses of 'statistical'. After scrolling through a half-dozen stat tutorials online, I find myself completely unable to grasp how I'd get the effect I want even if I wanted to use floats, which I don't. As you will soon be aware, I don't even have the language to figure out how to describe my problem. Seeing as how there are so many MC algorithm workers on the list, I thought I'd turn to you for some guidance. The essence of my idea is that I want a psuedo-random algorithm which takes as a parameter a 'degree-of-randomness' value. Something along these lines: int choose( int range, int degree-of-randomness) Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. Am I making *any* sense? If so, you may need some sort of psychiatric help, or alternatively, you could do me the favor of explaining how to ask for what I want or even how to actually get it. :) Cheers, and thanks, Hill ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] [OT] All-integer scalable distribution algorithm.
On Tue, 6 Nov 2007, Mike Hill wrote: int choose( int range, int degree-of-randomness) Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. This seems not so much the degree of randomness as the skew. Because a normal distribution has an infinite continuous range, I don't think that's what you want. You say half a normal; is something like a geometric distribution close enough? You might check it out, at least it's discrete. But when I have a problem like this, I tend to use what I think of as the weight, bisect algorithm. See if this solves your problem. Basically, skew can go from 0 to infinity, and the higher it is, the steeper the skew and the less likely you are to choose 0, the more likely you are to choose size-1. [begin python code] from bisect import bisect from random import random def draw(weights): sigma = 0.0 ps = [] for p in weights: sigma += p ps.append(sigma) return (ps,random()*sigma) def choose(size, skew): ''' skew=0 gives uniform distribution skew=1 gives linear, skew = 2 quadratic, and so on. ''' weights = [i**skew for i in range(size)] return draw(weights) [end python code] HTH, Tom ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] [OT] All-integer scalable distribution algorithm.
At 07:03 PM 11/6/2007, you wrote: ... Returns an integer in [0-range] distributed depending on the value of degree-of-randomness. At degree-of-randomness 100, I want the distribution to be uniform. At degree-of-randomness 0, I want the distribution to be -- I don't even know what to call this -- half-of-a-normal-distribution with the steepness proportionately related to degree-of-randomness. maybe a normal (gaussian) with the standard deviation (sigma) proportional to the degree of randomness. but clip the tails. see the graphs of the normal density function: http://en.wikipedia.org/wiki/Normal_distribution. a larger variance will get you a flatter curve that will approach a uniform distribution. --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/