> std.random could be greatly improved upon.

You can find a GPL'd implementation of the Mersenne Twister in Indigo: http://www.uwesalomon.de/code/indigo

Ciao
uwe

Oskar Linde wrote:
> I think Niko may be referring to the fact that some poor implementations of
> rand() suffer from having a lower degree of "randomness" in the less
> significant bits than in the more significant bits.

Yes, that's exactly it. I remember reading about it from a Donald Knuth textbook as well as some Java-related articles. Somehow it stuck to my mind.

But by all means, when we're talking about D, I would prefer Walter's advice against mine :)

-- 
Niko Korhonen
SW Developer

Niko Korhonen wrote:
> Oskar Linde wrote:
> 
>> I think Niko may be referring to the fact that some poor implementations of
>> rand() suffer from having a lower degree of "randomness" in the less
>> significant bits than in the more significant bits.
> 
> 
> Yes, that's exactly it. I remember reading about it from a Donald Knuth textbook as well as some Java-related articles. Somehow it stuck to my mind.
> 
> But by all means, when we're talking about D, I would prefer Walter's advice against mine :)
> 


Here's a really great, and very fast, function. It's the one employed by Mango:

        KISS (via George Marsaglia & Paul Hsieh)

        the idea is to use simple, fast, individually promising
        generators to get a composite that will be fast, easy to code
        have a very long period and pass all the tests put to it.
        The three components of KISS are

                x(n)=a*x(n-1)+1 mod 2^32
                y(n)=y(n-1)(I+L^13)(I+R^17)(I+L^5),
                z(n)=2*z(n-1)+z(n-2) +carry mod 2^32

        The y's are a shift register sequence on 32bit binary vectors
        period 2^32-1; The z's are a simple multiply-with-carry sequence
        with period 2^63+2^32-1.

        The period of KISS is thus 2^32*(2^32-1)*(2^63+2^32-1) > 2^127



        private static uint kiss_x = 1;
        private static uint kiss_y = 2;
        private static uint kiss_z = 4;
        private static uint kiss_w = 8;
        private static uint kiss_carry = 0;
        private static uint kiss_k;
        private static uint kiss_m;

        static final uint get ()
        {
                kiss_x = kiss_x * 69069 + 1;
                kiss_y ^= kiss_y << 13;
                kiss_y ^= kiss_y >> 17;
                kiss_y ^= kiss_y << 5;
                kiss_k = (kiss_z >> 2)+(kiss_w >> 3)+(kiss_carry >> 2);
                kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry;
                kiss_z = kiss_w;
                kiss_w = kiss_m;
                kiss_carry = kiss_k >> 30;
                return kiss_x + kiss_y + kiss_w;
        }


I still use this on tiny 10MHz MCUs ~ code generators love the design. Just for jollies, I'll throw down a challenge that this is the best compromise in terms of period & execution time <g>

kris wrote:
> 
> Here's a really great, and very fast, function. It's the one employed by
> Mango:
> 
>   KISS (via George Marsaglia & Paul Hsieh)
> 
>   static final uint get ()
>   {
>     kiss_x = kiss_x * 69069 + 1;
>     kiss_y ^= kiss_y << 13;
>     kiss_y ^= kiss_y >> 17;
>     kiss_y ^= kiss_y << 5;
>     kiss_k = (kiss_z >> 2)+(kiss_w >> 3)+(kiss_carry >> 2);
>     kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry;
>     kiss_z = kiss_w;
>     kiss_w = kiss_m;
>     kiss_carry = kiss_k >> 30;
>     return kiss_x + kiss_y + kiss_w;
>   }
> 
> I still use this on tiny 10MHz MCUs ~ code generators love the design. Just for jollies, I'll throw down a challenge that this is the best compromise in terms of period & execution time <g>

Had somebody shown that to me, at first sight I'd dissed it as a toy.

But then the idea of having "a random generator" whose output is added to "less random, but long-period" things is intriguing. And the fact that there's no cross transport of information between these is kind of neat.

At brief googling I didn't find any white papers or such about it. Any pointers?

BTW, that 10MHz stuff souded interesting. May I ask what you do for a daytime job?

Georg Wrede wrote:
> kris wrote:
> 
>>
>> Here's a really great, and very fast, function. It's the one employed by
>> Mango:
>>
>>   KISS (via George Marsaglia & Paul Hsieh)
>>
>>   static final uint get ()
>>   {
>>     kiss_x = kiss_x * 69069 + 1;
>>     kiss_y ^= kiss_y << 13;
>>     kiss_y ^= kiss_y >> 17;
>>     kiss_y ^= kiss_y << 5;
>>     kiss_k = (kiss_z >> 2)+(kiss_w >> 3)+(kiss_carry >> 2);
>>     kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry;
>>     kiss_z = kiss_w;
>>     kiss_w = kiss_m;
>>     kiss_carry = kiss_k >> 30;
>>     return kiss_x + kiss_y + kiss_w;
>>   }
>>
>> I still use this on tiny 10MHz MCUs ~ code generators love the design. Just for jollies, I'll throw down a challenge that this is the best compromise in terms of period & execution time <g>
> 
> 
> Had somebody shown that to me, at first sight I'd dissed it as a toy.
> 
> But then the idea of having "a random generator" whose output is added to "less random, but long-period" things is intriguing. And the fact that there's no cross transport of information between these is kind of neat.
> 
> At brief googling I didn't find any white papers or such about it. Any pointers?

http://www.agner.org/random/
has some interesting articles and highly optimised asm code, and good links, including
http://random.mat.sbg.ac.at/

At Agner's site I found that the low-bits-not-random issue is a property of lagged Fibonnacci generators.

>> At brief googling I didn't find any white papers or such about it.
>> Any pointers?
> 
> 
> http://www.agner.org/random/ has some interesting articles and highly
> optimised asm code, and good links, including http://random.mat.sbg.ac.at/
> 
> At Agner's site I found that the low-bits-not-random issue is a
> property of lagged Fibonnacci generators.

Excellent links!

"Georg Wrede" <georg.wrede@nospam.org> wrote...
> At brief googling I didn't find any white papers or such about it. Any pointers?

Here: http://www.helsbreth.org/random/unbiased.html


> BTW, that 10MHz stuff souded interesting. May I ask what you do for a daytime job?

Sure ~ I work at PARC (would like to get D adopted here, but ...)

However, the MCU was for this project:

http://www.gizmag.com/go/3409/ http://www.techimo.com/articles/i231.html http://www.gopro.at/flash_jack_neu.htm

The latter (slow) link has some fun, very 70's oriented, video shot by an Austrian reseller. It briefly shows some of the audio-driven animations (spectrum analysis, strange-attractors, genetic-algorithms, etc) in addition to the textual stuff.

The device itself has 4K RAM + 56K ROM. Used this particular MCU since it has 32-bit registers ~ came in handy for real-time audio/mic feature-extraction, and fast bitblt ops.

It's hooked up to to outside world via a BT-radio and a cell-phone (such as a Treo). Much of the ROM is filled with glyphs for the three fonts. The rest is populated with a kernel, bios, graphics engine, networking, audio analysis, a pseudo SVG compiler & animation engine, window-manager, widgets, pub/sub layer, etc; plus the various applications. A fun project.

Manfred Nowak wrote:
> Bruno Medeiros wrote:
> 
> [...]
> 
>>No, there are no numbers who "occur" 4 times, since that would
>>imply that *all* target numbers except the last one (0-98) would
>>"occur" 3 times at least, meaning that the original random
>>numbers would have to be at least 3*99 + 1 (near 300 basically,
>>not just 255).
> 
> 
> I do not agree with this try of a proof.
> 
> What I meant with my question is, that there might be three consecutive "buckets", that are drawn with the absolute values 232 if and only if there would not be any rounding erros resulting from the divison.
> 
> If rounding errors occur, then one draw normally falling into the middle bucket might be actually drawn from the left bucket, resulting in the absolute values 322, which is no problem, but if the normal draw would be out of the right bucket but because of the rounding error is actually drawn from the middle bucket the absolute values are 241.
> 

"but if the normal  draw would be out of the right bucket but because of the rounding  error is actually drawn from the middle bucket the absolute values are 241."
-> And I was telling why that doesn't happen. It's not a formal or detailed proof, I am aware, but I was hoping you would understand (or just believe..) that it was so, without having to explain in detail. :p

> Do you agree, that in all cases the total sum of draws does not change?
> 
> -manfred
Of course.

-- 
Bruno Medeiros - CS/E student
"Certain aspects of D are a pathway to many abilities some consider to be... unnatural."