ผู้ใช้:SippeCP/กระบะทราย
 | บทความนี้อาจต้องการตรวจสอบต้นฉบับ ในด้านไวยากรณ์ รูปแบบการเขียน การเรียบเรียง คุณภาพ หรือการสะกด คุณสามารถช่วยพัฒนาบทความได้ |
 | ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ขั้นตอนวิธีของ Schönhage–Strassen คือ ขั้นตอนวิธีในการคูณเลขจำนวนเต็มขนาดใหญ่ ขั้นตอนวิธีนี้ได้รับการพัฒนามาจาก อาร์โนลด์ ชุนฮาเก้ และ วอล์คเกอร์ สตราเซน ในปี ค.ศ. 1971 [1] โดยนำความสัมพันธ์เวียนเกิด มาใช้กับการแปลงฟูรีเยแบบเร็ว (Fast Fourier transforms) ใน ริง (Ring) ที่มีจำนวนสมาชิกเป็น 22n + 1 ตัว ซึ่งเป็นสมาชิกพิเศษประเภทหนึ่งของ ทฤษฎีการเปลี่ยนรูปของตัวเลข (number theoretic transform)
ขั้นตอนวิธีของ Schönhage–Strassen เป็นขั้นตอนวิธีการคูณที่เร็วที่สุดเท่าที่เคยค้นพบมาตั้งแต่ปี ค.ศ. 1971 จนถึง ปี ค.ศ. 2007 ก่อนที่จะมีวิธีใหม่เข้ามาแทนที่ซึ่งก็คือ ขั้นตอนวิธีของ Fürer (Fürer's algorithm) ที่ได้รับการประกาศไว้ว่าเป็นวิธีที่มีความซับซ้อนเชิงเส้นกำกับ (asymptotic complexity) น้อยกว่า[2] แต่อย่างไรก็ตามในปัจจุบัน ขั้นตอนวิธีของ Fürer ก็สามารถใช้งานได้เฉพาะกับ ค่าที่มีจำนวนมหาศาลเท่านั้น และไม่นิยมใช้กับการใช้งานในชีวิตปกติ
รายละเอียด แก้
การอธิบายในส่วนนี้ จะกล่าวถึงรายละเอียดของ ขั้นตอนวิธีของ Schönhage–Strassen ว่ามีวิธีการอย่างไร โดยมีพื้นฐานการทำงานขั้นต้นจาก หนังสือของ แครนเดล และ โพเมอร์แรนซ์ เรื่อง “จำนวนเฉพาะ : ทัศนคติเกี่ยวกับการคำนวณทางคอมพิวเตอร์” [3] รวมไปถึงข้อมูลจากหนังสือ “ศิลปะในการเขียนโปรแกรมคอมพิวเตอร์” [4] โดย โดนัลด์ คนูธ (Donald Knuth)
สังวัตนาการ (Convolutions) แก้
สมมติว่าเราต้องการจะคูณเลขจำนวน 2 ตัว เช่น 123 และ 456 โดยใช้การคูณแบบยาว ที่จำนวนที่นำมาคูณกันนั้นมีฐานเป็น “B” โดยการคูณนี้จะไม่มีการทดเลข ซึ่งผลลัพธ์ที่ได้มีลักษณะดังนี้
| 1 | 2 | 3 | ||
| × | 4 | 5 | 6 | |
| 6 | 12 | 18 | ||
| 5 | 10 | 15 | ||
| 4 | 8 | 12 | ||
| 4 | 13 | 28 | 27 | 18 |
ลำดับที่ได้จากการคูณนี้ (4,13,28,27,18) เรียกว่า acyclic หรือ linear convolution ซึ่งเกิดมาจาก ลำดับพื้นฐาน 2 ตัวคือ (1,2,3)และ(4,5,6) เมื่อเรามีลำดับของ acyclic convolution ครบทั้ง 2 ตัวแล้ว การคำนวณก็จะทำได้อย่างง่ายดาย โดยการจัดการกับเลขที่มีตัวทด จากตัวอย่าง หลักขวามือสุด เป็นเลข 18 ให้เก็บหลักขวามือ ซึ่งก็คือเลข 8 เอาไว้ จากนั้น นำเลขหลักซ้ายมือซึ่งก็คือเลข 1 ไปบวกกับ เลขในหลักขวามือของเลขที่อยู่ด้านซ้ายมือถัดไป ในที่นี้คือเลข 7 จาก เลข 27 ที่อยู่ในลำดับ acyclic ทำเช่นนี้ไปเรื่อย ๆ จะได้ผลลัพธ์สุดท้ายออกมาเป็น 56088 นอกจากนี้ยังมี convolution ชนิดอื่น ๆ อีก 2 ชนิดที่อาจจะมีประโยชน์ในการคำนวณ ชนิดแรก สมมติว่าลำดับของข้อมูลขาเข้ามีจำนวน “n” ตัว (ในที่นี้ลำดับมีจำนวน 3 ตัว) ดังนั้น acyclic convolution จะมีสมาชิกเป็นจำนวน n+n−1 ตัว ถ้าหากว่าเรานำเลขที่อยู่ขวามือสุด n ตัว มาบวกเข้ากับเลขซ้ายมือสุดจำนวน n−1 ตัว ผลที่ได้ออกมาจะเป็น cyclic convolution:
| 28 | 27 | 18 | ||
| + | 4 | 13 | ||
| 28 | 31 | 31 | ||
ถ้าหากเรานำค่าจาก cyclic convolution มาทำการคำนวณแบบการจัดการกับเลขที่มีตัวทด จะได้ผลลัพธ์ที่เกิดจาก การนำเอาคำตอบของการคูณเลข 2 จำนวนในตอนแรกมาทำการมอดดูโลด้วย Bn − 1 จากตัวอย่างจะได้ 103 − 1 = 999 ดังนั้นจากลำดับ (28,31,31) จะได้ค่าออกมาเป็น 3141 ซึ่ง 3141 ≡ 56088 (mod 999) ในทางกลับกัน สำหรับชนิดที่สอง เราจะนำเลขที่อยู่ขวามือสุด n ตัว มาลบ แทนที่จะบวก กับเลขซ้ายมือสุดจำนวน n−1 ตัว ผลที่ได้ออกมาเราจะเรียกว่า negacyclic convolution:
| 28 | 27 | 18 | ||
| − | 4 | 13 | ||
| 28 | 23 | 5 | ||
ถ้าหากเรานำค่าจาก negacyclic convolution มาทำการคำนวณแบบการจัดการกับเลขที่มีตัวทด จะได้ผลลัพธ์ที่เกิดจาก การนำเอาคำตอบของการคูณเลข 2 จำนวนในตอนแรกมาทำการมอดดูโลด้วย Bn + 1 จากตัวอย่างจะได้ 103 + 1 = 1001 ดังนั้นจากลำดับ (28,23,5) จะได้ค่าออกมาเป็น 3035 ซึ่ง 3035 ≡ 56088 (mod 1001) ลำดับของ negacyclic convolution สามารถเป็นเลขจำนวนลบได้ เพราะจำนวนลบนี้สามารถกำจัดทิ้งได้ เมื่อทำการบวกหลักตัวทด
ทฤษฎีบทสังวัตนาการ (Convolution theorem) แก้
ทฤษฎีบทสังวัตนาการ (en:convolution theorem) มีลักษณะเหมือนกับวิธีการการคูณทั่วๆไปที่มีการอ้างอิงถึงทฤษฏีการแปลงฟูรีเยอย่างเร็ว(multiplication methods based on the Fast Fourier transform) ซึ่งขั้นตอนวิธีของ Schonhage-Strassen จะมีหลักการเบื้องต้นที่อ้างอิงถึงทฤษฎีบทสังวัตนาการนี้ ทฤษฎีบทสังวัตนาการ (convolution theorem) มีส่วนช่วยอย่างมากในการคำนวณลำดับ cyclic convolution 2 ลำดับใดๆ โดยมีการกล่าวไว้ว่า :
สำหรับ cyclic convolution ของเวกเตอร์ใดๆ 2 ตัว เกิดได้จาก การแปลงฟูรีเยไม่ต่อเนื่อง( discrete Fourier transform: DFT)โดยผลคูณของสมาชิกในเวกเตอร์เกิดจากการคูณกันตัวต่อตัว จากนั้นจึงทำการ inverse discrete Fourier transform (IDFT) ต่อ
หรือเขียนออกมาในรูปของสัญลักษณ์ได้ดังนี้ :
- CyclicConvolution(X, Y) = IDFT(DFT(X) · DFT(Y))
หากทำการคำนวณเลข DFT และ IDFT โดยการใช้การแปลงฟูรีเยแบบเร็ว ทำให้เกิดขั้นตอนวิธีการคูณที่ใช้ความสัมพันธ์เวียนเกิดในการคูณสมาชิกเวกเตอร์ที่ถูกแปลงแล้ว DFT(X) and DFT(Y) โดลผลลัพธ์ที่ได้ออกมานั้นจะมีประสิทธิภาพในการคำนวณ cyclic convolution เป็นอย่างมาก
สำหรับขั้นตอนวิธีการนี้ มีประโยชน์ในการคำนวณ negacyclic convolution ด้วยเช่นกัน โดยการเปลี่ยนแปลงทฤษฎีบทสังวัตนาการเพียงเล็กน้อย สมมติว่ามีเวกเตอร์ X และ Y มีความยาว n และค่า a คือค่าฐานที่เป็นเอกภาพของลำดับ 2n (ซึ่งก็คือ a2n = 1 และจำนวน a ทุกๆตัวที่มีค่าของเลขชี้กำลังน้อยว่า มีค่าไม่เท่ากับ 1 ) ดังนั้นเราจะได้เวกเตอร์ตัวที่ใหม่ที่มีชื่อ A เป็นเวกเตอร์ตัวที่ 3 ที่เรียกกันว่า weight vector
- A = (aj), 0 ≤ j < n
- A−1 = (a−j), 0 ≤ j < n
ซึ่งก็คือ:
- NegacyclicConvolution(X, Y) = A−1 · IDFT(DFT(A · X) · DFT(A · Y))
จะเห็นได้ว่าในการคำนวณ negacyclic convolution นี้มีวิธีการเหมือนกันวิธีก่อนหน้านี้ที่ได้กล่าวมา แต่มีความต่างกันตรงที่วิธีก่อนหน้านั้นคูณด้วย A แต่วิธีนี้คูณด้วย A−1 นั่นเอง
ประสิทธิภาพการทำงาน แก้
ประสิทธิภาพในการทำงานของขั้นตอนวิธี Schonhage-Strassen หากเราพิจารณาจากความซับซ้อนในการกำหนดจำนวนบิต ( bit complexity) จะสามารถเขียนในรูปของ สัญกรณ์โอใหญ่ ได้คือ O(N log N log log N) ในขณะที่พิจารณาจากความซับซ้อนทางด้านการคำนวณทางคณิตศาสตร์ หรือที่เรียกว่า ( arithmetic complexity) จะได้เป็น O(N log N) [5]
อ้างอิง แก้
- ↑ A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
- ↑ Martin Fürer, "Faster integer multiplication", STOC 2007 Proceedings, pp. 57–66.
- ↑ R. Crandall & C. Pomerance. Prime Numbers - A Computational Perspective. Second Edition, Springer, 2005. Section 9.5.6: Schönhage method, pg.459. ISBN 0-387-94777-9
- ↑ Donald E. Knuth, en:The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition), 1997. Addison-Wesley Professional, ISBN 0201896842. Section 4.3.3.C: Discrete Fourier transforms, pg.305.
- ↑ Peter Bürgisser, Michael Clausen and Amin Shokrollahi, Algebraic Complexity Theory, 1997. Springer-Verlag, ISBN 3540605827.