Logarit nhị phân

Trong toán học, **logarit nhị phân** () là lũy thừa mà số  cần phải được nâng lên để được số , nghĩa là với mọi số thực  thì
:x=\log_2 n \quad\Longleftrightarrow\quad 2^x=n.

Ví dụ, logarit nhị phân của  là , logarit nhị phân của  là , logarit nhị phân của  là  và logarit nhị phân của  là .

Logarit nhị phân là logarit cơ số 2 và là hàm ngược của hàm lũy thừa của 2. Ngoài , logarit nhị phân còn có một số ký hiệu khác; xem mục Ký hiệu bên dưới.

Trong lịch sử, ứng dụng đầu tiên của logarit nhị phân là trong lý thuyết âm nhạc do Leonhard Euler khám phá: logarit nhị phân của tỉ lệ tần số giữa hai tông nhạc cho biết số quãng tám nằm giữa hai tông đó. Logarit nhị phân có thể được dùng để tính độ dài của một số khi được biểu diễn trong hệ nhị phân, hoặc số bit cần để mã hóa một thông điệp trong lý thuyết thông tin. Trong khoa học máy tính, logarit nhị phân đếm số bước cần để thực thi thuật toán tìm kiếm nhị phân và các thuật toán liên quan khác. Logarit nhị phân cũng có ứng dụng phổ biến trong một số lĩnh vực như toán học tổ hợp, tin sinh học, thiết kế giải đấu thể thao và nhiếp ảnh.

Logarit nhị phân là một trong các hàm toán học chuẩn của ngôn ngữ C và có trong một số bộ chương trình phần mềm toán học khác.

## Lịch sử

Lũy thừa của 2 đã được biết đến từ thời cổ xưa; chẳng hạn, chúng xuất hiện trong bộ ''Cơ sở'' của Euclid, mệnh đề IX.32 (về phân tích lũy thừa của 2) và IX.36 (một nửa định lý Euclid–Euler về sự xây dựng các số hoàn thiện chẵn), và logarit nhị phân chính là vị trí của chúng trong dãy lũy thừa của 2 được sắp xếp. Trên cơ sở đó, Michael Stifel được cho là đã xuất bản bảng logarit nhị phân đầu tiên vào năm 1544. Cuốn *Arithmetica Integra* của ông có một vài bảng số gồm các số nguyên và lũy thừa của 2 tương ứng. Khi đảo ngược các hàng trong các bảng số này thì chúng có thể được xem là bảng logarit nhị phân.

Trước Stifel, nhà toán học Kỳ Na thế kỷ 8 Virasena được cho là đã tìm ra tiền thân của logarit nhị phân. Khái niệm *ardhachena* của Virasena được xác định là số lần một số cho trước có thể chia hết cho 2. Định nghĩa này làm nảy sinh khái niệm về một hàm số cho cùng giá trị với logarit nhị phân đối với lũy thừa của 2, nhưng với các số nguyên khác thì hàm này cho biết cấp 2-adic của số đó thay vì logarit.

Dạng hiện đại của logarit nhị phân, áp dụng cho bất kỳ số nào (không chỉ có lũy thừa của 2) do Leonhard Euler phát hiện vào năm 1739. Euler cũng là người đầu tiên tìm ra ứng dụng của logarit nhị phân trong lý thuyết âm nhạc, từ lâu trước khi người ta được biết ứng dụng của chúng trong lý thuyết thông tin và khoa học máy tính. Trong công trình của mình, Euler đã lập được bảng logarit nhị phân của các số nguyên từ 1 đến 8 chính xác đến 7 chữ số thập phân.

## Định nghĩa và tính chất
Hàm logarit nhị phân được định nghĩa là hàm ngược của hàm lũy thừa của 2, vốn là một hàm số tăng trên tập hợp số thực dương và do đó có một hàm ngược duy nhất. Ngoài ra, nó cũng được xác định bằng  với  là logarit tự nhiên. Trong định nghĩa, khi thay logarit thực bằng logarit phức thì logarit nhị phân có thể được mở rộng cho số phức.

Giống như logarit thông thường, logarit nhị phân thỏa mãn các tính chất sau:

: \log_2 xy=\log_2 x + \log_2 y
: \log_2\frac{x}{y}=\log_2 x - \log_2 y
: \log_2 x^y = y\log_2 x.

Với các tính chất khác, xem danh sách đồng nhất thức logarit.

## Ký hiệu
Trong toán học, logarit nhị phân của một số  được ký hiệu là . Tuy nhiên, tùy theo lĩnh vực mà nó được sử dụng, còn tồn tại thêm một số ký hiệu khác.

Một số tác giả ký hiệu logarit nhị phân là ; đây là ký hiệu được liệt kê trong *[[The Chicago Manual of Style]]*. Theo Donald Knuth, ký hiệu này do Edward Reingold đề xuất, nhưng thực tế nó đã được dùng trong lý thuyết thông tin và khoa học máy tính từ trước khi Reingold bắt đầu sự nghiệp. Logarit tự nhiên cũng được viết là  cùng một câu trước đó giải thích rằng cơ số mặc định của logarit là . Một ký hiệu khác của chính hàm số đó (đặc biệt xuất hiện trong các bài viết khoa học của Đức) là , viết tắt của cụm từ *logarithmus dualis* hoặc *logarithmus dyadis* trong tiếng Latinh. Các tiêu chuẩn DIN 1302, ISO 31-11 và ISO 80000-2 còn khuyến nghị dùng một ký hiệu khác nữa, . Theo các tiêu chuẩn này, không nên dùng  để ký hiệu logarit nhị phân vì nó được dùng riêng cho logarit thập phân .

## Ứng dụng

### Lý thuyết thông tin
Số chữ số (bit) trong biểu diễn nhị phân của một số nguyên dương  là phần nguyên của  hay bằng
:  \lfloor \log_2 n\rfloor + 1. 
Trong lý thuyết thông tin, định nghĩa về lượng thông tin và entropy thông tin thường được biểu diễn qua logarit nhị phân, tương ứng với việc coi bit là đơn vị cơ bản của thông tin. Tuy nhiên, còn tồn tại một số dạng khác của các định nghĩa này được biểu thị qua logarit tự nhiên và đơn vị nat.

### Toán học tổ hợp

Mặc dù logarit tự nhiên có vai trò quan trọng hơn logarit nhị phân trong nhiều lĩnh vực của toán học thuần túy như lý thuyết số và giải tích toán học, nhưng logarit nhị phân vẫn có một số ứng dụng trong toán học tổ hợp:

* Một cây nhị phân gồm  lá có chiều cao nhỏ nhất là , đạt được khi  là lũy thừa của 2 và cây đó là cây nhị phân hoàn thiện. Liên quan đến nó, số Strahler lớn nhất của một hệ thống sông gồm  dòng chảy phụ lưu là .
* Hợp của một họ tập hợp bất kỳ gồm  tập hợp khác nhau có số phần tử nhỏ nhất là , đạt được khi họ đó là một tập lũy thừa.
* Một hình lập phương riêng  đỉnh có số chiều đẳng cự nhỏ nhất là  và số cạnh lớn nhất là , đạt được khi hình đó là đồ thị hình siêu lập phương.
* Theo định lý Ramsey, một đồ thị vô hướng  đỉnh có một clique hoặc một tổ hợp độc lập với cấp tỉ lệ thuận với logarit của . Chưa rõ cấp chính xác của nó là bao nhiêu nhưng các khoảng giá trị gần đúng nhất của cấp đó có liên quan đến logarit nhị phân. Đặc biệt, mọi đồ thị đều có một clique hoặc tổ hợp độc lập với cấp nhỏ nhất là  và hầu hết mọi đồ thị không có một clique hoặc tổ hợp độc lập với cấp lớn hơn .
* Dựa trên một phân tích toán học của mô hình Gilbert–Shannon–Reeds về xáo bài ngẫu nhiên, có thể thấy số lần chẽ bài mà một người cần thực hiện để sau đó một bộ bài  lá được phân phối hoán vị ngẫu nhiên gần đều là xấp xỉ  lần. Tính toán này là cơ sở để phát biểu rằng tốt nhất một bộ bài 52 lá phải được xáo 7 lần.

### Độ phức tạp tính toán

Do số học nhị phân được dùng nhiều trong thuật toán nên logarit nhị phân xuất hiện thường xuyên trong phân tích thuật toán theo phân nhánh nhị phân. Nếu một bài toán có  cách giải và mỗi vòng lặp của thuật toán làm giảm số cách giải đi một nửa thì số vòng lặp cần để cho ra một câu trả lời duy nhất là phần nguyên của . Ý tưởng này được ứng dụng khi phân tích một số thuật toán và cấu trúc dữ liệu. Ví dụ, trong tìm kiếm nhị phân, kích thước của bài toán cần giải giảm đi một nửa sau mỗi vòng lặp, và do đó cần  vòng lặp để cho câu trả lời đối với một bài toán kích thước . Tương tự, một cây tìm kiếm nhị phân cân bằng chứa  phần tử có chiều cao là .

Thời gian hoạt động của một thuật toán thường được biểu diễn qua ký hiệu O lớn, dùng để rút gọn biểu thức bằng cách bỏ qua hằng số tỉ lệ và hạng tử bậc thấp. Vì logarit cơ số khác nhau chỉ sai khác nhau bởi một hằng số tỉ lệ nên thuật toán hoạt động trong thời gian  cũng có thể nói là hoạt động trong thời gian . Do đó, cơ số của logarit trong các biểu thức như  hay  không quan trọng và có thể bỏ qua. Tuy nhiên, nếu logarit xuất hiện trên số mũ của một khoảng thời gian thì không thể bỏ qua cơ số của logarit đó. Chẳng hạn,  không giống với  vì khoảng thời gian thứ nhất bằng với  trong khi khoảng thời gian thứ hai bằng với .

Một số ví dụ về thuật toán có thời gian hoạt động là  hoặc  là:

* Sắp xếp nhanh (thời gian trung bình) và các thuật toán sắp xếp so sánh khác
* Tìm kiếm trong cây tìm kiếm nhị phân cân bằng
* Bình phương và nhân
* Dãy con tăng dài nhất

Logarit nhị phân cũng xuất hiện trong số mũ của khoảng thời gian để một số thuật toán chia để trị hoạt động, chẳng hạn như thuật toán Karatsuba dùng để nhân các số  bit trong thời gian , và thuật toán Strassen dùng để nhân ma trận  trong khoảng thời gian . Sự xuất hiện của logarit nhị phân trong các khoảng thời gian đó có thể được giải thích bằng cách liên hệ với định lý thợ cho hệ thức truy hồi chia để trị.

### Tin sinh học

Trong tin sinh học, microarray được dùng để đo mức độ biểu hiện gen trong một mẫu nguyên liệu sinh học. Các tốc độ biểu hiện khác nhau của một gen thường được so sánh bằng cách lấy logarit nhị phân của tỉ số giữa chúng: tỉ số log của hai tốc độ biểu hiện gen được định nghĩa là logarit nhị phân của tỉ số giữa chúng. Logarit nhị phân giúp việc so sánh tốc độ biểu hiện gen trở nên thuận lợi: chẳng hạn, tốc độ biểu hiện gen nhân đôi tương ứng với tỉ số log là , tốc độ giảm một nửa tương ứng với tỉ số log là  và tốc độ không đổi tương ứng với tỉ số log bằng không.

Các điểm dữ liệu thu được bằng cách này thường được minh họa thành một biểu đồ phân tán có một hoặc cả hai trục đều là logarit nhị phân của tỉ lệ tốc độ, hoặc thông qua các loại biểu đồ như MA và RA để quay và phóng to hoặc thu nhỏ biểu đồ phân tán đó.

### Lý thuyết âm nhạc
Trong lý thuyết âm nhạc, quãng giữa hai tông nhạc được xác định bằng tỉ lệ tần số của chúng. Các quãng âm có từ tỉ số số hữu tỉ với tử số và mẫu số nhỏ đều được xem là đặc biệt êm tai, nhịp nhàng. Trong đó, quãng âm đơn giản nhất và quan trọng nhất là quãng tám với tỉ lệ tần số là . Số quãng tám nằm giữa hai tông nhạc là logarit nhị phân của tỉ lệ tần số của chúng.

Để nghiên cứu hệ thống điều chỉnh cao độ và các khía cạnh khác của lý thuyết âm nhạc vốn cần sự phân biệt tinh vi hơn giữa các tông nhạc, cần có một độ đo để đo một quãng nhỏ hơn nhiều so với quãng tám và có tính cộng (giống logarit) thay vì tính nhân (giống tỉ lệ tần số). Theo đó, nếu ba tông , ,  tạo thành một chuỗi tông nhạc với cao độ tăng dần thì độ đo của quãng từ  đến  cộng với độ đo của quãng từ  đến  phải bằng độ đo của quãng từ  đến . Một độ đo như thế được cho bằng đơn vị cent, một đơn vị chia quãng tám thành 1200 quãng bằng nhau (12 nửa cung, mỗi cung gồm 100 cent). Cho hai tông nhạc với chu kỳ  và , khi đó số cent trong quãng từ  đến  là
: \left|1200\log_2\frac{f_1}{f_2}\right|.

### Tổ chức giải đấu thể thao
Trong các giải đấu thể thao gồm hai người (hoặc đội) thi đấu mỗi trận, logarit nhị phân cho biết số vòng đấu mà một giải đấu loại trực tiếp cần có để xác định nhà vô địch. Ví dụ, một giải gồm 4 người cần  vòng để tìm nhà vô địch, một giải gồm 32 đội cần  vòng, ... Trong trường hợp giải có  người/đội tham gia mà  không phải là lũy thừa của 2 thì  được làm tròn lên vì cần có ít nhất một vòng đấu nữa mà trong đó có một số người/đội không tham gia. Chẳng hạn,  gần bằng , làm tròn lên thành , nghĩa là một giải đấu gồm 6 đội cần có 3 vòng đấu (cho hai đội ngồi ngoài vòng thứ nhất hoặc một đội ngồi ngoài vòng thứ hai). Số vòng như vậy cũng là cần thiết để xác định nhà vô địch trong một giải đấu hệ Thụy Sĩ.

### Nhiếp ảnh
Trong nhiếp ảnh, giá trị phơi sáng được đo bằng logarit nhị phân của lượng ánh sáng tới màn ảnh hoặc cảm biến ảnh, phù hợp với luật Weber–Fechner mô tả phản ứng logarit của hệ thống thị giác con người với ánh sáng. Một bước ("khẩu") phơi sáng tương ứng với một đơn vị trong thang đo logarit cơ số 2. Chính xác hơn, giá trị phơi sáng của một bức ảnh bằng

: \log_2 \frac{N^2}{t}

trong đó  là chỉ số khẩu độ (số f) đo độ mở của ống kính khi phơi sáng và  là số giây phơi sáng.

Logarit nhị phân cũng được dùng khi biểu diễn dải tương phản động của vật liệu nhạy sáng hoặc cảm biến kỹ thuật số.

## Tính toán

### Đổi cơ số
Một cách dễ dàng để tính  trên các máy tính không có sẵn hàm  là thông qua hàm logarit tự nhiên () hoặc logarit thập phân ( hoặc ), có thể được tìm thấy trong hầu hết máy tính bỏ túi. Theo công thức đổi cơ số thì:

: \log_2 n = \frac{\ln n}{\ln 2} = \frac{\log_{10} n}{\log_{10} 2},

hay

: \log_2 n \approx 1,442695\ln n \approx 3,321928\log_{10} n.

### Làm tròn số nguyên
Logarit nhị phân có thể được làm thành một hàm với đầu vào là số nguyên và trả về số nguyên bằng cách làm tròn nó lên hay xuống. Hai dạng này của logarit nhị phân nguyên được liên hệ bằng công thức:

:  \lfloor \log_2(n) \rfloor = \lceil \log_2(n + 1) \rceil - 1 \text{ nếu }n \ge 1.

Có thể mở rộng định nghĩa này bằng cách quy ước  \lfloor \log_2(0) \rfloor = -1. Khi đó, hàm này có liên hệ với số bit 0 đứng trước trong biểu diễn nhị phân không dấu 32 bit của , :

: \lfloor \log_2(n) \rfloor = 31 - \operatorname{nlz}(n).

Logarit nhị phân nguyên có thể được xác định là chỉ số của bit 1 có trọng số cao nhất trong đầu vào (tính từ số 0). Trong trường hợp này, đó chính là phần bù của phép toán tìm bit 1 đầu tiên, dùng để tìm chỉ số của bit 1 có trọng số thấp nhất. Nhiều nền tảng phần cứng có hỗ trợ tìm số bit 0 đứng trước hoặc các phép toán tương đương, cho phép tìm logarit nhị phân một cách nhanh chóng. Các hàm `fls` và `flsl` trong hạt nhân Linux và trong một số phiên bản của thư viện phần mềm libc cũng tính được logarit nhị phân (làm tròn thành số nguyên cộng 1).

### Tính gần đúng bằng phép lặp
Với một số thực dương bất kỳ, logarit nhị phân có thể được chia thành hai phần để tính. Trước tiên, ta tính phần nguyên \lfloor\log_2 x\rfloor để đưa về thành bài toán mà trong đó đối số của logarit nằm trong nửa khoảng [1, 2), từ đó rút gọn bước thứ hai là tính phần thập phân của logarit. Với , tồn tại duy nhất một số nguyên  sao cho  hay . Từ lập luận này, ta suy ra được phần nguyên của logarit là  và phần thập phân là . Nói cách khác:

: \log_2 x = n + \log_2 y \quad\text{với } y = 2^{-n}x \text{ và } y \in [1,2).

Với số thực dấu phẩy động, phần nguyên là số mũ dấu phẩy động, còn đối với số nguyên thì nó được xác định bằng cách thực hiện phép toán đếm số bit 0 đứng trước.

Phần thập phân của kết quả thu được là  và có thể được tính chỉ bằng phép lặp cùng các phép nhân và phép chia cơ bản. Thuật toán tính phần thập phân có thể được mô tả bằng mã giả như sau:

# Bắt đầu với một số thực  thuộc nửa khoảng . Nếu  thì thuật toán kết thúc và phần thập phân bằng 0.
# Ngược lại, bình phương  lặp lại đến khi kết quả  thuộc nửa khoảng . Gọi  là số lần bình phương cần thực hiện. Khi đó  với  là giá trị sao cho  thuộc .
# Lấy logarit nhị phân cho cả hai vế rồi biến đổi đại số:
#:\begin{align}
 \log_2 z &= 2^m \log_2 y \\
 \log_2 y &= \frac{ \log_2 z }{ 2^m } \\
          &= \frac{ 1 + \log_2(z/2) }{ 2^m } \\
          &= 2^{-m} + 2^{-m}\log_2(z/2).
\end{align}
# Một lần nữa  là số thực trong nửa khoảng . Trở lại bước 1 và tính logarit nhị phân của  theo cách trên.
#
Kết quả cuối cùng được biểu diễn bằng các công thức đệ quy sau với  là số lần bình phương trong vòng lặp thứ  của thuật toán:

: \begin{align}
 \log_2 x &= n + 2^{-m_1} \left(1 + 2^{-m_2} \left(1 + 2^{-m_3} \left(1 + \cdots \right)\right)\right) \\
          &= n + 2^{-m_1} + 2^{-m_1-m_2} + 2^{-m_1-m_2-m_3} + \cdots
\end{align} 

Trong trường hợp đặc biệt khi phần thập phân ở bước 1 được xác định là bằng 0, đó là một chuỗi hữu hạn kết thúc tại một số hạng nào đó. Ngược lại, đó là một chuỗi vô hạn hội tụ theo dấu hiệu d'Alembert vì mỗi số hạng luôn nhỏ hơn số hạng liền trước (do ). Khi ứng dụng thực tế, phải cắt ngắn đi chuỗi vô hạn này để đạt kết quả gần đúng. Nếu chuỗi dừng lại ở số hạng thứ  thì sai số trong kết quả là nhỏ hơn .

### Trong thư viện phần mềm
Hàm `log2` là một hàm toán học nằm trong thư viện chuẩn của ngôn ngữ C. Dạng mặc định của hàm này yêu cầu đối số với độ chính xác kép (kiểu `double`) nhưng một số dạng khác của hàm cho phép đối số có độ chính xác đơn (kiểu `float`) hoặc độ chính xác kép mở rộng (kiểu `long double`). Trong MATLAB, đối số của hàm `log2` có thể là số âm, và trong trường hợp này thì đầu ra của hàm là một số phức.

## Ghi chú

## Tham khảo

## Liên kết ngoài
*
*
*Feynman and the Connection Machine