高速な16ビット乱数ジェネレーター？

ソフトウェアでは、多くの場合、乱数を生成する必要があります。通常、疑似乱数ジェネレーターを使用します。

単純なジェネレーターはwyhashです。これは乗算とそれに続くXORです。

uint64_t wyhash64_x; 

uint64_t wyhash64() {
  wyhash64_x += 0x60bee2bee120fc15;
  __uint128_t tmp;
  tmp = (__uint128_t) wyhash64_x * 0xa3b195354a39b70d;
  uint64_t m1 = (tmp >> 64) ^ tmp;
  tmp = (__uint128_t)m1 * 0x1b03738712fad5c9;
  uint64_t m2 = (tmp >> 64) ^ tmp;
  return m2;
}

64ビットの数値を生成します。私は最近、同等であるがより小さな規模を構築できるかどうか尋ねられました。
16ビット整数のみが必要で、wyhash64関数のモデルに従いたい場合はどうなりますか？これは、限られたプロセッサで作業していて、必要性がそれほど高くない場合に役立つことがあります。これが私の提案です：

uint16_t wyhash16_x; 

uint32_t hash16(uint32_t input, uint32_t key) {
  uint32_t hash = input * key;
  return ((hash >> 16) ^ hash) & 0xFFFF;
}


uint16_t wyhash16() {
  wyhash16_x += 0xfc15;
  return hash16(wyhash16_x, 0x2ab);
}

このコードを使用するには、最初にwyhash16_xを選択した値に初期化する必要があります。増分（0xfc15）を他の奇数の整数に置き換えることもできます。このジェネレーターの周期は65536です。これは、65536の値の後、完全な円に戻ることを意味します。

本質的なアイデアはhash16関数にあります。特定のキー値に対して、16ビット値から16ビット値へのマップがあります。一般に、マップは反転できません。キー値を0xfc15に選択します。この選択により、アバランシェ効果が「最大化」されます。つまり、指定された値を取得し、hash16でハッシュしてから、1ビットを変更し、再度ハッシュすると、2つの出力の差は約8ビット（16ビットのうち）反転するはずです。つまり、入力値を少し変更すると、出力が大幅に変わるはずです。

hash16の機能が可逆ではない...それは私が雪崩効果が非常に弱いようにする必要があります可逆にします。0xfc15の場合、そのドメイン（出力値のセット）のサイズは44,114のみですが、65536個の異なる16ビット値があります。それは悪いですか？良い。0から65536までの65536のランダムな値を生成する場合、いくつの異なる値を期待しますか？答えは約41,427です。したがって、どちらかといえば、私のhash16関数のドメインが大きすぎる可能性があります。

数千の16ビット値を生成するだけでよい場合は、この単純なジェネレーターで十分な場合があります。高速の32ビット乗算器がある場合も高速になります。明らかに、あなたが深刻な数の計算をすることを計画しているなら、それはすぐにその限界を示します。それらのどれもそのような小さな発電機のために設計されていないので、私はそれを標準的な統計的検定に押し込もうとさえしませんでした。
面白いと思ったのは、なだれ効果を最適化することで、まともな画像サイズのジェネレーターも手に入れたということです。

この問題の分析に使用したソースコードは入手可能です。
付録。さらに、[0、s）の範囲の整数値を効率的に生成できます。

uint16_t rand_range16(const uint16_t s) {
    uint16_t x = wyhash16();
    uint32_t m = (uint32_t)x * (uint32_t)s;
    uint16_t l = (uint16_t)m;
    if (l < s) {
        uint16_t t = -s % s;
        while (l < t) {
            x = wyhash16();
            m = (uint32_t)x * (uint32_t)s;
            l = (uint16_t)m;
        }
    }
    return m >> 16;
}

英語原稿: https://lemire.me/blog/2019/07/03/a-fast-16-bit-random-number-generator/