ความรู้ทั้งหมดเกี่ยวกับอัลกอริทึม Fast Inverse Square Root

ทุกอย่างเกี่ยวกับอัลกอริทึม Fast Inverse Square Root

อัลกอริทึม

• อัลกอริทึม Fast Inverse Square Root เป็นอัลกอริทึมที่มีชื่อเสียงจากซอร์สโค้ดของ Quake 3 และถูกใช้งานโดย John Carmack
• อัลกอริทึมนี้คำนวณค่า inverse square root ได้อย่างรวดเร็วด้วยการจัดการบิตของจำนวนทศนิยมแบบลอยตัว
• ตัวอย่างโค้ด:

  float Q_rsqrt(float number) {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
  
    x2 = number * 0.5F;
    y = number;
    i = *(long*)&y;              // 부동 소수점 비트 수준 해킹
    i = 0x5f3759df - ( i >> 1 ); // 마법의 상수
    y = *(float*)&i;
    y = y * ( threehalfs - ( x2 * y * y ) );  // 1차 반복
  
    return y;
  }
  

จำนวนทศนิยมแบบลอยตัว 32 บิต: การแทนค่า

• จำนวนทศนิยมแบบลอยตัว 32 บิตตามมาตรฐาน IEEE-754 ประกอบด้วย 3 ส่วน:
  • เครื่องหมาย: 1 บิต ใช้ระบุว่าค่าเป็นบวกหรือลบ
  • เลขชี้กำลัง: 8 บิต ใช้กำหนดช่วงของตัวเลข
  • แมนทิสซา: 23 บิต ใช้ระบุตำแหน่งของตัวเลขภายในช่วงนั้น
• ค่าจริงคำนวณได้ดังนี้:

  N = -1^S * 2^(E-127) * (1 + M/2^23)
  

จำนวนทศนิยมแบบลอยตัว 32 บิต: การตีความบิต

• โดยทั่วไป การแทนค่าภายในของจำนวนทศนิยมแบบลอยตัวไม่ใช่สิ่งสำคัญสำหรับโปรแกรมเมอร์
• อย่างไรก็ตาม หากเข้าใจการแทนค่านี้อย่างดี ก็สามารถออกแบบอัลกอริทึมที่มีประสิทธิภาพได้
• เมื่อตีความแพตเทิร์นบิตของจำนวนทศนิยมแบบลอยตัวเป็นจำนวนเต็ม จะได้ค่าประมาณของฟังก์ชันลอการิทึม

  log2(x) ≈ Ix / L - B
  

วิธีของนิวตัน

• เพื่อปรับปรุงค่าประมาณเริ่มต้น จะใช้วิธีของนิวตัน (Newton's method)
• วิธีของนิวตันเป็นอัลกอริทึมที่ปรับปรุงค่าประมาณของฟังก์ชันที่กำหนดซ้ำไปเรื่อย ๆ
• ตัวอย่างโค้ด:

  y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복
  

บทสรุป

• อัลกอริทึมนี้ถูกออกแบบขึ้นจากความเข้าใจอย่างลึกซึ้งในรายละเอียดทางคณิตศาสตร์ภายในของระบบจำนวนทศนิยมแบบลอยตัว และการใช้การคำนวณที่ทำงานได้รวดเร็วบนคอมพิวเตอร์
• แม้ที่มาของอัลกอริทึมจะไม่แน่ชัด แต่ก็เป็นตัวอย่างของงานวิศวกรรมที่มีประสิทธิภาพสูงและออกแบบมาอย่างยอดเยี่ยม

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

• ความสำคัญทางประวัติศาสตร์: อัลกอริทึมนี้เป็นวิธีการที่สร้างสรรค์ซึ่งถูกคิดค้นขึ้นเพื่อก้าวข้ามข้อจำกัดของฮาร์ดแวร์ในยุคนั้น
• คุณค่าทางการศึกษา: ช่วยอย่างมากในการทำความเข้าใจโครงสร้างภายในของจำนวนทศนิยมแบบลอยตัวและหลักการทางคณิตศาสตร์
• การประยุกต์ใช้ในปัจจุบัน: บนฮาร์ดแวร์สมัยใหม่อาจมีความจำเป็นน้อยลง แต่หลักการของอัลกอริทึมยังคงมีประโยชน์
• ความเป็นไปได้ในการปรับแต่งประสิทธิภาพ: ค่าคงที่ของอัลกอริทึมสามารถปรับให้เหมาะสมได้ และยังมีพื้นที่สำหรับการวิจัยเพิ่มเติม
• มุมมองเชิงวิพากษ์: บนฮาร์ดแวร์สมัยใหม่อาจมีวิธีที่ดีกว่า ดังนั้นการเปรียบเทียบกับเทคโนโลยีล่าสุดอยู่เสมอจึงเป็นสิ่งสำคัญ

[joyfui]

โค้ดชวนทึ่งที่โผล่ขึ้นมาทุกครั้งพอเริ่มจะลืม..ฮ่า

[GN⁺]

ความคิดเห็นบน Hacker News

• รองรับคำสั่ง SSE: คอมพิวเตอร์ที่ผลิตหลังปี 1999 รองรับชุดคำสั่ง SSE และสามารถคำนวณ inverse square root ได้อย่างรวดเร็วผ่านคำสั่ง _mm_rsqrt_ps.

• ความก้าวหน้าของฮาร์ดแวร์สมัยใหม่: บนฮาร์ดแวร์สมัยใหม่ การคำนวณ inverse square root สามารถทำได้อย่างรวดเร็วบน CPU และความเข้าใจที่ว่าการคำนวณ floating point ทั้งหมดถูก offload ไปยัง GPU นั้นเป็นความเข้าใจผิด

• การติดตั้งใช้งานด้วย MMIX: มีตัวอย่างโค้ดสำหรับติดตั้งใช้งานการคำนวณ inverse square root ด้วยภาษา MMIX โดยโค้ดนี้ตั้งอยู่บนสมมติฐานว่าเลขต้นฉบับมีค่ามากกว่า 2^-1021

• คำผิดในสูตร: มีคำผิดในสูตร floating point โดยควรแก้เป็น (-1)^S

• การตีความลอการิทึม: การตีความรูปแบบบิตดิบไม่ใช่การประมาณเชิงเส้นแบบแบ่งช่วงของลอการิทึม เส้นระหว่างจุดข้อมูลไม่ได้มีอยู่จริง

• อ้างอิง Wikipedia: มีการอธิบายฟังก์ชันนี้และประวัติของมันไว้ใน Wikipedia อย่างดี ลิงก์ Wikipedia

• รวมโค้ดบน GitHub: มีการรวบรวมโค้ดที่เกี่ยวข้องไว้บางส่วนบน GitHub ลิงก์ GitHub

• อ้างอิง StackOverflow: คำถามบน StackOverflow เกี่ยวกับ optimized low-accuracy approximation ก็น่าอ่านเช่นกัน ลิงก์ StackOverflow

• ประสบการณ์ด้านการปรับแต่ง 3D engine: เคยสร้าง 3D engine ตั้งแต่ก่อนยุค Quake และสั่งสมประสบการณ์ด้านการปรับแต่ง โดยอัลกอริทึมที่ปรับแต่งดีมักชนะเสมอ

• แนะนำวิดีโอ YouTube: มีวิดีโอที่น่าสนใจเกี่ยวกับหัวข้อนี้ ลิงก์ YouTube

• ตัวขโมยเวลาแห่งประสิทธิภาพการทำงาน: เคยหมกมุ่นกับหัวข้อนี้จนเสียเวลาในการทำงานไปมาก

• เลขมหัศจรรย์ที่เหมาะสมที่สุด: เลขมหัศจรรย์ในโค้ดสั้นชื่อดังไม่ใช่ค่าคงที่ที่เหมาะสมที่สุด ยังสามารถหาค่าคงที่ที่ดีกว่าได้ และสามารถใช้ Jupyter notebook เพื่อหาเลขมหัศจรรย์ที่เหมาะสมที่สุด