เหตุผลที่อัลกอริทึม CORDIC ตรึงอยู่ในหัวผมอย่างถาวร

 (github.com/francisrstokes)
3 คะแนน โดย GN⁺ 2024-05-12 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

เหตุผลที่อัลกอริทึม CORDIC อาศัยอยู่ในใจผมแบบไม่เสียค่าเช่า

หลีกเลี่ยง Floating Point ด้วยการใช้ Fixed Point

  • การใช้ Fixed Point แทน Floating Point ทำให้สามารถแทนจำนวนจริงได้
  • ใช้จำนวนเต็ม 32 บิต โดยแบ่ง 16 บิตบนเป็นส่วนจำนวนเต็ม และ 16 บิตล่างเป็นส่วนเศษ
  • ด้วยวิธีนี้จึงแทนค่าได้ประมาณตั้งแต่ -32768.99997 ถึง 32767.99997
  • โปรแกรมเมอร์สามารถกำหนดตำแหน่งของจุดทศนิยมเองเพื่อปรับระดับความแม่นยำได้
  • หากต้องการแปลง Float เป็น Fixed Point ให้คูณด้วย 2^16 แล้ว cast เป็น int32_t
  • หากต้องการแปลง Fixed Point เป็น Float ให้หารด้วย 2^16
  • การบวกและการลบทำงานได้ตรงไปตรงมา ส่วนการคูณและการหารต้องปรับ Scaling Factor

ภาพรวมของอัลกอริทึม CORDIC

  • CORDIC ย่อมาจาก "Co-ordinate Rotation Digital Computer" และถูกพัฒนาขึ้นในช่วงกลางทศวรรษ 1950
  • เป็นวิธีหาค่า sine และ cosine โดยค่อย ๆ หมุนเวกเตอร์บนวงกลมหนึ่งหน่วยด้วยมุมเล็กลงเรื่อย ๆ
  • คล้ายกับ binary search โดยจะขยับด้วยมุมใหญ่เพื่อเข้าใกล้มุมเป้าหมายก่อน แล้วค่อยลดมุมลงครึ่งหนึ่งทีละขั้น พร้อมหมุนตามเข็มหรือทวนเข็มนาฬิกาเพื่อให้ลู่เข้า
  • กำหนดมุมหมุนสูงสุดไว้ที่ 90 องศา (π/2 radian) และทำซ้ำ 16 ครั้งเพื่อให้ลู่เข้าใกล้มุมเป้าหมาย
  • เมื่อเวกเตอร์ลู่เข้าแล้ว ค่า y จะประมาณ sin(a) และค่า x จะประมาณ cos(a)

ทำให้เมทริกซ์ง่ายลงเพื่อใช้แค่การคูณค่าคงที่

  • เมทริกซ์การหมุนมีฟังก์ชัน sine, cosine และ tangent อยู่ จึงคำนวณซับซ้อน
  • เนื่องจากหมุนด้วยมุมคงที่ ฟังก์ชัน tangent จึงคำนวณล่วงหน้าและเก็บไว้ในตารางได้ (ประมาณ 64 ไบต์)
  • พจน์ cosine เกิดขึ้นในทุกการวนซ้ำ แต่ค่าที่ลู่เข้าจะเป็นค่าคงที่ (ประมาณ 0.6366) จึงคูณเพียงครั้งเดียวตอนท้ายได้

ใช้แค่การทำงานแบบ Shift และ Add

  • เลือกมุมที่ใช้กับฟังก์ชัน tangent ให้เป็นค่า 2^-i โดยใช้อาร์กแทนเจนต์
  • ทำให้สามารถแทนการคูณด้วยการเลื่อนบิตได้
  • เมื่อนำค่าลู่เข้าของพจน์ cosine มาคำนวณใหม่ จะได้ประมาณ 0.60725 และใช้ตั้งเป็นค่า x เริ่มต้นของเวกเตอร์
  • การวนซ้ำแต่ละครั้งของอัลกอริทึม CORDIC จึงย่อให้ง่ายได้ดังนี้
    • ถ้า z มีค่ามากกว่าหรือเท่ากับ 0 ให้หมุนทวนเข็มนาฬิกา (ลบ y>>i จาก x, บวก x>>i ให้ y)
    • ถ้า z น้อยกว่า 0 ให้หมุนตามเข็มนาฬิกา (บวก y>>i ให้ x, ลบ x>>i จาก y)
    • อัปเดต z โดยลบหรือบวกค่ามุมจากตาราง
  • ด้วยวิธีนี้จึงสามารถคำนวณฟังก์ชันตรีโกณมิติได้โดยใช้เพียงการคูณค่าคงที่ การเลื่อนบิต และการบวก

ความเห็นของ GN⁺

  • CORDIC ดูเป็นอัลกอริทึมที่มีประโยชน์ในสภาพแวดล้อมที่ทรัพยากรฮาร์ดแวร์จำกัด เช่น ระบบ embedded หรือ FPGA โดยเฉพาะเมื่อไม่มีการรองรับการคำนวณแบบ floating point ก็น่าเป็นวิธีที่ควรพิจารณา
  • แนวคิดการเลือกมุมของฟังก์ชัน tangent อย่างมีกลยุทธ์เพื่อแทนการคูณด้วยการเลื่อนบิตนั้นน่าประทับใจ เป็นตัวอย่างที่ดีของการผสานกันระหว่างความเข้าใจทางคณิตศาสตร์และสถาปัตยกรรมคอมพิวเตอร์
  • น่าสนใจเช่นกันที่มันไม่ได้ใช้ได้แค่กับฟังก์ชันตรีโกณมิติ แต่ยังประยุกต์ใช้กับการคำนวณฟังก์ชันต่าง ๆ เช่น logarithm, exponent และ square root ได้ด้วย อัลกอริทึมที่เกี่ยวข้องอย่าง BKM ก็น่าลองศึกษาไปพร้อมกัน
  • อย่างไรก็ตาม ฮาร์ดแวร์สมัยใหม่จำนวนมากมี FPU ในตัวอยู่แล้ว และการใช้การคำนวณแบบ fixed point ก็อาจทำให้เกิดการสูญเสียความแม่นยำได้ จึงควรระวังเมื่อจะนำไปใช้
  • หากเป็นระบบที่ต้องทำการคำนวณลักษณะนี้ซ้ำ ๆ จำนวนมาก ก็อาจพิจารณาออกแบบฮาร์ดแวร์เฉพาะสำหรับ CORDIC ได้เช่นกัน

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-05-12
ความคิดเห็นจาก Hacker News

  • อัลกอริทึม CORDIC สามารถนำไปใช้ได้ไม่ใช่แค่กับ FPGA เท่านั้น แต่ยังใช้กับการพัฒนาเกมหรือการจำลองฟิสิกส์แบบกระจายได้ด้วย การคำนวณจุดลอยตัวทำให้รับประกันการทำงานแบบกำหนดแน่นอนระหว่างแพลตฟอร์มได้ยาก ดังนั้นการทำเอนจินฟิสิกส์แบบ fixed-point และใช้ CORDIC เพื่อคำนวณฟังก์ชันตรีโกณมิติอาจเป็นทางออกหนึ่งได้

  • CORDIC ใช้ได้ไม่เพียงแค่กับ sine และ cosine แต่ยังใช้กับการคำนวณ log, exp, square root, ขนาดเวกเตอร์, การแปลงพิกัดเชิงขั้ว-คาร์ทีเซียน, การหมุนเวกเตอร์ และการคำนวณอื่น ๆ อีกมากมาย หากใช้ quaternion ก็น่าจะทำให้การคำนวณบนพื้นฐาน CORDIC มีประสิทธิภาพและความแม่นยำมากขึ้น

  • มีการแชร์ประสบการณ์ว่าในวิชา pre-calculus ระดับมัธยมปลายเคยเรียนเรื่องการทำงานของฟังก์ชันตรีโกณมิติในเครื่องคิดเลข และภายหลังถึงได้รู้ว่าสิ่งนั้นไม่ใช่อนุกรมเทย์เลอร์ แต่จริง ๆ คือ CORDIC จึงลองนำไปเขียนด้วย TI Basic เอง

  • ณ ปี 2023 แม้แต่ MCU ราคาประหยัดอย่าง STM32G4 ก็ยังมี FPU ในตัว ทำให้สามารถใช้จุดลอยตัวได้อย่างอิสระแทน fixed-point แต่ G4 ก็ยังมีอุปกรณ์ต่อพ่วง CORDIC ที่ทำด้วยฮาร์ดแวร์เฉพาะทาง ซึ่งดูเหมือนมีไว้เพื่อหลีกเลี่ยงการสูญเสียความแม่นยำของจุดลอยตัว

  • ดูเหมือนว่าคำอธิบายที่ว่า การหมุน 22.75° เท่ากับการหมุน 45° แล้วตามด้วย -22.5° จะมีข้อผิดพลาด น่าจะต้องเป็น 22.5°

  • ระบบ octree ของ Meagher ถูกสร้างขึ้นด้วยการคำนวณจำนวนเต็มล้วน ๆ โดยไม่มีการคูณหรือหารจำนวนเต็มเลย ซึ่งช่วยให้สร้างฮาร์ดแวร์เร่งกราฟิกแบบ VLSI ที่รวดเร็วและออกแบบเฉพาะสำหรับการแทนค่า octree ได้ง่ายขึ้น

  • CORDIC อาจมองได้ว่าเป็นแนวคิดที่คล้ายกับลำดับ Farey ของมุม (หรือ mediant, naive fraction sum)

  • CORDIC เคยถูกนำไปใช้บนเครื่องคิดเลข HP แบบตั้งโปรแกรมได้รุ่นวินเทจที่ใช้ CPU 4 บิตด้วย และยังสามารถเขียนโปรแกรมวิธีประมาณค่าจากการขยายเทย์เลอร์ของฟังก์ชัน sine ได้เช่นกัน

  • ถ้าชอบบทความนี้ ก็น่าอ่านหนังสือคลาสสิกของ Donald Knuth อย่าง "The Art of Computer Programming" ที่อธิบายอัลกอริทึมทางคณิตศาสตร์พร้อมตัวอย่าง

  • CORDIC เป็นอัลกอริทึมที่เคยได้รับความนิยมอย่างมากในวงการ DSP สมัยก่อน

  • เป็นอัลกอริทึมที่ยอดเยี่ยม และน่าจะมีประโยชน์ในการรันโครงข่ายประสาทเทียมบนฮาร์ดแวร์สมรรถนะต่ำ