ทำไม 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:

Post Navigation