a gift for the mortensens

K

Keith Thompson

frank said:
I've seen now several versions of
i = (j / (RAND_MAX + 1.0)) * N;
What is happening to 1222567701 / (RAND_MAX + 1.0) * 26?
Of what type is (RAND_MAX + 1.0) ?

RAND_MAX is of type int. 1.0 is of type double. The "usual
arithmetic conversions" are applied to the operands (C99 6.5.6p4).
These are described in 6.3.1.8. RAND_MAX is converted from int to
double, and the addition yields a double result.

Grab a copy of <http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf>
if you haven't already. Or any decent C reference should explain it.

Something else I just thought of: An alternative to
(RAND_MAX + 1.0)
would be
(double)(RAND_MAX + 1)
The version with 1.0 has two advantages that I can think of:
it avoids the need for a cast, and it avoids integer overflow if
RAND_MAX == INT_MAX.
 
F

frank

Keith said:
RAND_MAX is of type int. 1.0 is of type double. The "usual
arithmetic conversions" are applied to the operands (C99 6.5.6p4).
These are described in 6.3.1.8. RAND_MAX is converted from int to
double, and the addition yields a double result.

Grab a copy of <http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf>
if you haven't already. Or any decent C reference should explain it.

Something else I just thought of: An alternative to
(RAND_MAX + 1.0)
would be
(double)(RAND_MAX + 1)
The version with 1.0 has two advantages that I can think of:
it avoids the need for a cast, and it avoids integer overflow if
RAND_MAX == INT_MAX.

I'm not sure that does what you think it does:


dan@dan-desktop:~/source$ gcc -std=c99 -Wall -Wextra mort7.c -o out; ./out
mort7.c: In function ‘main’:
mort7.c:35: warning: integer overflow in expression
mort7.c:22: warning: unused variable ‘g’
mort7.c:21: warning: unused variable ‘k’
mort7.c:21: warning: unused variable ‘i’
3908406666 = 00010111010010111100000101011010
-2147483648.0000006 =
1100000111100000000000000000000000000000000000000000000000000000
dan@dan-desktop:~/source$ cat mort7.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <limits.h>

#define STRING "%7d6 = %s\n"
#define E_TYPE int
#define F_TYPE double
#define STRING2 "%7f6 = %s\n"
#define N 26

typedef E_TYPE e_type;
typedef F_TYPE f_type;

void bitstr (char *str, const void *obj, size_t n);

int
main (void)
{
int i, j, k;
double g;
e_type e;
f_type f;
char ebits[CHAR_BIT * sizeof e + 1];
char fbits[CHAR_BIT * sizeof f + 1];

srand (time (NULL));
j = rand ();
e = j;
bitstr (ebits, &e, sizeof e);
printf (STRING, e, ebits);


f = (double)(RAND_MAX + 1);
bitstr (fbits, &f, sizeof f);
printf (STRING2, f, fbits);



return 0;
}

void
bitstr (char *str, const void *obj, size_t n)
{
unsigned mask;
const unsigned char *const byte = obj;

while (n-- != 0)
{
mask = ((unsigned char) -1 >> 1) + 1;

do
{
*str++ = (char) (mask & byte[n] ? '1' : '0');
mask >>= 1;
}
while (mask != 0);
}
*str = '\0';
}


// gcc -std=c99 -Wall -Wextra mort7.c -o out; ./out
dan@dan-desktop:~/source$

I think we all agree that none of these values are to be negative.
 
F

frank

Phil said:
After years of dithering between different techniques, I now almost
always use Richard's. I think nothing says 'use floating point' more
concisely than actually sticking floating point numbers in the
expression. Try it - you might like it ;-)

Phil

I think it's important that the 1.0 bubbles up. You know a machine can
always give you one represented as a double. Adding RAND_MAX is then
small potatoes.

I've looked at a few different ways to do it, and the less good ones
involve building the integer, which isn't a good idea with RAND_MAX, and
then casting/converting it to a floating point type.

I still haven't figured out why we're creating a double type with a
value near RAND_MAX, but overflow is not the way to get there. Can
someone say a few words about
integer / double * integer?
 
F

frank

Keith said:
If you want random lowercase letters, you can declare

const char letters[] = "abcdefghijklmnopqrstuvwxyz"

and index into the array with a random number in the range 0..25.

I've got something now that looks alright, and it seems to test well for
the 200,000 times I put it through its paces:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define N 26

char random_char (void);

int
main (void)
{
char a;
int i, counter;

srand (time (NULL));

counter = 0;

for (i = 0; i < RAND_MAX / 1000; ++i)
{
a = random_char ();
// printf("a is %c\n", a);
++counter;
}
printf ("counter is %d\n", counter);

return 0;
}

char
random_char (void)
{
char c;
int i, j;
const char letters[] = "abcdefghijklmnopqrstuvwxyz";
j = rand ();
i = (j / (RAND_MAX + 1.0)) * N;
assert (0 <= i && i < N);
c = letters;
return c;
}


// gcc -std=c99 -Wall -Wextra f1.c -o out; ./out

What I can't tell here is whether I've written something hugely
expensive in terms of computation. Would this code perform well?
 
P

Phil Carmody

frank said:
I still haven't figured out why we're creating a double type with a
value near RAND_MAX, but overflow is not the way to get there. Can
someone say a few words about
integer / double * integer?

Treated as ((integer/double)*integer). (integer/double) is
performed as (double/double) to yield a double. And then
(double*integer) performed as (double*double) to yield a
double.

It's integer/integer you normally want to be very wary of,
if you're embedding it within a tree of expressions that
will eventually become a double.

Phil
 
P

Phil Carmody

Ben Bacarisse said:
I don't know of real world systems with 64-bit RAND_MAX. My warning
was for the future of this common idiom. Of course, if you switch
rand() for a 64-bit RNG (like KISS recently posted by George
Marsaglia) you get the same problem if you use the idiom above.


That doesn't help, I don't think. Using my gcc, it is true that a
large RAND_MAX get rounded up when converted to double, but so do a
few of the returned values from rand(). Adding 1 does not have the
effect of making the result of the division < 1.0 because the +1 has
no effect.

AH, I didn't realise you were looking at that end of the issue.
Indeed, that is a problem.
The probability of getting a large rand() from a 64-bit generator is
very low, but it will happen one day! Here is the worse case example
on my system. 512 returns from rand() can cause problems. You can
fix it with long double but since that may be no wider than double,
that option can just mask the problem until the code moves to another
machine.

#include <stdio.h>
#include <limits.h>

#define RAND_MAX LLONG_MAX
#define N 10

long long int rand(void) { return RAND_MAX-511; }

int main(void)
{
int n = (rand() / (RAND_MAX + 1.0)) * N;
if (n == N)
puts("Don't use n as an array index!");

Yeah, but if you're mucking around with FP anyway, you shouldn't
expect results to not be inconveniently rounded occasionally
unless you've done some very thorough numerical analysis. 754 may
help you but C on its own doesn't.

It does appear that implementers are very slow to migrate to
larger RAND_MAX, or in fact do anything to make rand() less of
the almost-useless toy that it currently is, so hopefully this
will never be a problem.

Already missing contributions by Dik,
Phil
 
F

frank

[big snip]
I've seen now several versions  of
i = (j / (RAND_MAX + 1.0)) * N;
What is happening to 1222567701 / (RAND_MAX + 1.0) * 26?
Of what type is (RAND_MAX + 1.0) ?

RAND_MAX is of type int.  1.0 is of type double.  The "usual
arithmetic conversions" are applied to the operands (C99 6.5.6p4).
These are described in 6.3.1.8.  RAND_MAX is converted from int to
double, and the addition yields a double result.

Grab a copy of <http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf>
if you haven't already.  Or any decent C reference should explain it.

Something else I just thought of: An alternative to
    (RAND_MAX + 1.0)
would be
    (double)(RAND_MAX + 1)
The version with 1.0 has two advantages that I can think of:
it avoids the need for a cast, and it avoids integer overflow if
RAND_MAX == INT_MAX.

Otherwise, if both operands have signed integer types or both have
unsigned
integer types, the operand with the type of lesser integer conversion
rank is
converted to the type of the operand with greater rank.
Otherwise, if the operand that has unsigned integer type has rank
greater or
equal to the rank of the type of the other operand, then the operand
with
signed integer type is converted to the type of the operand with
unsigned
integer type.
Otherwise, if the type of the operand with signed integer type can
represent
all of the values of the type of the operand with unsigned integer
type, then
the operand with unsigned integer type is converted to the type of the
operand with signed integer type.
Otherwise, both operands are converted to the unsigned integer type
corresponding to the type of the operand with signed integer type.

Can someone show an example for these integer promotions?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top