ทำไม arithmetic ในคอมพ์จึงยาก?

วันก่อน peter (ซี้เก่าสมัยเรียนที่ Tsukuba) ส่งเรื่อง bug ใน Excel 2007 มาให้อ่าน (อันที่ peter ส่งมาไม่ใช่อันนี้นะ แต่ว่าก็เรื่องเดียวกัน)



ก็ตกใจเล็กน้อยนะ แต่ว่าก็ไม่ได้มากอะไร เพราะว่าจริงๆ ก็รู้อยู่ว่า computer arithmetic มันยาก …..

อ่าว มันจะยากได้ไงล่ะ ก็วิธีการก็รู้ๆ กันอยู่นี่นา จริงๆ แล้วไม่หรอก เพราะว่าการทำ computer arithmetic มันมีปัจจัยเยอะมาก .. อย่างที่ว่าน่ะแหละ devils are in details … แทบทุกเรื่องน่ะแหละ เราจะลง details แค่ไหนเท่านั้นเอง

พอดีไปเจอนี่มา

ที่มีคำอธิบายค่อนข้างจะละเอียด แต่ว่าอ่านตามได้ง่ายๆ และที่สำคัญ ถ้าใครคุ้นๆ ชื่อ ก็คงจะร้องอ๋อ ว่านี่มันพวกที่ทำ Mathematica ซึ่งเป็น Mathematical Package ที่ถือกันว่าดีที่สุดตัวหนึ่งนี่นา (มีชื่อมากเรื่องประสิทธิภาพ เรื่อง programmability .. ภาษา Mathematica นี่สุดยอดมากเหมือนกัน และเรื่องความแม่นยำ — แต่ว่าแพงมาก) ใน blog นั้นเขาเขียนขาย/เชียร์ Mathematica มากไปนิด (ก็แน่นอน) ผมก็เลยเอาใจความตรงที่เป็นสาระของเรื่องนี้มาเขียนให้อ่านกันใหม่เป็นภาษไทยก็แล้วกันนะ ตามนี้เลย

  • มันยากเพราะว่าวิธีการทำ arithmetic ที่อยู่ในตำราคณิตศาสตร์เบื้องต้น (วิธีที่เราชอบคิดกัน) มันไม่มีประสิทธิภาพเพียงพอ เช่นการคูณเลข ถ้าเราต้องการคูณเลขที่มีตัวเลขทั้งหมด n ตัว จะต้องใช้การคูณทั้งหมด n^2 ครั้ง แต่ว่าจริงๆ แล้วจาก algorithm ขั้นสูง เราก็รู้วิธีการที่จะทำได้ใน n^1.58, n log n หรือแม้แต่น้อยกว่านั้นสำหรับ n ที่มีค่ามากๆ ดังนั้นถ้า n มันใหญ่พอ มันจะเห็นความแตกต่างได้ชัดเจนมาก เรื่องเวลาที่ใช้ในการคำนวณ (เสี้ยววินาที เทียบกับเป็นนาที อะไรทำนองนั้น) ตัวอย่างของ algorithm ดังกล่าวก็เช่น Karatsuba algorithm
  • Algorithm เหล่านี้ แม้ว่าจะมีประสิทธิภาพสูงกว่า (และมีความแม่นยำสูงกว่า) วิธีการแบบ school-book มาก .. แต่ว่าเนื่องจากความซับซ้อนของมัน ก็ทำให้พวกมันมี bug ง่ายกว่าเช่นกัน
  • นอกจากนั้นยังมีเรื่องของการเก็บค่าตัวเลขทศนิยมไว้ในหน่วยความจำ ซึ่งปกติจะเก็บเป็นฐาน 2 เพื่อคำนวณ แต่ว่าเมื่อจะนำมาแสดงผล จะต้องเปลี่ยนฐานเลขให้เป็นฐาน 10 ซึ่งโดยปกติจะต้องทำการ round ตัวเลขฐาน 2 พวกนั้นให้เป็นเลขฐาน 10 ที่มีความใกล้เคียงที่สุด จากรูปข้างล่างนี่จะเห็นว่ามีความคลาดเคลื่อนในการแสดงผล


  • ปัญหาหลักๆ จริงๆ มาจากการทำ base conversion ซึ่งจาก binary เป็น decimal จะใช้การคูณเป็นหลัก และจาก decimal เป็น binary จะกลับกันคือใช้การหารเป็นหลัก ประเด็นมันอยู่ที่ว่า บางที (สำหรับตัวเลขบางตัว) การคูณหรือหารนั้นจะต้องทำที่ precision ที่มากกว่าตัวเลขนั้นๆ เพื่อให้ได้ค่าที่ถูกต้อง
  • แต่ว่าระบบคำนวณหลายระบบดันผูกติดกับ fixed precision ของ hardware ที่ใช้งาน ดังนั้นในหลายๆ งานจึงไม่สามารถที่จะได้การแปลงเลขฐานที่ถูกต้องสำหรับตัวเลขหลายๆ ตัว
  • ความผิดพลาดยังเกิดได้จาก “เลขทด” (carries) หรือตัวเลขที่เกิดจากกระบวนการทดเลขน่ะแหละครับ ซึ่งระบบซอฟต์แวร์หลายตัวก็จะทำงานพลาดถ้ามีการทดมากๆ ไป ซึ่ง bug แบบนี้มีมาตั้งแต่สมัยไหนสมัยไรแล้ว โปรแกรมหลายตัวในปัจจุบันก็ยังมีปัญหาเรื่องนี้อยู่นะ
  • ปัญหาหนักอีกที่หนึ่งสำหรับ computer arithmetic ก็คือ ในกรณีทั่วๆ ไป มันค่อนข้างจะ “ง่าย” ที่จะทำให้มัน “เกือบถูกต้อง” (คือ ถูกกับ input case ทั่วๆ ไป แต่ว่ากับ input บางตัวจริงๆ จะทำให้เกิดปัญหาขึ้นมา)
  • และปัญหาที่หนักที่สุดก็คือพวก bug กับตัวเลขบางตัวที่มี bit pattern บางประเภทจริงๆ พวกนี้จะหาเจอยากมากในระหว่าง testing หรือว่าเรียกได้ว่า rare bug เลยก็ว่าได้ มันหายากขนาดที่ว่าเราอาจจะทดสอบกับตัวเลขเป็นพันๆ ล้านตัว แต่ว่าไม่เจอพวกมันเลยก็ได้

ยังเชื่อใจโปรแกรมหลายตัวของท่านอยู่อีกหรือเปล่าเนี่ย?

อ้างอิง: Wolfram Blog: Arithmetic is Hard — To Get Right

ปล. หลังจากคุยกันเสร็จ ผมกับ peter ก็ joke เล่นกันต่อว่า เฮ้ย นี่แหละ เห็นมั้ย OpenOffice.org ไม่ compatible กับ MS-Office อีกอย่างแล้วนะ (ค่าที่คำนวณมันได้ไม่เท่ากัน ใส่ตัวเลขข้างบนเข้าไปแล้ว OO.o มันคำนวณถูก…) แถม peter เล่าให้ฟังว่า บางคนตลกร้ายกว่านั้น บอกให้เพิ่ม tag MultiplyLikeExcel2007 ลงไปใน spec ของ OOXML ด้วยนะ ขำกลิ้งเลย

ปล.2 จริงๆ Slashdot ก็มีลง แต่ว่าพักหลังๆ ผมอ่าน /. น้อยลงมั้ง ก็เลยไม่ค่อยได้สังเกตหรือว่าใส่ใจ อันนี้ link:

Coincidence คำพูดปลอบใจ และทฤษฎีความน่าจะเป็น

เคยอ่านเจอ หรือว่าเคยได้ยิน เรื่องความคล้ายกันของ John F. Kennedy กับ Abraham Lincoln มั้ย? สองคนนี้มีอะไรที่คล้ายกันอย่างไม่น่าเชื่อเชียวล่ะ

มันบังเอิญขนาดนั้นเลยเหรอ?

ไม่มีอะไรหรอกครับ พอดีช่วงนี้เปิดฤดูกาลบอลน่ะ แล้วทีมโปรดของผม Manchester United ก็เปิดได้อย่างน่าดูสุดๆ คือ เสมอมันรวดสองนัด แพ้ใน derby match อีกตะหาก แต่ว่าช่วงก่อนจะแพ้ Man City ก็มีแฟนบอลที่แม่นสถิติของทีม มาบอกว่าคร้ังสุดท้ายที่เราเปิดฤดูกาลมาเสมอสองนัดเนี่ย ปีนั้นเราได้ 3 แชมป์

ปีก่อน ผมจำได้ว่าก่อนที่ Man United จะแพ้ Milan ใน ECL น่ะครับ มีหลายคนที่เอาสถิติปีที่แล้วกับปีที่ได้ 3 แชมป์นั้นมาเทียบกัน ว่ามันเหมือนกันสุดๆ ในหลายๆ อย่าง ….​

แต่แล้ว ปีที่แล้วก็ไม่ได้ 3 แชมป์ จริงๆ แล้วได้แค่แชมป์เดียว

ผมอยากจะเขียนเรื่องนี้มานานแล้วครับ เรื่องความเข้าใจความน่าจะเป็น ความเข้าใจปรากฏการณ์ของ coincidence และ common sense ที่บางทีอาจจะกลายเป็น common nonsense ไปเสียได้กับเรื่องแบบนี้

มันเป็นธรรมดาครับ ที่ถ้าเรามีข้อมูลอะไรบางอย่าง และเลือกพิจารณาข้อมูลบางอย่าง อย่าง “หลวม”ๆ แล้ว มันจะมีข้อมูลที่สามารถตรงกันได้อย่างน่าอัศจรรย์เลย ลองเล่นเกมง่ายๆ ดูครับ

  1. เอาไพ่มา 2 สำรับ ให้คน 2 คนช่วยกันสับไพ่คนละสำรับ สับให้เละจนกว่าจะพอใจนะ
  2. จากนั้นให้ทั้ง 2 คนหยิบไพ่ใบไหนก็ได้ (หรือว่าจะเอาใบบนสุดของสำรับก็ได้นะ) มาเปิดพร้อมกันทีละคู่
  3. ดูซิว่าจะมี “ตรง” กันบ้างมั้ย

สนุกนะครับ ที่ผม “” คำว่า “ตรง” เนี่ยแหละ เพราะว่าถ้าเรายิ่งระบุ condition ในการ “ตรง” ให้ “หลวม” เท่าไหร่ มันก็ยิ่งตรงกันมากขึ้นเท่านั้น (อันนี้ common sense ใช่มั้ย) เช่น condition ด้านล่างนี้ เรียงจาก strict มากที่สุด ถึงหลวมมากที่สุดนะ

  1. ไพ่จะตรงกันเมื่อทั้งสํญลักษณ์และหมายเลขตรงกัน (1 ใน 52 ใบ)
  2. ไพ่จะตรงกันเมื่อมีสีเหมือนกันและหมายเลขตรงกัน (2 ใน 52 ใบ)
  3. ไพ่จะตรงกันเมื่อหมายเลขตรงกัน (4 ใน 52 ใบ)
  4. ไพ่จะตรงกันเมื่อมีสัญลักษณ์เดียวกัน (13 ใน 52 ใบ)
  5. ไพ่จะตรงกันเมื่อมีสีเดียวกัน (26 ใน 52 ใบ)

เป็นต้น

ผมลองทำ simulation ง่ายๆ นะครับ โดยนับสถิติจากการเล่นเกมทั้งหมด 100 ครั้ง ได้ผลดังนี้ครับ

  1. สัญลักษณ์และหมายเลขตรงกัน มากที่สุด 4 ครั้ง น้อยที่สุด 0 ครั้ง เฉลี่ย 1.05 ครั้ง ตัวเลขที่ออกมากที่สุดคือ 1 (38 ครั้ง)
  2. หมายเลขตรงกัน มากที่สุด 9 ครั้ง น้อยที่สุด 0 ครั้ง เฉลี่ย 4.24 ครั้ง ตัวเลขที่ออกมากที่สุดคือ 3 (23 ครั้ง)
  3. สัญลักษณ์ตรงกัน มากที่สุด 21 ครั้ง น้อยที่สุด 6 ครั้ง เฉลี่ย 12.85 ครั้ง ตัวเลขที่ออกมากที่สุดคือ 10 (14 ครั้ง)
  4. สีตรงกัน มากที่สุด 34 ครั้ง น้อยที่สุด 16 ครั้ง เฉลี่ย 25.6 ครั้ง ตัวเลขที่ออกมากที่สุดคือ 26 (24 ครั้ง)

เห็นได้ชัดเจน ว่ามันจะมีสิ่งที่ บังเอิญ ตรงกันบ้าง ยิ่งเราให้ condition มันหลวมเท่าไหร่ มันยิ่งตรงกันมากขึ้น ง่ายขึ้น เท่านั้น ซึ่งก็พอๆ กับเรื่อง Lincoln กับ Kennedy หรือว่าเรื่องความบังเอิญทั้งหลายแหล่ในฟุตบอล เหตุการณ์ต่างๆ กีฬาต่างๆ สถานการณ์โลกต่างๆ ด้วย

บางทีถ้าเราคิดว่าอะไรมันสำคัญล่ะก็ เราจะ focus และมองเห็นแต่สิ่งนั้นอย่างเดียว เช่นเราลองคิดว่าตัวเลขบางตัวมันสำคัญสิ (เช่น 23 หรือว่า 3.14) เราอาจจะเห็นมันอยู่รอบๆ ตัวมากมายกว่าตัวเลขอื่นๆ .. เพราะว่าเราเลือกมองไพ่ที่สิ่งรอบตัวหงายขึ้นมา เฉพาะใบที่มันบังเอิญตรงกับไพ่ที่ใจเราหงายขึ้นมาเอง

เหตุการณ์ต่างๆ มากมายที่เกิดขึ้นตลอดเวลาบนโลกนี้ มันก็จะมีอะไรที่คล้ายกันบ้าง มากหรือน้อยก็แล้วแต่เหตุการณ์นั้นๆ บางทีถ้าเหตุการณ์มันคล้ายกับอะไรที่เคยเกิดขึ้นแล้วมันไม่ค่อยดี บางทีเราก็ระลึกไว้บ้างละกันว่า มันเป็นแค่ความบังเอิญเท่านั้น หรือว่าบางทีที่มันไปเกิดคล้ายกับเหตุการณ์ดีๆ มันก็แค่ความบังเอิญเช่นกัน

ระลึกไว้: เพราะว่าเราเลือก มอง ไพ่ที่สิ่งรอบตัวหงายขึ้นมา เฉพาะใบที่มัน บังเอิญตรง กับไพ่ที่ใจเราหงายขึ้นมาเอง

>> Good Math, Bad Math : Fractal Dust and Noise

Good Math, Bad Math : Fractal Dust and Noise:

ไปเจอมา เป็นเรื่องเกี่ยวกับ Fractals กับเรื่องธรรมชาติของ Noise แล้วก็ Dust ที่เกี่ยวข้องกับ Information Theory (Shannon’s Information) อืมมม ก็ไม่ใช่เรื่องน่าแปลกใจอะไรสำหรับผมนะ เพราะว่ารู้อยู่แล้วว่าธรรมชาติของ Noise ใน communication channel มันเป็น Fractals อยู่แล้ว

สำหรับตัวอย่างที่เค้าให้มาก็ obvious พอสมควร ลองอ่านและทำความเข้าใจดู สำหรับผมนะ มันไม่น่าแปลกใจหรอก เพราะว่าธรรมชาติมีอะไรที่เป็น Fractals เยอะ เรื่อง Self-similarity และ Fine structure หรือว่าเรื่องของ Fractional dimensions ของสิ่งต่างๆ ที่มีอยู่รอบตัว อะไรแบบ

ไว้วันหลัง (อีกล่ะ) ผมคงจะมีเวลาเขียนถึงเรื่องแบบนี้บ้าง โดยเฉพาะเรื่อง Chaos Theory, Information Theory, Fractals เนี่ย อยากหาเวลาเขียนบทความแนว Popular Science ถึงพวกมันบ้างจัง

ตอนนี้อ่านนี่ไปก่อนนะครับ

Good Math, Bad Math: An Introduction to Fractals