dimanche 2 mai 2021

Combined Linear Congruential Generator C++

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