-1

I needed a pseudo random number generation scheme (independent of standard libraries) for one of my projects and I tried a simple LCG based RNG. It seems to work fine except that it produces different values in C++ and Python. I am giving the relevant code for both below. I am not able to find the error. Any help will be greatly appreciated!

(c++)

// file: lgc.cc
// compile and run with: g++ lgc.cc -o lgc && ./lgc

#include <cstdio>
#include <cstdint>
#include <vector>

using namespace std;

uint64_t LGC(uint64_t x) {
  uint64_t A = 1103515245;
  uint64_t C = 12345;
  uint64_t M = (1 << 31);
  return (A * x + C) % M;
}

int main(int argc, char* argv[]) {

  for (auto x : {485288831, 485288832, 10, 16, 255, 756}) {
    uint64_t y = LGC(x);
    printf("%u %u\n", (uint32_t)x, (uint32_t) y);
  }

  return 0;
}

(python)

# file: lgc.py
# run with: python3 lgc.py

def LGC(x):
    A = 1103515245;
    C = 12345;
    M = int(2 ** 31);
    return (A * x + C) % M;

for x in [485288831, 485288832, 10, 16, 255, 756]:
    y = LGC(x)
    print(x, y)

(Results: c++)

485288831 3822790476
485288832 631338425
10 2445230203
16 476387081
255 2223525580
756 1033882141

(Results: python)

485288831 1675306828
485288832 631338425
10 297746555
16 476387081
255 76041932
756 1033882141
Axeon Thra
  • 334
  • 3
  • 14
  • *I am not able to find the error.* -- [What is a debugger, and how can it help diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – PaulMcKenzie Feb 07 '22 at 13:36
  • I tested for that. These are 64 bit integers. Also I tested with small numbers. Check the result of 10 for example. Ax+c do not overflow even 60 bits for any of the cases. @drescherjm – Axeon Thra Feb 07 '22 at 13:44
  • 1
    There appears to be a conflict between unsigned and signed values. (Don't know much about Python, or even if it has unsigned ints.) Also, (for signed values), the `%` operator is a bit different between C++ and Python (but I think that only matters when negative numbers are involved). – Adrian Mole Feb 07 '22 at 13:46
  • 1
    It looks like the python answer matches windows calculator. – drescherjm Feb 07 '22 at 13:46
  • 2
    @AdrianMole is correct The fix is here: `uint64_t M = (1U << 31);` [https://ideone.com/Z2XYGS](https://ideone.com/Z2XYGS) – drescherjm Feb 07 '22 at 13:49
  • 2
    @AxeonThra -- If that's the issue, shifting, then I go back to the first comment. A simple printing out of the various components `A`, `C`, and `M` would have revealed the problem. Now, the fix to the problem, yes, we could have stated that, but at the very least, you should have detected that the components were wrong in some way. – PaulMcKenzie Feb 07 '22 at 13:50
  • 1
    @PaulMcKenzie Or even enabling compiler warnings! Clang-cl says: *warning : signed shift result (0x80000000) sets the sign bit of the shift expression's type ('int') and becomes negative [-Wshift-sign-overflow]* – Adrian Mole Feb 07 '22 at 13:54
  • @drescherjm That fixed the problem. Thanks. – Axeon Thra Feb 07 '22 at 13:59
  • @PaulMcKenzie The printing was a bit of problem since I had the difficulty figuring out if the error was due to wrong printing flag or wrong value. Hence I used type cast in the printf function. – Axeon Thra Feb 07 '22 at 14:03
  • @AxeonThra You should have used `cout` and not `printf`. Then the wrong printing flags becomes a moot point. – PaulMcKenzie Feb 07 '22 at 14:08
  • @PaulMcKenzie, I understand what you are trying to convey. Had bad experiences with cout for logging in the past since printing floating values with precision is bit of an effort. – Axeon Thra Feb 07 '22 at 14:14

1 Answers1

1

The problem is with the shift in: uint64_t M = (1 << 31); the (1<<31) is a negative number -2147483648 for 32 bit integers because this is signed integer math. To fix you can use uint64_t M = (1U << 31); to make the shift use unsigned 32 bit integers. You could also use uint64_t M = (1UL << 31); to have the calculation use 64 bit unsigned integers

The following link shows printing the output of: (1 << 31), (1U << 31) and (1UL << 31) on a system with 32 bit int: https://ideone.com/vU0eyX

drescherjm
  • 10,365
  • 5
  • 44
  • 64