- CORDIC là thuật toán dùng để tính các hàm lượng giác như
sin, cos, tan mà không cần FPU hay bảng tra cứu lớn, bằng cách chuyển các phép toán phức tạp sang chủ yếu là phép cộng và dịch bit
- Cách này hữu ích trong môi trường nhúng, đặc biệt là các vi điều khiển hiệu năng thấp và FPGA, hơn là trong các hệ thống hiệu năng cao; khó đánh giá giá trị của nó chỉ bằng tốc độ
- Nếu dùng số cố định dấu phẩy thay cho số dấu phẩy động, có thể chia
int32_t thành 16 bit cao làm phần nguyên và 16 bit thấp làm phần thập phân, biểu diễn khoảng từ -32768.99997 đến 32767.99997
- Bằng cách xoay vector theo các góc ngày càng nhỏ để tiến đến góc mục tiêu, dùng 16 mục trong bảng
atan(2**-i) và giá trị khởi tạo x=39796, có thể thay phép nhân ở mỗi vòng lặp bằng dịch bit
- Với góc ví dụ
0.9152, sau 16 vòng lặp, sai số tuyệt đối của sin(0.9152) giảm xuống khoảng 0.00000956, còn sai số tuyệt đối của cos(0.9152) khoảng 0.0000434
Môi trường tính toán phù hợp với CORDIC
- CORDIC là thuật toán để tính các hàm lượng giác như
sin, cos, tan trên phần cứng tiêu thụ điện năng thấp
- Nó vẫn hoạt động trong môi trường không có FPU, tức bộ xử lý dấu phẩy động, hoặc khó dùng bảng tra cứu lớn
- Các phép toán thực tế chủ yếu gồm phép cộng đơn giản và dịch bit
- Nó kết hợp toán vector, lượng giác, sự hội tụ và các ý tưởng khoa học máy tính để xấp xỉ những hàm phức tạp bằng các phép toán đơn giản
- Trên phần cứng hiệu năng cao, kỹ thuật này có thể không thật sự cần thiết
- Đối tượng áp dụng chính là môi trường nhúng
- Đặc biệt phù hợp với vi điều khiển hiệu năng thấp và FPGA
- Có thể có phần cứng hoặc ngoại vi nhanh hơn, nhưng tốc độ không phải thước đo duy nhất cho tính hữu ích
Biểu diễn số cố định dấu phẩy để tránh số dấu phẩy động
- Ngay cả các hàm trả về giá trị trong khoảng từ
-1.0 đến 1.0 như sin(x) cũng không nhất thiết phải biểu diễn bằng số dấu phẩy động
- Số cố định dấu phẩy biểu diễn số hữu tỉ bằng cách cố định vị trí dấu thập phân bên trong một kiểu số nguyên
- Ví dụ chia
int32_t thành 16 bit cao làm phần nguyên và 16 bit thấp làm phần thập phân
- Khi đó phạm vi xấp xỉ từ
-32768.99997 đến 32767.99997
- Tùy đặt vị trí dấu thập phân ở đâu, có thể đánh đổi giữa phạm vi phần nguyên và độ chính xác phần thập phân
- Bản thân giá trị vẫn là
int32_t, còn lập trình viên gán thêm ý nghĩa cho mảng bit đó
Chuyển đổi số cố định dấu phẩy và các phép toán cơ bản
- Nếu độ chính xác phần thập phân là 16 bit, có thể nhân một giá trị float như
42.01 với (1 << 16) để tạo giá trị cố định dấu phẩy
42.01 * (1 << 16) khi ép kiểu sang int32_t sẽ thành 2753167- Để đổi lại sang float, tính
2753167 / (1 << 16) và nhận được khoảng 42.0099945
- Cũng có thể mã hóa trực tiếp một giá trị như
1.5 mà hoàn toàn không dùng số dấu phẩy động
- Phần nguyên
1 được nâng lên bằng (1 << 16)
- Một nửa phần thập phân có thể đặt là
0x7fff, giá trị nằm giữa 0x0000 và 0xffff
- Kết quả của cách này là số thập phân
98303
- Với các giá trị dùng cùng hệ số scale, phép cộng và phép trừ hoạt động như bình thường
- Với phép nhân, sau khi nhân hai giá trị cố định dấu phẩy, dịch kết quả sang phải lại theo hệ số scale
- Với phép chia, có thể đạt thêm độ chính xác bằng cách dịch trái số bị chia trước theo hệ số scale rồi chia cho số chia
Xấp xỉ hàm lượng giác bằng xoay vector
- CORDIC là viết tắt của “co-ordinate rotation digital computer”, được tạo ra vào giữa thập niên 1950
- Ý tưởng cốt lõi là xoay một vector trên đường tròn đơn vị theo các góc ngày càng nhỏ, sao cho khi đạt đến góc mục tiêu, các thành phần của vector trở thành giá trị sin và cos
- Quá trình này diễn ra tương tự tìm kiếm nhị phân
- Di chuyển một góc lớn về phía góc mục tiêu
- Kiểm tra xem đã đi quá mục tiêu chưa
- Sau đó lặp lại việc xoay theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ với góc nhỏ hơn
- Ví dụ khi tính
sin(0.7), bắt đầu với vector ban đầu (1, 0) và mục tiêu 0.7 radian
- Trước tiên xoay ngược chiều kim đồng hồ
0.7853 radian, tức 45˚
- Phần mục tiêu còn lại là
0.7 - 0.7853 = -0.0853
- Vì giá trị âm, lần tiếp theo xoay theo chiều kim đồng hồ
0.3926 radian, tức 22.5˚
- Sau đó tiếp tục đổi hướng xoay theo dấu của phần mục tiêu còn lại, với các góc nhỏ hơn như
0.1963 radian
- Sau 16 vòng lặp, vector gần như khớp với góc mục tiêu ban đầu,
y trở thành xấp xỉ của sin(a), còn x là xấp xỉ của cos(a)
Giảm các phép toán đắt đỏ trong ma trận xoay
- Phép xoay vector thông thường dùng phép nhân ma trận có chứa sin và cos
- CORDIC dùng các đồng nhất thức lượng giác để chuyển ma trận xoay sang xoay quanh
tan(a)
- Ban đầu dùng các góc xoay cố định như
45˚, 22.5˚, 11.25˚, nên có thể đặt giá trị tan(a) trong một bảng đã tính trước
- Bảng này chỉ cần 16 giá trị
uint32_t, tức 64 byte
- Để so sánh, một bảng
sin(x) chưa tối ưu chứa 4096 giá trị từ -1 đến 1 cần 16KiB và được xem là có độ chính xác thấp
- Thành phần
cos(a) đứng trước mỗi phép xoay xuất hiện ở từng vòng lặp, nhưng tích của tất cả chúng hội tụ thành một hằng số
- Khi dùng các góc kiểu
45˚, 22.5˚, 11.25˚, tích này khoảng 0.6366
- Chỉ cần nhân hằng số này một lần sau tất cả các vòng lặp
Chọn góc để chỉ còn dịch bit và phép cộng
- Để loại bỏ phép nhân, chọn góc sao cho kết quả
tan(a) luôn là lũy thừa nghịch đảo của 2
- Để làm vậy, tạo bảng 16 mục chứa giá trị
atan(2**-i) cho mỗi vòng lặp từ i=0 đến 15
- Các góc xoay thực tế lần lượt là
45˚, 26.565˚, 14.036˚, 7.125˚, v.v.
- Dù các góc không giảm chính xác một nửa, dùng những góc này quá trình vẫn hội tụ về kết quả đúng
- Phép nhân với
tan(a) được thay bằng dịch bit theo số thứ tự vòng lặp i
- Tích của các thành phần
cos(a) cũng được tính lại theo cách chọn góc mới
- Giá trị khoảng
0.60725
- Với số cố định dấu phẩy 16 bit, giá trị này là
39796
- Thay vì nhân ở cuối, chỉ cần đặt
x của vector ban đầu là 39796 thay vì 1
Quy trình thuật toán
- Ở bước tính trước, tạo bảng trong đó mỗi mục là
atan(2**-i), rồi chuyển từng giá trị sang số cố định dấu phẩy
- Công thức chuyển đổi là
atan(2**-i) * (1 << 16)
- Khi cần tính
sin hoặc cos, cũng đổi góc đầu vào sang số cố định dấu phẩy
- Ví dụ
0.9152 trở thành 0.9152 * (1 << 16) = 59978
- Trạng thái ban đầu như sau
x = 39796
y = 0
z = 59978
z không phải một phần của vector, mà là giá trị theo dõi góc mục tiêu còn lại- Dấu của
z quyết định hướng xoay
- Nếu
z >= 0, xoay ngược chiều kim đồng hồ và thực hiện z -= table[i]
- Nếu
z < 0, xoay theo chiều kim đồng hồ và thực hiện z += table[i]
- Mỗi vòng lặp chỉ dùng cộng, trừ và dịch
>> i cho x và 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
Kết quả hội tụ ví dụ và các chủ đề còn lại
- Trong ví dụ
0.9152 radian, ở vòng lặp đầu tiên z dương nên vector xoay ngược chiều kim đồng hồ khoảng 0.785 radian
- Ở vòng lặp thứ hai,
z vẫn dương nên tiếp tục xoay ngược chiều kim đồng hồ khoảng 0.436 radian, nhưng vượt qua mục tiêu
- Ở vòng lặp thứ ba,
z trở thành âm nên xoay theo chiều kim đồng hồ khoảng 0.244 radian
- Vòng lặp thứ tư cũng có
z âm nên xoay theo chiều kim đồng hồ khoảng 0.124 radian
- Khi biến thiên góc nhỏ dần, vector dao động quanh kết quả thực và hội tụ
- Sau 16 vòng lặp,
y trở thành một xấp xỉ rất gần của sin(0.9152)
- Sai số tuyệt đối của sin là
0.00000956
- Sai số tuyệt đối của cos ở
x là 0.0000434
- Vẫn còn một số chủ đề chưa đề cập
- Xử lý đặc biệt cần thiết khi góc quan tâm nằm ngoài góc phần tư thứ nhất hoặc thứ tư của đường tròn đơn vị
- Các biến thể CORDIC có thể tính
tan, atan, asin, acos, sinh, cosh, tanh, sqrt, ln, e^x
- Thuật toán liên quan BKM, được thiết kế để tính logarit và hàm mũ
- Dự kiến sẽ trình bày chi tiết hơn nội dung liên quan trên kênh YouTube Low Byte Productions
1 bình luận
Ý kiến trên Hacker News
Tác giả nói rằng nó chủ yếu được áp dụng ở những nơi như FPGA, nhưng cũng có thể dùng 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 rất khó bảo đảm tính quyết định giữa các nền tảng, và một cách giải quyết là tránh hẳn dấu phẩy động để triển khai một engine vật lý dùng dấu phẩy cố định
Để triển khai các hàm lượng giác thì cần thứ gì đó như CORDIC
Vài năm trước tôi từng bắt đầu làm một thứ như vậy cho vui, nhưng không hoàn thành; một ngày nào đó tôi muốn thử lại
https://randomascii.wordpress.com/2013/07/16/floating-point-...
Tóm lại, x87 có những điểm kỳ lạ; cần đặt nhất quán các thiết lập như chế độ làm tròn và flush-to-zero; các bộ xử lý cũ không có FMA; các lệnh xấp xỉ như
mmsqrtpskhông có đặc tả nhất quán; và trình biên dịch có thể tái kết hợp biểu thứcVới các routine nhỏ hoặc thư viện tự viết, dù khá đau đầu, vẫn có thể bảo đảm tránh được những vấn đề này
IEEE-754 2008 đã làm đặc tả rõ ràng hơn và trên thực tế giả định sự cáo chung của x87; đến năm 2024 thì có thể chắc chắn tránh x87
FMA cũng là một phần của đặc tả IEEE-754 2008, và có mặt trong các bộ xử lý hiện đại, bao gồm từ Intel Haswell trở về sau
Dù vậy, khác biệt kiến trúc như AVX2 8-wide và NEON 4-wide vẫn có thể gây vướng, nhưng nếu dùng assembly, intrinsic, hoặc C được kiểm tra bằng Compiler Explorer hay objdump, ta có thể nhìn vào đầu ra và đánh giá rằng “cái này sẽ nhất quán”
“Thực ra, trước khi IEEE 754 trở thành một chuẩn phổ biến như ngày nay, dấu phẩy cố định luôn được dùng. Hãy hỏi một nhà phát triển game từng làm việc trong khoảng từ năm 1980 đến khoảng năm 2000, họ sẽ kể chi tiết cho bạn”
Rapier, thư viện mới viết lại từ nphysics, thay vào đó dựa vào các bảo đảm của IEEE-754 2008 để cung cấp tính quyết định giữa các nền tảng
Vì vậy nó không chạy trên các nền tảng cũ, nhưng có tính quyết định trên các nền tảng hiện đại, bao gồm wasm
Tất nhiên không thể phụ thuộc vào các routine hàm siêu việt như sin, cos do từng nền tảng cung cấp; phải tự triển khai sao cho chúng hoạt động giống nhau ở mọi nơi
Nhưng nếu không chạy trên nền tảng không tuân thủ chuẩn, đây là một hướng tiếp cận khả thi
https://www.rustsim.org/blog/2020/06/01/this-month-in-rustsi...
https://rapier.rs/docs/user_guides/rust/determinism/
CORDIC có thể được dùng không chỉ để tính/sinh sin và cos, mà còn cho nhiều phép toán khác như logarit, hàm mũ, căn bậc hai, độ lớn vector, chuyển đổi tọa độ cực–tọa độ Descartes, và quay vector
Tác giả cũng gợi mở những khả năng này ở phần kết luận
Tôi có cảm giác rằng nếu dùng quaternion thay cho các ma trận trực chuẩn truyền thống, các phép toán dựa trên CORDIC có thể chạy hiệu quả hơn, tức là tốn ít chu kỳ tính toán và bộ nhớ hơn, đồng thời giảm sai số
https://core.ac.uk/works/8439118
Ở lớp tiền giải tích trung học, tôi đã học về chuỗi Taylor, và giáo viên nói rằng các hàm lượng giác trong máy tính bỏ túi thực sự được triển khai như vậy
Tìm hiểu thì hóa ra thực tế là CORDIC, và tôi đã thử triển khai bằng TI Basic khá vui
Nó không phải CORDIC, nhưng thuật toán có những điểm tương đồng
http://files.righto.com/calculator/sinclair_scientific_simul...
Các bài viết liên quan đến triển khai phần cứng:
https://arxiv.org/pdf/2211.04053
https://hal.science/hal-01327460/document
https://archive.ll.mit.edu/HPEC/agendas/proc05/Day_1/Abstrac...
Muốn xem nó được so sánh thế nào với các cách triển khai hàm lượng giác phần mềm/phần cứng thông thường trên nhiều loại phần cứng qua từng thời kỳ
IoT và giao tiếp giữa máy với máy đang phát triển, và xét đến triển khai CORDIC cùng hiệu quả tính toán, mức sử dụng có lẽ sẽ tăng mạnh, nên cần có tài liệu tham khảo tốt để triển khai đúng và tối ưu
Ngoại lệ là sách của Prof. Omondi và Prof. Deschamps
https://www.worldscientific.com/worldscibooks/10.1142/p1054
http://www.arithmetic-circuits.org/guide2fpga/vhdl_codes.htm
sin và cos thường được dùng để quay vector
Trong trường hợp này, mẹo của CORDIC là tránh phép tính sin/cos/nhân truyền thống, và đưa chính vector cần quay làm đầu vào cho CORDIC
Khi đó CORDIC trực tiếp tạo ra vector đã quay mà không cần tính sin/cos hay thực hiện phép nhân số phức
CORDIC đặc biệt tỏa sáng khi độ trễ không quá quan trọng
Nếu pipeline hóa từng bước của phép tính, có thể đạt throughput lớn, rất hợp với digital mixing trong các hệ thống vô tuyến
Tính đến năm 2023, một số MCU hiện đại vừa rẻ vừa có FPU
STM32G4 là một ví dụ tốt; khác với các MCU như M0, nếu không muốn dùng fixed-point thì có thể thoải mái dùng
f32Các chip như vậy có thể mua với giá khoảng 1–2 USD mỗi MCU
Tuy nhiên G4 cũng có một ngoại vi CORDIC phần cứng triển khai thuật toán này cho mục đích fixed-point
Tôi tò mò liệu nó chủ yếu dùng để tránh mất độ chính xác của floating-point hay không
Nó được lập trình qua thanh ghi, nhưng không phải CPU trực tiếp triển khai CORDIC; phần cứng chuyên dụng bên trong IC xử lý việc đó
STM32G4 rẻ nhất là STM32G441KBT6, làm tròn thì là 4 USD https://www.digikey.com/en/products/detail/microchip-technol...
Tôi tò mò không biết mua ở đâu được dưới 2 USD
Trên Digi-Key, chip Nuvoton chỉ vừa xuống dưới 2 USD ở mức số lượng 500 chiếc
Nó nhanh, xử lý tích trung gian 64-bit, nên độ chính xác của phép chia và hàm lượng giác đủ cho hầu hết mục đích sử dụng
Nếu cần, cũng có thể tăng độ chính xác thêm bằng phần mềm
Tôi biết đến CORDIC khá muộn; trước đó, trong thế giới assembly 8-bit/16-bit, tôi dùng fixed-point rất nhiều vì hiệu năng và tính quyết định
Khi biết rồi thì thấy kinh ngạc
Nó nhanh, và năng lực toán cần có để dùng hữu ích cũng chỉ là những kiến thức cơ bản
Tôi nhớ đến một đoạn code khá dễ thương mà trước đây từng tham gia
Cần tìm tọa độ đường phân giác của góc tạo bởi một cung trên đường tròn đơn vị, và tọa độ
(x,y)của hai cạnh đã có sẵnTriển khai cũ là một đống hàm lượng giác: đổi tọa độ
(x,y)sang tọa độ cực(r,θ), kiểm traθtính được có nằm đúng góc phần tư hay không, rồi chia đôiθvà đổi lại về(x,y)Kết quả là gọi rất nhiều hàm lượng giác và hàm ngược
Vì là Python nên có thể dùng số phức như kiểu dữ liệu hạng nhất; chỉ cần định nghĩa hai số phức
z1từ(x1,y1)vàz2từ(x2,y2), rồi lấy trung bình nhân của tích√(z1*z2)là xongTrong code mới không có hàm lượng giác tường minh nào, cũng không có phép biến đổi và biến đổi ngược tường minh nào
https://fgiesen.wordpress.com/2010/10/21/finish-your-derivat...
Có đoạn nói “việc quay 22,75˚ khá rõ ràng là giống như quay 45˚ rồi quay -22,5˚”, vậy chẳng phải là quay 22,5° sao?
Tôi tò mò không biết đó là lỗi của bài viết, hay tôi hiểu sai
Hệ thống octree của Meagher nổi tiếng vì chỉ dùng số học số nguyên, không dùng phép nhân/chia số nguyên
“Các thuật toán thời gian tuyến tính hiệu quả đã được phát triển cho việc hiển thị, bao gồm các phép toán Boolean (hợp, giao, hiệu), phép toán hình học (dịch chuyển, thay đổi kích thước, xoay), phát hiện giao thoa N chiều, và loại bỏ mặt khuất tại điểm bất kỳ trong không gian. Các thuật toán này không cần phép toán dấu phẩy động, phép nhân số nguyên hay phép chia số nguyên”
https://doi.org/10.1016/0146-664X(82)90104-6
Nhờ vậy, việc tạo phần cứng tăng tốc đồ họa VLSI tùy chỉnh nhanh cho biểu diễn octree trở nên dễ dàng hơn
Tôi tò mò CORDIC có hiệu năng thế nào so với nội suy bậc ba dùng bảng nhỏ hoặc các dạng nội suy đa thức khác
Tôi được biết rằng các bộ synthesizer bị giới hạn tài nguyên đôi khi dùng nội suy bậc ba, có lẽ là vào thời CORDIC còn tương đối mới
Nhìn đại khái thì CORDIC đạt thêm 1 bit độ chính xác sau mỗi vòng lặp, nên tính toán đắt hơn nhưng có vẻ dùng ít không gian hơn đa thức
Tuy nhiên, về mặt không gian, cần nhấn mạnh rằng nó có thể rẻ hơn bảng tra cứu 4096 mục cho
sin(x)được nêu trong bàiNhờ tính đối xứng, chỉ cần 1/4 toàn bộ đường tròn
Dùng góc kích thước byte thì tiện vì nó tự động tuần hoàn, và
2^8là khá đủ cho phép xoay trong game 2DTuy nhiên, nếu muốn chuyển động mượt thì trong 3D sẽ không đi được xa lắm