1

Bài đăng trước đây của tôi  về Câu hỏi của Gelfand đã  xem xét một vấn đề đòi hỏi phải liên tục tìm chữ số đầu tiên của  k n  trong đó k  là một chữ số duy nhất nhưng  n  có thể theo thứ tự hàng triệu hoặc hàng tỷ.

Cách tiếp cận trực tiếp nhất sẽ là đầu tiên tính  k n  là một số nguyên rất lớn, sau đó tìm chữ số đầu tiên. Cách tiếp cận đó chậm, và chậm hơn khi  n  tăng. Một cách nhanh hơn là nhìn vào phần phân đoạn của log  k n  =  n  log  k  và xem nó tương ứng với chữ số nào.

Nếu  n  không quá lớn, điều này có thể được thực hiện với độ chính xác thông thường. Nhưng khi  n  lớn, nhân log k  với  n  và lấy phần phân số mang lại các chữ số ít có ý nghĩa hơn. Vì vậy, đối với n rất lớn  , bạn cần thêm độ chính xác. Lần đầu tiên tôi đã làm điều này trong Python bằng SymPy, sau đó chuyển sang C ++ để có thêm tốc độ. Ở đó tôi đã sử dụng  quadmath thư viện cho  gcc. (Nếu  n  là đủ lớn, thậm chí chính xác bốn là không đủ. Một lợi thế để SymPy hơn  quadmath là trước đây có  độc đoán chính xác. Bạn có thể, ví dụ, thiết lập chính xác là 10 nhiều hơn số chữ số thập phân trong  n để giữ lại 10 số liệu có ý nghĩa trong phần phân số của  n  log  k .)

Các  quadmath.h tập tin tiêu đề cần phải được bọc trong một  extern C tuyên bố. Nếu không  gccsẽ cung cấp cho bạn thông báo lỗi gây hiểu lầm.

Loại dấu phẩy động 128 bit  __float128 có số bit gấp đôi a  double. Các  quadmathchức năng có cùng tên với các math.h đối tác tiêu chuẩn  của chúng, nhưng có  q thêm vào cuối, chẳng hạn như  log10q và  fmodq bên dưới.

Đây là mã để tính toán chữ số hàng đầu của  k n  minh họa bằng cách sử dụng  quadmath.

#include <cmath>
extern "C" {
#include <quadmath.h>
}
 
__float128 logs[11];
 
for (int i = 2; i <= 10; i++)
    logs[i] = log10q(i + 0.0);
 
int first_digit(int base, long long exponent)
{
    __float128 t = fmodq(exponent*logs[base], 1.0);
    for (int i = 2; i <= 10; i++)
        if (t < logs[i])
            return i-1;
}

Mã luôn trả về vì  t nhỏ hơn 1.

Lưu các giá trị  log10q lưu các cuộc gọi lặp lại vào một chức năng tương đối đắt tiền. Vì vậy, sử dụng tìm kiếm ở phía dưới hơn là máy tính  powq(10, t).

Tìm kiếm tuyến tính ở cuối là hiệu quả hơn nó có vẻ. Đầu tiên, nó chỉ tìm kiếm một danh sách có độ dài 9. Thứ hai, vì luật của Benford, các chữ số hàng đầu được tìm kiếm theo thứ tự tần số giảm, tức là hầu hết các đầu vào sẽ khiến  first_digit bạn quay lại sớm trong tìm kiếm.

Khi bạn biên dịch mã bằng cách sử dụng  quadmath, hãy chắc chắn để thêm  -lquadmath vào lệnh biên dịch.

|