이진 로그

3. 정의 및 성질

이진 로그 함수는 양의 실수에 대해 엄격하게 증가하는 함수인 2의 거듭제곱 함수의 역함수로 정의될 수 있으며, 따라서 고유한 역함수를 갖는다.^[7] 또는 ln|ln^영어 ''n''/ln|ln^영어 2로 정의할 수 있으며, 여기서 ln|ln^영어은 표준적인 방법으로 정의된 자연 로그이다. 이 정의에서 복소수 로그를 사용하면 이진 로그를 복소수로 확장할 수 있다.^[8]

다른 로그와 마찬가지로 이진 로그는 다음 방정식을 따르며, 이진 로그를 곱셈 또는 지수와 결합하는 공식을 단순화하는 데 사용할 수 있다.^[9]

• $\backslash log\_2\; xy=\backslash log\_2\; x\; +\; \backslash log\_2\; y$
• $\backslash log\_2\backslash frac\{x\}\{y\}=\backslash log\_2\; x\; -\; \backslash log\_2\; y$
• $\backslash log\_2\; x^y\; =\; y\backslash log\_2\; x.$

4. 표기법

수학에서 숫자 의 이진 로그는 종종 으로 표기된다. 그러나 특히 응용 분야에서는 이 함수에 대한 여러 다른 표기법이 사용되거나 제안되었다.

일부 저자는 이진 로그를 으로 표기하며,^[11][12] 이는 ''시카고 스타일 매뉴얼''에 나열된 표기법이다.^[13] 도널드 커누스는 이 표기법을 에드워드 레잉골드의 제안으로 돌렸지만,^[14] 정보 이론과 컴퓨터 과학에서 이 표기법의 사용은 레잉골드가 활동하기 전부터 시작되었다.^[15][16] 이진 로그는 또한 로그의 기본값이 임을 먼저 언급하고 으로 표기되기도 한다.^[17][18][19]

동일한 함수에 대해 자주 사용되는 또 다른 표기법(특히 독일 과학 문헌에서)은 인데,^[20][21][22] 이는 라틴어 ''logarithmus dualis''^[20] 또는 ''logarithmus dyadis''에서 유래되었다.

DIN 1302|DIN 1302^de, ISO 31-11 및 ISO 80000-2 표준은 또 다른 표기법인 을 권장한다. 이 표준에 따르면 은 이진 로그에 사용해서는 안 되며, 대신 상용 로그 에 예약되어 있다.^[23][24][25]

5. 응용

이진 로그는 정보 이론, 조합론, 계산 복잡도, 생물정보학, 음악 이론, 스포츠 일정, 사진술 등 다양한 분야에서 활용된다.

• 정보 이론: 정보 이론에서 자기 정보량과 정보 엔트로피는 비트를 기본 정보 단위로 사용하여 이진 로그로 표현된다.^[26]
• 조합론: 완전 이진 트리의 높이는 노드 수의 이진 로그로 표현할 수 있다.^[28] 강 시스템의 Strahler number는 최대 log₂n + 1이다.^[29]
• 계산 복잡도: 분할 정복 알고리즘의 시간 복잡도를 분석하는 데 이진 로그가 사용된다.^[19] 이진 탐색 알고리즘은 탐색 범위를 매 단계마다 절반으로 줄이므로, 크기가 n인 문제를 해결하는 데 대략 log₂n번의 반복이 필요하다.^[34]
• 생물정보학: 마이크로어레이에서 유전자 발현 비율을 비교하는 데 이진 로그가 사용된다.^[39]
• 음악 이론: 두 음 사이의 음정을 나타내는 센트는 주파수 비율의 이진 로그를 사용하여 계산된다.^[41]
• 스포츠 일정: 싱글 엘리네이션 토너먼트에서 필요한 라운드 수를 계산하는 데 이진 로그가 사용된다.^[43]
• 사진술: 노출 값을 측정하고, 광감성 재료 또는 디지털 센서의 다이내믹 레인지를 표현하는 데 이진 로그가 사용된다.^[44][45]

5. 1. 정보 이론

5. 2. 조합론

n개의 정점을 가진 모든 부분 큐브는 등거리 차원이 최소 log₂n이며, 최대 (1/2)nlog₂n개의 모서리를 가지며, 부분 큐브가 하이퍼큐브 그래프일 때 등식이 성립한다.^[31]

램지 정리에 따르면, 모든 n개의 정점을 가진 무방향 그래프는 크기가 n의 로그인 클리크 또는 독립 집합을 갖는다. 보장할 수 있는 정확한 크기는 알려져 있지 않지만, 크기에 대한 가장 좋은 경계는 이진 로그를 포함한다. 특히, 모든 그래프는 크기가 최소 (1/2)log₂n (1 - o(1))인 클리크 또는 독립 집합을 가지며, 거의 모든 그래프는 크기가 2log₂n (1 + o(1))보다 큰 클리크 또는 독립 집합을 갖지 않는다.^[32]

Gilbert–Shannon–Reeds 모델의 무작위 셔플에 대한 수학적 분석에서, 리플 셔플을 사용하여 n장의 카드 덱을 셔플하여 균일하게 무작위에 가까운 순열 분포를 얻는 데 필요한 셔플 횟수는 약 (3/2)log₂n임을 알 수 있다. 이 계산은 52장의 카드 덱을 7번 셔플해야 한다는 권장의 기반이 된다.^[33]

5. 3. 계산 복잡도

이진 로그는 알고리즘의 시간 복잡도를 분석하는 데 유용하게 사용된다. 특히, 이진 탐색이나 퀵 정렬과 같이 문제를 절반씩 나누어 해결하는 분할 정복 알고리즘의 분석에 자주 등장한다.^[19]

예를 들어, 이진 탐색 알고리즘은 탐색 범위를 매 단계마다 절반으로 줄여나가기 때문에, 크기가 인 문제를 해결하는 데 대략 번의 반복이 필요하다.^[34] 이와 유사하게, 개의 요소를 가진 균형 잡힌 이진 탐색 트리의 높이는 이다.^[35]

알고리즘의 실행 시간은 주로 빅 오 표기법으로 나타내는데, 이 표기법에서는 상수 인자와 낮은 차수의 항을 무시하여 식을 간략하게 표현한다. 로그의 밑이 다른 경우에도 상수 배만큼만 차이가 나기 때문에, 시간으로 실행되는 알고리즘은 시간으로 실행된다고 할 수도 있다. 따라서 또는 과 같은 표현에서는 로그의 밑이 중요하지 않아 생략할 수 있다.^[11][36]

그러나 시간 제한의 지수에 로그가 나타나는 경우에는 밑을 생략할 수 없다. 예를 들어, 는 와 같지만, 는 와 같다.

실행 시간이 인 알고리즘은 선형 로그라고도 불린다.^[37] 다음은 실행 시간이 또는 인 알고리즘의 예시이다.

• 평균 시간 퀵 정렬 및 기타 비교 정렬 알고리즘
• 균형 잡힌 이진 탐색 트리에서의 검색
• 제곱에 의한 거듭제곱
• 최장 증가 부분 수열^[38]

이진 로그는 비트 숫자를 시간 내에 곱하는 Karatsuba 알고리즘이나, 행렬을 시간 내에 곱하는 Strassen 알고리즘과 같은 일부 분할 정복 알고리즘의 시간 제한 지수에도 나타난다.

5. 4. 생물정보학

생물정보학에서 마이크로어레이는 생물학적 물질 샘플에서 서로 다른 유전자가 얼마나 강하게 발현되는지를 측정하는 데 사용된다. 유전자 발현의 서로 다른 비율은 종종 발현 비율의 비율에 대한 이진 로그를 사용하여 비교된다. 즉, 두 발현 비율의 로그 비율은 두 비율의 비율에 대한 이진 로그로 정의된다. 이진 로그는 발현 비율을 편리하게 비교할 수 있게 한다. 예를 들어, 두 배 증가된 발현 비율은 1의 로그 비율로 설명할 수 있고, 절반으로 감소된 발현 비율은 -1의 로그 비율로 설명할 수 있으며, 변화가 없는 발현 비율은 0의 로그 비율로 설명할 수 있다.^[39]

이러한 방식으로 얻은 데이터 포인트는 종종 좌표축 중 하나 또는 둘 다가 강도 비율의 이진 로그인 산점도로 시각화되거나, 이러한 로그 비율 산점도를 회전하고 크기를 조절하는 MA 플롯 및 RA 플롯과 같은 시각화로 표시된다.^[40]

5. 5. 음악 이론

음악 이론에서 두 음 사이의 음정 또는 지각적 차이는 주파수의 비율에 의해 결정된다. 분자와 분모가 작은 유리수 비율에서 나오는 음정은 특히 듣기 좋게 인식된다. 이러한 음정 중 가장 단순하고 중요한 것은 2:1의 주파수 비율인 옥타브이다. 두 음이 다른 옥타브 수는 주파수 비율의 이진 로그이다.^[41]

음조 간의 더 미세한 구분이 필요한 조율 시스템 및 기타 음악 이론 측면을 연구하려면 옥타브보다 미세하고 곱셈이 아닌 덧셈(로그처럼)인 음정 크기를 측정하는 것이 도움이 된다. 즉, 음 x, y, z가 상승하는 음 시퀀스를 형성하는 경우, x에서 y까지의 음정 측정값과 y에서 z까지의 음정 측정값을 더한 값은 x에서 z까지의 음정 측정값과 같아야 한다. 이러한 측정값은 옥타브를 1200개의 동일한 간격(100센트의 12 반음)으로 나누는 센트로 제공된다. 수학적으로, 주파수가 f₁과 f₂인 음이 주어지면, f₁에서 f₂까지의 간격의 센트 수는 다음과 같다.^[41]

:$\backslash left|1200\backslash log\_2\backslash frac\{f\_1\}\{f\_2\}\backslash right|.$

5. 6. 스포츠 일정

경쟁 게임 및 각 게임이나 경기에 두 명의 선수 또는 팀이 참여하는 스포츠에서 이진 로그는 승자를 결정하기 위해 필요한 싱글 엘리네이션 토너먼트의 라운드 수를 나타낸다. 예를 들어, 4명의 선수가 참여하는 토너먼트에서는 2라운드가 필요하며, 32개 팀의 토너먼트에서는 5라운드가 필요하다.^[43] n명의 선수/팀(n은 2의 거듭제곱이 아님)의 경우, log₂n은 반올림된다. 왜냐하면 모든 남은 경쟁자가 경기를 치르지 않는 라운드가 적어도 하나는 필요하기 때문이다. 예를 들어, log₂6은 대략 2.585인데, 이는 3으로 반올림된다. 이는 6개 팀의 토너먼트에는 3 라운드가 필요함을 나타낸다(두 팀이 첫 번째 라운드를 쉬거나 한 팀이 두 번째 라운드를 쉼). 스위스 시스템 토너먼트에서도 명확한 승자를 결정하는 데 동일한 수의 라운드가 필요하다.^[43]

5. 7. 사진술

사진술에서 노출 값은 필름이나 센서에 도달하는 빛의 양을 이진 로그를 기준으로 측정하며, 이는 인간의 시각 시스템이 빛에 대한 로그 응답을 설명하는 베버-페히너 법칙에 따른다. 노출의 한 스톱은 밑이 2인 로그 척도에서 한 단위이다.^[44][45] 이진 로그(스톱으로 표현)는 또한 농도 측정법에서 광감성 재료 또는 디지털 센서의 다이내믹 레인지를 표현하는 데 사용된다.^[47]

6. 계산

6. 1. 밑 변환

6. 2. 정수 이진 로그

6. 3. 반복 근사

• $1 \le y < 2$ 에서 시작한다. y = 1이면 소수 부분은 0이다.
• y를 반복적으로 제곱하여 $2 \le z < 4$ 인 z를 얻는다. 제곱 횟수를 m이라 하면, $z = y^{2^m}$ 이다.
• 양변에 로그를 취하고 식을 변형하면, $\log_2 y = \frac{1 + \log_2(z/2)}{2^m} = 2^{-m} + 2^{-m}\log_2(z/2)$ 를 얻는다.
• $z/2$는 다시 $1 \le z/2 < 2$ 구간의 실수이므로, 위 과정을 반복한다.

7. 소프트웨어 라이브러리 지원

`log2` 함수는 표준 C 수학 함수에 포함되어 있다. 이 함수의 기본 버전은 배정밀도 인수를 사용하지만, 변형을 통해 인수를 단정밀도 또는 long double로 사용할 수 있다.^[54] 복소수와 암시적 유형 변환을 지원하는 MATLAB과 같은 컴퓨팅 환경에서는 `log2` 함수의 인수가 음수가 될 수 있으며, 복소수를 반환한다.^[55]

참조

_[1] 서적 Precalculus mathematics https://books.google[...] Holt, Rinehart and Winston
_[2] 서적 Arithmetica integra https://books.google[...]
_[3] 서적 The Crest of the Peacock: Non-European Roots of Mathematics Princeton University Press
_[4] 서적 Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness https://books.google[...] Birkhäuser
_[5] 서적 Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae http://eulerarchive.[...] Saint Petersburg Academy
_[6] 서적 London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4 https://books.google[...]
_[7] 서적 Introduction to Mathematics for Life Scientists https://books.google[...] Springer
_[8] 서적 Excel Scientific and Engineering Cookbook https://books.google[...] O'Reilly Media
_[9] 서적 Algebra for College Students https://books.google[...] Academic Press
_[11] 서적 Introduction to Algorithms MIT Press and McGraw-Hill
_[12] 서적 Algorithms https://books.google[...] Addison-Wesley Professional
_[13] 서적 The Chicago Manual of Style University of Chicago Press
_[14] 서적 Fundamental Algorithms Addison-Wesley Professional
_[15] 간행물 A note on the information content of graphs
_[16] 간행물 Computer multiplication and division using binary logarithms
_[17] 서적 Mathematics for Engineers https://books.google[...] John Wiley & Sons
_[18] 서적 Elements of Information Theory https://books.google[...] "[[John Wiley & Sons]]"
_[19] 서적 Algorithm Design: Foundations, Analysis, and Internet Examples John Wiley & Sons
_[20] 서적 Einführung in die digitale Datenverarbeitung "[[Carl Hanser Verlag]]" 1971
_[21] 서적 Halbleiter-Schaltungstechnik https://archive.org/[...] "[[Springer Verlag]]" 1999
_[22] 서적 Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum https://books.google[...] "[[Springer Science & Business Media]]"
_[23] 서적 Brockhaus Enzyklopädie in zwanzig Bänden F.A. Brockhaus
_[24] 간행물 Guide for the Use of the International System of Units (SI) — NIST Special Publication 811, 2008 Edition — Second Printing http://physics.nist.[...] "[[NIST]]" 2008-03
_[25] 간행물 International Standard ISO 80000-2 2009-12-01
_[26] 서적 Information Theory https://books.google[...] Cambridge University Press
_[27] 서적 Taming the Infinite https://books.google[...] Quercus
_[28] 서적 A Programmer's Companion to Algorithm Analysis https://books.google[...] CRC Press
_[29] 간행물 On the Horton–Strahler number for random tries https://eudml.org/do[...]
_[31] 간행물 The lattice dimension of a graph
_[32] 서적 Ramsey Theory Wiley-Interscience
_[33] 간행물 Trailing the dovetail shuffle to its lair
_[34] 서적 Algorithms and Data Structures: The Basic Toolbox http://people.mpi-in[...] Springer
_[35] 서적 Applied Combinatorics https://books.google[...] CRC Press
_[36] 서적 Introduction to the Theory of Computation https://books.google[...] Cengage Learning
_[37] 서적 https://books.google[...]
_[38] 서적 How to Think About Algorithms https://books.google[...] Cambridge University Press
_[39] 서적 Microarray Gene Expression Data Analysis: A Beginner's Guide https://books.google[...] John Wiley & Sons
_[40] 서적 Computational and Statistical Methods for Protein Quantification by Mass Spectrometry https://books.google[...] John Wiley & Sons
_[41] 서적 The Musician's Guide to Acoustics https://books.google[...] Oxford University Press
_[42] 서적 The Harvard Dictionary of Music https://books.google[...] The Belknap Press of Harvard University Press
_[43] 서적 Introduction to Physical Education and Sport Science https://books.google[...] Cengage Learning
_[44] 서적 The Manual of Photography https://books.google[...] Taylor & Francis
_[45] 서적 Beyond the Zone System https://books.google[...] CRC Press
_[46] 서적 https://books.google[...]
_[47] 서적 Visual Effects Society Handbook: Workflow and Techniques https://books.google[...] CRC Press
_[48] 서적 Secret History: The Story of Cryptology https://books.google[...] CRC Press
_[49] 서적 Hacker's Delight Addison Wesley 2002
_[50] 웹사이트 fls https://www.kernel.o[...] kernel.org 2010-10-17
_[51] 간행물 A note on base-2 logarithm computations
_[52] 서적 Production Rendering: Design and Implementation https://books.google[...] Springer-Verlag
_[53] 서적 Hacker's Delight Addison Wesley – Pearson Education, Inc. 2013
_[54] 간행물 ISO/IEC 9899:1999 specification http://www.open-std.[...]
_[55] 서적 The Matlab® 5 Handbook https://books.google[...] Springer-Verlag
_[56] 서적 Introduction to Algorithms MIT Press and McGraw-Hill
_[57] 서적 Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum https://books.google[...] Springer Science & Business Media
_[58] 문서
_[59] 서적 Hacker's Delight Addison Wesley
_[60] 문서
_[61] 문서