Christian Couder wrote:
> On Thu, Jun 11, 2009 at 7:05 AM, H. Peter Anvin<hpa@xxxxxxxxx> wrote:
>> Urk, I managed to get myself completely confused -- I did the series
>> approximation on the wrong side of inverting the function. The correct
>> power is actually 1.5 (over the range 0 to 1), a value > 1 is necessary
>> to bias the PRNG toward the beginning (x = 0) of the list.
>
> I started working on this, but I wonder if it's better to add a
> #include <math.h> and link with -lm than to provide a custom sqrt
> implementation. Too bad the best power is not 2.
>
That's what I would do. It's not like sqrt() is a strange, unportable
function.
> To implement the PRNG, I guess that using something based on the
> function given by "man 3 rand" should be ok:
>
> int get_prn(int count) {
> count = count * 1103515245 + 12345;
> return((unsigned)(count/65536) % 32768);
> }
>
> where the "count" we pass is the count of elements in the list rather
> than the static seed.
Yes, or perhaps better we could use some combination of the SHA-1s
involved as seeds... they are rather nice for this as they are wide and
much better PRNGs than most classical algorithms.
The main problem with the above algorithm is that it only produces 16
bits of output, which when biased can turn into a fairly significant
granularity.
-hpa
--
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel. I don't speak on their behalf.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html