Tôi cần tham số hóa một số PRNG, giả sử tôi cần số 32 bit. Nhưng khi các con số trông không ngẫu nhiên lắm, nó sẽ cho kết quả xấu. Những người tạo ra SplitMix cũng gặp vấn đề tương tự (lưu ý rằng theo những gì tôi hiểu thì họ đã không giải quyết đúng):
https://www.pcg-random.org/posts/bugs-in-splitmix.html
Vì vậy, tôi cần một hàm sẽ biến đổi giả sử số 1 thành thứ gì đó như 10011110001101110111100110111001. Nhưng số 10100111101101010110001111100101 với độ phức tạp thuật toán tốt (ý tôi là độ phức tạp Kolmogorov) có thể vẫn tốt tương tự (tất nhiên không nhất thiết phải giống nhau).
Vì vậy, băm bằng cách nhân: x = x*2654435769 mod 2^32 không phải là tùy chọn, bởi vì chúng ta có thể tìm nghịch đảo phép nhân mô-đun, điều này sẽ cho chúng ta 1 hoặc một giá trị nào đó xấu. Tôi đã cố gắng sử dụng bộ trộn bit từ PCG:
uint32_t RXSMXS(uint32_t rxs)
{
uint8_t r;
r = rxs >> 28;
rxs = rxs^(rxs>>(4+r));
rxs = rxs*277803737;
trả về rxs^(rxs >> 22);
}
Nhưng có vẻ như nó cũng có thể đảo ngược 1 đến 1 (vấn đề là sự phân biệt, không phải bản thân khả năng đảo ngược). Cùng tiếng thì thầm32:
uint32_t rì rầm32(uint32_t z)
{
z ^= (z >> 16);
z *= 0x85ebca6bul;
z ^= (z >> 13);
z *= 0xc2b2ae35ul;
trả về z^(z>>16);
}
Nó có thể đảo ngược và song phản lực, phải không (vì vậy chúng ta có thể tìm thấy đầu vào mang lại cho chúng ta đầu ra tệ như chúng ta muốn)?
Vì vậy, có một phương pháp nổi tiếng, hiệu quả để làm điều đó? Ý tôi là - lấy một số có độ phức tạp Kolmogorov thấp (hoặc cao) và xuất ra một số có độ phức tạp Kolmogorov cao. Tất nhiên, một chức năng/ánh xạ như vậy sẽ không phải là từ chối, bởi vì chúng tôi chỉ loại bỏ một số giá trị. Vì vậy, các khóa/hệ số khác nhau đôi khi sẽ tạo ra kết quả giống nhau.
Ý tưởng của tôi là xác định một nửa số là hằng số, ví dụ: đặt các bit quan trọng nhất là: 10011110001101110000000000000000 và sau đó chỉ cần chọn ngẫu nhiên các bit ít quan trọng nhất (sau đó có thể là mọi số 16 bit). Và sau đó đặt nó vào bộ trộn bit như thì thầm32 hoặc cái gì khác. Nhưng chúng tôi vẫn không đảm bảo rằng tiếng rì rầm32 sẽ không biến đổi, ví dụ 10011110001101110000000000000011 thành 1, 2 hoặc 3. Vì vậy, có thể tôi sẽ không sử dụng bộ trộn (nhưng những con số như vậy có thể có entropy thuật toán sai ở các bit ít quan trọng nhất).
Bạn có bất kỳ ý tưởng tốt hơn nhưng hiệu quả?