LCG and ICG

prng.c

/**
LCG output...
lcg(1) : 40B2947B
lcg(2) : 73718F14
lcg(3) : 6203F04B
lcg(4) : 1BB91A70
lcg(5) : 0CFC23E0

ICG output...
icg(5) : 0CFC23E0
icg(4) : 1BB91A70
icg(3) : 6203F04B
icg(2) : 73718F14
icg(1) : 40B2947B
*/

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <inttypes.h>

// LCG parameters based on RtlUniform in Windows
static uint64_t state      = 1;
static uint64_t multiplier = ((int)(0x80000000 - 19)); // 2**31 - 19
static uint64_t increment  = ((int)(0x80000000 - 61)); // 2**31 - 61
static uint64_t modulus    = ((int)(0x80000000 - 1));  // 2**31 - 1

void xsrand(uint64_t seed) {
    state = seed;
}

uint64_t 
lcg() {
    state = (multiplier * state + increment) % modulus;
    return state;
}

uint64_t 
icg() {
    uint64_t tmp = state;
    state = (multiplier * state + increment) % modulus;
    return tmp;
}

// Modular Inverse Function using Extended Euclidean Algorithm
int64_t 
invmod(int64_t a, int64_t m) {
    int64_t m0 = m, t, q;
    int64_t x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

int main() {
    xsrand((uint64_t)time(NULL));

    printf("\nLCG output...\n");
    
    for (int i = 0; i < 5; i++) {
        printf("lcg(%d) : %08" PRIX64 "\n", (i + 1), lcg());
    }
    
    int64_t inv_multiplier = invmod((int64_t)multiplier, (int64_t)modulus);
    
    if (inv_multiplier == 0) {
        printf("Multiplicative inverse does not exist.\n");
        return EXIT_FAILURE;
    }
    
    multiplier = (uint64_t)inv_multiplier;
    
    int64_t new_increment = -((int64_t)increment) * (int64_t)multiplier;
    
    new_increment %= (int64_t)modulus;
    
    if (new_increment < 0)
        new_increment += modulus;
    
    increment = (uint64_t)new_increment;

    printf("\nICG output...\n");
    
    for (int i = 4; i >= 0; i--) {
        printf("icg(%d) : %08" PRIX64 "\n", (i + 1), icg());
    }

    return 0;
}