Thuật toán toán học nhanh hơn hi sinh độ chính xác

Question

Tôi đang phát triển trò chơi gọi rất nhiều hàm toán học cho vật lý và hiển thị. "Fast inverse sqrt" được sử dụng trong Quake3 được biết là nhanh hơn sqrt() và nền của nó là đẹp.

Bạn có biết bất kỳ thuật toán nào khác nhanh hơn thuật toán thông thường với mức độ mất chính xác chấp nhận được không?

Answer 1

Các thuật toán này được gọi là "thuật toán xấp xỉ" trong tài liệu. Cuốn sách tiêu chuẩn với nhiều ví dụ là Approximation Algorithms by Vijay V. Vazirani.

Trường hợp tội lỗi x ~~ x là trường hợp đặc biệt chung hơn: Nhìn vào Taylor series (hoặc chuỗi Fourier trong trường hợp chức năng định kỳ) của hàm và chỉ tính một vài thuật ngữ đầu tiên.

Kỹ thuật khác (hơi tàn bạo) là tập hợp ngẫu nhiên một vài điểm chức năng của bạn và sau đó chạy hồi quy tuyến tính đối với nó. Bằng cách đó, bạn có thể nhận được một đa thức tốt mô tả chức năng của bạn, quá :).

Answer 2

cho nhỏ x: sin (x) ~ = x là một trong đó thường được sử dụng trong vật lý

Answer 3

Bất cứ điều gì xác suất thường như thế này. Chạy mô phỏng 10 lần sẽ nhanh hơn, nhưng cho kết quả kém chính xác hơn so với chạy mô phỏng 1000 lần.

Answer 4

Niko có một số gợi ý tốt mà tôi muốn thêm bảng thời trang cũ vào bảng.

Tôi đã sử dụng bảng tra cứu các hàm tròn (sin/cos/tan) thành công nhiều lần trong systesm thời gian thực hiệu suất cao. Các sqrt() là khó hơn theo cách này, nhưng nếu phạm vi đầu vào của bạn bị hạn chế (để nói pixel màn hình) thật khó để đánh bại cho tốc độ, và bạn có thể điều chỉnh không gian/độ chính xác thương mại tắt chính xác. Bạn cũng có thể sử dụng tìm kiếm một phạm vi phổ biến, và sau đó có một fallout để một khuôn khổ sqrt() chức năng cho trường hợp hiếm hoi.

Paul

Answer 5

Bất kỳ chức năng liên tục (trong đó bao gồm các hoạt động toán học phổ biến nhất) có thể xấp xỉ hơn một khoảng thời gian bị chặn bởi một đa thức. Điều này, cùng với các định danh tương đối đơn giản mà các hàm toán phổ biến thường đáp ứng (như các luật bổ sung) và tra cứu bảng, cung cấp cơ sở của các kỹ thuật chuẩn để xây dựng các thuật toán xấp xỉ nhanh (và cũng là cơ sở của các phương pháp chính xác cao như các phương pháp được sử dụng trong toán học hệ thống. thư viện).

Chuỗi Taylor thường là lựa chọn kém; Các đa thức Chebyshev hoặc Minimax có nhiều đặc tính lỗi tốt hơn cho hầu hết các công dụng tính toán. Kỹ thuật tiêu chuẩn cho các đa thức minimax là sử dụng thuật toán Remes, được thực hiện trong rất nhiều phần mềm toán học thương mại, hoặc bạn có thể triển khai thực hiện của riêng bạn với công việc trong ngày nếu bạn biết bạn đang làm gì.

Đối với hồ sơ, các "nghịch đảo nhanh vuông gốc" nên tránh trên bộ vi xử lý hiện đại, vì nó là đáng kể nhanh hơn để sử dụng một dấu chấm động căn bậc hai đối ứng hướng dẫn dự toán (rsqrtss/rsqrtps trên SSE, vrsqrte trên NEON, vrsqrtefp trên AltiVec). Ngay cả phần gốc của phần cứng (không gần đúng) là khá nhanh trên các bộ xử lý Intel hiện tại.

Answer 6

Từ mã nguồn Doom, cho khoảng cách tương đối giữa hai điểm 2D mà không cần phải sử dụng sqrt() hoặc hàm lượng giác:

fixed_t P_AproxDistance(fixed_t dx, fixed_t dy) 
{ 
    dx = abs(dx); 
    dy = abs(dy); 
    if (dx < dy) 
     return dx+dy-(dx>>1); 
    else 
     return dx+dy-(dy>>1); 
} 

Lưu ý rằng x >> 1 cũng giống như x/2 nhưng nhanh hơn một chút - trình biên dịch hiện đại tốt làm điều này tự động ngày nay nhưng sau đó họ không tuyệt vời như vậy.