On Sat, Jun 13, 2009 at 9:03 PM, H. Peter Anvin<hpa@xxxxxxxxx> wrote:
> 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.
Yes, but I feared that there could be rounding related differences
between platforms.
By the way, could you explain why power 1.5 is better than 2? It would
be much simpler if we could avoid square rooting anything in the first
place.
>> 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.
I don't think this is a real problem for this application. In fact I
think it's already quite overkill and there are better things to do,
like looking for a commit on a different branch among the first ones
in the list, if we want to improve the current behavior.
So unless there is a real flaw, I am going to work on something else.
Best regards,
Christian.
--
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