Implementation of a linear congruential generator

Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
1
down vote
favorite
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 0 ;
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;
c++ random
 |Â
show 1 more comment
up vote
1
down vote
favorite
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 0 ;
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;
c++ random
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.
â Mast
May 27 at 10:12
Your code looks an awful lot like this pastebin. Did you write this yourself?
â Mast
May 27 at 10:15
1
@Mast it's an LCG, and those names (Aas multiplier,Cas constant offset andMas modulus) are common with LCGs. I'd expect them the follow the Hull-Dobell requirements (see $c neq 0$ in the article).
â Zeta
May 27 at 10:17
@Mast, I did write it myself. As far as I know, I'm the only one that prefixes the private member variables withthis_. Also, some of the comments from that paste bin are missing.
â João Pires
May 27 at 10:38
1
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.
â rossum
May 27 at 12:18
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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 0 ;
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;
c++ random
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 0 ;
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;
c++ random
edited May 27 at 12:41
Vogel612â¦
20.9k345124
20.9k345124
asked May 26 at 12:54
João Pires
1347
1347
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.
â Mast
May 27 at 10:12
Your code looks an awful lot like this pastebin. Did you write this yourself?
â Mast
May 27 at 10:15
1
@Mast it's an LCG, and those names (Aas multiplier,Cas constant offset andMas modulus) are common with LCGs. I'd expect them the follow the Hull-Dobell requirements (see $c neq 0$ in the article).
â Zeta
May 27 at 10:17
@Mast, I did write it myself. As far as I know, I'm the only one that prefixes the private member variables withthis_. Also, some of the comments from that paste bin are missing.
â João Pires
May 27 at 10:38
1
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.
â rossum
May 27 at 12:18
 |Â
show 1 more comment
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.
â Mast
May 27 at 10:12
Your code looks an awful lot like this pastebin. Did you write this yourself?
â Mast
May 27 at 10:15
1
@Mast it's an LCG, and those names (Aas multiplier,Cas constant offset andMas modulus) are common with LCGs. I'd expect them the follow the Hull-Dobell requirements (see $c neq 0$ in the article).
â Zeta
May 27 at 10:17
@Mast, I did write it myself. As far as I know, I'm the only one that prefixes the private member variables withthis_. Also, some of the comments from that paste bin are missing.
â João Pires
May 27 at 10:38
1
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.
â rossum
May 27 at 12:18
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.
â Mast
May 27 at 10:12
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.
â Mast
May 27 at 10:12
Your code looks an awful lot like this pastebin. Did you write this yourself?
â Mast
May 27 at 10:15
Your code looks an awful lot like this pastebin. Did you write this yourself?
â Mast
May 27 at 10:15
1
1
@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).â Zeta
May 27 at 10:17
@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).â Zeta
May 27 at 10:17
@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.â João Pires
May 27 at 10:38
@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.â João Pires
May 27 at 10:38
1
1
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.
â rossum
May 27 at 12:18
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.
â rossum
May 27 at 12:18
 |Â
show 1 more comment
3 Answers
3
active
oldest
votes
up vote
2
down vote
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.
The constantsA,CandMare fromMMIX by Donald Knuth. As for thegetmethods, they've always yielded values between the range specified in the comments. As for thenextmethod comment, I wasn't sure... what would be the correct range?[0, 2 ^ 64 - 1]?
â João Pires
May 26 at 18:23
I took theMvalue from herehttps://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 used2 ^ 64 - 1, but you're right, I've just tested the code and neither&nor%works, they just yield the same value.
â João Pires
May 26 at 18:33
@JoãoPires I've updated the answer with the proper range fornext. Using numbers from MMIX is good.
â 1201ProgramAlarm
May 26 at 20:38
What about the&and theMvalue, how can I correct it?
â João Pires
May 26 at 22:06
add a comment |Â
up vote
2
down vote
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
I've tried improving thedouble get()with your code, but it messes up the other twogetmethods. How do I fix them? There's plenty of tutorials on how to implemente a RNG, but they all skip theHow do I get a number between a and b from that?.
â João Pires
May 27 at 10:50
My bad, I wrotenext() >> 1instead ofnext() >> 11. It is working now. :)
â João Pires
May 27 at 10:59
add a comment |Â
up vote
0
down vote
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.
In the new improved version, thenowfunction was made static. Both the constructor and the seed method has the parametervaluemarked asconst, in fact, all my parameters are marked asconst.
â João Pires
May 27 at 19:22
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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.
The constantsA,CandMare fromMMIX by Donald Knuth. As for thegetmethods, they've always yielded values between the range specified in the comments. As for thenextmethod comment, I wasn't sure... what would be the correct range?[0, 2 ^ 64 - 1]?
â João Pires
May 26 at 18:23
I took theMvalue from herehttps://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 used2 ^ 64 - 1, but you're right, I've just tested the code and neither&nor%works, they just yield the same value.
â João Pires
May 26 at 18:33
@JoãoPires I've updated the answer with the proper range fornext. Using numbers from MMIX is good.
â 1201ProgramAlarm
May 26 at 20:38
What about the&and theMvalue, how can I correct it?
â João Pires
May 26 at 22:06
add a comment |Â
up vote
2
down vote
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.
The constantsA,CandMare fromMMIX by Donald Knuth. As for thegetmethods, they've always yielded values between the range specified in the comments. As for thenextmethod comment, I wasn't sure... what would be the correct range?[0, 2 ^ 64 - 1]?
â João Pires
May 26 at 18:23
I took theMvalue from herehttps://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 used2 ^ 64 - 1, but you're right, I've just tested the code and neither&nor%works, they just yield the same value.
â João Pires
May 26 at 18:33
@JoãoPires I've updated the answer with the proper range fornext. Using numbers from MMIX is good.
â 1201ProgramAlarm
May 26 at 20:38
What about the&and theMvalue, how can I correct it?
â João Pires
May 26 at 22:06
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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.
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.
edited May 26 at 20:37
answered May 26 at 17:46
1201ProgramAlarm
2,4752618
2,4752618
The constantsA,CandMare fromMMIX by Donald Knuth. As for thegetmethods, they've always yielded values between the range specified in the comments. As for thenextmethod comment, I wasn't sure... what would be the correct range?[0, 2 ^ 64 - 1]?
â João Pires
May 26 at 18:23
I took theMvalue from herehttps://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 used2 ^ 64 - 1, but you're right, I've just tested the code and neither&nor%works, they just yield the same value.
â João Pires
May 26 at 18:33
@JoãoPires I've updated the answer with the proper range fornext. Using numbers from MMIX is good.
â 1201ProgramAlarm
May 26 at 20:38
What about the&and theMvalue, how can I correct it?
â João Pires
May 26 at 22:06
add a comment |Â
The constantsA,CandMare fromMMIX by Donald Knuth. As for thegetmethods, they've always yielded values between the range specified in the comments. As for thenextmethod comment, I wasn't sure... what would be the correct range?[0, 2 ^ 64 - 1]?
â João Pires
May 26 at 18:23
I took theMvalue from herehttps://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 used2 ^ 64 - 1, but you're right, I've just tested the code and neither&nor%works, they just yield the same value.
â João Pires
May 26 at 18:33
@JoãoPires I've updated the answer with the proper range fornext. Using numbers from MMIX is good.
â 1201ProgramAlarm
May 26 at 20:38
What about the&and theMvalue, how can I correct it?
â João Pires
May 26 at 22:06
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]?â João Pires
May 26 at 18:23
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]?â João Pires
May 26 at 18:23
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.â João Pires
May 26 at 18:33
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.â João Pires
May 26 at 18:33
@JoãoPires I've updated the answer with the proper range for
next. Using numbers from MMIX is good.â 1201ProgramAlarm
May 26 at 20:38
@JoãoPires I've updated the answer with the proper range for
next. Using numbers from MMIX is good.â 1201ProgramAlarm
May 26 at 20:38
What about the
& and the M value, how can I correct it?â João Pires
May 26 at 22:06
What about the
& and the M value, how can I correct it?â João Pires
May 26 at 22:06
add a comment |Â
up vote
2
down vote
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
I've tried improving thedouble get()with your code, but it messes up the other twogetmethods. How do I fix them? There's plenty of tutorials on how to implemente a RNG, but they all skip theHow do I get a number between a and b from that?.
â João Pires
May 27 at 10:50
My bad, I wrotenext() >> 1instead ofnext() >> 11. It is working now. :)
â João Pires
May 27 at 10:59
add a comment |Â
up vote
2
down vote
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
I've tried improving thedouble get()with your code, but it messes up the other twogetmethods. How do I fix them? There's plenty of tutorials on how to implemente a RNG, but they all skip theHow do I get a number between a and b from that?.
â João Pires
May 27 at 10:50
My bad, I wrotenext() >> 1instead ofnext() >> 11. It is working now. :)
â João Pires
May 27 at 10:59
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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
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
edited May 31 at 18:52
answered May 27 at 6:51
Jeremy
363
363
I've tried improving thedouble get()with your code, but it messes up the other twogetmethods. How do I fix them? There's plenty of tutorials on how to implemente a RNG, but they all skip theHow do I get a number between a and b from that?.
â João Pires
May 27 at 10:50
My bad, I wrotenext() >> 1instead ofnext() >> 11. It is working now. :)
â João Pires
May 27 at 10:59
add a comment |Â
I've tried improving thedouble get()with your code, but it messes up the other twogetmethods. How do I fix them? There's plenty of tutorials on how to implemente a RNG, but they all skip theHow do I get a number between a and b from that?.
â João Pires
May 27 at 10:50
My bad, I wrotenext() >> 1instead ofnext() >> 11. It is working now. :)
â João Pires
May 27 at 10:59
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?.â João Pires
May 27 at 10:50
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?.â João Pires
May 27 at 10:50
My bad, I wrote
next() >> 1 instead of next() >> 11. It is working now. :)â João Pires
May 27 at 10:59
My bad, I wrote
next() >> 1 instead of next() >> 11. It is working now. :)â João Pires
May 27 at 10:59
add a comment |Â
up vote
0
down vote
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.
In the new improved version, thenowfunction was made static. Both the constructor and the seed method has the parametervaluemarked asconst, in fact, all my parameters are marked asconst.
â João Pires
May 27 at 19:22
add a comment |Â
up vote
0
down vote
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.
In the new improved version, thenowfunction was made static. Both the constructor and the seed method has the parametervaluemarked asconst, in fact, all my parameters are marked asconst.
â João Pires
May 27 at 19:22
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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.
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.
answered May 27 at 17:04
JDÃ Âugosz
5,047731
5,047731
In the new improved version, thenowfunction was made static. Both the constructor and the seed method has the parametervaluemarked asconst, in fact, all my parameters are marked asconst.
â João Pires
May 27 at 19:22
add a comment |Â
In the new improved version, thenowfunction was made static. Both the constructor and the seed method has the parametervaluemarked asconst, in fact, all my parameters are marked asconst.
â João Pires
May 27 at 19:22
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.â João Pires
May 27 at 19:22
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.â João Pires
May 27 at 19:22
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f195218%2fimplementation-of-a-linear-congruential-generator%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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.
â Mast
May 27 at 10:12
Your code looks an awful lot like this pastebin. Did you write this yourself?
â Mast
May 27 at 10:15
1
@Mast it's an LCG, and those names (
Aas multiplier,Cas constant offset andMas modulus) are common with LCGs. I'd expect them the follow the Hull-Dobell requirements (see $c neq 0$ in the article).â Zeta
May 27 at 10:17
@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.â João Pires
May 27 at 10:38
1
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.
â rossum
May 27 at 12:18