เรื่องที่อยากเขียน ... เรื่องที่พยายามเขียน ...
Group Blog
 
All blogs
 
Random Number


random number หรือ ตัวเลขสุ่ม
คือตัวเลขที่สร้างขึ้นมา โดยไม่มีรูปแบบหรือลำดับแน่นอน
มีลักษณะเหมือนการสุ่ม คือเป็นเลขมั่วๆ

random number แบ่งได้เป็น 2 แบบ คือ
แบบที่เกิดในธรรมชาติ ควบคุมและทำนายไม่ได้
กับแบบที่มนุษย์คำนวนขึ้นมาเอง

แบบที่เกิดในธรรมชาติ
ตัวอย่างเช่น
  • noise ทั้งหลาย
  • thermal noise ในสารกึ่งตัวนำ
  • การแผ่รังสีจากสารกัมมันตภาพรังสี
  • สัณญาณวิทยุจากชั้นบรรยากาศ
    บางทีเรียก random number แบบนี้ว่าเป็น true random number
    เพราะมันทำนายไม่ได้ ถือเป็นเลขสุ่มอย่างแท้จริง

    แบบที่มนุษย์คำนวนขึ้นมาเอง
    เป็นการใช้ algorithm ทาง math ทำการคำนวนเพื่อให้ได้ตัวเลขที่ดูเหมือนสุ่ม
    เรียกว่าเป็นเลขสุ่มอย่างเทียม pseudorandom number
    algorithm ที่ใช้ทำ pseudorandom number มีด้วยกันหลายตัว
    แต่ที่ใช้กันแพร่หลายที่สุดคือ linear congruential generator
    ใน entry นี้จะยกตัวอย่างของ linear congruential generator มาให้ดูกันครับ



    linear congruential generator
    เป็นการสร้างตัวเลขสุ่มโดยใช้สมการดังนี้
    Xn+1 = (aXn + c) mod m
    เมื่อ a, c และ m เป็นค่าคงที่
    และ mod m คือการหาเศษเหลือจากการหารด้วย m

    ตัวเลขสุ่มที่ได้จากสมการนี้คือค่าของ Xn+1
    จะเป็นผลมาจากค่าของตัวเลขสุ่มตัวก่อนหน้า Xn
    เรียกได้ว่าเลขสุ่มแต่ละตัวจะเป็นผลมาจากเลขสุ่มตัวก่อนหน้า
    เลขสุ่มตัวแรกคือ X1
    ส่วน X0 เป็นค่าเริ่มต้น เรียกว่า seed
    ลักษณะที่สำคัญของ linear congruential generator คือ
    ถ้าเริ่มต้นที่ seed เดียวกัน จะได้ชุดตัวเลขสุ่มออกมาเหมือนเดิมทุกครั้ง


    คุณภาพของตัวเลขสุ่ม ที่ได้จาก linear congruential generator
    จะขึ้นอยู่กับการเลือกค่าคงที่ a, c และ m
    การวิเคราะห์ว่าควรเลือกค่าคงที่พวกนี้อย่างไร
    เป็นเรื่องปวดหัวสำหรับผมมาก
    เพราะจะไม่ค่อยรู้เรื่องครับ

    เอาเป็นว่าถ้าใครสนใจอยากรู้ว่า เค้าเลือกค่ากันยังไง
    ก็ลองอ่านหนังสือของ Donald E. Knuth
    เรื่อง The Art of Computer Programming
    เล่มที่สอง chapter ที่สามเรื่อง Random numbers ดู
    หรือจะค้นจาก net ก็มี paper ให้อ่านมากมาย


    เรามาดูที่เค้าเลือกไว้แล้วดีกว่า


    ตัวอย่างแรกมาจากหนังสือ
    The C Programming Language

    Brian W. Kernighan
    Dennis M. Ritchie
    ใน chapter ที่สอง หัวข้อ 2.7 Type Conversions
    unsigned long int next = 1;
    /* rand: return pseudo-random integer on 0..32767 */
    int rand(void)
    {
       next = next * 1103515245 + 12345;
       return (unsigned int)(next/65536) % 32768;
    }
    /* srand: set seed for rand() */
    void srand(unsigned int seed)
    {
       next = seed;
    }


    ในตัวอย่างด้านบน ตรงที่
    next = next * 1103515245 + 12345;
    ดูคล้ายกับจะเป็น linear congruential โดยมี
    a = 1103515245
    c = 12345
    แต่ไม่มีการ mod ด้วย m
    จริงๆแล้ว มันมีการ mod อยู่ด้วย แต่เป็นการ mod แบบอัตโนมัติครับ

    มาดูว่า mod แบบอัตโนมัติหมายความว่าอย่างไร
    สมมุติเรามี variable x เป็น unsigned short มีขนาด 16 bits
    ค่าสูงสุดของ 16 bits คือ 0xFFFF หรือ 65535
    ไม่ว่าเราจะทำอะไรกับ x ก็ตาม เช่น เอาไปบวกหนึ่งหรือคูณล้าน เช่น
    unsigned short x = 123;
    x = x + 1;
    x = x * 1000000;
    ค่าที่เกิน 16 bits ก็ล้นออกไป
    สุดท้าย x ก็มีค่าไม่เกิน 16 bits และไม่เกินค่าสูงสุดของ 16 bits คือ 0xFFFF อยู่ดี
    เทียบเท่ากับเอา x ไป mod กับค่าสูงสุด+1 (0x10000)
    ดังนั้นสอง statement ด้านบน ก็เหมือนกับ
    x = (x +1) % 0x10000;
    x = (x * 1000000) % 0x10000;
    สรุปว่า ไม่ว่าเราจะทำอะไรกับ variable ก็จะเหมือนมี mod อยู่ด้วยเสมอ
    คือ mod ด้วย ค่าสูงสุดของ variable บวกหนึ่ง
    เป็น mod แบบอัตโนมัติ

    กลับมาที่ตัวอย่างของเรา
    variable next มี type เป็น unsigned long
    ค่าสูงสุดของ unsigned long คือ ULONG_MAX
    สามารถดูได้จาก file limits.h
    ถ้า unsigned long มีขนาด 32 bits ULONG_MAX จะเท่ากับ 0xFFFFFFFF หรือ 4294967295

    สรุปว่า
    next = next * 1103515245 + 12345;
    เป็น linear congruential ที่มี
    a = 1103515245
    c = 12345
    m = 4294967296

    ส่วนตรง
    return (unsigned int)(next/65536) % 32768
    เป็นแค่การเลือกค่าบาง bit ไปใช้
    next/65536
    จะเทียบเท่ากับการ shift bit
    next>>16

    ส่วน
    % 32768
    ถึงเป็นการ mod แต่ผลที่ได้เป็นการเลือกค่าเฉพาะ 15 bits ซึ่งเทียบเท่ากับการ and
    & 0x7FFF
    หรือ
    & 32767

    สรุปว่า
    return (unsigned int)(next/65536) % 32768
    เป็นการ
    shift bit ลงมา 16 bits แล้วเลือกเอาแค่ 15 bits



    ขอออกนอกเรื่องหน่อยนะครับ
    เรื่อง การหาร กลายเป็น shift bit และ mod กลายเป็น and อย่างที่อธิบายไปนี่
    compiler อาจจะทำให้เอง เป็นส่วนหนึ่งของการ optimize เวลา compile
    เพราะการคูณและการหารเป็น operation ที่ใช้เวลานาน
    โดยเฉพาะการหาร จะใช้เวลานานกว่า operation อื่น
    ดังนั้นถ้ามีช่องทาง compiler ก็จะพยายาม optimize ให้
    ลองดู ตัวอย่าง
    #include <stdio.h>
    unsigned long next = 1;
    unsigned int random() {
       next = next * 1103515245 + 12345;
       return (unsigned int)(next/65536) % 32768;
    }
    int main() {
       printf("%d",random());
       return 0;
    }


    ตัวอย่างด้านบนถ้าไป compile ด้วย Visual C++ 6.0
    โดยเลือก option ให้ compiler สร้าง assembly ด้วย
    ไปที่ Project Settings เลือก tab C/C++
    เลือก Category: เป็น Listing Files
    และเลือก Listing file type เป็น Assembly with Source Code
    หลัง compile จะได้ file .asm ซึ่งจะแสดงให้เห็นว่า compiler แปลง C statement ไปเป็น assembly ยังไง
    ลองดู asm ที่ผมได้ ตัดมาเฉพาะตอน return (unsigned int)(next/65536) % 32768;
    ; 5 : return (unsigned int)(next/65536) % 32768;
    shr eax, 16 ; 00000010H
    and eax, 32767 ; 00007fffH


    แต่ถ้าใช้ gcc บน linux ก็ใช้ -S เช่น
    gcc -S -O test_mod.c
    จะได้ file asm เป็น
    test_mod.s
    ลองดู asm ที่ผมตัดมาเฉพาะตอน return (unsigned int)(next/65536) % 32768;
    shrl $16, %eax
    andl $32767, %eax
    leave
    ret


    ทั้งสองกรณีด้านบน compiler จะแปลง
    return (unsigned int)(next/65536) % 32768;
    ไปเป็น
    shift right 16 bits ตามด้วย and 32767
    ทำเหมือนกันทั้ง Visual C++ และ gcc เลยครับ



    กลับมาเรื่องตัวอย่างของ linear congruential generator

    ลองมาดู function rand() จาก library ของ Visual C++ 6.0 กันบ้าง
    ใน MSDN ไม่มีรายละเอียดการทำงานของ rand()
    เราลองมาหาดูว่า rand() มันทำงานยังไง

    ลองสร้าง project ใน Visual C++ 6.0 เป็นแบบ Win32 Console Application
    แล้วเอา code ด้านล่างไป compile และ run ใน debug mode ดู
    #include <stdio.h>
    #include <stdlib.h>
    int main() {
       int r = rand();
       printf("%d",r);
       return 0;
    }

    ให้ set breakpoint ที่บรรทัด
       int r = rand();
    พอสั่ง run มันจะมาหยุดที่บรรทัดนี้
    ทำ step into เพื่อเข้าไปใน rand()
    มันจะถามหา source code ของ rand.c ให้กด cancel
    Visual C++ จะแสดง assembly code ของ rand() ดังนี้
    rand:
    00401100 push ebp
    00401101 mov ebp,esp
    00401103 mov eax,[holdrand (00424a30)]
    00401108 imul eax,eax,343FDh
    0040110E add eax,269EC3h
    00401113 mov [holdrand (00424a30)],eax
    00401118 mov eax,[holdrand (00424a30)]
    0040111D sar eax,10h
    00401120 and eax,7FFFh
    00401125 pop ebp
    00401126 ret


    จาก code ด้านบนจะเห็น
    00401108 imul eax,eax,343FDh
    0040110E add eax,269EC3h

    เป็นการคูณด้วย 343FDh แล้วบวกด้วย 269EC3h
    และไม่มีการ mod จึงเป็น mod แบบอัตโนมัติ
    ส่วน
    0040111D sar eax,10h
    00401120 and eax,7FFFh

    เป็นการ shift right 16 bits ตามด้วย and กับ 7FFFh
    จึงเป็นการเลือก bits เหมือนตัวอย่างด้านบน

    จึงสรุปได้ว่า rand() จาก library ของ Visual C++ 6.0
    เป็น linear congruential generator ที่มี
    a = 0x343FD
    c = 0x269EC3
    m = 4294967296



    อีกตัวอย่างหนึ่งของ linear congruential generator คือ
    Class Random จาก package java.util


    นี่เป็น code จาก method next ของ Class Random ครับ
    synchronized protected int next(int bits) {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return (int)(seed >>> (48 - bits));
    }


    code ตรง
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    เป็น linear congruential ที่มี
    a = 0x5DEECE66D
    c = 0xB
    ส่วน
    & ((1L << 48) - 1)
    เป็นการ mod ด้วย (1L << 48)
    ซึ่ง (1L << 48) ก็คือ (2 ยกกำลัง 48) นั่นเอง
    สรุปว่า
    m = 2 ยกกำลัง 48




    ทำไมถึงใช้ linear congruential generator กันอย่างแพร่หลาย

    ถ้าดูจากสมการ
    Xn+1 = (aXn + c) mod m
    จะเห็นว่า มันไม่ได้เป็น math ที่ซับซ้อนเกินไป
    สามารถทำความเข้าใจและเขียน code ได้ง่าย
    นอกจากนี้ ถ้าเลือกค่า m ดีๆ
    ยังหลีกเลี่ยงการทำ mod ทำให้โปรแกรมทำงานได้เร็ว
    เลยเป็นที่นิยมใช้กันอย่างแพร่หลาย


    แต่อย่าลืมว่า
    seed เดียวกัน จะได้ชุดตัวเลขสุ่มออกมาเหมือนเดิมทุกครั้งนะครับ












    Create Date : 04 ตุลาคม 2551
    Last Update : 7 ตุลาคม 2551 22:23:42 น. 6 comments
    Counter : 3501 Pageviews.

  •  
    หุหุ แค่ RND() ไม่น่าเชื่อว่าเรื่องมันใหญ่ขนาดนี้
    นับถือ นับถือ คาราวะ 1 จอก


    โดย: ช่วยเหลือ IP: 124.120.243.122 วันที่: 6 พฤศจิกายน 2551 เวลา:3:03:59 น.  

     
    เป็นเรื่องที่น่าสนใจมากครับ ทำการบ้านมาดีมากครับ เยี่ยมจริง ๆ




    ขอให้มีความสุขในวันอาทิตย์สบาย ๆ แบบนี้นะครับ




    โดย: motokop วันที่: 21 ธันวาคม 2551 เวลา:10:59:57 น.  

     
    คลิกที่รูป เพื่อเอาโค้ดรูปนี้ไปแปะ



    โดย: motokop วันที่: 24 ธันวาคม 2551 เวลา:17:32:20 น.  

     
    คลิกที่รูป เพื่อเอาโค้ดรูปนี้ไปแปะ



    ขอให้มีสุขภาพแข็งแรง คิดหวังสิ่งใดขอให้สมปรารถนาทุกประการนะครับ


    โดย: motokop วันที่: 30 ธันวาคม 2551 เวลา:13:18:42 น.  

     
    .... เหรอ


    โดย: กล้วยเน่านะหนองบึง IP: unknown, 202.44.135.34 วันที่: 17 มิถุนายน 2553 เวลา:9:44:27 น.  

     
    ขอบคุณครับที่ตั้งใจให้ความรู้กับผม ^^


    โดย: Rang IP: 1.47.102.145 วันที่: 22 มิถุนายน 2555 เวลา:7:39:40 น.  

    ชื่อ :
    Comment :
      *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
     
    รหัสส่งข้อความ
    กรุณายืนยันรหัสส่งข้อความ

    zkaru
    Location :
    กรุงเทพฯ Thailand

    [Profile ทั้งหมด]

    ให้ทิปเจ้าของ Blog [?]
    ฝากข้อความหลังไมค์
    Rss Feed
    Smember
    ผู้ติดตามบล็อก : 2 คน [?]




    เรื่องที่อยากเขียน ... เรื่องที่พยายามเขียน ...
    Friends' blogs
    [Add zkaru's blog to your web]
    Links
     

     Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.