search

elki-project / elki

ELKI Data Mining Toolkit
https://elki-project.github.io/
GNU Affero General Public License v3.0
794 stars 323 forks source link

signed long overflow in Xoroshiro128NonThreadsafeRanom #82

Closed lixun910 closed 3 years ago

lixun910 commented 3 years ago

I noticed an issue of signed long overflow in elki-core-util/src/main/java/elki/utilities/random/Xoroshiro128NonThreadsafeRandom.java

 @Override
  public void setSeed(long seed) {
    long xor64 = seed != 0 ? seed : 4101842887655102017L;
    // XorShift64* generator to seed:
    xor64 ^= xor64 >>> 12; // a
    xor64 ^= xor64 << 25; // b
    xor64 ^= xor64 >>> 27; // c
    s0 = xor64 * 2685821657736338717L;
    xor64 ^= xor64 >>> 12; // a
    xor64 ^= xor64 << 25; // b
    xor64 ^= xor64 >>> 27; // c
    s1 = xor64 * 2685821657736338717L;
  }

I've traced the computed results and the following code has overflow issue:

https://github.com/elki-project/elki/blob/e0e673f85581aa1cfbd68e033374b6fe67a48e51/elki-core-util/src/main/java/elki/utilities/random/Xoroshiro128NonThreadsafeRandom.java#L89

Is it on purpose? The comment shows the source is from http://xoroshiro.di.unimi.it/, where I can't find the above code. Could you provide a reference to the original code? Thanks!

lixun910 commented 3 years ago

Some details:
max long (64bit) is 9223372036854775807 for s1 = xor64 * 2685821657736338717L it means any value of xor64 > 40 will cause overflow issue.

E.g. input: seed = 123456789 then: s1 = 4142347051685507 * 2685821657736338717

kno10 commented 3 years ago

Random number generators rely heavily on overflows to randomize. 0x2545f4914f6cdd1d is a well known constant used for such purposes. Its a very large prime number.