3 ms·

> I think that rand() is much faster than any good pseudorandom algorithm too. This is simply not true. It's often _slower_, since it uses the integer div inst

> I think that rand() is much faster than any good pseudorandom algorithm too. This is simply not true. It's often _slower_, since it uses the integer div instruction. For an example of a good fast PRNG, see Tyche: https://eden.dei.uc.pt/~sneves/pubs/2011-snfa2.pdf https://eden.dei.uc.pt/~sneves/pubs/2011-snfa2.pdf It's faster and produces infinitely better distributions.

clarry 12y ago
> This is simply not true. It's often _slower_, since it uses the integer div instruction. Actually I think most implementations reduce modulo a power of two (e.g. 2^31 or 2^32): 0000000000048ee0 <rand_r>: 48ee0: 8b 07 mov (%rdi),%eax 48ee2: 69 c0 6d 4e c6 41 imul $0x41c64e6d,%eax,%eax 48ee8: 05 39 30 00 00 add $0x3039,%eax 48eed: 89 07 mov %eax,(%rdi) 48eef: 25 ff ff ff 7f and $0x7fffffff,%eax 48ef4: c3 retq https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use https://en.wikipedia.org/wiki/Linear_congruential_generator#...
- nightcracker 12y ago
  Woops, I totally forgot about that, I think I was confused with range reduction on the final result. Nevertheless, Tyche-i is also blazing fast and small: 0000000000000000 <_Z6tycheiv>: 0: 8b 0d 0c 00 00 00 mov 0xc(%rip),%ecx 6: c4 e3 7b f0 05 07 00 rorx $0x7,0x7(%rip),%eax d: 00 00 07 10: c4 e3 7b f0 15 ff ff rorx $0x8,-0x1(%rip),%edx 17: ff ff 08 1a: 44 8b 05 04 00 00 00 mov 0x4(%rip),%r8d 21: 31 ca xor %ecx,%edx 23: 44 31 c0 xor %r8d,%eax 26: 41 29 d0 sub %edx,%r8d 29: c4 e3 7b f0 d2 10 rorx $0x10,%edx,%edx 2f: 29 c1 sub %eax,%ecx 31: c4 e3 7b f0 c0 0c rorx $0xc,%eax,%eax 37: 44 31 c0 xor %r8d,%eax 3a: 31 ca xor %ecx,%edx 3c: 29 c1 sub %eax,%ecx 3e: 89 05 08 00 00 00 mov %eax,0x8(%rip) 44: 41 29 d0 sub %edx,%r8d 47: 89 15 00 00 00 00 mov %edx,0x0(%rip) 4d: 44 89 05 04 00 00 00 mov %r8d,0x4(%rip) 54: 89 0d 0c 00 00 00 mov %ecx,0xc(%rip) 5a: c3 retq

clarry 12y ago

> This is simply not true. It's often _slower_, since it uses the integer div instruction. Actually I think most implementations reduce modulo a power of two (e.g. 2^31 or 2^32): 0000000000048ee0 <rand_r>: 48ee0: 8b 07 mov (%rdi),%eax 48ee2: 69 c0 6d 4e c6 41 imul $0x41c64e6d,%eax,%eax 48ee8: 05 39 30 00 00 add $0x3039,%eax 48eed: 89 07 mov %eax,(%rdi) 48eef: 25 ff ff ff 7f and $0x7fffffff,%eax 48ef4: c3 retq https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use https://en.wikipedia.org/wiki/Linear_congruential_generator#...

nightcracker 12y ago
Woops, I totally forgot about that, I think I was confused with range reduction on the final result. Nevertheless, Tyche-i is also blazing fast and small: 0000000000000000 <_Z6tycheiv>: 0: 8b 0d 0c 00 00 00 mov 0xc(%rip),%ecx 6: c4 e3 7b f0 05 07 00 rorx $0x7,0x7(%rip),%eax d: 00 00 07 10: c4 e3 7b f0 15 ff ff rorx $0x8,-0x1(%rip),%edx 17: ff ff 08 1a: 44 8b 05 04 00 00 00 mov 0x4(%rip),%r8d 21: 31 ca xor %ecx,%edx 23: 44 31 c0 xor %r8d,%eax 26: 41 29 d0 sub %edx,%r8d 29: c4 e3 7b f0 d2 10 rorx $0x10,%edx,%edx 2f: 29 c1 sub %eax,%ecx 31: c4 e3 7b f0 c0 0c rorx $0xc,%eax,%eax 37: 44 31 c0 xor %r8d,%eax 3a: 31 ca xor %ecx,%edx 3c: 29 c1 sub %eax,%ecx 3e: 89 05 08 00 00 00 mov %eax,0x8(%rip) 44: 41 29 d0 sub %edx,%r8d 47: 89 15 00 00 00 00 mov %edx,0x0(%rip) 4d: 44 89 05 04 00 00 00 mov %r8d,0x4(%rip) 54: 89 0d 0c 00 00 00 mov %ecx,0xc(%rip) 5a: c3 retq