Should rand() return a RAND_MAX value for 32 bit target?

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

Should rand() return a RAND_MAX value for 32 bit target?

Neha Gowda
Hi,

I am trying to run the following testcase for Random Number Generator
function.
The testcase returns true when generated number is RAND_MAX and returns
false when its not generated.

Command :- gcc -m32 -O2 test.c
======================================================
#include <stdio.h>
#include <stdlib.h>

int main()
{
    unsigned int i;
    float f;
    srand(0);
    for (i = 0; i <= RAND_MAX; i++) {
        f = rand();
        if (f == RAND_MAX) {
                printf("True\n");
            return 0;
        }
    }
        printf("False\n");
    return 1;
}
======================================================
Tried them on the latest source and observed that the RAND_MAX is generated
when
the optimization is not enabled. When optimization is enabled for 32 bit
target RAND_MAX
is not being generated. However, 64 bit generates RAND_MAX with or without
optimization.

On further investigation, I found that the expand phase is optimizing the
following and hence
the RAND_MAX value is not being generated.
=========================================
Replacing Expressions
f_10 replace with --> f_10 = (float) _1;
=========================================

Can you please let me know if its the expected behavior or some bug?

Thanks,
Neha
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Xi Ruoyao-3
On 2018-09-18 17:52 +0530, Neha Gowda wrote:

> Hi,
>
> I am trying to run the following testcase for Random Number Generator
> function.
> The testcase returns true when generated number is RAND_MAX and returns
> false when its not generated.
>
> Command :- gcc -m32 -O2 test.c
> ======================================================
> #include <stdio.h>
> #include <stdlib.h>
>
> int main()
> {
>     unsigned int i;
>     float f;
>     srand(0);
>     for (i = 0; i <= RAND_MAX; i++) {
>         f = rand();

There is a rounding error introduced since a float can not represent
all integer values in [0, RAND_MAX].

>         if (f == RAND_MAX) {

RAND_MAX is 2147483647 on 32-bit GNU/Linux.  It can not be represented
by a float.

>                 printf("True\n");
>             return 0;
>         }
>     }
>         printf("False\n");
>     return 1;
> }
> ======================================================
> Tried them on the latest source and observed that the RAND_MAX is generated
> when
> the optimization is not enabled. When optimization is enabled for 32 bit
> target RAND_MAX
> is not being generated. However, 64 bit generates RAND_MAX with or without
> optimization.
>
> On further investigation, I found that the expand phase is optimizing the
> following and hence
> the RAND_MAX value is not being generated.
> =========================================
> Replacing Expressions
> f_10 replace with --> f_10 = (float) _1;
> =========================================
>
> Can you please let me know if its the expected behavior or some bug?

See https://gcc.gnu.org/wiki/FAQ#PR323.
--
Xi Ruoyao <[hidden email]>
School of Aerospace Science and Technology, Xidian University

Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Xi Ruoyao-3
On 2018-09-18 21:09 +0800, Xi Ruoyao wrote:
> > Tried them on the latest source and observed that the RAND_MAX is generated
> > when
> > the optimization is not enabled. When optimization is enabled for 32 bit
> > target RAND_MAX
> > is not being generated. However, 64 bit generates RAND_MAX with or without
> > optimization.

And I must say, in your program RAND_MAX is NOT generated with Glibc 2.26 on
Linux.  You seen "True" because of floating point rounding error.

> See https://gcc.gnu.org/wiki/FAQ#PR323.
--
Xi Ruoyao <[hidden email]>
School of Aerospace Science and Technology, Xidian University

Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Andrew Haley
In reply to this post by Neha Gowda
On 09/18/2018 01:22 PM, Neha Gowda wrote:
> Can you please let me know if its the expected behavior or some bug?

First consider the value of (float)RAND_MAX. Then please consider if
using -ffloat-store will make any difference to your program and then
you may be enlightened. If not, please come back and ask again.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Jonathan Wakely-4
In reply to this post by Xi Ruoyao-3
On Tue, 18 Sep 2018 at 14:09, Xi Ruoyao wrote:

>
> On 2018-09-18 17:52 +0530, Neha Gowda wrote:
> > Hi,
> >
> > I am trying to run the following testcase for Random Number Generator
> > function.
> > The testcase returns true when generated number is RAND_MAX and returns
> > false when its not generated.
> >
> > Command :- gcc -m32 -O2 test.c
> > ======================================================
> > #include <stdio.h>
> > #include <stdlib.h>
> >
> > int main()
> > {
> >     unsigned int i;
> >     float f;
> >     srand(0);
> >     for (i = 0; i <= RAND_MAX; i++) {
> >         f = rand();
>
> There is a rounding error introduced since a float can not represent
> all integer values in [0, RAND_MAX].
>
> >         if (f == RAND_MAX) {
>
> RAND_MAX is 2147483647 on 32-bit GNU/Linux.  It can not be represented
> by a float.

Which leads to the question, why are you using float anyway?

rand() returns an int, not a float.
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
In reply to this post by Andrew Haley
On 2018-09-18 14:46:24 +0100, Andrew Haley wrote:
> On 09/18/2018 01:22 PM, Neha Gowda wrote:
> > Can you please let me know if its the expected behavior or some bug?
>
> First consider the value of (float)RAND_MAX. Then please consider if
> using -ffloat-store will make any difference to your program and then
> you may be enlightened. If not, please come back and ask again.

No, the program is so buggy that -ffloat-store does not solve the
problem because there is rounding in the == expression. As a short
example:

#include <stdio.h>

int main (void)
{
  float f = 2147483646;
  if (f == 2147483647)
    {
      printf("%.20g\n", (double) f);
    }
  return 0;
}

outputs 2147483648 because the == is done on float. Thus, from the
original program, you cannot deduce anything.

And BTW, don't try to cast f to int, that's undefined behavior here.

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
Actually, there may be a bug with -m32:

#include <stdio.h>
#include <float.h>

int main (void)
{
  float f = 2147483646;
  printf ("FLT_EVAL_METHOD = %d\n", (int) FLT_EVAL_METHOD);
  if (f == 2147483647)
    {
      printf("%.20g\n", (double) f);
    }
  return 0;
}

$ gcc -std=c99 -m32 -O tst.c -o tst
$ ./tst
FLT_EVAL_METHOD = 2
2147483648

Since FLT_EVAL_METHOD = 2, float_t is long double, thus shouldn't
2147483647 be converted to long double directly (as f is regarded
as an operand of type long double), so that the result of the
equality test should be false?

The C standard says for FLT_EVAL_METHOD = 2: "evaluate all operations
and constants to the range and precision of the long double type".
^^^^^^^^^^^^^

Converting f first to float is contrary to the idea behind
FLT_EVAL_METHOD = 2, which is to avoid loss of precision in
intermediate operations.

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Liu Hao-2
在 2018/9/20 23:05, Vincent Lefevre 写道:

> Actually, there may be a bug with -m32:
>
> #include <stdio.h>
> #include <float.h>
>
> int main (void)
> {
>    float f = 2147483646;
>    printf ("FLT_EVAL_METHOD = %d\n", (int) FLT_EVAL_METHOD);
>    if (f == 2147483647)
>      {
>        printf("%.20g\n", (double) f);
>      }
>    return 0;
> }
>
> $ gcc -std=c99 -m32 -O tst.c -o tst
> $ ./tst
> FLT_EVAL_METHOD = 2
> 2147483648
>
> Since FLT_EVAL_METHOD = 2, float_t is long double, thus shouldn't
> 2147483647 be converted to long double directly (as f is regarded
> as an operand of type long double), so that the result of the
> equality test should be false?
>
> The C standard says for FLT_EVAL_METHOD = 2: "evaluate all operations
> and constants to the range and precision of the long double type".
> ^^^^^^^^^^^^^
>

-----
ISO/IEC 9899:2017
(WG14 N2176)
5.2.4.2.2 Characteristics of floating types <float.h>
9 Except for assignment and cast (which remove all extra range and
precision), the values yielded by operators with floating operands and
values subject to the usual arithmetic conversions and of **floating
constants** are evaluated to a format whose range and precision may be
greater than required by the type. The use of evaluation formats is
characterized by the implementation-defined value of FLT_EVAL_METHOD:24)
-----

`2147483647` is an integer constant. This rule only describes floating
constants, so it does not apply.

According to '6.3.1.8 Usual arithmetic conversions', here `2147483647`
is converted to a value having type `float`, which is then compared with
`f` using the internal `long double` type.


> Converting f first to float is contrary to the idea behind
> FLT_EVAL_METHOD = 2, which is to avoid loss of precision in
> intermediate operations.
>


--
Best regards,
LH_Mouse
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Dennis Clarke-2
In reply to this post by Vincent Lefevre-3
On 09/20/2018 11:05 AM, Vincent Lefevre wrote:

> Actually, there may be a bug with -m32:
>
> #include <stdio.h>
> #include <float.h>
>
> int main (void)
> {
>    float f = 2147483646;
>    printf ("FLT_EVAL_METHOD = %d\n", (int) FLT_EVAL_METHOD);
>    if (f == 2147483647)
>      {
>        printf("%.20g\n", (double) f);
>      }
>    return 0;
> }
>
> $ gcc -std=c99 -m32 -O tst.c -o tst
> $ ./tst
> FLT_EVAL_METHOD = 2
> 2147483648
>
> Since FLT_EVAL_METHOD = 2, float_t is long double, thus shouldn't
> 2147483647 be converted to long double directly (as f is regarded
> as an operand of type long double), so that the result of the
> equality test should be false?
>
> The C standard says for FLT_EVAL_METHOD = 2: "evaluate all operations
> and constants to the range and precision of the long double type".
> ^^^^^^^^^^^^^
>
> Converting f first to float is contrary to the idea behind
> FLT_EVAL_METHOD = 2, which is to avoid loss of precision in
> intermediate operations.
>

Hrmmm ... I see FLT_EVAL_METHOD = 0 here with gcc 8.1.0 on sparc :

$ file ./flt_eval
./flt_eval: ELF 32-bit MSB executable SPARC32PLUS Version 1, V8+
Required, dynamically linked, not stripped, no debugging information
available

$ ./flt_eval
FLT_EVAL_METHOD = 0
2147483648

I see similar on ppc64 :

$ file flt_eval
flt_eval: ELF 32-bit MSB executable, PowerPC or cisco 4500, version 1
(SYSV), dynamically linked, interpreter /lib/ld.so.1, for GNU/Linux
3.2.0, not stripped
$ ./flt_eval
FLT_EVAL_METHOD = 0
2147483648
$

Not sure how you are getting FLT_EVAL_METHOD as 2.

What platform is this on ?


Dennis
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
In reply to this post by Liu Hao-2
On 2018-09-20 23:21:23 +0800, Liu Hao wrote:
> `2147483647` is an integer constant. This rule only describes floating
> constants, so it does not apply.

Actually the fact that it is a constant doesn't matter, but...

> According to '6.3.1.8 Usual arithmetic conversions', here `2147483647`
> is converted to a value having type `float`, which is then compared with
> `f` using the internal `long double` type.

The conversion of the int needs to be done with the precision and
range of long double since this is neither an assignment nor a cast.

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
On 2018-09-20 17:58:30 +0200, Vincent Lefevre wrote:

> On 2018-09-20 23:21:23 +0800, Liu Hao wrote:
> > `2147483647` is an integer constant. This rule only describes floating
> > constants, so it does not apply.
>
> Actually the fact that it is a constant doesn't matter, but...
>
> > According to '6.3.1.8 Usual arithmetic conversions', here `2147483647`
> > is converted to a value having type `float`, which is then compared with
> > `f` using the internal `long double` type.
>
> The conversion of the int needs to be done with the precision and
> range of long double since this is neither an assignment nor a cast.

Similarly, for

  float a, b;
  double c;

  (a + b) + c;

I would expect the result of a + b to be kept in long double instead
of being converted to double due to the operand c.

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
In reply to this post by Dennis Clarke-2
On 2018-09-20 11:46:38 -0400, Dennis Clarke wrote:
> Not sure how you are getting FLT_EVAL_METHOD as 2.
>
> What platform is this on ?

32-bit x86, like the OP, I assume.

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Liu Hao-2
In reply to this post by Vincent Lefevre-3
在 2018-09-20 23:58, Vincent Lefevre 写道:
> On 2018-09-20 23:21:23 +0800, Liu Hao wrote:
>> `2147483647` is an integer constant. This rule only describes floating
>> constants, so it does not apply.
>
> Actually the fact that it is a constant doesn't matter, but...
>

The paragraph quoted by the previous message contains a sentence saying
'...  and of floating constants are evaluated to a format ...'. While
all following paragraphs don't mention `floating constants` explicitly,
it is implied.

If it could be said that 'constants' included integer constants here
then I would also reasonably think that 'all operations' here also
included operations involving only integers - which does not make any
sense at all.

This is not the place for discussion of the C standard. Anyway I don't
see any problems in GCC's implementation.

>> According to '6.3.1.8 Usual arithmetic conversions', here `2147483647`
>> is converted to a value having type `float`, which is then compared with
>> `f` using the internal `long double` type.
>
> The conversion of the int needs to be done with the precision and
> range of long double since this is neither an assignment nor a cast.
>

If there is no indeterminate results (as in your example) then there is
no difference.

An example where this truncation does matter is as follows, tested on
Linux Mint 19, x64 with GCC 7.3 :

-----
lh_mouse@lhmouse-ideapad ~/Desktop $ cat test.c
#include <stdio.h>
#include <float.h>

float a = 0x1.0002p0;
float b = 0x1.0003p0;
float c = 0x1.0005p0;

int main(void)
   {
     printf("FLT_EVAL_METHOD = %d\n", (int)FLT_EVAL_METHOD);
     printf("a * b == c        ?   %d\n", a * b == c);
     printf("a * b == (float)c ?   %d\n", a * b == (float)c);
   }
lh_mouse@lhmouse-ideapad ~/Desktop $ gcc test.c  -std=c99 -O0 -m32
-march=pentium4 -mfpmath=sse && ./a.out
FLT_EVAL_METHOD = 0
a * b == c        ?   1
a * b == (float)c ?   1
lh_mouse@lhmouse-ideapad ~/Desktop $ gcc test.c  -std=c99 -O0 -m32 &&
./a.out
FLT_EVAL_METHOD = 2
a * b == c        ?   0
a * b == (float)c ?   0
-----


--
Best regards,
LH_Mouse
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
On 2018-09-21 10:49:19 +0800, Liu Hao wrote:

> 在 2018-09-20 23:58, Vincent Lefevre 写道:
> > On 2018-09-20 23:21:23 +0800, Liu Hao wrote:
> >> `2147483647` is an integer constant. This rule only describes floating
> >> constants, so it does not apply.
> >
> > Actually the fact that it is a constant doesn't matter, but...
>
> The paragraph quoted by the previous message contains a sentence saying
> '...  and of floating constants are evaluated to a format ...'. While
> all following paragraphs don't mention `floating constants` explicitly,
> it is implied.

Forgot what I said at that time. It's an integer constant, thus it
is always evaluated *exactly* as an integer. Then, the rules for
type conversions in a floating-point expression are the same, whether
the values come from constants and non-constants.

Thus if one does

  float a;
  int b;

  /* ... */
  a + b;

with FLT_EVAL_METHOD = 2, the evaluation type of a is long double, b
is converted to the semantic type float, but its evaluation type is
long double, so that its value should not change if representable as
a long double. That's what FLT_EVAL_METHOD means. The *only* cases
for which the precision and range need to be reduced to those of the
semantic type if for assignment and cast, but here one just has an
implicit conversion.

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
On 2018-09-22 10:17:04 +0200, Vincent Lefevre wrote:

> Thus if one does
>
>   float a;
>   int b;
>
>   /* ... */
>   a + b;
>
> with FLT_EVAL_METHOD = 2, the evaluation type of a is long double, b
> is converted to the semantic type float, but its evaluation type is
> long double, so that its value should not change if representable as
> a long double. That's what FLT_EVAL_METHOD means. The *only* cases
> for which the precision and range need to be reduced to those of the
> semantic type if for assignment and cast, but here one just has an
> implicit conversion.

Bug reported here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87390
(note that the tests do not involve constants, these are just about
implicit type conversions).

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Liu Hao-2
在 2018/9/22 18:08, Vincent Lefevre 写道:
> Bug reported here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87390
> (note that the tests do not involve constants, these are just about
> implicit type conversions).
>

That's about contraction. The behavior in the OP can only be observed
when no optimization is enabled (i.e. with `-O0`) or when strict
standard compliance is requested (i.e. with `-std=c99` or `-ansi`) and
no `-ffp-contract=fast` is in effect.

It is irrelevant to this issue. Contraction is about what happens within
a floating-point operation, but in your program (the standard says)
`2147483647` is converted to type `float` before the floating-point
comparison, so it behaves as if you had added a cast like `f ==
(float)2147483647`. This implicit conversion can be observed by
compiling the program in question with `-Wconversion`. You already had
precision loss BEFORE the comparison which is irrecoverable by any
evaluation method.

--
Best regards,
LH_Mouse
Reply | Threaded
Open this post in threaded view
|

Re: Should rand() return a RAND_MAX value for 32 bit target?

Vincent Lefevre-3
On 2018-09-22 21:52:34 +0800, Liu Hao wrote:
> 在 2018/9/22 18:08, Vincent Lefevre 写道:
> > Bug reported here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87390
> > (note that the tests do not involve constants, these are just about
> > implicit type conversions).
>
> That's about contraction.

No, FLT_EVAL_METHOD is not related to contraction.

> The behavior in the OP can only be observed when no optimization is
> enabled (i.e. with `-O0`) or when strict standard compliance is
> requested (i.e. with `-std=c99` or `-ansi`) and no
> `-ffp-contract=fast` is in effect.

With the OP's program, I get False only when optimization is enabled
and strict standard compliance is not requested (or equivalent).

> It is irrelevant to this issue.

It is: If FLT_EVAL_METHOD were honored for integer-to-float
conversion, one should have never got True with strict standard
compliance, because the value of f is exactly representable in
a float and RAND_MAX isn't.

> Contraction is about what happens within a floating-point operation,

I'm not considering contraction, but FLT_EVAL_METHOD.

> but in your program (the standard says) `2147483647` is converted to
> type `float` before the floating-point comparison,

This is the semantic type. But the evaluation type is long double.

> so it behaves as if you had added a cast like `f ==
> (float)2147483647`.

No, the standard says "Except for assignment and cast (which remove
all extra range and precision), [...]", thus by adding the cast, you
are changing the semantics.

See the testcase I've posted to my bug report, and the parallel
between (float) d + (float) 1.0 and  i + 1 (both are converted
to the semantic type double, but GCC's behavior is different on
these two expressions).

--
Vincent Lefèvre <[hidden email]> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)