Phân chia số nguyên nhanh hơn khi mẫu số được biết?

Question

Tôi đang làm việc trên thiết bị GPU có độ trễ số nguyên phân chia rất cao, vài trăm chu kỳ. Tôi đang tìm cách tối ưu hóa các bộ phận.

Tất cả các bộ phận theo mẫu số trong tập hợp {1,3,6,10}, tuy nhiên tử số là giá trị dương thời gian chạy, khoảng 32000 trở xuống. do hạn chế về bộ nhớ, bảng tra cứu có thể không phải là một lựa chọn tốt.

Bạn có thể nghĩ lựa chọn thay thế không? Tôi đã nghĩ về tính toán điểm phao inverses, và sử dụng chúng để nhân tử số.

Cảm ơn

PS. cảm ơn mọi người. bit shift hack là một thực sự mát mẻ. để phục hồi từ roundoff, tôi sử dụng sau đây phân khúc C:

hệ thống

// q = m/n 
q += (n*(j +1)-1) < m; 

Answer 1

a/b=a*(1/b) 
x=(1<<16)/b 
a/b=(a*x)>>16 

bạn có thể tạo bảng tra cứu cho mẫu số không? kể từ khi bạn nói 15 tử số bit, bạn có thể sử dụng 17 cho sự thay đổi nếu mọi thứ đều unsigned 32 bit:

a/b=a*((1<<17)/b)>>17 

càng lớn thì sự thay đổi càng ít lỗi làm tròn. Bạn có thể kiểm tra sức mạnh vũ phu để xem có bao nhiêu lần, nếu có, điều này thực sự là sai.

Answer 2

Các tiêu chuẩn nhúng hack này là để chuyển đổi một bộ phận nguyên bởi N thành một nhân điểm cố định bằng 1/N.

Giả sử 16 bit, 0.33333 có thể được biểu diễn là 21845 (thập phân). Nhân, cho ra một sản phẩm nguyên 32 bit, và dịch chuyển xuống 16 bit.

Bạn gần như chắc chắn sẽ gặp phải một số lỗi ngắt (cắt ngắn). Điều này có thể hoặc không thể là thứ bạn có thể sống cùng.

Điều quan trọng là phải xem xét kỹ GPU của bạn và xem liệu bạn có thể viết mã thủ tục phân chia số nguyên nhanh hơn hay không, tận dụng kiến ​​thức của bạn về phạm vi hạn chế của tử số.

Answer 3

Cuốn sách, "Hacker's Delight" by Henry Warren, có toàn bộ chương dành cho phân chia số nguyên theo hằng số, bao gồm các kỹ thuật biến đổi phân chia số nguyên thành chuỗi hoạt động nhân/chuyển/thêm.

trang này tính toán những con số kỳ diệu cho nhân/ca/​​thêm hoạt động:

• http://www.hackersdelight.org/magic.htm