I'm trying to implement a combined linear congruential generator (CLCG) on myself for a school-project. Whereas i did implement successfully a single LCG, i do not understand what is the problem in combining them.
Single LCG:
#include<iostream>
#include<climits>
#include<cmath>
#include<ctime>
#include<fstream>
// See: https://en.wikipedia.org/wiki/Linear_congruential_generator#LCG_derivatives
//Numerical Recipes Parameters
#define A 1664525
#define C 1013904223
#define POW232 4294967296
#define M POW232
unsigned long CLG();
int main(){
srand(time(NULL));
//Variables
unsigned long ull_tmp = 0;
unsigned long long i = 1;
ull_tmp = CLG(); // First Execution
while ( CLG() != ull_tmp ){
++i;
}
return 0;
}
inline unsigned long CLG(){
static unsigned long seed = rand();
seed = (A*(seed) + C) % M;
return seed;
}
This implementation correctly has a period of m - 1 as expected. For the combined algorithm i've tried to generalize this solution with the following code.
Combine LCGs
#include<iostream>
#include<climits>
#include<cmath>
#include<ctime>
#include<fstream>
#include<cstdint>
#include<stdint.h>
#define LCGS_NUMBER 2
// See: https://en.wikipedia.org/wiki/Linear_congruential_generator#LCG_derivatives
//Numerical Recipes Parameters
#define A 1664525
#define C 1013904223
#define POW232 4294967296
#define M POW232 //Chain verified to M - 1
//Borland C/C++
#define A1 22695477
#define C1 1
#define M1 POW232 //Chain verified to M - 1
uint64_t CCLG();
unsigned long CLG();
unsigned long CLG1();
int main(){
//Variables
uint64_t ull_tmp = 0, tmp = 0;
unsigned long long j = 0;
// First Execution
ull_tmp = CCLG();
//Execution
std::cout << std::endl << std::endl;
std::cout << "Random Number Generation..." << std::endl;
std::cout << std::endl << std::endl;
while ( CCLG() != ull_tmp ){
++j;
}
return 0;
}
inline uint64_t CCLG(){
static intmax_t seed = 0;
seed = ((intmax_t)CLG( ) - (intmax_t)CLG1( ) )% M ;
if (seed > 0){
seed = seed % M;
}else if (seed == 0){
seed = (M-1)/M;
}else{
seed = (seed % M) + 1;
}
return seed;
}
inline unsigned long CLG(){
static unsigned long seed = rand();
seed = (A*(seed) + C) % M;
return seed;
}
inline unsigned long CLG1(){
static unsigned long seed1 = rand();
seed1 = (A1*(seed1) + C1) % M1;
return seed1;
}
In first tests the CCLG() function used to be of unsigned long type leading to a period of about 2^32 / 2, after few trials i noticed that i was loosing all the negative values within CCLG() and before returning; after switching the return value to uint_64 and the local static seed to intmax_t i managed to get a period as long as the single LCG with Numerical Recipes Parameters.
Does anyone has any suggestion on why it's not able to obtain a longer period than single LCG ? In this particular case i think the combined period should be around 2^18 because each LCG has an approximate period of 10^8/10^9. Actually i really don't know what could be wrong.
Thanks in advance for helping in understand this code.
Aucun commentaire:
Enregistrer un commentaire