Thuật toán giả ngẫu nhiên đơn giản

Question

Tôi cần một trình tạo giả ngẫu nhiên lấy số là đầu vào và trả về một số phù thủy khác có thể lặp lại và có vẻ là ngẫu nhiên.

• Mỗi số đầu vào phải phù hợp với chính xác một số đầu ra và ngược lại
• số đầu vào cùng luôn luôn dẫn đến số lượng cùng
• số đầu vào liên tục mà là gần nhau (ví dụ. 1 và 2) nên sản xuất các số đầu ra hoàn toàn khác nhau (ví dụ: 1 => 9783526, 2 => 283)

Nó không được hoàn hảo, nó chỉ là tạo dữ liệu thử nghiệm ngẫu nhiên nhưng có thể tái sản xuất.

Tôi sử dụng C#.

---

Tôi đã viết đoạn mã ngộ nghĩnh này một thời gian trước đây đã tạo ra điều gì đó ngẫu nhiên.

public static long Scramble(long number, long max) 
    { 
    // some random values 
    long[] scramblers = { 3, 5, 7, 31, 343, 2348, 89897 }; 
    number += (max/7) + 6; 
    number %= max; 
    // shuffle according to divisibility 
    foreach (long scrambler in scramblers) 
    { 
     if (scrambler >= max/3) break; 
     number = ((number * scrambler) % max) 
     + ((number * scrambler)/max); 
    } 

    return number % max; 
    } 

Tôi muốn có thứ gì đó tốt hơn, đáng tin cậy hơn, làm việc với mọi kích thước (không có đối số tối đa).

Điều này có thể được giải quyết bằng thuật toán CRC không? Hoặc một số công cụ xáo trộn.

Answer 1

Bạn (có thể) có thể làm điều này một cách dễ dàng trong C# bằng cách sử dụng lớp ngẫu nhiên:

public int GetPseudoRandomNumber(int input) 
{ 
    Random random = new Random(input); 
    return random.Next(); 
} 

Vì bạn đang gieo hạt một cách rõ ràng ngẫu nhiên với đầu vào, bạn sẽ nhận được cùng một kết quả tất cả các thời gian nhất định các giá trị đầu vào tương tự .

Answer 2

tôi loại bỏ mã microsoft từ câu trả lời này, các tập tin mã GNU dài rất nhiều nhưng về cơ bản nó chứa này từ http://cs.uccs.edu/~cs591/bufferOverflow/glibc-2.2.4/stdlib/random_r.c:

int32_t val = state[0]; 
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff; 
state[0] = val; 
*result = val; 

cho mục đích của mình, hạt giống là nhà nước [0] để nó sẽ trông giống như

int getRand(int val) 
{ 
    return ((val * 1103515245) + 12345) & 0x7fffffff; 
} 

Answer 3

Hai quy tắc đầu tiên đề xuất hoán vị đầu vào cố định hoặc hạt giống đầu vào, nhưng quy tắc thứ ba yêu cầu phải chuyển đổi thêm.

Có hạn chế nào khác về kết quả đầu ra không, để hướng dẫn biến đổi đó? - ví dụ. có một bộ đầu vào của các giá trị đầu ra để lựa chọn không?

Nếu hướng dẫn duy nhất là "không max", tôi muốn sử dụng sau đây ...

1. Áp dụng một thuật toán băm để toàn bộ đầu vào để có được những mục đầu ra đầu tiên. CRC có thể hoạt động, nhưng đối với nhiều kết quả "ngẫu nhiên" hơn, hãy sử dụng thuật toán băm mã hóa như MD5.

2. Sử dụng thuật toán hoán vị tiếp theo (nhiều liên kết trên Google) trên đầu vào.

3. Lặp lại hàm băm sau đó cho đến khi tất cả các kết quả đầu ra được yêu cầu được tìm thấy.

Hoán vị tiếp theo có thể quá mức cần thiết, bạn có thể tăng đầu vào đầu tiên (và có thể, trên tràn, tăng thứ hai vv) trước khi làm lại băm.

Đối với băm kiểu crypto, bạn sẽ cần một khóa - chỉ lấy được thứ gì đó từ đầu vào trước khi bạn bắt đầu.

Answer 4

Máy phát điện tausworthe rất dễ triển khai và khá nhanh. Việc thực hiện giả sau đây có chu kỳ đầy đủ (2 ** 31-1, bởi vì không có một điểm cố định):

def tausworthe(seed) 
    seed ^= seed >> 13 
    seed ^= seed << 18 
    return seed & 0x7fffffff 

Tôi không biết C#, nhưng tôi giả sử nó có XOR (^) và chút shift (<<, >>) các toán tử như trong C.

Đặt giá trị hạt ban đầu và gọi với seed = tausworthe(seed).