Le 25/08/2010 06:13, Anthony D. Baye a écrit :
> I'm working on an implementation of the Diamond-Square algorithm, and it seems
> to be working... sort of, but for two things.
> 
> First, I'm getting seriously large pixel values.  I've been trying to clamp them
> between 0 and 255 inclusive, but it's not working the way I hoped it would.
> 
> Second my random number function. (I've attached the source file, but I'll
> reiterate the function here) I'm using the rand() function from cstdlib:
> 
> double Random(double r)
> {
>      double rNum;
> 
>      rNum = r - (2*r)/(rand()%65535);
> 
>      return rNum;
> }
> 
> theoretically, this should generate a random number between -r and r, but I'm
> only getting positive values within a small range.  reducing the range of random
> values to 100 or less seems to generate more negative numbers but problems
> persist.

The problem is in your formula:  R - 2R/X with X between 0 & 65534 leads to:
 * a problem with when X== 0
 * -r when X== 1
 * 0 when X== 2
 * a positive value near r when X > 10 (with near ~ within 10%)

I guess you want to fix it.
Also, rand() is weak, why not using drand48() instead ?

   rnum = r*(1.0-2.0*drand48());
/* notice the usage of .0 to force double computation not integer one */

or even better if non portable is not a problem and you are in the gnu
world: the drand48_r version (or at least the rand_r version), so as to
avoid reentrancy issue ? (as long as YOU protect the state)

> 
> At the moment, the largest problem seems to be clamping the values.
> 
> the code outputs the result to a pgm file with a depth of 8 bits
> 
> changing the range multiplier seems to have some interesting effects, but I'm
> not sure I like the results.
> 
> Any help would be appreciated.
> 
> A.D.B.
> 


-- 
Real software engineers work from 9 to 5, because that is<br/>
the way the job is described in the formal spec.  Working<br/>
late would feel like using an undocumented external procedure.

Post a reply to this message

Am 25.08.2010 06:13, schrieb Anthony D. Baye:

> Second my random number function. (I've attached the source file, but I'll
> reiterate the function here) I'm using the rand() function from cstdlib:
>
> double Random(double r)
> {
>       double rNum;
>
>       rNum = r - (2*r)/(rand()%65535);
>
>       return rNum;
> }

What type of random distribution do you want to achieve? If you're 
attempting to get a uniform distribution in the interval -r to +r (i.e. 
each value in this interval is equally likely), then you're pretty much 
off the track.

First, note that rand() /is/ uniformly distributed, in the interval 0 to 
RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).

Now, taking this number modulo 65535 doesn't change a thing, provided 
that RAND_MAX < 65535. Otherwise, it will give you a uniformly 
distributed value in the range 0 to 65534 (sic!).

You take the inverse of this value, which gives you a /non-uniformly/ 
distributed number. Not sure from the top of my hat /what/ distribution 
this gives you, but I think it's an exponential one, with the value x 
having a probability of c*e^-x. At any rate, the range is also modified. 
In a nutshell, at this point you get random values in the range 
1/RAND_MAX (about 0.00003) to 1/0 (1.#INF, positive infinity), and while 
each individual value in practice still has roughly the same 
probability, the values clump together near 0.0 (for instance, the 
highest values are ..., 0.20, 0.25, 0.333, 0.50, 1.00, 1.#INF).

The final operations - multiplying by 2*r and subtracting the result 
from r - just scale and shift this non-uniform distribution.


What you probably really want is

     rNum = r - (2*r) * ((double)rand() / (double)RAND_MAX);

This will give you a uniformly distributed value in the range -r to +r 
(excluding +r). Or, to get rid of the small bias towards -r:

     rNum = r - (2*r) * ((rand() + 0.5) / (double)RAND_MAX);


OTOH, if the exponential distribution is intentional, then what you want is:

     rNum = r / (1 - 2 * ((rand() + 0.5) / (double)RAND_MAX));

This will give you a uniformly distributed value in the range -1.#INF to 
+1.#INF (actually -r*RAND_MAX to +r*RAND_MAX if I'm not mistaken), 
clustering around 0.0.


>       srand(65535);

Are you sure you know what seed() does? The parameter, though not being 
illegal, looks suspicious for a random seed.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 25.08.2010 06:13, schrieb Anthony D. Baye:
>
> > Second my random number function. (I've attached the source file, but I'll
> > reiterate the function here) I'm using the rand() function from cstdlib:
> >
> > double Random(double r)
> > {
> >       double rNum;
> >
> >       rNum = r - (2*r)/(rand()%65535);
> >
> >       return rNum;
> > }
>
> What type of random distribution do you want to achieve? If you're
> attempting to get a uniform distribution in the interval -r to +r (i.e.
> each value in this interval is equally likely), then you're pretty much
> off the track.
>
> First, note that rand() /is/ uniformly distributed, in the interval 0 to
> RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).

this has not been my experience.  printing the result of one million calls to
rand() gives numbers up to ten digits long, but I've never seen a result less
than six digits in length.  If every result were equally likely, there should be
SOME lower numbers in the batch, shouldn't there?

A.D.B.
>
> Now, taking this number modulo 65535 doesn't change a thing, provided
> that RAND_MAX < 65535. Otherwise, it will give you a uniformly
> distributed value in the range 0 to 65534 (sic!).
>
> You take the inverse of this value, which gives you a /non-uniformly/
> distributed number. Not sure from the top of my hat /what/ distribution
> this gives you, but I think it's an exponential one, with the value x
> having a probability of c*e^-x. At any rate, the range is also modified.
> In a nutshell, at this point you get random values in the range
> 1/RAND_MAX (about 0.00003) to 1/0 (1.#INF, positive infinity), and while
> each individual value in practice still has roughly the same
> probability, the values clump together near 0.0 (for instance, the
> highest values are ..., 0.20, 0.25, 0.333, 0.50, 1.00, 1.#INF).
>
> The final operations - multiplying by 2*r and subtracting the result
> from r - just scale and shift this non-uniform distribution.
>
>
> What you probably really want is
>
>      rNum = r - (2*r) * ((double)rand() / (double)RAND_MAX);
>
> This will give you a uniformly distributed value in the range -r to +r
> (excluding +r). Or, to get rid of the small bias towards -r:
>
>      rNum = r - (2*r) * ((rand() + 0.5) / (double)RAND_MAX);
>
>
> OTOH, if the exponential distribution is intentional, then what you want is:
>
>      rNum = r / (1 - 2 * ((rand() + 0.5) / (double)RAND_MAX));
>
> This will give you a uniformly distributed value in the range -1.#INF to
> +1.#INF (actually -r*RAND_MAX to +r*RAND_MAX if I'm not mistaken),
> clustering around 0.0.
>
>
> >       srand(65535);
>
> Are you sure you know what seed() does? The parameter, though not being
> illegal, looks suspicious for a random seed.

Post a reply to this message

Am 25.08.2010 18:38, schrieb Anthony D. Baye:

>> First, note that rand() /is/ uniformly distributed, in the interval 0 to
>> RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).
>
> this has not been my experience.  printing the result of one million calls to
> rand() gives numbers up to ten digits long, but I've never seen a result less
> than six digits in length.  If every result were equally likely, there should be
> SOME lower numbers in the batch, shouldn't there?

Okay, let me rephrase that:

"... rand() /is/ _supposed_ to be uniformly distributed..."

According to ANSI-C standard, the actual implementation of rand() is 
implementation-specific, and is known to be poor in typical 
implementations. The maximum number returned - RAND_MAX - is 
implementation-specific as well, and is specified to be at least 32767. 
According to Microsoft documentation, their C runtime library has 
RAND_MAX=32767, though I haven't actually bothered to test it.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 25.08.2010 18:38, schrieb Anthony D. Baye:
>
> >> First, note that rand() /is/ uniformly distributed, in the interval 0 to
> >> RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).
> >
> > this has not been my experience.  printing the result of one million calls to
> > rand() gives numbers up to ten digits long, but I've never seen a result less
> > than six digits in length.  If every result were equally likely, there should be
> > SOME lower numbers in the batch, shouldn't there?
>
> Okay, let me rephrase that:
>
> "... rand() /is/ _supposed_ to be uniformly distributed..."
>
> According to ANSI-C standard, the actual implementation of rand() is
> implementation-specific, and is known to be poor in typical
> implementations. The maximum number returned - RAND_MAX - is
> implementation-specific as well, and is specified to be at least 32767.
> According to Microsoft documentation, their C runtime library has
> RAND_MAX=32767, though I haven't actually bothered to test it.

At any rate, the solution suggested by Le Forgeron, using drand48(), seems to
work.

There are still a few issues, however.

The chief problem is thatsuccessive calls to the program return the same result
every time.

The only way I've found to change the result is to modify the initial conditions
(i.e. changing the number of seed values in the grid before calling the
Diamond_Square() function.)

Thanks for the input, so far.

A.D.B.

Post a reply to this message

Anthony D. Baye wrote:
> The chief problem is thatsuccessive calls to the program return the same result
> every time.

There's undoubtedly a way to seed any such random number generator. Most 
people seed it off the wall clock.

-- 
Darren New, San Diego CA, USA (PST)
    Quoth the raven:
        Need S'Mores!

Post a reply to this message

Am 26.08.2010 00:52, schrieb Anthony D. Baye:

> The chief problem is thatsuccessive calls to the program return the same result
> every time.
>
> The only way I've found to change the result is to modify the initial conditions
> (i.e. changing the number of seed values in the grid before calling the
> Diamond_Square() function.)

Why, yes - of course; that's how pseudo-random number generators work 
;-). they're deterministic, after all (and as often as not this is even 
desired). To get a different result each time, a typical solution 
(outside of cryptographic applications that is) would be to seed with 
the current system time instead of a constant.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 26.08.2010 00:52, schrieb Anthony D. Baye:
>
> > The chief problem is thatsuccessive calls to the program return the same result
> > every time.
> >
> > The only way I've found to change the result is to modify the initial conditions
> > (i.e. changing the number of seed values in the grid before calling the
> > Diamond_Square() function.)
>
> Why, yes - of course; that's how pseudo-random number generators work
> ;-). they're deterministic, after all (and as often as not this is even
> desired). To get a different result each time, a typical solution
> (outside of cryptographic applications that is) would be to seed with
> the current system time instead of a constant.

I was getting hinky results when calling srand48(time(NULL)), but it turns out
that the solution was to call it once at the beginning of the program, rather
than every time I called my Random() function...

makes sense, I guess...

Thanks for all the help...

Post a reply to this message

> this has not been my experience.  printing the result of one million 
calls to
 > rand() gives numbers up to ten digits long, but I've never seen a 
result less
 > than six digits in length.  If every result were equally likely, 
there should be
 > SOME lower numbers in the batch, shouldn't there?

If your rand() gives you numbers between 0 and, say, 9999999999 (the 
largest number that is ten digits long), then 99.99% of those numbers 
will be over six digits in length. That's assuming that all numbers in 
the range are possible, which would not be the case if, say, it were 
taking a random integer from 0 to 32767 and then multiplying it to be 
much higher.

  - Slime

Post a reply to this message

Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> I was getting hinky results when calling srand48(time(NULL)), but it turns out
> that the solution was to call it once at the beginning of the program, rather
> than every time I called my Random() function...

  Well, think about it a bit. time() returns the amount of seconds since
some starting time. You are using that value to tell the random number
generator "start from here".

  If you do it again in less than a second, you will be again telling the
random number generator "start from here" (ie. the exact same number). What
do you expect to happen?

-- 
                                                          - Warp

Post a reply to this message