1
\$\begingroup\$

Here's a simple LCG that I've made to learn a bit more about pseudo random number generation.

Is this implementation correct, and if so, how can I improve it further?

The following code is self contained and it should run without problems.

#include <chrono>
#include <iostream>
#include <map>

namespace Random {
    class LCG {
        static constexpr uint64_t const A = 0x5851F42D4C957F2D;
        static constexpr uint64_t const C = 0x14057B7EF767814F;
        static constexpr uint64_t const M = 0xFFFFFFFFFFFFFFFF;

        uint64_t this_seed;

        auto now() noexcept {
            using namespace std::chrono;
            auto const output = high_resolution_clock::now();
            return output.time_since_epoch().count();
        }

    public:
        LCG() noexcept
            : this_seed(now()) {
        }

        LCG(uint64_t const value) noexcept
            : this_seed(value) {
        }

        void seed() noexcept {
            this_seed = now();
        }

        void seed(uint64_t const value) noexcept {
            this_seed = value;
        }

        // [0, 2 ^ 64 - 1)
        auto next() noexcept {
            this_seed = (this_seed * A + C) & M;
            return this_seed;
        }

        void discard(uint64_t const amount) noexcept {
            for (uint64_t i = 0; i != amount; ++i) {
                next();
            }
        }

        // [0, 1)
        double get() noexcept {
            return static_cast<double>(next()) / M;
        }

        // x - 0 == (-1 | 0 | 1) ? 0 : x > 0 ? [0, x) : (x, 0]
        int64_t get(int64_t const x) noexcept {
            return static_cast<int64_t>(get() * x);
        }

        // b - a == (-1 | 0 | 1) ? 0 : b > a ? [a, b) : (b, a]
        int64_t get(int64_t const a, int64_t const b) noexcept {
            return a + static_cast<int64_t>(get() * (b - a));
        }
    };
}

int main() {

    Random::LCG lcg(0);
    std::map<int64_t, uint64_t> buckets;
    for (uint64_t i = 0; i != 1000000; ++i) {
        ++buckets[lcg.get(10)];
    }
    for (auto const [a, b] : buckets) {
        std::cout << a << '\t' << b << '\n';
    }

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Yes, it's self contained. It's also filled with magic numbers and oddly named variables making it hard to see what you're doing and why. An explanation would greatly improve this question. \$\endgroup\$ – Mast May 27 '18 at 10:12
  • \$\begingroup\$ Your code looks an awful lot like this pastebin. Did you write this yourself? \$\endgroup\$ – Mast May 27 '18 at 10:15
  • 1
    \$\begingroup\$ @Mast it's an LCG, and those names (A as multiplier, C as constant offset and M as modulus) are common with LCGs. I'd expect them the follow the Hull-Dobell requirements (see \$c \neq 0\$ in the article). \$\endgroup\$ – Zeta May 27 '18 at 10:17
  • \$\begingroup\$ @Mast, I did write it myself. As far as I know, I'm the only one that prefixes the private member variables with this_. Also, some of the comments from that paste bin are missing. \$\endgroup\$ – João Pires May 27 '18 at 10:38
  • 1
    \$\begingroup\$ With something like a LCG, which is a common library function, you can learn a lot by looking at source libraries. The C, C++ and Java libraries are certainly available and I presume others. \$\endgroup\$ – rossum May 27 '18 at 12:18
2
\$\begingroup\$

Your mask value M is gaining you nothing, since the types for this_seed and M are the same and you have every bit in M set to 1. Your comment for next is wrong; it can return 264-1 (i.e., all bits set). The correct range can be stated as either [0, 2 ^ 64 - 1] or [0, 2 ^ 64). This in turn can cause your get functions to return a value larger than expected (1.0, x, or b).

Where did you get the values for the A and B constants? I've not looked to see if they are appropriate.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ The constants A, C and M are from MMIX by Donald Knuth. As for the get methods, they've always yielded values between the range specified in the comments. As for the next method comment, I wasn't sure... what would be the correct range? [0, 2 ^ 64 - 1]? \$\endgroup\$ – João Pires May 26 '18 at 18:23
  • \$\begingroup\$ I took the M value from here https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use. On the table it says, 2 ^ 64, but because that number will overflow in C++, I've used 2 ^ 64 - 1, but you're right, I've just tested the code and neither & nor % works, they just yield the same value. \$\endgroup\$ – João Pires May 26 '18 at 18:33
  • \$\begingroup\$ @JoãoPires I've updated the answer with the proper range for next. Using numbers from MMIX is good. \$\endgroup\$ – 1201ProgramAlarm May 26 '18 at 20:38
  • \$\begingroup\$ What about the & and the M value, how can I correct it? \$\endgroup\$ – João Pires May 26 '18 at 22:06
2
\$\begingroup\$

this_seed = (this_seed * A + C) & M;

should just read

this_seed = this_seed * A + C;

The modulo is done free for you - unsigned arithmetic in a 64-bit word. You do not need M

For the double function [0.0,1.0) this gives a uniform distribution:

return static_cast<double>(next() >> 11) * (1.0 / (UINT64_C(1) << 53));

The less random low order bits are discarded. The multiplier compiles to 0x1p-53

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I've tried improving the double get() with your code, but it messes up the other two get methods. How do I fix them? There's plenty of tutorials on how to implemente a RNG, but they all skip the How do I get a number between a and b from that?. \$\endgroup\$ – João Pires May 27 '18 at 10:50
  • \$\begingroup\$ My bad, I wrote next() >> 1 instead of next() >> 11. It is working now. :) \$\endgroup\$ – João Pires May 27 '18 at 10:59
0
\$\begingroup\$

The now function doesn’t have anything to do with the class; it is just a helper. So make it static.

void seed(uint64_t const value)

The const is OK, but you are not doing that consistently. The constructor with the same kind of argument does not have const.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ In the new improved version, the now function was made static. Both the constructor and the seed method has the parameter value marked as const, in fact, all my parameters are marked as const. \$\endgroup\$ – João Pires May 27 '18 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.