ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน

ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน (Schönhage–Strassen algorithm) เป็นขั้นตอนวิธีในการคูณเลขจำนวนเต็มขนาดใหญ่ ขั้นตอนวิธีนี้ได้รับการพัฒนามาจาก อาร์น็อลท์ เชินฮาเกอ และ ฟ็อลเคอร์ ชตรัสเซิน ในปี ค.ศ. 1971A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292. โดยนำความสัมพันธ์เวียนเกิด มาใช้กับการแปลงฟูรีเยแบบเร็ว ในริงที่มีจำนวนสมาชิกเป็น 22n + 1 ตัว ซึ่งเป็นสมาชิกพิเศษประเภทหนึ่งของ ทฤษฎีการเปลี่ยนรูปของตัวเลข (number theoretic transform)

ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซินเป็นขั้นตอนวิธีการคูณที่เร็วที่สุดเท่าที่เคยค้นพบมาตั้งแต่ปี ค.ศ. 1971 จนถึง ปี ค.ศ. 2007 ก่อนที่จะมีวิธีใหม่เข้ามาแทนที่ซึ่งก็คือ ขั้นตอนวิธีของฟือเรอร์ (Fürer's algorithm) ที่ได้รับการประกาศไว้ว่าเป็นวิธีที่มีความซับซ้อนเชิงเส้นกำกับ (asymptotic complexity) น้อยกว่าMartin Fürer, "Faster integer multiplication ", STOC 2007 Proceedings, pp. 57–66. แต่อย่างไรก็ตามในปัจจุบัน ขั้นตอนวิธีของ Fürer ก็สามารถใช้งานได้เฉพาะกับ ค่าที่มีจำนวนมหาศาลเท่านั้น และไม่นิยมใช้กับการใช้งานในชีวิตปกติ

 รายละเอียด 
การอธิบายในส่วนนี้ จะกล่าวถึงรายละเอียดของ ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซินว่ามีวิธีการอย่างไร โดยมีพื้นฐานการทำงานขั้นต้นจาก หนังสือของ แครนเดล และ โพเมอร์แรนซ์ เรื่อง “จำนวนเฉพาะ : ทัศนคติเกี่ยวกับการคำนวณทางคอมพิวเตอร์”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. โดย โดนัลด์ คนูธ (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 ทำเช่นนี้ไปเรื่อย ๆ จะได้ผลลัพธ์สุดท้ายออกมาเป็น 5608

นอกจากนี้ยังมี 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) 

ทฤษฎีบทสังวัตนาการ (convolution theorem) มีลักษณะเหมือนกับวิธีการการคูณทั่ว ๆ ไปที่มีการอ้างอิงถึงทฤษฏีการแปลงฟูรีเยอย่างเร็ว(multiplication methods based on the Fast Fourier transform) ซึ่งขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน จะมีหลักการเบื้องต้นที่อ้างอิงถึงทฤษฎีบทสังวัตนาการนี้
ทฤษฎีบทสังวัตนาการ (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<sup>−j</sup>), 0 ≤ j < nซึ่งก็คือ:

NegacyclicConvolution(X, Y) = A−1 · IDFT(DFT(A · X) · DFT(A · Y))

 จะเห็นได้ว่าในการคำนวณ negacyclic convolution นี้มีวิธีการเหมือนกันวิธีก่อนหน้านี้ที่ได้กล่าวมา แต่มีความต่างกันตรงที่วิธีก่อนหน้านั้นคูณด้วย A แต่วิธีนี้คูณด้วย A''−1 นั่นเอง

 ประสิทธิภาพการทำงาน 

ประสิทธิภาพในการทำงานของขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน หากเราพิจารณาจากความซับซ้อนในการกำหนดจำนวนบิต (bit complexity) จะสามารถเขียนในรูปของ สัญกรณ์โอใหญ่ ได้คือ O(N log N log log N) ในขณะที่พิจารณาจากความซับซ้อนทางด้านการคำนวณทางคณิตศาสตร์ หรือที่เรียกว่า (arithmetic complexity) จะได้เป็น O(N log N) Peter Bürgisser, Michael Clausen and Amin Shokrollahi, Algebraic Complexity Theory, 1997. Springer-Verlag, ISBN 3540605827.

 ตัวอย่างการใช้งาน 

ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน ใช้ในการลดรูปการคูณจำนวนเต็มใด ๆ ที่มีจำนวน S บิต ไปเป็นจำนวนการคูณ L ครั้งโดยประมาณใกล้เคียงได้เป็น 4S/L บิตของจำนวนเต็ม เท่านั้นไม่พอขั้นตอนวิธีนี้ได้นำไปประยุกต์ใช้กับทฤษฎีบทดิจิทัล อิเลคทรอนิกส์ โดยเฉพาะเรื่องเสียงดิจิทัล โดย ทฤษฎี Fast Fourier transforms นั้นถือเป็นหัวใจหลักของขั้นตอนวิธีนี้เลยก็ว่าได้ นอกจากนี้ ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซินยังสามารถนำไปใช้จริงใน GNU Multi-Precision LibraryPierrick Gaudry, Alexander Kruppa, and Paul Zimmermann. A GMP-based Implementation of Schönhage–Strassen’s Large Integer Multiplication Algorithm. Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, pp.167–174. หรือที่รู้จักกันในชื่อย่อว่า GMP ซึ่งเป็นซอร์ฟแวร์ทางคณิตศาสตร์ ที่ได้รับการพัฒนาจาก The GNU Project นั่นเอง

 ดูเพิ่มเติม 
 A GMP-based Implementation of Schönhage-Strassen’s Large Integer Multiplication Algorithm
 FASTER INTEGER MULTIPLICATION 
 A GMP-based implementation of Schonhage-Strassen’s large integer multiplication algorithm
 fcarc-multiplication
 Fast Fourier transforms

 อ้างอิง 

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:การคูณ