ก้าวแรก HPC #04 : ตำนาน Note G

เกริ่นนำ

ในบทความชุดนี้ ผมจะนำเสนอแนวคิดพื้นฐานในการประยุกค์ HPC กับงาน Big Compute ที่ผ่านมา ผมแนะนำภาษารวมทั้ง Hardware ที่ใช้ มาถึงบทนี้เป็นเรื่องของโจทย์ทดลอง วันนี้เราจะมาคุยเรื่องนี้กัน อาศัยมันเป็นแกนกลาง เพื่อวิ่งเข้าหาเครื่องมือต่างๆ เชื่อว่าวิธีนี้จะเห็นภาพรวมได้ดีกว่า  ถ้าพร้อมแล้ว เรามาเข้าเรื่องกันเลย

จากหัวเรื่องบทความนี้ Note G … Note G  มันคืออะไรกัน ใช่ tablet รุ่นใหม่รึเปล่า หรือจะเป็นเรื่องของดาวตลกในตำนานของไทย ไม่ใช่ทั้งนั้นครับ ผมขอทิ้งเป็นปริศนาไว้ก่อน อ่านไปเรื่อยๆ จะทราบเองครับ ในตอนนี้ขอตั้งคำถามก่อน ท่านรู้จัก “โปรแกรมเมอร์คนแรกของโลก”  หรือไม่ครับ ที่ถามเพราะจะโยงต่อไปถึง Note G ในที่สุด

ในบทความก่อนหน้านี้ ผมเขียนถึงเครื่อง IAS machine หรือที่รู้จักกันว่า von Neumann Machine  บางท่านเมื่อนึกถึงคำว่า “โปรแกรมเมอร์คนแรกของโลก” ก็ชวนให้นึกถึงใครสักคนหนึ่งที่เขียนโปรแกรมแรกสำหรับเครื่อง IAS นั้น หรือจะเป็น von Neumann เองก็ได้ที่อาจจะนับได้ว่าเป็นโปรแกรมเมอร์คนแรกของโลก

แต่ใครที่เคยอ่านบทความของผมเมื่อสิบกว่าปีก่อน อาจจะจำได้ว่าผมเคยเขียนไว้อาลัย Edsger W. Dijkstra ในวันที่ท่านจากไป ท่านผู้เป็นอาจารย์ใหญ่ของโลกของอัลกอริทึมและคอมพิวเตอร์ ทำไมผมถึงบอกว่าท่านนี้เป็นโปรแกรมเมอร์คนแรกของโลก ผมขอย้อนเรื่องให้ฟังอีกที เรื่องของเรื่องเกิดจากการเล่นคำของผมเองครับ คือตอนที่สำรวจทะเบียนประชากรของชาวดัตช์ในสมัยประมาณ 100 ปีที่ผ่านมา ประชาชนต้องกรอกแบบฟอร์ม ในนั้นมีถามอาชีพด้วย Dijkstra ก็เลยเขียนไปว่า Programmer ซึ่งก่อนหน้านี้ไม่เคยมีใครพูดว่าตัวเองมีอาชีพ Programmer เลย จึงเป็นครั้งแรกที่อาชีพ Programmer อุบัติขึ้นมาในโลก ผมก็เลยถือว่านี่เป็นโปรแกรมเมอร์คนแรก แม้ว่าอาจจะเป็นดูศรีธนญชันไปสักหน่อยก็ตาม

แต่ถ้าไปถามคนในวงการคอมพิวเตอร์ ก็มักจะได้คำตอบว่าโปรแกรมเมอร์คนแรกของโลกเป็นผู้หญิงชื่อว่า Lady Augusta Ada Byron  ผู้เป็นภรรยาของท่านเคานต์แห่ง Lovelace เรื่องนี้ “ใครๆ ก็รู้” ว่าเธอเป็น “โปรแกรมเมอร์คนแรกของโลก” เธอเขียนโปรแกรมแรกเมื่อปี ค.ศ. 1842 ปีนั้นเป็นปีที่จีนแพ้สงครามฝิ่นต่ออังกฤษ หรือถ้าเทียบเป็นไทยก็ปลายรัชกาลที่ 3 เครื่องคอมพิวเตอร์ที่เธอใช้เขียนโปรแกรมคือเครื่อง Analytical Engine ที่คิดค้นโดย Charles Babbage ถ้าถามเครื่องนั้นหน้าตาเป็นยังไง ตอบได้เลยครับ ไม่มีใครรู้ แม้แต่ Babbage ผู้ออกแบบเครื่องก็ไม่รู้ ไม่ต้องงงครับ ทั้งนี้เพราะไม่เคยมีใครสร้างเครื่องนี้ได้จริง ฟังดูแหม่งๆ แล้วใช่ไหมครับ โปรแกรมเมอร์คนแรกเขียนโปรแกรมบนเครื่องที่ไม่มีต้วตน เรื่องนี้เป็นเรื่องที่ถกเถียงกันทั่วโลก ถกกันหลายประเด็น มีไม่น้อยครับที่ไม่ยอมรับว่าเธอเป็นโปรแกรมเมอร์ของโลก  ในบทความนี้ ผมขอก้าวข้ามความขัดแย้งนั้นไป ยอมรับให้เธอเป็น “โปรแกรมเมอร์คนแรกของโลก” มิฉะนั้นเราจะไปต่อไม่ได้

ว่าแต่ว่าโปรแกรมแรกของโลกคือโปรแกรมอะไร

โปรแกรมแรกของโลก ไม่ใช่ Hello, World นะครับ Hello, World เกิดขึ้นกับหนังสือสอนภาษา C ในยุคต้นทศวรรษ 1970 โปรแกรมแรกของโลกถอยไปไกลกว่านั้น ก็เราตกลงกันแล้วนี่ครับว่าเราถือว่า Ada เป็นโปรแกรมเมอร์คนแรกของโลก โปรแกรมแรกของโลกก็ย่อมเป็นเธอที่เป็นผู้เขียน เพื่อให้ทราบความจริง ผมขอย้อนเวลากลับไปในปี ค.ศ. 1842  เวลานั้น Ada ได้รับมอบหมายให้แปลเอกสารฉบับหนึ่งให้เป็นภาษาอังกฤษ เป็นบทความของหนุ่มน้อยนักวิศวกรทางทหารชาวอิตาลีชื่อว่า Luigi Menabrea (ผู้ซึ่งต่อมาใหญ่โตจนกลายเป็นถึงนายกรัฐมนตรีของอิตาลีในที่สุด) เนื้อหาในบทความนั้นกล่าวถึงโครงสร้างอย่างหยาบ (โคตรๆ) ของเครื่องจักรกลระบบเฟืองมือหมุน Analytical Engine ของ Babbage นั่นเอง ซึ่ง Ada ก็นับได้ว่าเหมาะอย่างที่สุดแล้วที่เป็นผู้แปล เพราะรู้จักเครื่องจักรตัวแรกของ Babbage คือ Difference Engine มาก่อน ประกอบกับ Ada เองก็เป็นนักคณิตศาสตร์อยู่แล้วด้วย ซึ่งเอกสารที่ Ada แปลนั้น มีชื่อว่า Sketch of The Analytical Engine Invented by Charles Babbage

ลำพังถ้าแปลเฉยๆ วันนี้ก็คงไม่มีใครรู้จัก Ada อย่างแน่นอน วิธีการที่ Ada สร้างตัวตนขึ้นมาในประวัติศาสตร์ได้นั้นน่าสนใจครับ คือระหว่างที่ Ada นั่นแปลเอกสารอยู่นั้น เธอนึกถึงวิธีใช้เครื่องไปด้วย เลยเกิดจินตนาการว่า เครื่องนี้น่าจะเอามาแก้ปัญหาโจทย์เลขที่มีความซับซ้อนได้ โดยใช้หลักการวนรอบ (loop) เรื่องการวนรอบที่ประยุกต์ใช้กับเครื่องคอมพิวเตอร์จึงกำเนิดขึ้นมาบนโลกเป็นครั้งแรกนับแต่บัดนั้น และ Ada ก็เขียนบันทึกสิ่งที่อยู่ในความคิดของเธอเอาไว้ตอนท้ายของเอกสารที่เธอแปลนั่นเอง เรียกว่า Note ซึ่งไล่ไปตั้งแต่ Note A ไปถึง Note G  ที่เผยให้เห็นถึงวิธีการโปรแกรมเครื่องคอมพิวเตอร์นั้น ทำไปทำมา Note ต่างๆ ที่เธอเขียนยาวยิ่งกว่าตัวเอกสารจริงที่เธอแปลเสียอีก ที่สำคัญที่สุดจนกลายเป็นตำนานก็คือ Note G นั่นเอง ใน Note G นั้น Ada  นำเสนออัลกอริทึมที่สามารถนำไปโปรแกรมบนเครื่อง Analytical Engine สำหรับแก้โจทย์ที่โหดมากข้อหนึ่ง เป็นการหาค่า Bernoulli Number ซึ่งผมจะละเอาไว้ก่อน ไว้คุยในหัวข้อต่อไป ตอนนี้เอาเรื่อง Ada ให้จบ   ชาวโลกก็เลยถือว่าโปรแกรมแรกของโลกคือโปรแกรมหาค่า  Bernoulli Number นั่นเอง ในหัวข้อนี้ผมขอสรุปว่า สิ่งที่อยู่ใน Note G นั้นทำให้เธอเป็นอมตะและกลายเป็น “โปรแกรมเมอร์คนแรกของโลก” นั่นเอง

มีคนอยู่กลุ่มหนึ่งที่ไม่เชื่อว่า Ada เป็นคนเขียน Note ด้วยตัวเอง โดยใช้หลักการวิเคราะห์ทางภาษาศาสตร์เทียบกับเอกสารฉบับอื่นของเธอ พบว่าต่างกันค่อนข้างมาก บ้างแม้เชื่อว่า Ada เป็นคนเขียน Note เองแต่ก็คิดว่าเนื้อหาไปลอก Babbage มา โดยเฉพาะอย่างยิ่งอัลกอริทึมในตำนานนั้น เพราะในเวลาต่อมา Babbage ร้องขอให้ Ada ยกเลิกตีพิมพ์เอกสารฉบับนี้เสีย แต่ Ada ก็ปฏิเสธ ใครสนใจเรื่องราวก็ลองไปค้นคว้าดูนะครับ ถ้าถามผม ผมไม่อยากจะถือว่านี่คือโปรแกรมตัวแรกของโลก ไม่ใช่เพราะไม่เชื่อถือในตัว Ada แต่ผมไม่เชื่อถือเครื่อง Analytical Engine เพราะจนป่านนี้ พ.ศ. นี้ยังไม่มีใครสร้างขึ้นมาได้จริงเลย มีแต่เครื่องต้นแบบที่ยังสร้างไม่เสร็จของ Babbage  (แต่เครื่องจักรก่อนหน้า difference engine มีคนในยุคสมัยเราสร้างขึ้นทำงานได้จริงแล้ว) ดังนั้นเครื่องนี้จึงเป็นเครื่องที่อยู่ในจินตนาการ ผมเชื่อว่า Ada อยากใส่อะไรก็ได้ให้เครื่องมันมี เพื่อให้มันสามารถไปจนจบได้ แต่เอาจริงๆ เครื่องมันอาจจะเป็ดง่อยมากทำอะไรไม่ได้เลย “ก็เป็นได้”

สิ่งหนึ่งที่ผมยังแปลกใจมากๆ ก็คืออัลกอริทึมของการหาค่าตัวเลขของ Ada นั้นไม่เคยมีใครกล่าวถึงเลย วิธีการหาค่า Bernoulli Number มีหลายวิธีมาก แต่ในนั้นไม่มีใครพูดถึงวิธีของ Ada เลย ทั้งๆ ที่ผมอ่านดูในเอกสาร มันก็น่าจะเป็นอัลกอริทึมทางคณิตศาสตร์ธรรมดา แต่ผมค้นหาดูแล้วยังไม่มึใครฟันธงเลยว่าอัลกอริทึมนั้นมันถูกหรือผิด เป็นวิธีใหม่หรือซ้ำกับอัลกอริทึมของใคร ดูเหมือนงานของเธอจะอยู่แต่ในนิยายปรัมปรา ไม่ได้ออกมาโลดแล่นในโลกความเป็นจริงเอาเสียเลย ผมเองก็ยังไม่ได้อ่านเอกสารของ Ada อย่างจริงจัง ก็เลยตอบอะไรไม่ได้ เอาเป็นว่าสักวันถ้าว่างจริงๆ ผมอาจจะค่อยๆ อ่านเอกสารมาศึกษาแล้วลองเขียนมาเป็นโปรแกรมดูว่ามันหาค่าได้จริงหรือไม่

จบนะครับ เรื่องของ Ada จบตรงนี้นะครับ ไม่งั้นดราม่าจะยาวเกิน

ขอนอกเรื่องไปแวะรับ Sagemath ก่อนครับ

เว็ปนี้เกี่ยวข้องกับ High Performance Computing (HPC) ซึ่งแน่นอนครับต้องดองญาติกับคณิตศาสตร์อย่างหลีกเลี่ยงไม่ได้ คณิตศาสตร์นี่ก็แปลก ใครไม่รักไปเลยก็เกลียดสุดใจ เพื่อให้ผ่านวันเวลาไม่ให้ขมจนเกินไปนักสำหรับผู้ที่ยืนตรงข้ามคณิตศาสตร์ ผู้ขอเรียกตัวผู้ช่วยมาครับ ผมคัดสรรแล้วสามารถผ่อนแรงเราได้มาก ผู้ช่วยที่ว่านี้คือโปรแกรม Sagemath ครับ ใครไม่รู้จักแต่รู้จัก Mathematica ก็บอกได้เลยว่ามันแนวเดียวกัน สามารถคำนวณงานซับซ้อน มีฟังก์ชันทางคณิตศาสตร์เพียบ และยังรองรับ Symbolic Math ซึ่งก็คือสามารถสร้าง symbol ขึ้นมาที่ไม่ใช่ตัวแปร ดังนั้น  10 A / 5  สามารถตอบได้ว่าเป็น 2 A  โดยไม่พยายามสนใจว่าภายใน A มีค่าอะไร มอง A เป็น Symbol นั่นเอง ความเก่งกาจของโปรแกรมนี้เทียบชั้นได้กับ Mathematica ซึ่งเป็นสุดยอดโปรแกรมทางการคำนวณแบบ Symbolic Math

แน่นอนครับที่เลือกโปรแกรมตัวนี้มาใช้ ข้อแรกเลยก็คือฟรี และข้อที่สองก็คือสามารถเขียนโปรแกรมเชื่อมต่อได้หลายภาษา ซึ่งในนั้นมีภาษา Python ซึ่งผมจะใช้เป็นหลักภาษาหนึ่งในเว็บนี้  ข้อเสียที่เห็นก็คือทำงานได้บน OS ตระกูล Unix เท่านั้น ทำงานบน Windows ไม่ได้ แต่ทางแก้ก็พอมีครับ ก็คือทำงานเป็นแบบ Virtual Machine จำลอง Linux บนเครื่อง Windows เลย ซึ่งถ้าใครไม่ถนัด Linux ก็ไม่เป็นปัญหาครับ ใน Website  http://www.sagemath.org ก็มี Virtual Machine สำเร็จรูปให้ Download ไปใช้ได้เลย

แต่ถ้าใครยังคิดว่ายุ่งยากอยู่ ผมขอแนะนำให้ใช้อีกวิธีหนึ่ง เป็นวิธีหลักที่ผมใช้ตลอดการเขียนบทความนี้ นั่นคือการใช้งาน online เราไม่ต้องลงโปรแกรมใดๆ ใช้งานผ่าน Browser ปกติได้เลย ไปที่ ttp://www.sagemath.org เลือก Try Sage Online  จากนั้นก็ลงทะเบียนฟรีครับ เมื่อลงทะเบียนเสร็จก็สร้าง project ตั้งชื่ออะไรก็ได้ ภายใน project เลือก new และสร้าง Sage Worksheet ขึ้นมา จะได้หน้าเปล่าครับ เรามาลอง Hello, World Sagemath กันเล่นๆ ลองพิมพ์สองบรรทัดนี้ดูครับ

โปรแกรมที่เขียนเป็นภาษา Python นะครับ เมื่อเขียนเสร็จแล้วลองกดปุ่ม Run ดูครับ ถ้าทุกอย่างถูกต้อง ก็จะได้ผลลัพธ์ประมาณนี้ครับ

first sagemath

Hello, Sagemath

วิธีนี้ใช้งานง่ายมากครับ ฟรีและไม่ต้องลงโปรแกรมให้เสียเวลา ผมคงไม่สอนในรายละเอียดการใช้มากไปกว่านี้นะครับ เชื่อว่าลองผิดลองถูกเล็กน้อยก็สามารถใช้งานได้อย่างคล่องมือ ลองใช้ดูนะครับ เพราะผมจะใช้ Sagemath ไปตลอด และในบทความนี้ source code ทุกตัวเขียนบน Sagemath ครับ และถ้าใครอ่านบนความนี้โดยใช้โทรศัพท์มือถือหรือกระดานชนวน ก็สามารถ download sage math client ได้ทั้ง Android และ iOS ลองใช้งานนอกบ้านได้เลยครับ

เมื่อเรารับ Sagemath มาแล้ว ก็ให้มันทำหน้าที่เป็นไกด์พาเราท่องโลกของ Bernoulli Number กันต่อเลยครับ

รู้จัก Bernoulli Number

ผมเองพอมาเขียนบทความเรื่องเกี่ยวกับ HPC ก็อยากจะหาตัวอย่างโจทย์ทางคณิตศาสตร์ที่มีความซับซ้อนพอสมควร จะได้ดึงกำลังของเครื่องคอมพิวเตอร์มาคำนวณเพื่อให้เห็นถึงประสิทธิภาพของระบบ นึกไปนึกมา ก็นึกถึง Bernoulli Number  ตัวเลขชุดนี้ มีทั้งตำนาน มีทั้งดราม่า ความซับซ้อน เหมาะมากครับที่จะเป็นโจทย์โหมโรงให้เรามาทดลองกัน เราจึงควรมาทำความรู้จักผู้คิดค้นกันก่อน

John Bernoulli ชาวสวิส มีชีวิตอยู่ใกล้ๆ ช่วงเสียกรุงศรีอยุธยาครั้งที่ 2 ร่วมสมัยกับ Leonhard Euler ชาติเดียวกัน ผู้ซึ่งเป็นอาจารย์ใหญ่หลายศาสตร์โดยเฉพาะอย่างยิ่งคณิตศาสตร์ ทั้งสองท่านร่วมมือกันคิดค้นทฤษฎีทางวิทยาศาสตร์มากมาย ซึ่งผมขอไม่พูดถึงในที่นี้ (เพราะเกินขอบเขตความรู้ของผม) ผมขอเจาะประเด็นเฉพาะ Bernoulli Number ก็แล้วกัน

เพื่อทำความเข้าใจ Bernoulli Number ผมขอไล่ตั้งแต่ต้น แสดงให้ดูเป็นขั้นๆ จะได้เข้าใจได้ง่าย ถ้าอย่างนั้นขอเริ่มที่อนุกรมนี้ครับ

1 + 2 + 3 + .. + 100

หาผลรวมได้ไหมครับ โจทย์ข้อนี้เจ้าชายคณิตศาสตร์อย่าง Gauss สามารถหาคำตอบได้ตอน 9 ขวบ ทันทีว่า 5050  จริงๆ แล้ว ต่อให้บวกกันถึงล้าน Gauss ก็ยังคงตอบได้ทันทีเช่นเดิม ก็เพราะ Gause ไม่ได้ไล่บวกจริงๆ แต่หากใช้วิธีสังเกตและสรุปเป็นสูตร ซึ่งแทนค่าก็จบ ดังนี้ครับ

\frac{n(n+1)}{2}

ซึ่งผมขอปรับรูปโดยเอา n เข้าไปคูณในวงเล็บและแยกพจน์ออกมา จะได้

\frac{1}{2}n^{2}+\frac{1}{2}n

Gauss ไม่ใช่คนแรกที่คิดสมการนี้ได้นะครับ เชื่อว่าสมการนี้คิดกันได้ก่อนหน้า Gauss หลายร้อยปี จนอาจเป็นหลักพันปี “ก็เป็นได้” แต่ Gauss ที่เป็นตำนานก็เพราะคิดได้ตอนอายุ 9 ขวบและคิดสดด้วย เราจะไม่หยุดที่ Gauss ตรงนี้ ไปกันต่อครับ ทำให้มันซับซ้อนขึ้น ผมขอแปลงอนุกรมนี้เป็นอนุกรมกำลังดังนี้ครับ

1^{1}+2^{1}+3^{1}+ \cdots +n^{1}

ผลลัพธ์ไม่เปลี่ยนใช่ไหมครับ เพราะอะไรที่ยกกำลัง 1 จะได้ค่าเดิม Bernoulli เลยนิยามฟังก์ชัน S ดังนี้ครับ

S(k) = \sum_{i=1}^{n}i^{k}

พอเข้าใจนะครับ

S(0)=1^{0}+2^{0}+3^{0}+\cdots+n^{0}=1+1+1+\cdots+1=n

 S(1)=1^{1}+2^{1}+3^{1}+\cdots+n^{1}=1+2+3+\cdots+n=\frac{1}{2}n^{2}+\frac{1}{2}n

S(2)=1^{2}+2^{2}+3^{2}+\cdots+n^{2}=1+4+9+\cdots+n^{2}=\frac{1}{3}n^{3}+\frac{1}{2}n^{2}+\frac{1}{6}n

อย่าถามผมนะครับว่าทำไม S(2) ถึงยุบเป็นสูตรนี้ได้ จำได้มันเป็นข้อสอบตอนเอ็น ลองกลับไปทบทวนดูครับ Bernoulli ทดลองคำนวณไปจนถึง S(10) ครับ เหนื่อยครับ ผมคงไม่ทำเอง ผมขอใช้ตัวช่วย เรียกพี่เสกสิบสี่อีกครั้งมาช่วย เขียน online จาก www.sagemath.org เลยครับ เป็นภาษา Python

จะได้ผลลัพธ์ดังนี้ครับ

งานหลักของนักคณิตศาสตร์เลยครับ พยายามมองหารูปแบบที่ซ้ำและนำมาสร้างเป็นสูตรและพิสูจน์ความถูกต้อง ว่าแต่ว่าท่านมองเห็นรูปแบบซ้ำๆ ไหมครับ ดูที่พจน์ซ้ายสุดเลยครับ ถ้าเป็น S(1) มันจะมีสัมประสิทธิ์ 1/2 ถ้าเป็น S(2) มันจะเป็น 1/3 เช่นนี้ไปเรื่อยๆ ดังนั้นสัมประสิทธิ์ของ S(m) จะมีค่า  1 / (m+1) นั่นเอง Bernoulli จึงแยก เอา 1 / (m+1) ออกมาข้างหน้า เขียนเป็น Sage ได้ดังนี้ครับ

จะได้

เมื่อเราแยกสัมประสิทธิ์แรกออกมา จะทำให้พจน์แรกมีสัมประสิทธิ์เป็น 1 เสมอ ส่วนตัวต่อไปก็จะเปลี่ยนไปหมด จับรูปแบบไม่ได้แล้ว ถ้าเป็นผมก็จบกันที่ขั้นนี้ แต่ Bernoulli ไม่ครับ อึดตายยาก ยังไปได้ต่อ Bernoulli เป็นจ้าวแห่ง Binomial อยู่แล้ว ก็เลยจะเรียกใช้ Binomial มาช่วย แต่ก่อนที่จะไปกันต่อขอเวลานอกทบทวน binomial เล็กน้อยครับ binomial มีนิยามดังนี้ครับ

\binom{n}{k}=\frac{n!}{k!(n-k)!}

หรือที่เราเรียกตอนเด็กๆ ว่าการจัดหมู่นั่นเอง จำได้ไหมครับ ให้หาจำนวนวิธีที่จัดคนสามคนจาก 8 คน เพื่อไปดูหนัง ถามว่ามีกี่วิธี อะไรทำนองนี้ เราใช้สูตรนี้ครับในการแก้โจทย์

ย้อนกลับเรื่องของเราต่อครับ Bernoulli เชื่อว่าสัมประสิทธิ์ทุกตัวในวงเล็บนี้มีส่วนประกอบของ binomial คูณอยู่ทั้งสิ้น จึงนำเอา binomial ไปหารออกเพื่อตัดองค์ประกอบของ binomial ทิ้งไป เราจะได้องค์ประกอบตัวที่เหลือที่ซ่อนอยู่ แต่ binomial นั้นแปรผันไปตามแต่ละพจน์ครับ ตัวหารจะอยู่ในรูปของ \binom{m+1}{k} โดยที่ m ก็มาจาก S(m) ส่วน k ก็ได้มาจาก m + 1 – เลขชี้กำลังเช่น   ใน S(7) มีพจน์หนึ่งคือ  -7/3*n^4   หมายความว่าเรา ต้องหาร -7/3 ด้วย  \binom{m+1}{m+1-4}  เป็นต้น ให้ทำอย่างนี้กับทุกพจน์ เพื่อกำจัดองค์ประกอบ Binomial ออกจากสัมประสิทธิ์ทุกตัวให้หมด  เรามาลองดูกันครับ เมื่อทำแล้วจะได้ผลลัพธ์เป็นอย่างไร

ได้ผลลัพธ์ดังนี้ครับ

อึ้งไหมครับ จากตัวเลขที่ดูมั่วๆ ในแต่ละพจน์ พอเราถอดเอา Binomial ออกไปกลายเป็นลำดับชุดหนึ่งที่เหมือนกันในทุก S มันน่าจะเป็นตัวเลขชุดลำดับที่พระเจ้าแอบซ่อนเอาไว้ แล้วมนุษย์เดินดินมาค้นพบเจอในที่สุด “ก็เป็นได้” ผมขอถอดเลขลำดับชุดนี้ออกมาเพื่อให้เห็นชัดๆ ขอพิจารณาที่ S(10) ก็แล้วกัน เพราะยาวที่สุด ผมนิยาม B_0 เป็นค่าสัมประสิทธิ์ของพจน์ซ้ายสุดที่มีเลขชี้กำลังที่ m+1 ซึ่งประประสิทธิ์นี้คือ 1  ดังนั้น  B_1 มีค่า 1/2 ,   B_2 มีค่า 1/6 ส่วน  B_3 มีค่าเป็น 0 ครับ เพราะเลขชี้กำลังที่ 8 ไม่มี  B_4 มีค่า -1/30  และ  B_5 เป็น 0 ทำเช่นนี้ไปเรื่อยๆ จึงสรุปมาเป็นตารางได้ดังนี้ครับ

n 0 1 2 3 4 5 6 7 8 9 10
B_{n} 1 \frac{1}{2} \frac{1}{6} 0 \frac{-1}{30} 0 \frac{1}{42} 0 \frac{-1}{30} 0 \frac{5}{66}

ไม่ว่าจะทำกับ S ใดๆ ตัวเลขลำดับที่ได้ก็จะเป็นตามนี้เหมือนกันหมด S ที่มีค่า m ยิ่งมาก ยิ่งจะได้ค่าในตารางมากขึ้น ตารางนี้หละครับคือตารางเป้าหมายของเรา ที่เรียกว่า Bernoulli Number นั่นเอง สังเกตนะครับ B ที่เป็นเลขคี่ที่ไม่ใช่ 1 มีค่าเป็น 0 เสมอ ใน Note G ของ Ada ก็แสดงอัลกอริทึมในการหาค่า B_n โดยที่ n เป็นค่าใดๆ

Bernoulli Number ใช้ทำอะไร

ถ้าเราต้องการคำนวณ

S(m, n) = \sum_{i=1}^{n}k^{m}=1^{m}+2^{m}+3^{m}+\cdots+n^{m}

แน่นอนครับ ถ้า n เป็น 1000  ก็ต้องยกกำลังกัน 1000 รอบ แล้วบวกกันอีก 1000 ครั้ง ดังนั้นจึงมีการสร้างสูตรคำนวณขึ้นเพื่อทำให้คำนวณได้อย่างรวดเร็ว แต่การสร้างสูตรนั้นมีความซับซ้อน จากข้างต้น Bernoulli นำเอาสูตรของ S ต่างๆ มาทำการวิเคราะห์  ค้นพบมาว่าในแต่ละพจน์ที่เป็นผลลัพธ์นั้น เกิดจากการคูณของ Binomial กับค่าสวรรค์สร้าง ซึ่งเรารู้จักกันในยุคปัจจุบันว่า  Bernoulli Number เราจึงสามารถสร้างสูตรในการคำนวณได้โดยง่าย ดังนี้

S(m, n) = \frac{1}{m+1}\sum_{k=0}^{m}B_(k)\binom{m+1}{k}\tfrac{n}{m+1-k}

ดังนั้นเราจึงสามารถหาผลบวกของอนุกรมกำลังได้โดยไม่ต้องสร้างสูตรก่อน และจำนวนพจน์ที่เอามาบวกกันนั้นขึ้นอยู่กับ m ถ้ายกกำลัง 10 ก็จะกระทำเพียงแค่ 10 เทอมเท่านั้น ลดงานลงไปได้มากมาย

ตามประวัติศาสตร์แล้ว Bernoulli ไม่ได้เป็นคนค้นพบชุดเลขลำดับมหัศจรรย์ชุดนี้เป็นคนแรกหรอกครับ มีมาก่อนหน้านั้นแล้ว ที่น่าทึ่งที่ตอนที่ Bernoulli คิดค้นอยู่นั้น ชาวญี่ปุ่นคนหนึ่งก็คิดได้เช่นกันในเวลาไล่เลี่ยกัน ในคณิตศาสตร์นี้มีความบังเอิญเกิดขึ้นบ่อย Calculus ก็ใช่ จะตีกันตายไปข้างหนึ่ง แม้ว่า Bernoulli จะไม่ใช่เป็นคนแรกที่ค้นพบก็ตาม แต่ก็เป็นผู้ที่เรียบเรียงเป็นระบบกว่าทุกคนก่อนหน้า โลกจึงให้เกียรติตั้งชื่อชุดตัวเลขลำดับชุดนี้ว่า Bernoulli Number

ก็เลยลองมาเขียนเป็นโปรแกรมกัน

Bernoulli บันทึกเอาไว้ว่า ขอเวลาผมไม่เกินเจ็ดนาที ผมสามารถหา S(10, 1000) ได้โดยใช้ลำดับข้างต้นมาช่วย (ผมแปลงเนื้อหาที่ Bernoulli บันทึก เพื่อให้สอดคล้องกับบริบทที่ผมเขียน) เรามาลองดูคำตอบกันก่อนครับ

อันนี้ใช้ Sage หาตรงๆ เลยครับ คอมพิวเตอร์ทำงานเร็วอยู่แล้ว ได้ผลลัพธ์ดังนี้ครับ

Bernoulli ก็บันทึกค่านี้ครับ แต่เข้าไม่ได้บวก 1,000 พจน์ เขาทำแค่ 10 พจน์เท่านั้น โดยใช้อนุกรม Bernoulli ที่เขาคิดค้นมาช่วย ต้องเข้าใจนะครับว่าสมัยนั้นไม่มีไฟฟ้า เครื่องคิดเลขย่อมต้องไม่มี คำนวณโดยใช้กระดาษเท่านั้นนะครับ การหาค่าอนุกรมกำลังลำดับ 10 ถึง 1000 ค่าใช้เวลาเพียงแค่ 7 นาทีโดยใช้การคำนวณมือ นี่ถือว่าเป็นก้าวกระโดดในวงการคณิตศาสตร์เลยครับ  เรามาลองทำเป็น Python ดังนี้

ซึ่งจะเห็นในการวนรอบ จำนวนรอบตาม m=10 ไม่ใช่ n=1000  โปรแกรมที่เขียนนี้เป็นโปรแกรมภาษา Pyhon เต็มรูปครับ ไม่สามารถทำงานบน Sage Worksheet ได้ ถ้าต้องการทดสอบการทำงานของโปรแกรม ต้องไปสร้าง IPython Notebook ที่อยู่ใน Project ของ Sagemath เดียวกัน จะได้ผลลัพธ์เช่นเดียวกับข้างต้นครับ

แถมท้าย (20-dec-14)

บทนี้ผมครึ้มใจอ้างชื่ออาจารย์ใหญ่ทุกสถาบันอย่าง Euler ผมก็ขอใช้หัวข้อนี้นอกเรื่องหน่อย ที่จริงก็ไม่มีอะไรมากหรอกครับ หาเรื่องฝึกใช้ sagemath ไปอย่างนั้นเอง กราฟ Hello, World ข้างบนมีที่มานะครับ เป็นผลงานของอาจารย์ใหญ่ Euler นั่นเอง เพื่อไขข้อข้องใจที่มีมาหลายพันปีแล้วว่า จำนวนเฉพาะมีจุดสิ้นสุดไหม เมื่อค่าตัวเลขมากขึ้นเรื่อยๆ ยังจะมีตัวเลขจำนวนเฉพาะอยู่หรือไม่ นี่เป็นโจทย์พื้นฐานของสาขาย่อยคณิตศาสตร์ที่ชื่อว่าทฤษฎีจำนวน (number theory) ดังจะมีรายละเอียดอยู่บ้างในบทความหน้าครับ

เพื่อตอบคำถามข้างบน Euler จึงหกคะเมนตีลังกาคิด หาผลรวมสะสมของอนุกรม 1/p เสียเลย ได้มาเป็นกราฟข้างบน ถ้ากราฟข้างบนยังเพิ่มค่าขึ้นเรื่อยๆ ไม่เข้าใกล้จุดใดจุดหนึ่งแสดงว่า ยังคงมีค่าจำนวนเฉพาะเพิ่มขึ้นมาเรื่อยๆ แม้ว่าจะหายากขึ้นตามลำดับก็ตาม แต่กราฟตัวนี้บอกอะไรมากไม่ได้นะครับ เพราะเราไม่สามารถวาดกราฟนี้ยาวไปถึงอนันต์เพื่อพิสูจน์ได้ วิธีการที่อาจารย์ใหญ่ใช้ก็คือ การหาสูตรคณิตศาสตร์ที่เทียบเคียงได้กับกราฟนี้ ทับเส้นกันเลยยิ่งดี จากนั้นก็เอาสูตร์นั้นไปหา limit ถ้าได้ limit เป็น infinity ก็ฟินเลยครับ และแน่นอนครับอาจารย์ใหญ่หาสูตรดังว่าได้ครับ

ในเวลาต่อมา Meissel-Mertens ก็นำสูตรของอาจารย์ใหญ่ไปปรับเพื่อให้ได้ใกล้เคียงขึ้นกลายเป็นสูตรง่ายๆ เลยครับ นั่นคือ

ln(ln(n))

เรามาลองทดสอบหา limit โดย sagemath กันเลยครับ

ลองเอาไปรันดูครับ ไม่ต้องสงสัยเลยว่าคำตอบที่ได้ก็คือ Infinity นั่นเอง สรุปได้ว่าค่าจำนวนเฉพาะมีค่าไม่รู้จบครับ ที่เหลือก็คือพิสูจน์ให้ได้ว่าสูตรที่ให้มานั้นเป็นตัวแทนของกราฟได้ ก็ต้องเอาไปพล็อตดูครับ

จะได้ผลลัพธ์ดังนี้ครับ

meissel-mertens

เส้นสีแดงคือเส้นที่ได้จาก ln(ln(x)) จะเห็นได้ว่าเป็นไปทำนองเดียวกันผลรวมสะสมของส่วนกลับค่าจำนวนเฉพาะ แต่การดูด้วยตาเปล่าก็เห็นว่ามันขนานไปเรื่อยๆ แต่พอไหมที่บอกว่ามันเป็นตัวแทนของกันและกันได้ เมื่อ “หิมะขาวพิสุทธิกว่าดอกเหมยสามหุน แต่หิมะขาดความกรุ่นของดอกเหมย” ความขาวโอโม่ในนวนิยายจีนกำลังภายในยังวัดเทียบเป็นหุนๆ ได้ แล้วทำไมระยะห่างถึงจะวัดไม่ได้หละครับ ก็แค่เอาค่าจากกราฟทั้งสองมาหักลบกัน ก็แค่นั้น ผลปรากฏว่าได้ระยะห่าง M ที่คงที่ครับ ขนานกันไปเรื่อยๆ ที่ช่วงห่างคงที่ นั่นคือประมาณ  0.2614971218478…   ค่า M นี้เองเรียกว่า Meissel-Mertens constant เป็นอันจบการพิสูจน์ว่าค่าจำนวนเฉพาะนั้นมีค่าไม่สิ้นสุดนั่นเอง

ผมขอหมุนเวลาเดินหน้ากลับมาถึงปี 2011 ไปดูมหกรรมการประมูลสิทธิบัตรที่ยิ่งใหญ่ที่สุดในโลกทั้งด้านจำนวนสิทธิบัตรที่มากถึงกว่า 6,000 ใบในคราวเดียว และมูลค่าเงินสุดท้ายที่ประมูลได้ถึง $4,500 ล้าน US dollars อลังการงานประมูลจริงๆ  สิ่งที่ประมูลก็คือเทคโนโลยีของ Nortel แคนาดาที่เพิ่งล้มละลาย บริษัทนี้ไม่ธรรมดานะครับ พัฒนาจากโรงงานของ Alexander Graham Bell ตั้งแต่ยุคกำเนิดโทรศัพท์กันเลยทีเดียว จึงไม่น่าแปลกใจครับว่ามีสิทธิบัตรมากมาย โดยเฉพาะอย่างยิ่ง โทรศัพท์ไร้สาย 4G และ internet ใครได้ไปก็เป็นเสือติดปีกกันไปเลย

บริษัทที่เข้าร่วมประมูลนั้นก็แน่นอนครับ ใหญ่คับโลกกันทั้งนั้น แต่ด้วยความยิ่งใหญ่ของตัวสิทธิบัตรเอง บริษัทต่างๆ ที่ว่าใหญ่ ก็ต้องรวมกลุ่มกันเพื่อประมูล บินเดี่ยวก็มีหลายเจ้า แต่ก็แพ้ไปตั้งแต่รอบแรกครับ กลุ่มที่น่าจับตามองก็มี Rockstar ที่ประกอบด้วย Apple, Microsoft, Sony, Ericsson, RIM และ EMC  ดวลกับ Ranger ที่ประกอบด้วย Google และ Intel ผลสุดท้ายกลุ่ม Rockstar ก็ชนะไปครับ ด้วยมูลค่า $4,500 ล้านดังที่กล่าวมา จึงไม่น่าแปลกใจ ว่ากลุ่มนี้ถึงกอบโกยเงินจากการผลิตตัวเครื่องโทรศัพท์ได้อย่างเป็นกอบเป็นกำในยุคปัจจุบัน

ผมไม่เน้นที่ผู้ชนะ ผมสนใจผู้แพ้มากกว่า ตลอดเวลาที่ขับเคี่ยวประมูลกัน 4 วันนั้น Google เสนอประมูล 3 ครั้ง เป็นตัวเลขที่ไม่ใช่ตัวเลขกลมๆ ทั้งสามค่า ซึ่งวิจารณ์กันขรม บ้างก็ว่า Google เล่นเกินไปเลยแพ้ บ้างก็ว่าเท่ดี ตัวเลขประมูลทั้งสามเรียงลำดับดังนี้

  • $1,902,160,540
  • $2,614,972,128
  • $3,141,592,653

ตัวเลขตัวแรกเรียกว่า Brun’s constant มีค่าประมาณ 1.902160583104 ได้มาจากผลรวมของส่วนกลับค่าจำนวนเฉพาะที่ติดกัน ตัวเลขนี้มีตำนานเหมือนกันนะครับ เป็นตัวเลขที่ Professor Thomas Nicely ใช้เครื่องคอมพิวเตอร์เพื่อคำนวณค่านี้ออกมา ปรากฏว่าเขียนโปรแกรมยังไงก็ไม่ถูกซะที หลังจากทดสอบเปรียบเทียบกับเครื่องอื่นทำให้รู้ว่า math-coprocessor ของ CPU ตัวนั้นทำงานผิดพลาดในระดับวงจรอิเล็คทรอนิกส์ ซึ่งเรารู้จักกันดีในยุคปัจจุบันว่า Pentium FDIV bug นั่นเอง ทำเอา Intel เสียรูปมวยมากในเวลานั้น  โชคลางมีจริงนะครับ ฝรั่งไม่เชื่อ ก็เล่นประมูลร่วมกับ Intel แต่ดันไปใช้เลขที่เป็นอัปมงคลสำหรับ Intel แบบนี้ไม่แพ้ก็ไม่รู้จะว่ายังไงแล้วครับ

ผมเฉลยเลขตัวแรกแล้ว ก็ขอฝากเลขอีกสองตัวให้ลองไปขบคิดหาที่มาดูครับ

สรุป

ในบทความนี้ เราได้เรียนรู้ถึงการกำเนิดและการประยุกต์ใช้งานของ Bernoulli Number ตลอดจน Ada นำเอาไปใช้สร้างเป็น “โปรแกรมแรกของโลก” และทำให้เธอกลายเป็น “โปรแกรมเมอร์คนแรกของโลก” เมื่อเราเข้าใจถึงนิยามของ Bernoulli Number ดีแล้ว ในบทต่อไปเราจะมาสร้างอัลกอริทึมในการหาค่า Bernoulli Number ในระดับสูงๆ ที่เกินกว่า 10 กัน เราจะได้เห็นถึงการรีดกำลังของเครื่องคอมพิวเตอร์มาใช้อย่างเต็มสูบ

จนกว่าจะถึงวันนั้น

[Total: 6    Average: 3.8/5]

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *