Skybuck Flying said:
Well since I am not a real C programmer... how do I know what is ansi
c/portable c and what's not ?
You can find out what ANSI C functions are by looking them up e.g.
in a reasonably good book on C (or by buying the standard, but
since it's written in a rather difficult to understand language,
you're probably better of with a book). If you have some UNIX
system these function are also usually marked in the "CONFORMING
TO" section of the man page as conforming to standard C (either the
"old" C89 standard or/and the "new" C99 standard).
Also this code is from unix... C was created for/from unix ?
There are probably millions of programs written for UNIX that
are not written in standard C but using some system specific
extensions. These then are to be discussed in for example
comp.unix.programmer.
I can see how unix libraries etc have evolved... and I can understand that
nrand48() is not part of the ansi C standard.
However... how about __builtin_expect this has to do with branch prediction
apperently etc.. so I can see how this might evolve into an ANSI C
standard...
"Branch prediction" is something that is relevant for only a subset
of all existing processors. But standard C tries to stay as far as
humanly possible from any system specific stuff, so you probably
will never see anything related to "branch prediction" in the standard.
Actually, "branch prediction" is something that might or might not
become relevant in the _implementation_ of a C compiler for a specific
platform. But the C standard is just about the language, not how it
is actually realized on a certain system. It's like the difference
between some electronic circuitry you draw on some piece of paper
and what you solder together according to that schematics. When you
draw the circuitry you usually don't give too much thought to the
resistance of the wires connecting the parts or some stray capacitances
or impedances. These problems usually come into play only when you
really start soldering stuff together ("implement" the circuitry).
Or is the ANSI C standard completely frozen ?
Yes, of course. But some people are probably already working on
a new version.
None the less, I also totally don't care about the implementation of builtin
expect... I do care about how to replace the concept in portable/ansi C
I tried understanding the algorithm... Unfortunately for me all the
documentation that I found is very hard to understand and doesn't even talk
about pseudo code etc...
So I am better off trying out some already made code... seeing if it
works... seeing how it works...
Well, the algorithm is rather simple and is described in
http://www.opengroup.org/onlinepubs/009695399/functions/drand48.html
When you have an element X_n of the series of pseudo-random numbers
you get the next one, X_n+1, by applying the formula
X_n+1 = ( a * X_n + c ) mod m n >= 0
That's what's called a "linear congruential algorithm". The numbers
a, c and m are (at least for nrand48())
a = 0x5DEECE66D = 0273673163155
b = 0xB = 013
m = 2^48
where numbers starting with '0x' are in hexadecimal and numbers starting
with just '0' are in octal. 2^48 means 2 to the power of 48. All the
X_n's are 48-bit numbers and the value returned by the function is X_n+1
after taking the top-most 31 bits and shifting them right by 17 bits.
Unless you seed the ramdom generator (using seed48()) it will start with
X_0 being 0.
The important part now is that the calculations have to be done in a
way in which you don't lose (too many) bits by integer overflows. That
could be the difficult part of it. As far as I can see, the code you
showed don't really care about overflows - it does the multiplication
without much regard for possible overflows when using 64-bit wide
variables, making things rather simple (but I don't know if every
implementation of nrand48() deals with this in the same way, so you
might find out that your version of nrand48() delivers a different
sequence of random numbers than the nrand48() function from some other
machine.)
Actually, I am still not convinced that you really need any special
properties of nrand48() but would guess that any reasonable pseudo-
random generator delivering numbers in the interval [0,2^31) (i.e.
between 0 and 2^31 - 1) would also do. Probably the rand() function
would do just fine...
Regards, Jens