วิธีการที่คล้ายคลึงกันนี้ย้อนกลับไปหลายพันปี อย่างน้อยก็สำหรับชาวสุเมเรียนและชาวอียิปต์โบราณแต่นี่เป็นวิธีที่ดีที่สุดในการคูณเลขสองตัวเข้าด้วยกันจริงหรือ? ในการคูณแบบยาว เราต้องคูณทุก ๆ หลักของตัวเลขแรกด้วยทุก ๆ หลักของตัวเลขที่สอง ถ้าตัวเลขสองตัวแต่ละตัวมี ตัวเลข Nหลัก นั่นคือ การคูณ N 2 (หรือN x N ) ในตัวอย่างข้างต้นNคือ 3 และเราต้องคูณ 3 2 = 9 ประมาณปี 1956 Andrey Kolmogorovนักคณิตศาสตร์ชื่อดังชาวโซเวียตได้
คาดคะเนว่านี่เป็นวิธีที่ดีที่สุดในการคูณเลขสองตัวเข้าด้วยกัน
กล่าวอีกนัยหนึ่ง ไม่ว่าคุณจะจัดการ คำนวณอย่างไร ปริมาณงานที่คุณต้องทำจะเป็นสัดส่วนกับN 2 เป็นอย่างน้อย ตัวเลขสองเท่าหมายถึงงานมากขึ้นสี่ เท่า Kolmogorov รู้สึกว่าถ้าทางลัดเป็นไปได้ แน่นอนว่ามันจะถูกค้นพบแล้ว ท้ายที่สุดผู้คนก็เพิ่มจำนวนขึ้นเป็นพัน ๆ ปี นี่เป็นตัวอย่างที่ยอดเยี่ยมของการเข้าใจผิดเชิงตรรกะที่เรียกว่า “การโต้แย้งจากความไม่รู้”
ในปี 1960 Anatoly Karatsuba นักเรียนคณิตศาสตร์วัย 23 ปีในรัสเซีย ได้ค้นพบเคล็ด ลับเกี่ยว กับพีชคณิตลับๆ ล่อๆที่ช่วยลดจำนวนการคูณที่จำเป็น
ตัวอย่างเช่น หากต้องการคูณตัวเลขสี่หลัก แทนที่จะต้องใช้การคูณ 4 2 = 16 วิธีของ Karatsuba จะเหลือเพียงเก้าเท่านั้น เมื่อใช้วิธีการของเขา ตัวเลขสองเท่าหมายถึงงานมาก เพียง สาม เท่า
สิ่งนี้ทำให้เกิดข้อได้เปรียบที่น่าประทับใจเมื่อจำนวนเพิ่มขึ้น สำหรับตัวเลขที่มีหลักพัน วิธีของคาราสึบะต้องการการคูณน้อยกว่าการคูณแบบยาวประมาณ 17 เท่า
แต่ทำไมบนโลกนี้ใครๆ ก็อยากคูณจำนวนมหาศาลเข้าด้วยกัน? ในความเป็นจริงมีแอปพลิเคชันจำนวนมาก หนึ่งในสิ่งที่มองเห็นได้ชัดเจนและมีความสำคัญทางเศรษฐกิจที่สุดคือการเข้ารหัส
ทุกครั้งที่คุณมีส่วนร่วมในการสื่อสารที่เข้ารหัสบนอินเทอร์เน็ต ตัวอย่างเช่น เข้าถึงเว็บไซต์ธนาคารของคุณหรือทำการค้นหาเว็บ อุปกรณ์ของคุณจะทำการคูณจำนวนนับไม่ถ้วนที่เกี่ยวข้องกับตัวเลขที่มีหลายร้อยหรือหลายพันหลัก
เป็นไปได้มากว่าอุปกรณ์ของคุณจะใช้เคล็ดลับของ Karatsuba สำหรับเลขคณิตนี้ ทั้งหมดนี้เป็นส่วนหนึ่งของระบบนิเวศซอฟต์แวร์ที่น่าทึ่งที่ช่วยให้หน้าเว็บของเราโหลดเร็วที่สุดเท่าที่จะเป็นไปได้
สำหรับการใช้งานที่ลึกลับกว่านั้น นักคณิตศาสตร์ต้องจัดการกับตัวเลขที่มากกว่านั้น เช่น หลักล้าน พันล้าน หรือแม้แต่ล้านล้านหลัก ด้วยจำนวนมหาศาลเช่นนี้ แม้แต่อัลกอริธึมของคาราสึบะยังช้าเกินไป
ก้าวหน้าที่แท้จริงเกิดขึ้นในปี 1971 ด้วยผลงานของนักคณิตศาสตร์
ชาวเยอรมัน Arnold Schönhage และ Volker Strassen พวกเขาอธิบายวิธีใช้การแปลงฟูเรียร์เร็ว ( FFT ) ที่เผยแพร่ล่าสุดเพื่อคูณจำนวนมหาศาลอย่างมีประสิทธิภาพ วิธีการของพวกเขาถูกใช้เป็นประจำโดยนักคณิตศาสตร์ในทุกวันนี้เพื่อจัดการกับตัวเลขหลายพันล้านหลัก
FFT เป็นหนึ่งในอัลกอริทึมที่สำคัญที่สุดของศตวรรษที่ 20 แอปพลิเคชั่นหนึ่งที่คุ้นเคยในชีวิตประจำวันคือเสียงดิจิทัล เมื่อใดก็ตามที่คุณฟัง MP3 บริการสตรีมเพลงหรือวิทยุดิจิทัล FFT จะจัดการการถอดรหัสเสียงเบื้องหลัง
วิธีที่เร็วยิ่งขึ้น?
ในรายงานปี 1971 ของพวกเขา Schönhage และ Strassen ได้ทำการคาดเดาที่น่าทึ่งเช่นกัน เพื่ออธิบาย ฉันจะต้องเรียนรู้ทางเทคนิคสักเล็กน้อย
ครึ่งแรกของการคาดเดาของพวกเขาคือควรคูณตัวเลขN หลักโดยใช้การดำเนินการพื้นฐานจำนวนหนึ่งที่เป็นสัดส่วนกับ N log ( N ) มากที่สุด (นั่นคือNคูณลอการิทึมธรรมชาติของN )
อัลกอริธึมของพวกเขาเองยังไปไม่ถึงเป้าหมายนี้เสียทีเดียว พวกเขาช้าเกินไปโดยปัจจัยของล็อก (ล็อกN ) (ลอการิทึมของลอการิทึมของN ) อย่างไรก็ตาม สัญชาตญาณทำให้พวกเขาสงสัยว่าพวกเขาขาดอะไรไป และN log ( N ) น่าจะเป็นไปได้
ในช่วงหลายทศวรรษตั้งแต่ปี 1971 นักวิจัยไม่กี่คนได้ค้นพบการปรับปรุงอัลกอริทึมของ Schönhage และ Strassen โดยเฉพาะอย่างยิ่งอัลกอริทึมที่ออกแบบโดย Martin Fürer ในปี 2550 ใกล้เคียงกับN log ( N ) ที่เข้าใจยากอย่างน่าปวดหัว
ส่วนที่สอง (และยากกว่านั้นมาก) ของการคาดเดาคือN log ( N ) ควรเป็นขีดจำกัดความเร็วพื้นฐาน — ซึ่งไม่มีอัลกอริธึมการคูณใดสามารถทำได้ดีกว่านี้
ไม่กี่สัปดาห์ที่ผ่านมาJoris van der Hoevenและฉันได้โพสต์บทความวิจัยที่อธิบายถึงอัลกอริธึมการคูณแบบใหม่ที่ไปถึงN log ( N ) จอกศักดิ์สิทธิ์ ด้วยเหตุนี้จึงเป็นการยุติส่วนที่ “ง่าย” ของการคาดเดา Schönhage–Strassen
บทความนี้ยังไม่ได้รับการตรวจสอบโดยเพื่อน ดังนั้นจึงควรระมัดระวังบางประการ เป็นการปฏิบัติมาตรฐานในวิชาคณิตศาสตร์ในการเผยแพร่ผลการวิจัยก่อนที่จะได้รับการทบทวนโดยผู้รู้
แทนที่จะใช้ FFT แบบหนึ่งมิติ ซึ่งเป็นงานหลักของการแก้ปัญหานี้ตั้งแต่ปี 1971 อัลกอริทึมของเราอาศัยFFT แบบหลายมิติ แกดเจ็ตเหล่านี้ไม่ใช่ของใหม่: รูปแบบภาพ JPEG ที่ใช้กันอย่างแพร่หลายขึ้นอยู่กับ FFT แบบ 2 มิติ และ FFT แบบ 3 มิติมีแอปพลิเคชันมากมายในด้านฟิสิกส์และวิศวกรรม
ในรายงานของเรา เราใช้ FFT กับ 1,729 มิติข้อมูล นี่เป็นเรื่องยากที่จะจินตนาการ แต่ในทางคณิตศาสตร์ไม่มีปัญหามากไปกว่ากรณี 2 มิติ
ตัวเลขเยอะจริงๆ
อัลกอริทึมใหม่นี้ใช้ไม่ได้จริง ๆ ในรูปแบบปัจจุบัน เพราะการพิสูจน์ที่ให้ไว้ในเอกสารของเราใช้ได้กับตัวเลขจำนวนมากที่น่าหัวเราะเท่านั้น แม้ว่าตัวเลขแต่ละหลักจะถูกเขียนบนอะตอมของไฮโดรเจน ก็ไม่มีที่ว่างมากพอในเอกภพที่สังเกตได้เพื่อจดตัวเลขเหล่านั้นลงไป
อ่านเพิ่มเติม: ทำไมเราต้องรู้เกี่ยวกับจำนวนเฉพาะที่มีหลักล้าน?
ในทางกลับกัน เราหวังว่าด้วยการปรับแต่งเพิ่มเติม อัลกอริทึมอาจนำไปใช้ได้จริงสำหรับตัวเลขที่มีตัวเลขเพียงพันล้านหรือล้านล้านหลัก ถ้าเป็นเช่นนั้น มันอาจกลายเป็นเครื่องมือที่ขาดไม่ได้ในคลังแสงของนักคณิตศาสตร์คำนวณ
หากการคาดคะเนเชินฮาเกอ–ชตราสเซินทั้งหมดถูกต้อง จากมุมมองทางทฤษฎี อัลกอริทึมใหม่คือจุดสิ้นสุดของเส้นทาง – เป็นไปไม่ได้ที่จะทำอะไรให้ดีขึ้น
โดยส่วนตัวแล้วฉันจะประหลาดใจมากหากการคาดเดากลายเป็นผิด แต่เราไม่ควรลืมสิ่งที่เกิดขึ้นกับ Kolmogorov คณิตศาสตร์บางครั้งอาจทำให้ประหลาดใจได้
