Tại sao log2 và log1p nhanh hơn rất nhiều so với nhật ký và log10?

Question

Trong khi chơi đùa với this question tôi nhận thấy một cái gì đó tôi không thể giải thích liên quan đến việc thực hiện tương đối của np.log2, np.log và np.log10:

In [1]: %%timeit x = np.random.rand(100000) 
    ....: np.log2(x) 
    ....: 
1000 loops, best of 3: 1.31 ms per loop 

In [2]: %%timeit x = np.random.rand(100000) 
np.log(x) 
    ....: 
100 loops, best of 3: 3.64 ms per loop 

In [3]: %%timeit x = np.random.rand(100000) 
np.log10(x) 
    ....: 
100 loops, best of 3: 3.93 ms per loop 

np.log2 khoảng 3x nhanh hơn np.log và np.log10. Có lẽ thậm chí nhiều hơn phản trực giác, np.log1p(x), mà tính ln (x + 1), là ngang bằng với np.log2:

In [4]: %%timeit x = np.random.rand(100000) 
np.log1p(x) 
    ....: 
1000 loops, best of 3: 1.46 ms per loop 

tôi đắc gần như giống hệt nhau trong timings v1.10.1 NumPy và v1.8.2.

Có giải thích trực quan về những khác biệt này trong hiệu suất thời gian chạy không?

Answer 1

Đây chỉ là ghi chú, nhưng dài hơn một nhận xét. Rõ ràng đây đã làm với cụ thể của bạn cài đặt:

import numpy as np 
import numexpr as ne 
x = np.random.rand(100000) 

tôi nhận được timings cùng với NumPy 1.10 từ conda và một phiên bản được biên soạn với icc:

%timeit np.log2(x) 
1000 loops, best of 3: 1.24 ms per loop 

%timeit np.log(x) 
1000 loops, best of 3: 1.28 ms per loop 

tôi nghĩ rằng nó có thể có một cái gì đó để có grabbing gói VML MKL, nhưng trông giống như vậy là không:

%timeit ne.evaluate('log(x)') 
1000 loops, best of 3: 218 µs per loop 

Có vẻ như cài đặt gọn gàng của bạn đang thực hiện đăng nhập log2/log2 từ hai địa điểm khác nhau.

Answer 2

Tôi đã tìm thấy câu hỏi của bạn vô cùng thú vị, vì vậy tôi đã dành một vài giờ để làm một chút phục hồi; Tôi nghĩ rằng tôi đã tìm thấy một lời giải thích cho sự khác biệt hiệu suất vì nó áp dụng cho số nguyên (cảm ơn bạn Matteo Italia cho ghi chú của bạn) - Không rõ cách lập luận rằng có thể được mở rộng đến nổi mặc dù:

Máy tính sử dụng cơ sở 2 - Theo đối với các bài báo được liên kết trong tham chiếu, tính toán của log2 là một quá trình 4 chu trình bộ xử lý - của log10 yêu cầu nhân log2 (val) bằng 1/log2 (10), thêm 5 chu kỳ khác.

Tìm log2 là vấn đề finding the index of the least significant bit of a value.(video vào khoảng phút thứ 23 trở đi).

hacks bit: Find integer log base 10 of an integer

chút hacks: Find the log base 2 of an N-bit integer in O(lg(N))

Nhật ký nguyên gốc 10 được tính bằng cách đầu tiên bằng một trong những kỹ thuật nói trên cho việc tìm kiếm các cơ sở log 2. Bằng mối quan hệ log10 (v) = log2 (v)/log2 (10), chúng ta cần nhân nó với 1/log2 (10), là khoảng 1233/4096, hoặc 1233 theo sau bởi một sự dịch chuyển đúng của 12. Thêm một là cần thiết vì IntegerLogBase2 làm tròn xuống. Cuối cùng, vì giá trị t chỉ là một phép tính xấp xỉ có thể bị tắt bởi , giá trị chính xác được tìm thấy bằng cách trừ kết quả của v < PowersOf10 [t].

Phương pháp này cần thêm 6 hoạt động hơn IntegerLogBase2. Có thể là tăng tốc (trên máy có truy cập bộ nhớ nhanh) bằng cách sửa đổi phương thức tra cứu bảng cơ sở 2 ở trên để các mục nhập giữ được tính cho t (nghĩa là, thêm trước, -mulitply và - shift). Làm như vậy sẽ yêu cầu tổng cộng chỉ có 9 hoạt động để tìm cơ sở nhật ký 10, giả sử 4 bảng đã được sử dụng (một cho mỗi byte của v).

Đáng chú ý: việc sử dụng các chuỗi DeBruijn tra cứu & kỹ thuật chút thay đổi để tính toán log2 trong MIT video: Lec 2 | MIT 6.172 Performance Engineering of Software Systems, Fall 2010này (video, ở phút thứ 36 trở đi).

Đáng chú ý bài này StackOverflow đó chứng tỏ a method to make efficient log2 calculations truly cross platform with C++

Caveat: Tôi đã không kiểm tra mã nguồn NumPy để xác minh rằng nó thực sự thực hiện các kỹ thuật tương tự, nhưng nó sẽ là đáng ngạc nhiên rằng nó không. Trong thực tế, từ các ý kiến ​​dưới bài của OP, Fermion Portal đã kiểm tra:

sử dụng thực tế NumPy math.h từ glibc, bạn sẽ thấy sự khác biệt cùng trong C/C++ nếu bạn sử dụng math.h/cmath .h. Bạn có thể tìm thấy mã nguồn độc đáo được nhận xét cho hai hàm, ví dụ: ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/… và ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/… - Fermion Portal [9]

Answer 3

Disclaimer: Tôi không phải là một đáng tin cậy cũng như một nguồn chính thức.

Tôi gần như chắc chắn rằng việc thực hiện đăng nhập vào chức năng cơ sở e có thể được thực hiện nhanh như hàm log2, bởi vì để chuyển đổi sang hàm kia, bạn yêu cầu một bộ phận bằng một hằng số. Đây là khóa học giả định rằng một hoạt động phân chia đơn lẻ là một phần nhỏ của các tính toán khác; mà trong việc thực hiện chính xác logarit là đúng.

Trong hầu hết các trường hợp, sử dụng gọn gàng math.h từ glibc, bạn sẽ thấy sự khác biệt tương tự trong C/C++ nếu bạn sử dụng math.h/cmath.h. Trong nhận xét, một số người quan sát cùng một tốc độ cho np.log và np.log2; Tôi nghi ngờ điều này có thể đến từ các nền tảng/nền tảng khác nhau.

Bạn có thể tìm thấy mã nguồn độc đáo nhận xét cho hai chức năng trong các tập tin e_log.c, e_log2.c, e_logf.c, e_log2f.c trong dbl-64/ và flt-32/ thư mục con của this GitHub repo.

Đối với độ chính xác gấp đôi, trong glibc, các log chức năng đang triển khai một algo hoàn toàn khác nhau (so với log2) từ IBM từ ~ năm 2001, trong đó đã được đưa vào thư viện libultim của họ. Trong khi đó, log2 là từ Sun Microsystems từ ~ 1993. Chỉ cần nhìn vào mã một có thể thấy hai xấp xỉ khác nhau đang được thực hiện. Ngược lại, đối với độ chính xác đơn, cả hai chức năng log và log2 là giống nhau ngoài việc chia cho ln2 trong trường hợp log2, do đó có cùng tốc độ.

Để biết thêm thông tin cơ bản về các thuật toán cơ bản, các lựa chọn thay thế và các cuộc thảo luận sẽ bao gồm trong glibc trong tương lai, hãy xem here.