Vì sao thuật toán CORDIC lại sống miễn phí trong tâm trí tôi
Tránh Floating Point bằng cách dùng Fixed Point
- Dùng Fixed Point thay vì Floating Point vẫn có thể biểu diễn số thực
- Sử dụng số nguyên 32 bit, chia 16 bit trên cho phần nguyên và 16 bit dưới cho phần thập phân
- Nhờ đó có thể biểu diễn xấp xỉ từ -32768.99997 đến 32767.99997
- Lập trình viên có thể chỉ định vị trí dấu chấm để điều chỉnh độ chính xác
- Để chuyển Float sang Fixed Point, nhân với 2^16 rồi ép kiểu sang
int32_t
- Để chuyển Fixed Point sang Float, chia cho 2^16
- Phép cộng và trừ hoạt động như bình thường, còn phép nhân và chia thì cần điều chỉnh Scaling Factor
Tổng quan về thuật toán CORDIC
- CORDIC là viết tắt của "Co-ordinate Rotation Digital Computer", được phát triển vào giữa những năm 1950
- Đây là phương pháp tìm giá trị sin và cos bằng cách quay dần một vector trên đường tròn đơn vị qua các góc nhỏ hơn
- Tương tự tìm kiếm nhị phân, trước hết di chuyển theo góc lớn để tiến gần góc mục tiêu, rồi giảm dần một nửa góc theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ để hội tụ
- Đặt góc quay tối đa là 90 độ (
π/2 radian) và lặp 16 lần để hội tụ gần góc mục tiêu
- Khi hội tụ, giá trị y của vector xấp xỉ
sin(a), còn giá trị x xấp xỉ cos(a)
Đơn giản hóa ma trận để chỉ dùng phép nhân hằng số
- Ma trận quay chứa các hàm sin, cos và tan nên việc tính toán khá phức tạp
- Vì hàm tan quay theo các góc cố định, có thể tính trước và lưu trong bảng (khoảng 64 byte)
- Thành phần cos xuất hiện ở mọi vòng lặp, nhưng giá trị hội tụ của nó là một hằng số (xấp xỉ 0.6366), nên chỉ cần nhân một lần ở cuối
Chỉ dùng các phép Shift và Add
- Chọn các góc dùng trong hàm tan bằng hàm arctangent sao cho có dạng giá trị
2^-i
- Nhờ đó có thể thay phép nhân bằng phép dịch bit
- Giá trị hội tụ của thành phần cos cũng được tính lại thành xấp xỉ 0.60725, và được đặt làm giá trị x ban đầu của vector
- Mỗi vòng lặp của thuật toán CORDIC được đơn giản hóa như sau
- Nếu z lớn hơn hoặc bằng 0 thì quay ngược chiều kim đồng hồ (trừ
y>>i khỏi x, cộng x>>i vào y)
- Nếu z nhỏ hơn 0 thì quay theo chiều kim đồng hồ (cộng
y>>i vào x, trừ x>>i khỏi y)
- Cập nhật z bằng cách trừ hoặc cộng giá trị góc từ bảng
- Nhờ vậy có thể tính các hàm lượng giác chỉ bằng phép nhân hằng số, dịch bit và cộng
Ý kiến của GN⁺
- CORDIC có vẻ là một thuật toán hữu ích trong các môi trường có tài nguyên phần cứng hạn chế như hệ thống nhúng hoặc FPGA. Đặc biệt, đây là một phương án đáng cân nhắc khi không hỗ trợ phép toán dấu phẩy động.
- Ý tưởng chọn chiến lược các góc của hàm tan để thay phép nhân bằng dịch bit rất ấn tượng. Đây là một ví dụ hay cho sự kết hợp giữa trực giác toán học và hiểu biết về kiến trúc máy tính.
- Điểm thú vị nữa là nó có thể được dùng không chỉ cho các hàm lượng giác mà còn cho nhiều phép tính khác như log, hàm mũ và căn bậc hai. Có lẽ cũng nên tìm hiểu thêm về thuật toán liên quan là BKM.
- Tuy nhiên, trên phần cứng hiện đại thường đã có sẵn FPU, và khi dùng phép toán fixed-point có thể xảy ra mất mát độ chính xác, nên cần cẩn trọng khi áp dụng.
- Nếu là hệ thống phải thực hiện rất nhiều phép tính tương tự, có lẽ cũng đáng cân nhắc thiết kế phần cứng chuyên dụng cho CORDIC.
1 bình luận
Ý kiến Hacker News
Thuật toán CORDIC có thể được dùng không chỉ cho FPGA mà còn trong phát triển game hoặc mô phỏng vật lý phân tán. Tính toán dấu phẩy động khó bảo đảm hành vi tất định giữa các nền tảng, nên một cách giải quyết là xây dựng engine vật lý dấu phẩy cố định và triển khai các hàm lượng giác bằng CORDIC.
CORDIC có thể được dùng cho nhiều phép toán khác nhau ngoài sin và cos, như log, số mũ, căn bậc hai, độ lớn vector, chuyển đổi giữa tọa độ cực và tọa độ Descartes, cũng như xoay vector. Nếu dùng quaternion thì có vẻ có thể thực hiện các phép toán dựa trên CORDIC hiệu quả và chính xác hơn.
Có người chia sẻ trải nghiệm từng học về cách máy tính cầm tay triển khai hàm lượng giác trong lớp tiền giải tích ở trung học, rồi phát hiện ra đó thực ra là CORDIC chứ không phải chuỗi Taylor, sau đó tự cài đặt bằng TI Basic.
Tính đến năm 2023, ngay cả các MCU giá rẻ như STM32G4 cũng đã tích hợp FPU, nên có thể thoải mái dùng dấu phẩy động thay vì dấu phẩy cố định. Tuy vậy, G4 vẫn có cả thiết bị ngoại vi CORDIC được triển khai bằng phần cứng chuyên dụng, có vẻ là để tránh mất độ chính xác của dấu phẩy động.
Có vẻ phần giải thích rằng phép quay 22.75° tương đương quay 45° rồi quay -22.5° là bị sai. Có lẽ phải là 22.5° mới đúng.
Hệ thống octree của Meagher được triển khai chỉ bằng phép toán số nguyên, không cần nhân/chia số nguyên. Điều này giúp việc chế tạo phần cứng tăng tốc đồ họa VLSI nhanh và thiết kế riêng cho biểu diễn octree trở nên dễ dàng hơn.
Có thể xem CORDIC là một khái niệm tương tự dãy Farey cho góc (hoặc mediant, phép cộng phân số ngây thơ).
CORDIC cũng đã được triển khai trên các máy tính cầm tay HP lập trình được đời cũ dùng CPU 4-bit. Cách xấp xỉ bằng khai triển Taylor của hàm sin cũng có thể lập trình được.
Nếu thích bài này thì cũng nên đọc "The Art of Computer Programming", tác phẩm kinh điển của Donald Knuth giải thích các thuật toán toán học kèm ví dụ.
CORDIC là một thuật toán từng rất được ưa chuộng trong lĩnh vực DSP trước đây.
Đây là một thuật toán tuyệt vời, và có vẻ sẽ hữu ích để chạy mạng nơ-ron trên phần cứng hiệu năng thấp.