Mid-Square Hashing ใน C++

ข้อความโจทย์

วิธี Mid-Square เป็นวิธีหนึ่งในการสร้างเลขสุ่มแบบปลอม (Pseudorandom Numbers) วิธีนี้ đượcคิดค้นโดย John von Neumann และอธิบายในงานประชุมในปี 1949

• ในเทคนิคนี้ จะนำค่า Seed เริ่มต้นมา ยกกำลังสอง
• จากนั้นนำหลักกลาง (Middle Digits) บางส่วนมา และหลักที่นำออกมาเหล่านี้จะสร้างตัวเลขที่ถูกนำมาเป็น Seed ใหม่
  • สมมติ Seed = 3456 กำลังสองคือ 11943936
  • นำหลักกลาง 4 หลักเป็น Seed ใหม่ คือ 9439 กำลังสองคือ 89094721
  • นำหลักกลาง 4 หลักเป็น Seed ใหม่ คือ 0947
  • ทำซ้ำกระบวนการนี้

อัลกอริทึม

1. เลือกค่า Seed เริ่มต้น
2. ยกกำลังสองของค่า Seed
3. อัปเดต Seed โดยนำ n หลักจากผลลัพธ์ก่อนหน้า

ตัวอย่างโค้ด

#include <iostream>
#include <ctime>
using namespace std;

long long getTime() {
    time_t t = time(NULL);
    struct tm *tm = localtime(&t);
    long long x = (tm->tm_hour) * 50000000 + (tm->tm_min) * 100000 + (tm->tm_sec) * 5000 + (tm->tm_mday) * 50 + (tm->tm_year);
    return x;
}

long getHash() {
    long long key = getTime();
    key = key * key;
    key = key / 10000;
    key = key % 100000000;
    return key;
}

int main() {
    cout << "Random number: " << getHash() << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Random number: 10088419