Movatterモバイル変換

[0]ホーム
URL:

Bước tới nội dung
WikipediaBách khoa toàn thư mở
Tìm kiếm

Logarit nhị phân

Đây là một bài viết tốt. Nhấn vào đây để biết thêm thông tin.
Bách khoa toàn thư mở Wikipedia
Đồ thịlog2 x dưới dạng hàm của một số thực dươngx

Trongtoán học,logarit nhị phân (log2 n) làlũy thừa mà số2 cần phải được nâng lên để được sốn, nghĩa là với mọi số thựcx thì

x=log2⁡n⟺2x=n.{\displaystyle x=\log _{2}n\quad \Longleftrightarrow \quad 2^{x}=n.}

Ví dụ, logarit nhị phân của1 là0, logarit nhị phân của2 là1, logarit nhị phân của4 là2 và logarit nhị phân của32 là5.

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

Trong lịch sử, ứng dụng đầu tiên của logarit nhị phân là tronglý thuyết âm nhạc doLeonhard Euler khám phá: logarit nhị phân của tỉ lệ tần số giữa haitô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 tronghệ nhị phân, hoặc sốbit cần để mã hóa một thông điệp tronglý thuyết thông tin. Trongkhoa học máy tính, logarit nhị phân đếm số bước cần để thực thi thuật toántì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ử

[sửa |sửa mã nguồn]
Bài chi tiết:Lịch sử logarit
Leonhard Euler là người đầu tiên ứng dụng logarit nhị phân vàolý thuyết âm nhạc năm 1739.

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 trongbộ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ácsố 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ốnArithmetica Integra của ông có một vài bảng số gồm cácsố 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.[1][2]

Trước Stifel, nhà toán họcKỳ Na thế kỷ 8Virasena được cho là đã tìm ra tiền thân của logarit nhị phân. Khái niệmardhachena 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,[3] nhưng với các số nguyên khác thì hàm này cho biếtcấp 2-adic của số đó thay vì logarit.[4]

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) doLeonhard 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.[5][6]

Định nghĩa và tính chất

[sửa |sửa mã nguồn]

Hàm logarit nhị phân được định nghĩa làhàm ngược của hàmlũy thừa của 2, vốn là một hàm số tăng trên tập hợpsố thực dương và do đó có một hàm ngược duy nhất.[7] Ngoài ra, nó cũng được xác định bằnglnn/ln 2 vớiln làlogarit tự nhiên. Trong định nghĩa, khi thay logarit thực bằnglogarit phức thì logarit nhị phân có thể được mở rộng chosố phức.[8]

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

log2⁡xy=log2⁡x+log2⁡y{\displaystyle \log _{2}xy=\log _{2}x+\log _{2}y}
log2⁡xy=log2⁡x−log2⁡y{\displaystyle \log _{2}{\frac {x}{y}}=\log _{2}x-\log _{2}y}
log2⁡xy=ylog2⁡x.{\displaystyle \log _{2}x^{y}=y\log _{2}x.}

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

Ký hiệu

[sửa |sửa mã nguồn]

Trong toán học, logarit nhị phân của một sốn được ký hiệu làlog2 n.[a] 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àlgn;[10][11] đây là ký hiệu được liệt kê trongThe Chicago Manual of Style.[12] TheoDonald Knuth, ký hiệu này doEdward Reingold đề xuất,[13] 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.[14][15] Logarit tự nhiên cũng được viết làlogn cùng một câu trước đó giải thích rằng cơ số mặc định của logarit là2.[16][17][18] 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àldn, viết tắt của cụm từlogarithmus dualis hoặclogarithmus dyadis trongtiếng Latinh.[19][20][21] Các tiêu chuẩnDIN 1302,ISO 31-11 vàISO 80000-2 còn khuyến nghị dùng một ký hiệu khác nữa,lbn. Theo các tiêu chuẩn này, không nên dùnglgn để ký hiệu logarit nhị phân vì nó được dùng riêng chologarit thập phânlog10n.[22][23][24]

Ứng dụng

[sửa |sửa mã nguồn]
Xem thêm:Thời gian nhân đôi

Lý thuyết thông tin

[sửa |sửa mã nguồn]

Số chữ số (bit) trongbiểu diễn nhị phân của một số nguyên dươngn là phần nguyên của1 + log2 n hay bằng[11]

⌊log2⁡n⌋+1.{\displaystyle \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ị qualogarit tự nhiên và đơn vịnat.[25]

Toán học tổ hợp

[sửa |sửa mã nguồn]
Nhánh thi đấu của một giải đấu loại trực tiếp gồm 16 người theo cấu trúc của mộtcây nhị phân hoàn thiện. Chiều cao của cây đó (số vòng của giải đấu) bằng logarit nhị phân của số người tham gia giải (làm tròn đến hàng đơn vị).

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ủatoán học thuần túy nhưlý thuyết số vàgiải tích toán học,[26] nhưng logarit nhị phân vẫn có một số ứng dụng trongtoán học tổ hợp:

  • Mộtcây nhị phân gồmn lá có chiều cao nhỏ nhất làlog2 n, đạt được khin làlũy thừa của 2 và cây đó làcây nhị phân hoàn thiện.[27] Liên quan đến nó,số Strahler lớn nhất của một hệ thống sông gồmn dòng chảy phụ lưu làlog2 n + 1.[28]
  • Hợp của mộthọ tập hợp bất kỳ gồmn tập hợp khác nhau có số phần tử nhỏ nhất làlog2 n, đạt được khi họ đó là mộttập lũy thừa.[b]
  • Mộthình lập phương riêngn đỉnh có số chiều đẳng cự nhỏ nhất làlog2 n và số cạnh lớn nhất là1/2n log2 n, đạt được khi hình đó làđồ thị hình siêu lập phương.[29]
  • Theođịnh lý Ramsey, mộtđồ thị vô hướngn đỉnh có mộtclique hoặc mộttổ hợp độc lập với cấptỉ lệ thuận với logarit củan. 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à1/2log2 n (1 −o(1)) 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ơn2log2 n (1 +o(1)).[30]
  • Dựa trên một phân tích toán học củamô hình Gilbert–Shannon–Reeds về xáo bài ngẫu nhiên, có thể thấy số lầnchẽ bài mà một người cần thực hiện để sau đó một bộ bàin lá được phân phốihoán vị ngẫu nhiên gần đều là xấp xỉ3/2log2 n 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.[31]

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

[sửa |sửa mã nguồn]
Tìm kiếm nhị phân trên một mảng đã sắp xếp, một thuật toán có độ phức tạp tính toán liên quan đến logarit nhị phân

Do số học nhị phân được dùng nhiều trongthuật toán nên logarit nhị phân xuất hiện thường xuyên trongphân tích thuật toán theo phân nhánh nhị phân.[13][18] Nếu một bài toán cón 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ủalog2 n. Ý 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ụ, trongtì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ầnlog2 n vòng lặp để cho câu trả lời đối với một bài toán kích thướcn.[32] Tương tự, mộtcây tìm kiếm nhị phân cân bằng chứan phần tử có chiều cao làlog2(n + 1) − 1.[33]

Thời gian hoạt động của một thuật toán thường được biểu diễn quaký 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 gianO(log2 n) cũng có thể nói là hoạt động trong thời gianO(log13n). Do đó, cơ số của logarit trong các biểu thức nhưO(logn) hayO(n logn) không quan trọng và có thể bỏ qua.[10][34] 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,O(2log2 n) không giống vớiO(2lnn) vì khoảng thời gian thứ nhất bằng vớiO(n) trong khi khoảng thời gian thứ hai bằng vớiO(n0,6931...).

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

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ốn bit trong thời gianO(nlog2 3),[39] vàthuật toán Strassen dùng để nhân ma trậnn ×n trong khoảng thời gianO(nlog2 7).[40] 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

[sửa |sửa mã nguồn]
Một microarray gồm khoảng 8700 gen. Tốc độ biểu hiện của các gen này được so sánh qua logarit nhị phân.

Trongtin 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à1, tốc độ giảm một nửa tương ứng với tỉ số log là−1 và tốc độ không đổi tương ứng với tỉ số log bằng không.[41]

Các điểm dữ liệu thu được bằng cách này thường được minh họa thành mộtbiể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 đó.[42]

Lý thuyết âm nhạc

[sửa |sửa mã nguồn]

Tronglý thuyết âm nhạc,quãng giữa haitô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à2:1. 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.[43]

Để nghiên cứuhệ 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ôngx,y,z 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ừx đếny cộng với độ đo của quãng từy đếnz phải bằng độ đo của quãng từx đếnz. 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 (12nửa cung, mỗi cung gồm 100 cent). Cho hai tông nhạc với chu kỳf1 vàf2, khi đó số cent trong quãng từf1 đếnf2 là[43]

|1200log2⁡f1f2|.{\displaystyle \left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\right|.}

Tổ chức giải đấu thể thao

[sửa |sửa mã nguồn]

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ộtgiả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ầnlog2 4 = 2 vòng để tìm nhà vô địch, một giải gồm 32 đội cầnlog2 32 = 5 vòng, ... Trong trường hợp giải cón người/đội tham gia màn không phải là lũy thừa của 2 thìlog2 n đượ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,log2 6 gần bằng2,585, làm tròn lên thành3, 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ộtgiải đấu hệ Thụy Sĩ.[44]

Nhiếp ảnh

[sửa |sửa mã nguồn]

Trongnhiế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ặccảm biến ảnh, phù hợp vớiluậ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.[45][46] Chính xác hơn, giá trị phơi sáng của một bức ảnh bằng

log2⁡N2t{\displaystyle \log _{2}{\frac {N^{2}}{t}}}

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

Logarit nhị phân cũng được dùng khi biểu diễndả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ố.[48]

Tính toán

[sửa |sửa mã nguồn]
Máy tính bỏ túi TI SR-50 (1974). Phím ln và log nằm ở hàng phím thứ hai; máy không có phím log2.

Đổi cơ số

[sửa |sửa mã nguồn]

Một cách dễ dàng để tínhlog2 n trên cácmáy tính không có sẵn hàmlog2 là thông qua hàmlogarit tự nhiên (ln) hoặclogarit thập phân (log hoặclog10), có thể được tìm thấy trong hầu hết máy tính bỏ túi. Theocông thức đổi cơ số thì:[46][49]

log2⁡n=ln⁡nln⁡2=log10⁡nlog10⁡2,{\displaystyle \log _{2}n={\frac {\ln n}{\ln 2}}={\frac {\log _{10}n}{\log _{10}2}},}

hay

log2⁡n≈1,442695ln⁡n≈3,321928log10⁡n.{\displaystyle \log _{2}n\approx 1,442695\ln n\approx 3,321928\log _{10}n.}

Làm tròn số nguyên

[sửa |sửa mã nguồ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áchlà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:[50]

⌊log2⁡(n)⌋=⌈log2⁡(n+1)⌉−1 nếu n≥1.{\displaystyle \lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1{\text{ nếu }}n\geq 1.}

Có thể mở rộng định nghĩa này bằng cách quy ước⌊log2⁡(0)⌋=−1{\displaystyle \lfloor \log _{2}(0)\rfloor =-1}. Khi đó, hàm này có liên hệ vớisố bit 0 đứng trước trong biểu diễn nhị phân không dấu 32 bit củan,nlz(n):[50]

⌊log2⁡(n)⌋=31−nlz⁡(n).{\displaystyle \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ántì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àmfls vàflsl tronghạt nhân Linux[51] và trong một số phiên bản của thư viện phần mềmlibc 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

[sửa |sửa mã nguồn]

Với mộtsố thực dương bất kỳ, logarit nhị phân có thể được chia thành hai phần để tính.[52] Trước tiên, ta tínhphần nguyên⌊log2⁡x⌋{\displaystyle \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ớix > 0, tồn tại duy nhất một số nguyênn sao cho2n ≤x < 2n+1 hay1 ≤ 2−nx < 2. Từ lập luận này, ta suy ra được phần nguyên của logarit làn và phần thập phân làlog2(2−nx).[52] Nói cách khác:

log2⁡x=n+log2⁡yvới y=2−nx và y∈[1,2).{\displaystyle \log _{2}x=n+\log _{2}y\quad {\text{với }}y=2^{-n}x{\text{ và }}y\in [1,2).}

Vớisố thực dấu phẩy động, phần nguyên là số mũ dấu phẩy động,[53] 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 đếmsố bit 0 đứng trước.[54]

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

  1. Bắt đầu với một số thựcy thuộc nửa khoảng[1, 2). Nếuy = 1 thì thuật toán kết thúc và phần thập phân bằng 0.
  2. Ngược lại, bình phươngy lặp lại đến khi kết quảz thuộc nửa khoảng[2, 4). Gọim là số lần bình phương cần thực hiện. Khi đóz =y2m vớim là giá trị sao choz thuộc[2, 4).
  3. Lấy logarit nhị phân cho cả hai vế rồi biến đổi đại số:
    log2⁡z=2mlog2⁡ylog2⁡y=log2⁡z2m=1+log2⁡(z/2)2m=2−m+2−mlog2⁡(z/2).{\displaystyle {\begin{aligned}\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{aligned}}}
  4. Một lần nữaz/2 là số thực trong nửa khoảng[1, 2). Trở lại bước 1 và tính logarit nhị phân củaz/2 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ớimi là số lần bình phương trong vòng lặp thứi của thuật toán:

log2⁡x=n+2−m1(1+2−m2(1+2−m3(1+⋯)))=n+2−m1+2−m1−m2+2−m1−m2−m3+⋯{\displaystyle {\begin{aligned}\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{aligned}}}

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ộtchuỗi vô hạnhội tụ theodấu hiệu d'Alembert vì mỗi số hạng luôn nhỏ hơn số hạng liền trước (domi > 0). 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ứi thì sai số trong kết quả là nhỏ hơn2−(m1 +m2 + ... +mi).[52]

Trong thư viện phần mềm

[sửa |sửa mã nguồn]

Hàmlog2 là một hàm toán học nằm trongthư viện chuẩn củangô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ểudouble) 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ểufloat) hoặc độ chính xác kép mở rộng (kiểulong double).[55] TrongMATLAB, đối số của hàmlog2 có thể làsố âm, và trong trường hợp này thì đầu ra của hàm là mộtsố phức.[56]

Ghi chú

[sửa |sửa mã nguồn]
  1. ^Đây là ký hiệu được dùng trongBách khoa toàn thư Toán học vàThe Princeton Companion to Mathematics.
  2. ^Một cách tương đương, một họ tập hợp gồmk phần tử khác nhau có nhiều nhất2k tập hợp khác nhau, đạt được khi họ đó là tập lũy thừa.

Tham khảo

[sửa |sửa mã nguồn]
  1. ^Groza, Vivian Shaw; Shelley, Susanne M. (1972),Precalculus mathematics, New York: Holt, Rinehart and Winston, tr. 182,ISBN 978-0-03-077670-0
  2. ^Stifel, Michael (1544),Arithmetica integra (bằng tiếng La-tinh), tr. 31. Một bảng tương tự khác gồm 9 số xuất hiện ở tr. 237, và một bảng khác nữa ở tr. 249b được mở rộng sang lũy thừa âm.
  3. ^Joseph, G. G. (2011),The Crest of the Peacock: Non-European Roots of Mathematics (ấn bản thứ 3), Princeton University Press, tr. 352,ISBN 978-0-691-13526-7.
  4. ^Chẳng hạn xemShparlinski, Igor (2013),Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, Progress in Computer Science and Applied Logic, quyển 22, Birkhäuser, tr. 35,ISBN 978-3-0348-8037-4.
  5. ^Euler, Leonhard (1739), "Chapter VII. De Variorum Intervallorum Receptis Appelationibus",Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (bằng tiếng La-tinh), Viện Hàn lâm Khoa học Saint Petersburg, tr. 102–112.
  6. ^Tegg, Thomas (1829), "Binary logarithms",London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4, tr. 142–143.
  7. ^Batschelet, E. (2012),Introduction to Mathematics for Life Scientists, Springer, tr. 128,ISBN 978-3-642-96080-2.
  8. ^Chẳng hạn,Microsoft Excel có hàmIMLOG2 để tính logarit nhị phân phức; xemBourg, David M. (2006),Excel Scientific and Engineering Cookbook, O'Reilly Media, tr. 232,ISBN 978-0-596-55317-3.
  9. ^Kolman, Bernard; Shapiro, Arnold (1982), "11.4 Properties of Logarithms",Algebra for College Students, Academic Press, tr. 334–335,ISBN 978-1-4832-7121-7.
  10. ^abCormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990],Introduction to Algorithms (ấn bản thứ 2), MIT Press và McGraw-Hill, tr. 34,53–54,ISBN 0-262-03293-7
  11. ^abSedgewick, Robert; Wayne, Kevin Daniel (2011),Algorithms, Addison-Wesley Professional, tr. 185,ISBN 978-0-321-57351-3.
  12. ^The Chicago Manual of Style (ấn bản thứ 15), University of Chicago Press, 2003, tr. 530,ISBN 0-226-10403-6.
  13. ^abKnuth, Donald E. (1997),Fundamental Algorithms,The Art of Computer Programming, quyển 1 (ấn bản thứ 3), Addison-Wesley Professional, tr. 23,ISBN 978-0-321-63574-7.
  14. ^Trucco, Ernesto (1956), "A note on the information content of graphs",The Bulletin of Mathematical Biophysics,18 (2):129–135,doi:10.1007/BF02477836,MR 0077919.
  15. ^Mitchell, John N. (1962), "Computer multiplication and division using binary logarithms",IRE Transactions on Electronic Computers, EC-11 (4):512–517,doi:10.1109/TEC.1962.5219391.
  16. ^Fiche, Georges; Hebuterne, Gerard (2013),Mathematics for Engineers, John Wiley & Sons, tr. 152,ISBN 978-1-118-62333-6,In the following, and unless otherwise stated, the notationlogx always stands for the logarithm to the base2 ofx.
  17. ^Cover, Thomas M.; Thomas, Joy A. (2012),Elements of Information Theory (ấn bản thứ 2),John Wiley & Sons, tr. 33,ISBN 978-1-118-58577-1,Unless otherwise specified, we will take all logarithms to base2.
  18. ^abGoodrich, Michael T.; Tamassia, Roberto (2002),Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, tr. 23,ISBN 0-471-38365-1,One of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of logarithms ... As is the custom in the computing literature, we omit writing the baseb of the logarithm whenb = 2.
  19. ^Tafel, Hans Jörg (1971).Einführung in die digitale Datenverarbeitung [Giới thiệu về xử lý thông tin số] (bằng tiếng Đức). Munich: Carl Hanser Verlag. tr. 20–21.ISBN 3-446-10569-7.
  20. ^Tietze, Ulrich; Schenk, Christoph (1999).Halbleiter-Schaltungstechnik (bằng tiếng Đức) (ấn bản thứ 11). Springer Verlag. tr. 1370.ISBN 3-540-64192-0.
  21. ^Bauer, Friedrich L. (2009).Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum.Springer Science+Business Media. tr. 54.ISBN 978-3-642-02991-2.
  22. ^Với DIN 1302 xemBrockhaus Enzyklopädie in zwanzig Bänden [Bách khoa toàn thư Brockhaus trong hai mươi tập] (bằng tiếng Đức), quyển 11, Wiesbaden: F.A. Brockhaus, 1970, tr. 554,ISBN 978-3-7653-0000-4.
  23. ^Với ISO 31-11 xemThompson, Ambler; Taylor, Barry M (tháng 3 năm 2008),Guide for the Use of the International System of Units (SI) — NIST Special Publication 811, 2008 Edition — Second Printing(PDF),NIST, tr. 33.
  24. ^Với ISO 80000-2 xem"Quantities and units – Part 2: Mathematical signs and symbols to be used in the natural sciences and technology"(PDF),International Standard ISO 80000-2 (ấn bản thứ 1), ngày 1 tháng 12 năm 2009, Section 12, Exponential and logarithmic functions, tr. 18,Bản gốc(PDF) lưu trữ ngày 28 tháng 2 năm 2019, truy cập ngày 23 tháng 8 năm 2020.
  25. ^Van der Lubbe, Jan C. A. (1997),Information Theory, Cambridge University Press, tr. 3,ISBN 978-0-521-46760-5.
  26. ^Stewart, Ian (2015),Taming the Infinite, Quercus, tr. 120,ISBN 978-1-623-65473-3,in advanced mathematics and science the only logarithm of importance is the natural logarithm.
  27. ^Leiss, Ernst L. (2006),A Programmer's Companion to Algorithm Analysis, CRC Press, tr. 28,ISBN 978-1-4200-1170-8.
  28. ^Devroye, L.; Kruszewski, P. (1996),"On the Horton–Strahler number for random tries",RAIRO Informatique Théorique et Applications,30 (5):443–456,doi:10.1051/ita/1996300504431,MR 1435732.
  29. ^Eppstein, David (2005), "The lattice dimension of a graph",European Journal of Combinatorics,26 (5):585–592,arXiv:cs.DS/0402028,doi:10.1016/j.ejc.2004.05.001,MR 2127682.
  30. ^Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980),Ramsey Theory, Wiley-Interscience, tr. 78,ISBN 0-471-05997-8.
  31. ^Bayer, Dave; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair",The Annals of Applied Probability,2 (2):294–313,doi:10.1214/aoap/1177005705,JSTOR 2959752,MR 1161056.
  32. ^Mehlhorn, Kurt; Sanders, Peter (2008), "2.5 An example – binary search",Algorithms and Data Structures: The Basic Toolbox(PDF), Springer, tr. 34–36,ISBN 978-3-540-77977-3.
  33. ^Roberts, Fred; Tesman, Barry (2009),Applied Combinatorics (ấn bản thứ 2), CRC Press, tr. 206,ISBN 978-1-4200-9983-6.
  34. ^Sipser, Michael (2012), "Example 7.4",Introduction to the Theory of Computation (ấn bản thứ 3), Cengage Learning, tr. 277–278,ISBN 978-1-133-18779-0.
  35. ^Cormen và đồng nghiệp 2001, tr. 156;Goodrich & Tamassia 2002, tr. 238.
  36. ^Cormen và đồng nghiệp 2001, tr. 276;Goodrich & Tamassia 2002, tr. 159.
  37. ^Cormen và đồng nghiệp 2001, tr. 879–880;Goodrich & Tamassia 2002, tr. 464.
  38. ^Edmonds, Jeff (2008),How to Think About Algorithms, Cambridge University Press, tr. 302,ISBN 978-1-139-47175-6.
  39. ^Cormen và đồng nghiệp 2001, tr. 844;Goodrich & Tamassia 2002, tr. 279.
  40. ^Cormen và đồng nghiệp 2001, mục 28.2.
  41. ^Causton, Helen; Quackenbush, John; Brazma, Alvis (2009),Microarray Gene Expression Data Analysis: A Beginner's Guide, John Wiley & Sons, tr. 49–50,ISBN 978-1-4443-1156-3.
  42. ^Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (2012),Computational and Statistical Methods for Protein Quantification by Mass Spectrometry, John Wiley & Sons, tr. 105,ISBN 978-1-118-49378-6.
  43. ^abCampbell, Murray; Greated, Clive (1994),The Musician's Guide to Acoustics, Oxford University Press, tr. 78,ISBN 978-0-19-159167-9.
  44. ^France, Robert (2008),Introduction to Physical Education and Sport Science, Cengage Learning, tr. 282,ISBN 978-1-4180-5529-5.
  45. ^Allen, Elizabeth; Triantaphillidou, Sophie (2011),The Manual of Photography, Taylor & Francis, tr. 228,ISBN 978-0-240-52037-7.
  46. ^abDavis, Phil (1998),Beyond the Zone System, CRC Press, tr. 17,ISBN 978-1-136-09294-7.
  47. ^Allen & Triantaphillidou 2011, tr. 235.
  48. ^Zwerman, Susan; Okun, Jeffrey A. (2012),Visual Effects Society Handbook: Workflow and Techniques, CRC Press, tr. 205,ISBN 978-1-136-13614-6.
  49. ^Bauer, Craig P. (2013),Secret History: The Story of Cryptology, CRC Press, tr. 332,ISBN 978-1-4665-6186-1.
  50. ^abWarren Jr., Henry S. (2002),Hacker's Delight (ấn bản thứ 1), Addison Wesley, tr. 215,ISBN 978-0-201-91465-8.
  51. ^"fls".Linux kernel API. kernel.org. Truy cập ngày 22 tháng 8 năm 2020.
  52. ^abcdMajithia, J. C.; Levan, D. (1973), "A note on base-2 logarithm computations",Proceedings of the IEEE,61 (10):1519–1520,doi:10.1109/PROC.1973.9318.
  53. ^Stephenson, Ian (2005), "9.6 Fast Power, Log2, and Exp2 Functions",Production Rendering: Design and Implementation, Springer-Verlag, tr. 270–273,ISBN 978-1-84628-085-6.
  54. ^Warren Jr., Henry S. (2013) [2002],"11-4: Integer Logarithm",Hacker's Delight (ấn bản thứ 2), Addison Wesley – Pearson Education, Inc., tr. 291,ISBN 978-0-321-84268-8, 0-321-84268-5.
  55. ^"7.12.6.10 The log2 functions",ISO/IEC 9899:1999 specification(PDF), tr. 226,Bản gốc(PDF) lưu trữ ngày 15 tháng 10 năm 2005, truy cập ngày 31 tháng 8 năm 2020.
  56. ^Redfern, Darren; Campbell, Colin (1998),The Matlab® 5 Handbook, Springer-Verlag, tr. 141,ISBN 978-1-4612-2170-8.

Liên kết ngoài

[sửa |sửa mã nguồn]

Bài viết tốt"Logarit nhị phân" là mộtbài viết tốt của Wikipedia tiếng Việt.
Mời bạn xemphiên bản đã được bình chọn vào ngày 22 tháng 9 năm 2020 và so sánhsự khác biệt với phiên bản hiện tại.
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Logarit_nhị_phân&oldid=74370946”
Thể loại:
Thể loại ẩn:
[8]ページ先頭
©2009-2026 Movatter.jp