Độ phức tạp của chức năng nhật ký là gì?

Question

Độ phức tạp của cơ sở nhật ký là gì?

Answer 1

Điều này thực sự phụ thuộc vào miền của giá trị bạn muốn tính toán lôgarit.

Đối với IEEE đôi, nhiều bộ xử lý có thể lấy logarit trong một lệnh lắp ráp đơn; x86 có các chỉ dẫn FYL2X và FYL2XP1, ví dụ. Mặc dù thường hướng dẫn như thế này sẽ chỉ mất logarit ở một số cơ sở cố định, chúng có thể được sử dụng để lấy logarit trong các căn cứ tùy ý bằng cách sử dụng thực tế là

log _một b = log _c b/log _c a

đơn giản bằng cách lấy hai logarit và tìm thương.

Đối với các số nguyên chung (độ chính xác tùy ý), bạn có thể sử dụng bình phương lặp lại kết hợp với tìm kiếm nhị phân để nhận logarit chỉ sử dụng các phép tính số học O (log log n) (mỗi lần bạn đặt một số bạn tăng gấp đôi số mũ) bạn chỉ có thể viết nhật ký nhật ký số n lần trước khi bạn đã vượt quá giá trị của nó và có thể thực hiện tìm kiếm nhị phân). Sử dụng some cute tricks with Fibonacci numbers, bạn có thể thực hiện việc này chỉ trong không gian O (log n). Nếu bạn đang tính toán binary logarithm, có một số thủ thuật dễ thương bạn có thể sử dụng với các thay đổi bit để tính toán giá trị trong thời gian ngắn hơn (mặc dù độ phức tạp tiệm cận là như nhau).

Đối với các số thực tùy ý, logic khó hơn. Bạn có thể sử dụng phương pháp Newton hoặc chuỗi Taylor để tính logarit trong một độ chính xác nhất định, mặc dù tôi thú nhận rằng tôi không quen thuộc với các phương pháp để thực hiện điều này. Tuy nhiên, bạn hiếm khi thực sự cần phải làm điều này bởi vì hầu hết các số thực là IEEE tăng gấp đôi và có các thuật toán tốt hơn (hoặc thậm chí là hướng dẫn phần cứng) trong trường hợp đó.

Hy vọng điều này sẽ hữu ích!