Re: Pseudo Random Number Generation across PicoLisp implementations
Hi Chri, On 22. Apr, 2015, at 22:50, Christophe Gragnic wrote: . . > > Now the question. I found discrepancies between PicoLisp: > : (rand 1 1000) > -> 1 > : (rand 1 1000) > -> 934 > : (bye) > > And Ersatz > : (rand 1 1000) > -> 1 > : (rand 1 1000) > -> 967 > : (bye) > > I tried to inspect the source for getting some explanation with no luck. > PicoLisp > https://code.google.com/p/picolisp/source/browse/src/big.c#1213 > Ersatz: > https://code.google.com/p/picolisp/source/browse/ersatz/fun.src#3325 > Is there a reason for those different behaviours ? > > Last thing (mostly for Jon), I read that the PicoLisp generator is > a 64-bit linear congruential random generator (both pil64 and pil32) > with the multiplier 6364136223846793005. > I'd like to implement this generator for EmuLisp. Any advice ? > Any objection ? > > > chri Feel free to give it a try. As EmuLisp uses JavaScript numbers, 6364136223846793005 is too many digits, but you may find a way around it. /Jon-- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Pseudo Random Number Generation across PicoLisp implementations
Hi Christophe, our mails overlapped :) > PicoLisp was not the Haynes one, but the one referred as «Newlib» here: > http://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use Right. I took it originally from the book by Donald Knuth. > Maybe I was too tired. The difference is 33, and we see in the Ersatz src: > n = (int)(Seed >>> 33) % n; Right. > What I don't understand is why Ersatz shifts by 33, and PicoLisp by BITS, > (which should IMHO be 32). True. In fact, as I wrote, I don't remember that either. Perhaps a sign issue? Would it make sense to change it? Should be well tested though. This connects to my next remarks/questions: > * The Wikipedia page mentions taking «bits 63...32». I guess that > they start at bit 0, thus should the shift be 32 ? Knuth writes that the highest bits are more random than the lower bits in a linear congruential generator. > * Is 33 used because of the sign bit ? Yes, perhaps. > * In the PicoLisp src, why use LL and not ULL to define > 6364136223846793005? : (hex 6364136223846793005) -> "5851F42D4C957F2D" As you see, this number doesn't have its sign bit set in 64-bit two-complement representation (it would be 8 or higher in its most siginificant digit). So "unsigned" makes no difference. ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Pseudo Random Number Generation across PicoLisp implementations
Hi Christophe, > I use PicoLisp to implement a pedagogical language, directly > embedded in PicoLisp. In an exercise about dices, I noticed a > kind of similarity among the results of my students. > ... Nice! This sounds really interesting. > Now the question. I found discrepancies between PicoLisp: > ... > -> 934 > And Ersatz > ... > -> 967 Right. In fact, three of the four implementations (pil64, pil32, mini and ersatz) will give different results. Only mini and pil32 behave identically. > Is there a reason for those different behaviours ? > > Last thing (mostly for Jon), I read that the PicoLisp generator is > a 64-bit linear congruential random generator (both pil64 and pil32) > with the multiplier 6364136223846793005. That's correct. All four basically do Seed = Seed * 6364136223846793005 + 1 The differences arise from how the Seed is reduced to a 32-bit number after that. pil64 uses the middle 64 bits of the 128-bit result of the multiplication, while pil32 and mini use the highest 32 bits of the 64-bit result. Ersatz does similar to pil32 (i.e. a 64-bit result), but shifts by 33 (I don't know if there was a special reason). ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Pseudo Random Number Generation across PicoLisp implementations
Hi, After some more time to investigate, I found out that the LCG used in PicoLisp was not the Haynes one, but the one referred as «Newlib» here: http://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use More auto-answers and other questions below. On Wed, Apr 22, 2015 at 10:50 PM, Christophe Gragnic wrote: > Now the question. I found discrepancies between PicoLisp: > : (rand 1 1000) > -> 1 > : (rand 1 1000) > -> 934 > : (bye) > > And Ersatz > : (rand 1 1000) > -> 1 > : (rand 1 1000) > -> 967 > : (bye) > > I tried to inspect the source for getting some explanation with no luck. > PicoLisp > https://code.google.com/p/picolisp/source/browse/src/big.c#1213 > Ersatz: > https://code.google.com/p/picolisp/source/browse/ersatz/fun.src#3325 > Is there a reason for those different behaviours ? Maybe I was too tired. The difference is 33, and we see in the Ersatz src: n = (int)(Seed >>> 33) % n; But it is a coincidence since a bit shift should not have this effect (confirmed when trying with the args 0 and 1000): PicoLisp: : (rand 0 1000) -> 0 : (rand 0 1000) -> 648 : (rand 0 1000) -> 760 Ersatz: : (rand 0 1000) -> 0 : (rand 0 1000) -> 824 : (rand 0 1000) -> 880 Then I had to find the shift in the C code, which is hidden in the `hi` macro (for high bits): https://code.google.com/p/picolisp/source/browse/src/pico.h#161 #define hi(w) num((w)>>BITS) Where: #define WORD ((int)sizeof(long)) #define BITS (8*WORD) What I don't understand is why Ersatz shifts by 33, and PicoLisp by BITS, (which should IMHO be 32). This connects to my next remarks/questions: * The Wikipedia page mentions taking «bits 63...32». I guess that they start at bit 0, thus should the shift be 32 ? * Is 33 used because of the sign bit ? * In the PicoLisp src, why use LL and not ULL to define 6364136223846793005? chri -- http://profgra.org/lycee/ (site pro) http://delicious.com/profgraorg (liens, favoris) https://twitter.com/profgraorg http://microalg.info -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
