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 christophegrag...@gmail.com 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
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 Chri, On 22. Apr, 2015, at 22:50, Christophe Gragnic christophegrag...@gmail.com 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
