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

 (github.com/francisrstokes)
3 คะแนน โดย GN⁺ 2024-05-12 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • CORDIC คืออัลกอริทึมที่เปลี่ยนการคำนวณที่ซับซ้อนให้เน้นการบวกและการเลื่อนบิต เพื่อคำนวณฟังก์ชันตรีโกณมิติอย่าง sin, cos, tan โดยไม่ต้องใช้ FPU หรือตาราง lookup ขนาดใหญ่
  • วิธีนี้มีประโยชน์ใน สภาพแวดล้อมแบบ embedded มากกว่าระบบประสิทธิภาพสูง โดยเฉพาะไมโครคอนโทรลเลอร์สมรรถนะต่ำและ FPGA และไม่ควรตัดสินคุณค่าด้วยความเร็วเพียงอย่างเดียว
  • หากใช้ fixed-point แทน floating-point สามารถแบ่ง int32_t เป็น 16 บิตบนสำหรับส่วนจำนวนเต็ม และ 16 บิตล่างสำหรับส่วนทศนิยม เพื่อแทนค่าได้ตั้งแต่ประมาณ -32768.99997 ถึง 32767.99997
  • หมุนเวกเตอร์ไปยังมุมเป้าหมายด้วยมุมที่เล็กลงเรื่อย ๆ และใช้ตาราง atan(2**-i) 16 ค่า กับค่าเริ่มต้น x=39796 ก็สามารถแทนการคูณในแต่ละรอบด้วยการเลื่อนบิตได้
  • เมื่อทำซ้ำ 16 รอบกับมุมตัวอย่าง 0.9152 ค่าความคลาดเคลื่อนสัมบูรณ์ของ sin(0.9152) ลดลงเหลือระดับ 0.00000956 และของ cos(0.9152) เหลือระดับ 0.0000434

สภาพแวดล้อมการคำนวณที่ CORDIC เหมาะสม

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

การแทนค่าแบบ fixed-point เพื่อหลีกเลี่ยง floating-point

  • แม้ฟังก์ชันที่ให้ค่าระหว่าง -1.0 ถึง 1.0 อย่าง sin(x) ก็ไม่จำเป็นต้องแทนค่าด้วย floating-point เสมอไป
  • fixed-point แทนจำนวนตรรกยะโดยกำหนดตำแหน่งจุดทศนิยมไว้ตายตัวภายในชนิดข้อมูลจำนวนเต็ม
  • ตัวอย่างนี้แบ่ง int32_t เป็นส่วนจำนวนเต็ม 16 บิตบน และส่วนทศนิยม 16 บิตล่าง
    • ในกรณีนี้ ช่วงค่าจะอยู่ประมาณ -32768.99997 ถึง 32767.99997
    • การวางตำแหน่งจุดทศนิยมไว้ตรงไหนเป็นการแลกเปลี่ยนระหว่างช่วงของส่วนจำนวนเต็มกับความละเอียดของส่วนทศนิยม
  • ตัวค่าเองยังคงเป็น int32_t และโปรแกรมเมอร์เป็นผู้กำหนดความหมายเพิ่มเติมให้กับอาร์เรย์บิต

การแปลง fixed-point และการดำเนินการพื้นฐาน

  • หากความละเอียดทศนิยมเป็น 16 บิต สามารถนำค่า float อย่าง 42.01 ไปคูณด้วย (1 << 16) เพื่อสร้างค่า fixed-point ได้
    • 42.01 * (1 << 16) เมื่อ cast เป็น int32_t จะได้ 2753167
    • หากต้องการแปลงกลับเป็น float ให้คำนวณ 2753167 / (1 << 16) จะได้ประมาณ 42.0099945
  • ยังสามารถ encode ค่าอย่าง 1.5 ได้โดยตรงโดยไม่ใช้ floating-point เลย
    • ส่วนจำนวนเต็ม 1 ถูกยกขึ้นด้วย (1 << 16)
    • ครึ่งหนึ่งของส่วนทศนิยมสามารถกำหนดเป็น 0x7fff ซึ่งเป็นค่ากลางระหว่าง 0x0000 กับ 0xffff
    • ผลลัพธ์ของวิธีนี้คือเลขฐานสิบ 98303
  • การบวก และ การลบ ระหว่างค่าที่ใช้ตัวคูณสเกลเดียวกันทำงานได้ตามปกติ
  • การคูณทำโดยคูณค่า fixed-point สองค่าเข้าด้วยกัน แล้วเลื่อนผลลัพธ์กลับไปทางขวาตามตัวคูณสเกล
  • การหารสามารถเพิ่มความละเอียดได้โดยเลื่อนตัวตั้งไปทางซ้ายล่วงหน้าตามตัวคูณสเกล แล้วจึงหารด้วยตัวหาร

การประมาณฟังก์ชันตรีโกณมิติด้วยการหมุนเวกเตอร์

  • CORDIC ย่อมาจาก “co-ordinate rotation digital computer” และถูกสร้างขึ้นในช่วงกลางทศวรรษ 1950
  • แนวคิดหลักคือหมุนเวกเตอร์บนวงกลมหนึ่งหน่วยด้วยมุมที่เล็กลงเรื่อย ๆ เพื่อให้เมื่อถึงมุมเป้าหมาย องค์ประกอบของเวกเตอร์กลายเป็นค่าไซน์และโคไซน์
  • กระบวนการนี้คล้ายกับ binary search
    • เคลื่อนที่ด้วยมุมใหญ่ไปยังมุมเป้าหมาย
    • ตรวจสอบว่าเลยเป้าหมายไปหรือไม่
    • จากนั้นหมุนตามเข็มนาฬิกาหรือทวนเข็มนาฬิกาซ้ำด้วยมุมที่เล็กลง
  • ตัวอย่างเมื่อต้องการหา sin(0.7) เริ่มจากเวกเตอร์ตั้งต้น (1, 0) และเป้าหมาย 0.7 เรเดียน
    • ก่อนอื่นหมุนทวนเข็มนาฬิกา 0.7853 เรเดียน หรือ 45˚
    • เป้าหมายที่เหลือกลายเป็น 0.7 - 0.7853 = -0.0853
    • เนื่องจากค่าเป็นลบ ครั้งถัดไปจึงหมุนตามเข็มนาฬิกา 0.3926 เรเดียน หรือ 22.5˚
    • หลังจากนั้นจะสลับทิศทางไปตามเครื่องหมายของเป้าหมายที่เหลือด้วยมุมที่เล็กลง เช่น 0.1963 เรเดียน
  • เมื่อทำซ้ำ 16 รอบ เวกเตอร์จะเกือบตรงกับมุมเป้าหมายเดิม และ y จะเป็นค่าประมาณของ sin(a) ส่วน x จะเป็นค่าประมาณของ cos(a)

ลดการคำนวณราคาแพงจากเมทริกซ์การหมุน

  • การหมุนเวกเตอร์ทั่วไปใช้การคูณเมทริกซ์ที่มีไซน์และโคไซน์
  • CORDIC ใช้เอกลักษณ์ตรีโกณมิติเปลี่ยนเมทริกซ์การหมุนให้เน้น tan(a)
  • ในตอนแรกใช้มุมหมุนที่กำหนดไว้ เช่น 45˚, 22.5˚, 11.25˚ จึงสามารถเก็บค่า tan(a) ไว้เป็นตารางที่คำนวณล่วงหน้าได้
  • ตารางนี้ต้องใช้ uint32_t เพียง 16 ค่า รวม 64 ไบต์
    • เพื่อเทียบกัน ตาราง sin(x) ที่ไม่ได้ปรับแต่งซึ่งเก็บ 4096 ค่าตั้งแต่ -1 ถึง 1 ต้องใช้ 16KiB และถือว่าความละเอียดต่ำกว่า
  • พจน์ cos(a) ที่อยู่ด้านหน้าของแต่ละการหมุนเกิดขึ้นในทุก iteration แต่ผลคูณทั้งหมดจะลู่เข้าเป็นค่าคงที่
    • เมื่อใช้มุมแบบ 45˚, 22.5˚, 11.25˚ ผลคูณนี้อยู่ประมาณ 0.6366
    • จึงคูณค่าคงที่นี้เพียงครั้งเดียวหลัง iteration ทั้งหมดก็ได้

การเลือกมุมให้เหลือเพียง shift และการบวก

  • หากต้องการกำจัดการคูณ ต้องเลือกมุมให้ผลลัพธ์ของ tan(a) เป็น กำลังผกผันของ 2 เสมอ
  • เพื่อทำเช่นนั้น ให้สร้างตาราง 16 entries ที่เก็บค่า atan(2**-i) สำหรับแต่ละรอบ i=0 ถึง 15
  • มุมหมุนจริงจะเป็น 45˚, 26.565˚, 14.036˚, 7.125˚ เป็นต้น
  • แม้มุมจะไม่ได้ลดลงครึ่งหนึ่งอย่างแม่นยำ แต่เมื่อใช้มุมเหล่านี้ กระบวนการก็ยังลู่เข้าสู่ผลลัพธ์ที่ถูกต้อง
  • การคูณ tan(a) เปลี่ยนเป็นการเลื่อนบิตตามหมายเลขรอบ i
  • ผลคูณของพจน์ cos(a) ก็ถูกคำนวณใหม่ให้เข้ากับการเลือกมุมแบบใหม่นี้
    • ค่าประมาณคือ 0.60725
    • ใน fixed-point 16 บิต จะเป็น 39796
    • แทนที่จะคูณตอนท้าย ให้ตั้งค่า x ของเวกเตอร์เริ่มต้นเป็น 39796 ไม่ใช่ 1

ขั้นตอนของอัลกอริทึม

  • ในขั้น precompute ให้สร้างตารางที่แต่ละ entry คือ atan(2**-i) แล้วแปลงแต่ละค่าเป็น fixed-point
    • สูตรแปลงคือ atan(2**-i) * (1 << 16)
  • เมื่อต้องการหา sin หรือ cos ให้แปลงมุม input เป็น fixed-point ด้วย
    • ตัวอย่าง 0.9152 จะได้ 0.9152 * (1 << 16) = 59978
  • สถานะเริ่มต้นเป็นดังนี้
x = 39796
y = 0
z = 59978
  • z ไม่ใช่ส่วนหนึ่งของเวกเตอร์ แต่เป็นค่าที่ติดตามมุมเป้าหมายที่เหลืออยู่
  • เครื่องหมายของ z เป็นตัวกำหนดทิศทางการหมุน
    • ถ้า z >= 0 จะหมุนทวนเข็มนาฬิกาและทำ z -= table[i]
    • ถ้า z < 0 จะหมุนตามเข็มนาฬิกาและทำ z += table[i]
  • แต่ละ iteration ใช้เฉพาะการบวก การลบ และการ shift >> i กับ x และ y
if z >= 0:
    x_next = x - (y >> i)
    y_next = y + (x >> i)
    z -= table[i]
else:
    x_next = x + (y >> i)
    y_next = y - (x >> i)
    z += table[i]
x = x_next
y = y_next

ผลการลู่เข้าตัวอย่างและหัวข้อที่ยังเหลือ

  • ในตัวอย่าง 0.9152 เรเดียน รอบแรก z เป็นบวก จึงหมุนทวนเข็มนาฬิกาประมาณ 0.785 เรเดียน
  • รอบที่สอง z ยังเป็นบวก จึงหมุนทวนเข็มนาฬิกาประมาณ 0.436 เรเดียน แต่เลยเป้าหมายไป
  • รอบที่สาม z กลายเป็นลบ จึงหมุนตามเข็มนาฬิกาประมาณ 0.244 เรเดียน
  • รอบที่สี่ z ก็เป็นลบเช่นกัน จึงหมุนตามเข็มนาฬิกาประมาณ 0.124 เรเดียน
  • เมื่อการเปลี่ยนมุมเล็กลง เวกเตอร์จะเคลื่อนไปมารอบผลลัพธ์จริงและลู่เข้า
  • หลังทำซ้ำ 16 รอบ y จะเป็นค่าประมาณที่ใกล้มากของ sin(0.9152)
    • ค่าความคลาดเคลื่อนสัมบูรณ์ของไซน์คือ 0.00000956
    • ค่าความคลาดเคลื่อนสัมบูรณ์ของโคไซน์สำหรับ x คือ 0.0000434
  • ยังมีหัวข้อที่ไม่ได้ครอบคลุมอยู่
    • การจัดการพิเศษที่จำเป็นเมื่อมุมที่สนใจอยู่นอก quadrant ที่ 1 หรือ 4 ของวงกลมหนึ่งหน่วย
    • tan, atan, asin, acos, sinh, cosh, tanh, sqrt, ln, e^x ที่สามารถคำนวณได้ด้วย CORDIC variants
    • อัลกอริทึมที่เกี่ยวข้องซึ่งออกแบบมาสำหรับการคำนวณลอการิทึมและเอ็กซ์โพเนนเชียลอย่าง BKM
  • มีแผนจะลงรายละเอียดเพิ่มเติมเกี่ยวกับเนื้อหาที่เกี่ยวข้องใน Low Byte Productions YouTube channel

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

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

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

  • ผู้เขียนบอกว่าส่วนใหญ่ถูกนำไปใช้กับพวก FPGA แต่ก็ใช้กับการพัฒนาเกมหรือการจำลองฟิสิกส์แบบกระจายได้เช่นกัน
    การคำนวณแบบจุดลอยตัวทำให้ปรับ ความเป็นเชิงกำหนด ระหว่างแพลตฟอร์มให้ตรงกันได้ยาก และวิธีแก้แบบหนึ่งคือหลีกเลี่ยงจุดลอยตัวไปเลยแล้วทำเอนจินฟิสิกส์แบบ fixed-point
    หากจะทำฟังก์ชันตรีโกณมิติ ก็ต้องมีสิ่งอย่าง CORDIC
    เมื่อหลายปีก่อนเคยเริ่มทำอะไรแบบนี้เล่น ๆ แต่สุดท้ายก็ทำไม่เสร็จ และสักวันก็อยากกลับไปลองใหม่
    https://randomascii.wordpress.com/2013/07/16/floating-point-...

    • บทความนั้นตอนนี้ก็มีอายุ 10 ปีแล้ว แต่มีคำพูดสำคัญอยู่: “มาตรฐาน IEEE รับประกันบางอย่างไว้ มันรับประกันมากกว่าที่คนที่มองคณิตศาสตร์จุดลอยตัวราวกับเป็นเรื่องลึกลับคิดไว้ แต่ก็น้อยกว่าที่โปรแกรมเมอร์บางคนเข้าใจ”
      สรุปคือ x87 มีจุดประหลาดอยู่ ต้องตั้งค่าอย่างโหมดการปัดเศษและการ flush-to-zero ให้สอดคล้องกัน, โปรเซสเซอร์รุ่นเก่าไม่มี FMA, คำสั่งประมาณค่าอย่าง mmsqrtps ไม่มีสเปกที่สม่ำเสมอ และคอมไพเลอร์อาจจัดกลุ่มนิพจน์ใหม่ได้
      ถ้าเป็นรูทีนเล็ก ๆ หรือไลบรารีที่เขียนเอง แม้จะลำบากแต่ก็ยังพอรับประกันได้ว่าจะหลีกเลี่ยงสิ่งเหล่านี้
      IEEE-754 2008 ทำให้สเปกชัดเจนขึ้นและโดยพฤตินัยก็ถือว่าการตายของ x87 เกิดขึ้นแล้ว และในปี 2024 ก็สามารถหลีกเลี่ยง x87 ได้อย่างมั่นใจ
      FMA ก็เป็นส่วนหนึ่งของสเปก IEEE-754 2008 และมีอยู่ในโปรเซสเซอร์สมัยใหม่ รวมถึง Intel Haswell เป็นต้นไป
      ถึงอย่างนั้นความต่างของสถาปัตยกรรมอย่าง 8-wide AVX2 กับ 4-wide NEON ก็ยังอาจเป็นอุปสรรคได้ แต่ถ้าใช้แอสเซมบลี, intrinsics หรือ C ที่ตรวจด้วย Compiler Explorer หรือ objdump ก็สามารถดูผลลัพธ์แล้วตัดสินได้ว่า “อันนี้น่าจะสม่ำเสมอ”
    • ผู้เขียนก็กล่าวว่าก่อนที่จุดลอยตัวจะแพร่หลายในงานพัฒนาเกมเพราะฮาร์ดแวร์แรงขึ้น fixed-point เคยพบได้บ่อยมาก และ CORDIC ก็น่าจะถูกใช้ไปพร้อมกันด้วย
      “จริง ๆ แล้วก่อนที่ IEEE 754 จะกลายเป็นมาตรฐานกระแสหลักแบบทุกวันนี้ fixed-point ถูกใช้อยู่เสมอ ลองไปถามนักพัฒนาเกมที่ทำงานช่วงราวปี 1980 ถึง 2000 ดู พวกเขาน่าจะเล่าได้ละเอียด”
    • ไลบรารีจำลองฟิสิกส์สำหรับการพัฒนาเกม nphysics เลือกใช้คณิตศาสตร์แบบ fixed-point ร่วมกับ CORDIC เมื่อต้องการความเป็นเชิงกำหนดข้ามแพลตฟอร์ม แต่ตอนนี้เลิกใช้ไปแล้ว
      ไลบรารีใหม่ Rapier ที่เขียนขึ้นมาแทน nphysics เลือกพึ่งการรับประกันของ IEEE-754 2008 เพื่อให้ได้ความเป็นเชิงกำหนดข้ามแพลตฟอร์มแทน
      เพราะอย่างนั้นจึงใช้ไม่ได้บนแพลตฟอร์มเก่า แต่บนแพลตฟอร์มสมัยใหม่รวมถึง wasm จะเป็นเชิงกำหนด
      แน่นอนว่าไม่สามารถพึ่งรูทีนฟังก์ชันอดิศัยอย่าง sin, cos ที่แต่ละแพลตฟอร์มมีให้ได้ และต้องเขียนเองเพื่อให้ทำงานเหมือนกันทุกที่
      แต่ถ้าไม่รันบนแพลตฟอร์มที่ไม่เป็นไปตามมาตรฐาน แนวทางนี้ก็ทำได้
      https://www.rustsim.org/blog/2020/06/01/this-month-in-rustsi...
      https://rapier.rs/docs/user_guides/rust/determinism/

  • CORDIC ใช้ได้ไม่ใช่แค่การคำนวณหรือสร้าง sine และ cosine เท่านั้น แต่ยังใช้กับ ลอการิทึม, เอ็กซ์โปเนนเชียล, รากที่สอง, ขนาดเวกเตอร์, การแปลงพิกัดเชิงขั้ว-คาร์ทีเซียน, การหมุนเวกเตอร์ และการคำนวณอื่น ๆ อีกหลายแบบ
    ผู้เขียนก็เกริ่นถึงความเป็นไปได้แบบนี้ไว้ในบทสรุป
    ถ้าใช้ quaternion แทนเมทริกซ์ออร์โธนอร์มัลแบบเดิม ก็ดูเหมือนว่าจะทำการคำนวณแบบอิง CORDIC ได้มีประสิทธิภาพกว่า คือใช้รอบการคำนวณและหน่วยความจำน้อยลง ลดความคลาดเคลื่อนได้ และรันได้ดีขึ้น
    https://core.ac.uk/works/8439118

    • ถ้าจำไม่ผิด น่าจะขยายไปยัง Lie group แบบใดก็ได้ด้วย

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

    • ถ้าได้อ่านว่าเครื่องคิดเลข Sinclair scientific อันน่าทึ่งคำนวณตรีโกณมิติและลอการิทึมอย่างไร ก็น่าจะน่าสนใจ
      มันไม่ใช่ CORDIC แต่มีความคล้ายกันในเชิงอัลกอริทึม
      http://files.righto.com/calculator/sinclair_scientific_simul...
    • มีเครื่องคิดเลขที่ใช้การขยายแบบเทย์เลอร์จริง ๆ สักเครื่องไหม?

  • บทความเกี่ยวกับการนำไปใช้งานในฮาร์ดแวร์:
    https://arxiv.org/pdf/2211.04053
    https://hal.science/hal-01327460/document
    https://archive.ll.mit.edu/HPEC/agendas/proc05/Day_1/Abstrac...
    อยากดูว่ามันถูกเปรียบเทียบกับการ ทำฟังก์ชันตรีโกณมิติ แบบซอฟต์แวร์และฮาร์ดแวร์ทั่วไปบนฮาร์ดแวร์หลากหลายยุคสมัยอย่างไร

    • น่าแปลกที่แม้ CORDIC จะเป็นเทคนิคคอมพิวเตอร์ที่ใช้กันอย่างแพร่หลายและเป็นที่รู้จักมาก แต่ในหนังสือกลับไม่ค่อยอธิบายอย่างละเอียดจริงจัง
      ตอนนี้ IoT และการสื่อสารระหว่างเครื่องจักรกำลังเติบโต และเมื่อพิจารณาจากการนำ CORDIC ไปใช้งานและประสิทธิภาพการคำนวณ การใช้งานก็น่าจะเพิ่มขึ้นมาก จึงจำเป็นต้องมีเอกสารอ้างอิงที่ดีสำหรับการนำไปใช้ให้ถูกต้องและเหมาะที่สุด
      ข้อยกเว้นคือหนังสือของ Prof. Omondi และ Prof. Deschamps
      https://www.worldscientific.com/worldscibooks/10.1142/p1054
      http://www.arithmetic-circuits.org/guide2fpga/vhdl_codes.htm

  • sin และ cos มักถูกใช้กับการหมุนเวกเตอร์
    ในกรณีนี้ เคล็ดลับของ CORDIC คือหลีกเลี่ยงการคำนวณ sin/cos/การคูณ แบบดั้งเดิม แล้วป้อนเวกเตอร์ที่จะหมุนเข้าไปเป็นอินพุตของ CORDIC โดยตรง
    จากนั้น CORDIC จะสร้างเวกเตอร์ที่ถูกหมุนแล้วออกมาโดยตรง โดยไม่ต้องคำนวณ sin/cos หรือทำการคูณจำนวนเชิงซ้อน
    CORDIC จะโดดเด่นเป็นพิเศษเมื่อค่าหน่วงเวลาไม่ใช่เรื่องสำคัญมาก
    ถ้าทำแต่ละขั้นของการคำนวณเป็น pipeline ก็จะได้ throughput สูงมาก จึงเหมาะกับ digital mixing ในระบบไร้สาย

  • ณ ปี 2023 MCU สมัยใหม่บางรุ่นมี FPU ทั้งที่ยังราคาถูก
    STM32G4 เป็นตัวอย่างที่ดี และต่างจากกรณีอย่าง MCU ตระกูล M0 ถ้าไม่อยากใช้ fixed-point ก็สามารถใช้ f32 ได้อย่างสบาย
    ชิปรุ่นพวกนี้หาได้ในราคาราว ๆ 1~2 ดอลลาร์ต่อ MCU
    อย่างไรก็ตาม G4 ก็ยังมีอุปกรณ์ต่อพ่วง CORDIC แบบฮาร์ดแวร์ที่นำอัลกอริทึมนี้ไปใช้สำหรับ fixed-point ด้วย
    เลยสงสัยว่าสิ่งนี้มีไว้หลัก ๆ เพื่อหลีกเลี่ยงการสูญเสียความแม่นยำของ floating-point หรือเปล่า
    มันถูกโปรแกรมผ่านรีจิสเตอร์ แต่ไม่ได้ให้ CPU ทำ CORDIC เองโดยตรง เพราะมีฮาร์ดแวร์เฉพาะทางภายใน IC เป็นผู้จัดการให้

    • ถ้าดูจากสต็อกของ Digi-Key และตัดรายการซ้ำออก Cortex-M4F ที่ถูกที่สุดก็ประมาณ Nuvoton M481LE8AE ราคา 3 ดอลลาร์ https://www.digikey.com/en/products/detail/nuvoton-technolog..., Maxim MAX32660 ราคา 3 ดอลลาร์ https://www.digikey.com/en/products/detail/analog-devices-in..., และ Atmel ATSAMD51 ราคา 5 ดอลลาร์ https://www.digikey.com/en/products/detail/microchip-technol...
      STM32G4 ที่ถูกที่สุดคือ STM32G441KBT6 และถ้าปัดเศษก็ราคา 4 ดอลลาร์ https://www.digikey.com/en/products/detail/microchip-technol...
      เลยสงสัยว่าเขาหาซื้อกันต่ำกว่า 2 ดอลลาร์จากที่ไหน
      ใน Digi-Key ชิป Nuvoton เพิ่งจะต่ำกว่า 2 ดอลลาร์แบบเฉียด ๆ เมื่อซื้อจำนวน 500 ชิ้น
    • ชิป Parallax Propeller รุ่นที่สองมี CORDIC engine ที่ฝังอยู่ในซิลิคอน
      มันเร็ว และรองรับ intermediate multiply แบบ 64 บิต ทำให้ความแม่นยำของการหารและฟังก์ชันตรีโกณมิติเพียงพอสำหรับงานส่วนใหญ่
      ถ้าจำเป็นก็ยังเพิ่มความแม่นยำด้วยซอฟต์แวร์ได้อีก
      ฉันมารู้จัก CORDIC ช้าไปหน่อย ก่อนหน้านั้นจึงใช้ fixed-point เยอะมากในโลกของแอสเซมบลี 8 บิตและ 16 บิตเพื่อเอาทั้งประสิทธิภาพและความแน่นอนของผลลัพธ์
      พอได้รู้จักแล้วก็ทึ่งมาก
      มันเร็ว และความรู้คณิตศาสตร์ที่ต้องมีเพื่อใช้งานให้เป็นประโยชน์ก็มีแค่ระดับพื้นฐานเท่านั้น

  • ทำให้นึกถึงโค้ดชิ้นเล็ก ๆ ที่น่ารักพอสมควรที่เคยมีส่วนร่วมเมื่อก่อน
    ตอนนั้นต้องหาพิกัดของ เส้นแบ่งครึ่งมุม ที่เกิดจากส่วนโค้งบนวงกลมหนึ่งหน่วย และมีพิกัด (x,y) ของแขนทั้งสองข้างอยู่แล้ว
    การติดตั้งเดิมเป็นก้อนตรีโกณมิติที่แปลงพิกัด (x,y) เป็นพิกัดเชิงขั้ว (r,θ) ตรวจว่า θ ที่คำนวณได้อยู่ในควอดแรนต์ที่ถูกต้องหรือไม่ จากนั้นหาร θ ครึ่งหนึ่งแล้วแปลงกลับเป็น (x,y)
    สรุปแล้วจึงต้องเรียกใช้ฟังก์ชันตรีโกณมิติและฟังก์ชันผกผันจำนวนมาก
    แต่เพราะใน Python ใช้จำนวนเชิงซ้อนเป็นชนิดข้อมูลชั้นหนึ่งได้ จึงแค่กำหนดจำนวนเชิงซ้อนสองตัว z1 จาก (x1,y1) และ z2 จาก (x2,y2) แล้วเอาแค่ค่า geometric mean ของผลคูณ √(z1*z2) ก็จบ
    โค้ดใหม่ไม่มีทั้งฟังก์ชันตรีโกณมิติแบบชัด ๆ และไม่มีทั้งการแปลงกับการแปลงย้อนกลับแบบชัด ๆ

  • มีประโยคว่า “การหมุน 22.75˚ เท่ากับการหมุน 45˚ แล้วตามด้วย -22.5˚ ซึ่งค่อนข้างชัดเจน” แต่ถ้าอย่างนั้นก็ควรเป็นการหมุน 22.5° ไม่ใช่หรือ?
    เลยสงสัยว่าเป็นข้อผิดพลาดในบทความ หรือว่าฉันเข้าใจผิดเอง

    • เป็นข้อผิดพลาดในบทความ

  • ระบบ octree ของ Meagher มีชื่อเสียงว่าใช้เพียงเลขคณิตจำนวนเต็มโดยไม่ใช้การคูณหรือหารจำนวนเต็ม
    “ได้มีการพัฒนาอัลกอริทึมเวลาเชิงเส้นที่มีประสิทธิภาพสำหรับการดำเนินการแบบบูลีน (union, intersection, difference), การดำเนินการทางเรขาคณิต (การย้าย, การปรับขนาด, การหมุน), การตรวจจับการรบกวนกันใน N มิติ และการแสดงผลรวมถึงการลบพื้นผิวที่ถูกบัง ณ จุดใดๆ ในอวกาศ อัลกอริทึมนี้ไม่ต้องการการคำนวณจุดลอยตัว, การคูณจำนวนเต็ม, หรือการหารจำนวนเต็ม”
    https://doi.org/10.1016/0146-664X(82)90104-6
    ด้วยเหตุนี้จึงทำให้สร้าง ฮาร์ดแวร์เร่งกราฟิก VLSI แบบปรับแต่งเฉพาะที่รวดเร็วสำหรับการแทนค่า octree ได้ง่าย

  • สงสัยว่า CORDIC ให้ประสิทธิภาพอย่างไรเมื่อเทียบกับ การอินเตอร์โพเลชันกำลังสาม ที่ใช้ตารางขนาดเล็กหรือการอินเตอร์โพเลชันพหุนามแบบอื่น
    เคยเรียนมาว่าซินธิไซเซอร์ที่มีทรัพยากรจำกัดบางครั้งใช้การอินเตอร์โพเลชันกำลังสาม ซึ่งก็น่าจะเป็นช่วงที่ CORDIC ยังถือว่าค่อนข้างใหม่
    มองคร่าวๆ แล้ว CORDIC ได้ความละเอียดเพิ่ม 1 บิตต่อการวนซ้ำแต่ละครั้ง จึงน่าจะมีต้นทุนการคำนวณสูงกว่า แต่ใช้พื้นที่น้อยกว่าพหุนาม
    แต่ในแง่ของพื้นที่ก็ควรเน้นด้วยว่ามันอาจถูกกว่าตาราง lookup 4096 รายการสำหรับ sin(x) ที่ยกมาในบทความ
    ด้วยสมมาตรจึงต้องใช้เพียง 1/4 ของวงกลมทั้งหมด

    • นักพัฒนาเกมยุคก่อนและนักพัฒนาเดโมซีนเคยใช้ ตาราง lookup เพียง 256 รายการ สำหรับ sin และ cos
      ถ้าใช้มุมขนาดไบต์ก็จะวนรอบให้อัตโนมัติและใช้งานสะดวก และสำหรับการหมุนในเกม 2D นั้น 2^8 ก็เพียงพอพอสมควร
      แต่ถ้าต้องการการเคลื่อนไหวที่ลื่นไหล ใน 3D ก็ไปได้ไม่ไกลนัก