Thư viện số nguyên 128 bit nhanh nhất

Question

Tôi đang làm việc trên ứng dụng tính toán số CPU nặng. Không đi vào nhiều chi tiết, đó là một dự án nghiên cứu toán học tính toán liên quan đến việc tính toán một hàm nhất định f (x) cho số nguyên lớn x.

Ngay bây giờ mọi thứ được triển khai trong C++ ở chế độ x64, sử dụng int 64 bit gốc. Điều đó giới hạn tôi thành x < 2^64 ~ 1,8 * 10^19. Tôi muốn đi xa hơn, để làm điều đó, tôi cần một thư viện có số học 128 bit. Và nó phải rất nhanh. Đặc biệt, các phân số nguyên phải nhanh. Nếu không, tôi sẽ ngồi đây đợi kết quả cho đến Lễ Tạ Ơn. Và tôi không muốn sáng tạo lại bánh xe.

Tôi đã tìm thấy danh sách ~ 20 thư viện số nguyên lớn trên Wikipedia, nhưng hầu hết các thư viện này dường như được nhắm mục tiêu theo các số có độ chính xác tùy ý, quá tải cho nhiệm vụ của tôi và tôi không cần thêm chi phí.

Có ai biết thư viện nào có thể hoạt động trên số nguyên 128 bit nhanh nhất không?

Answer 1

Bạn không đề cập đến các yêu cầu về nền tảng/tính di động của mình. Nếu bạn sẵn sàng sử dụng gcc hoặc clang, trên nền tảng 64 bit, chúng có sẵn các loại 128 bit được cung cấp miễn phí, __uint128_t và __int128_t. Có thể các nền tảng khác có phần mở rộng kiểu tương tự.

Trong mọi trường hợp, bạn có thể tìm mã chung tương ứng trong các nguồn gcc lắp ráp hai số nguyên chiều rộng N để tổng hợp một số nguyên chiều rộng 2N. Điều này có lẽ sẽ là một điểm khởi đầu tốt để tạo một thư viện độc lập cho mục đích đó.

Answer 2

Điều này có thể không dành cho tất cả mọi người, nhưng những gì tôi sẽ làm là chọn thư viện số nguyên tùy ý hiệu suất cao nhất với mã nguồn và phù hợp với công việc, và hack nó cho kích thước nguyên cố định. Thay đổi một số biến "nbits" thành 128 mã hóa cứng. Nó có thể phân bổ bộ nhớ trong thời gian chạy, không biết số byte cho đến lúc đó. Thay đổi nó để sử dụng struct với dữ liệu tại chỗ, lưu dereferencing con trỏ mỗi khi dữ liệu được đọc. Mở một số vòng quan trọng nhất định bằng tay. Hard-code bất cứ điều gì khác mà có thể là quan trọng. Sau đó, trình biên dịch sẽ có một thời gian dễ dàng hơn tối ưu hóa mọi thứ. Tất nhiên, phần lớn sẽ được lắp ráp, sử dụng SIMD ưa thích với bất kỳ công nghệ nào được sử dụng trong tuần này.

Sẽ rất thú vị! Nhưng sau đó, với tư cách là một lập trình viên, tôi bắt đầu với mã máy và các công cụ cấp độ rất thấp.

Nhưng đối với những người không điên như tôi, có lẽ một trong những thư viện có sẵn sử dụng mẫu hoặc có một số phương tiện tạo mã tùy chỉnh cho một số kích thước. Và, một số trình biên dịch có loại số nguyên "dài" có thể phù hợp.

Answer 3

Thư viện ttmath làm những gì bạn muốn.