İkili logaritma - Binary logarithm

Pozitif gerçek sayı x'in bir fonksiyonu olarak log ₂  x grafiği

Gelen matematik , ikili logaritma ( log ₂  N ) olduğu güç sayısı olduğu 2 olmalıdır yükseltilmiş değeri elde etmek için  n . Yani, herhangi bir gerçek sayı x için ,

${\displaystyle x=\log _{2}n\quad \Longleftrightarrow \dörtlü 2^{x}=n.}$

Örneğin, ikili logaritması 1 olan 0 ikili logaritması, 2 olduğu 1 ikili logaritması, 4 olan  2 ve ikili logaritma 32 olan  5 .

İkili logaritmasıdır logaritma tabanına 2 ve bir ters dönüşüm ve iki güç işlevi. Log _2'nin yanı sıra ikili logaritma lb için alternatif gösterim ( ISO 31-11 ve ISO 80000-2 tarafından tercih edilen gösterim ).

Tarihsel olarak, ikili logaritmaların ilk uygulaması Leonhard Euler tarafından müzik teorisindeydi : iki müzik tonunun frekans oranının ikili logaritması , tonların farklılık gösterdiği oktav sayısını verir . İkili logaritmalar, ikili sayı sistemindeki bir sayının temsilinin uzunluğunu veya bilgi teorisinde bir mesajı kodlamak için gereken bit sayısını hesaplamak için kullanılabilir . Gelen bilgisayar bilimleri , bunlar için gerekli adımların sayısını saymak ikili arama ve ilgili algoritmalar. İkili logaritmanın sıklıkla kullanıldığı diğer alanlar arasında kombinatorik , biyoinformatik , spor turnuvalarının tasarımı ve fotoğrafçılık yer alır .

İkili logaritmalar, standart C matematiksel fonksiyonlarına ve diğer matematiksel yazılım paketlerine dahildir. İkili logaritmanın tamsayı kısmı, bir tamsayı değerindeki ilk kümeyi bul işlemi kullanılarak veya bir kayan nokta değerinin üssü aranarak bulunabilir . Logaritmanın kesirli kısmı verimli bir şekilde hesaplanabilir.

Tarih

Leonhard Euler , 1739'da müzik teorisine ikili logaritma uygulayan ilk kişi oldu .

İkisinin güçler antik çağlardan beri bilinmektedir; örneğin, Euclid'in Elements , Props'da görünürler . IX.32 (ikinin kuvvetlerinin çarpanlara ayrılması üzerine) ve IX.36 ( Öklid-Euler teoreminin yarısı , hatta mükemmel sayıların yapısı üzerine ). Ve ikinin kuvvetinin ikili logaritması, ikinin kuvvetlerinin sıralı dizisindeki konumudur. Bu temelde, Michael Stifel , 1544'te bilinen ilk ikili logaritma tablosunu yayınlamakla itibar kazanmıştır. Arithmetica Integra adlı kitabı , tamsayıları karşılık gelen iki güçleriyle gösteren birkaç tablo içermektedir . Bu tabloların satırlarını tersine çevirmek, bunların ikili logaritma tabloları olarak yorumlanmasına izin verir.

Stifel'den önce, 8. yüzyıl Jain matematikçisi Virasena , ikili logaritmanın öncüsü olarak kabul edilir. Arasında Virasena kavramı ardhacheda kez belirli bir sayısı ikiye kadar eşit bir şekilde bölünebilir sayısı olarak tanımlanmıştır. Bu tanım, ikinin kuvvetleri üzerinde ikili logaritma ile örtüşen, ancak diğer tamsayılar için farklıdır , logaritma yerine 2-adic düzenini veren bir fonksiyona yol açar .

Herhangi bir sayıya (yalnızca ikinin kuvvetlerine değil) uygulanan ikili logaritmanın modern biçimi, 1739'da Leonhard Euler tarafından açıkça ele alındı . Euler, ikili logaritmaların müzik teorisine uygulanmasını, onların bilgi teorisi ve bilgisayar bilimlerindeki uygulamalarının ortaya çıkmasından çok önce kurdu. bilinen. Euler, bu alandaki çalışmasının bir parçası olarak, 1'den 8'e ve yedi ondalık basamaklı tamsayıların ikili logaritmalarını içeren bir tablo yayınladı.

Tanım ve özellikler

İkili logaritma fonksiyonu olarak tanımlanabilir ters fonksiyon için iki güç pozitif üzerinde kesin artan fonksiyonudur fonksiyonu, gerçek sayılar ve bu nedenle benzersiz tersi var. Alternatif olarak, ln n /ln2 olarak tanımlanabilir , burada ln , standart yollarından herhangi birinde tanımlanan doğal logaritmadır . Kullanımı karmaşık logaritma bu tanımı ikili logaritma uzatılacak sağlayan karmaşık sayılar .

Diğer logaritmalarda olduğu gibi, ikili logaritma, ikili logaritmaları çarpma veya üs ile birleştiren formülleri basitleştirmek için kullanılabilen aşağıdaki denklemlere uyar:

${\displaystyle \log _{2}xy=\log _{2}x+\log _{2}y}$

${\displaystyle \log _{2}{\frac {x}{y}}=\log _{2}x-\log _{2}y}$

${\displaystyle \log _{2}x^{y}=y\log _{2}x.}$

Daha fazla bilgi için, logaritmik kimliklerin listesine bakın .

gösterim

Matematikte, bir n sayısının ikili logaritması genellikle log ₂  n olarak yazılır . Bununla birlikte, özellikle uygulama alanlarında, bu işlev için birkaç başka gösterim kullanılmış veya önerilmiştir.

Bazı yazarlar ikili logaritmayı The Chicago Manual of Style'da listelenen notasyon olan lg n olarak yazarlar . Donald Knuth , bu gösterimi Edward Reingold'un bir önerisine bağlıyor , ancak hem bilgi teorisinde hem de bilgisayar biliminde kullanımı Reingold'un aktif olmasından önceye dayanıyor. İkili logaritma, logaritmanın varsayılan tabanının 2 olduğu önceki bir ifadeyle  log n olarak da yazılmıştır . Genellikle (özellikle Alman bilimsel literatürde) aynı işlevi için kullanılan bir başka sembol olan ld n dan, Latin tersüstel dualis veya tersüstel dyadis . DIN 1302  [ de ] , ISO 31-11 ve ISO 80000-2 standartları henüz başka notasyonu, tavsiye lb n . Bu standartlara göre, lg n ikili logaritma için kullanılmamalıdır, çünkü bunun yerine ortak logaritma log ₁₀ n için ayrılmıştır .

Uygulamalar

bilgi teorisi

Basamak sayısı ( bit olarak) ikili gösterimi olumlu tamsayı ve n, bir parçası arasında giriş + 1 ₂  , n , örneğin,

${\displaystyle \lfloor \log _{2}n\rfloor +1.}$

Bilgi teorisinde, öz bilgi miktarının ve bilgi entropisinin tanımı , genellikle biti temel bilgi birimi yapmaya karşılık gelen ikili logaritma ile ifade edilir . Bu birimlerle, Shannon-Hartley teoremi , bir kanalın bilgi kapasitesini, sinyal-gürültü oranının ikili logaritması artı bir olarak ifade eder. Ancak, bu tanımlar için alternatif gösterimlerde doğal logaritma ve nat da kullanılmaktadır.

Kombinatorik

Tam bir ikili ağaç yapısına sahip 16 oyunculu tek elemeli turnuva grubu . Ağacın yüksekliği (turnuvadaki tur sayısı), oyuncu sayısının bir tam sayıya yuvarlanmış ikili logaritmasıdır.

Sayı teorisi ve matematiksel analiz gibi saf matematiğin birçok alanında doğal logaritma ikili logaritmadan daha önemli olsa da , ikili logaritmanın kombinatorikte birkaç uygulaması vardır :

• Her ikili ağaç ile n yaprakları en az yüksekliğe sahip günlüğüne ₂  n eşitlik ile, n bir olan iki güç ve ağaç bir olduğunu tam ikili ağaç . Buna bağlı olarak, n adet yan dereye sahip bir nehir sisteminin Strahler sayısı en fazla log ₂ n + 1'dir . 
• Her setleri aile ile n farklı setleri, en azından sahip günlüğü ₂  n ailesi ise eşitlik birliği sayesinde elemanları, güç seti .
• Her kısmi küp ile N köşe izometrik en azından bir boyuta sahiptir günlük ₂  n ve en fazla var 1/2 n log ₂  n kenar, kısmi küp bir hiperküp grafiği olduğunda eşitlikle.
• Göre Ramsey teoremi , her n -vertex grafik yönlendirilmeyen bir ya sahip klik veya bağımsız bir dizi boyut logaritmik bir n . Kesin olarak garanti edilebilecek boyut bilinmemektedir, ancak boyutu hakkında bilinen en iyi sınırlar ikili logaritmalardır. Özellikle, tüm grafikler en azından bir klik veya bağımsız bir boyut kümesine sahiptir.1/2log ₂  n (1 − o (1)) ve hemen hemen tüm grafikler 2 log ₂  n (1 + o (1)) ' den daha büyük bir klik veya bağımsız boyut kümesine sahip değildir .
• Matematiksel analizlerden Gilbert-Shannon-Kamışlar modelinin rastgele shuffles bir kaç kez bir ihtiyacı bir karıştırmak için bu gösterebilir n kullanarak, kartların aldığı yolcuların kart güverte şıraynır shuffles yakındır permütasyon bir dağılım elde etmek için, tekdüze rastgele, yaklaşık olarak3/2kayıt ₂  n . Bu hesaplama, 52 kartlık destelerin yedi kez karıştırılması önerisinin temelini oluşturur.

hesaplama karmaşıklığı

Sıralanmış bir dizide ikili arama , zaman karmaşıklığı ikili logaritmalar içeren bir algoritma

İkili logaritma , yalnızca algoritmalarda ikili sayı aritmetiğinin sık kullanımı nedeniyle değil, aynı zamanda iki yönlü dallanmaya dayalı algoritmaların analizinde ikili logaritmalar meydana geldiği için algoritmaların analizinde de sıklıkla görülür . Bir sorun başlangıçta varsa n çözümü için seçimler ve algoritmanın her yineleme iki kat seçenek sayısını azaltır, daha sonra tek bir seçim seçmek için gerekli adım sayısının yine ayrılmaz bir parçası olan günlük ₂  n . Bu fikir, çeşitli algoritmaların ve veri yapılarının analizinde kullanılır . Örneğin, ikili arama , sorunun büyüklüğü her bir tekranyla ikiye bölünür çözüldü ve bu nedenle yaklaşık olmak log ₂  N tekrarlamalar boyutu bir sorun için bir çözüm elde etmek için gerekli olan n . Benzer şekilde, n eleman içeren mükemmel bir şekilde dengelenmiş ikili arama ağacının yüksekliği log ₂ ( n + 1) − 1 .

Bir algoritmanın çalışma süresi genellikle , sabit faktörlerini ve düşük dereceli terimlerini atlayarak ifadeleri basitleştirmek için kullanılan büyük O notasyonu ile ifade edilir. Farklı tabanlardaki logaritmalar birbirinden yalnızca sabit bir faktörle farklılık gösterdiğinden, O (log ₂  n ) zamanında çalışan algoritmaların , diyelim ki, O (log ₁₃ n ) zamanında çalıştığı da söylenebilir . O (log n ) veya O ( n log n ) gibi ifadelerdeki logaritmanın tabanı bu nedenle önemli değildir ve ihmal edilebilir. Ancak, bir zaman sınırının üssünde görünen logaritmalar için, logaritmanın tabanı ihmal edilemez. Örneğin, O (2 ^{log ₂  n} ) O (2 ^{ln n} ) ile aynı değildir çünkü birincisi O ( n ) ve ikincisi O ( n ^0.6931... ) ^{değerine eşittir} .

O ( n  log  n ) çalışma süresine sahip algoritmalara bazen lineerithmic denir . O (log n ) veya O ( n log n ) çalışma süresine sahip bazı algoritma örnekleri şunlardır:

• Ortalama süre hızlı sıralama ve diğer karşılaştırmalı sıralama algoritmaları
• Dengeli ikili arama ağaçlarında arama
• kare alarak üs alma
• En uzun artan ardışıklık

İkili logaritmalar, aynı zamanda, O ( n ^{log ₂  3} ) zamanında n- bit sayıları çarpmaya yönelik Karatsuba algoritması ve içindeki n × n matrisleri çarpmaya yönelik Strassen algoritması gibi, bazı böl ve yönet algoritmalarının zaman sınırlarının üslerinde de meydana gelir . zaman O ( n ^{log ₂  7} ) . Bu çalışma sürelerinde ikili logaritmaların ortaya çıkışı, böl ve yönet yinelemeleri için ana teorem referans alınarak açıklanabilir .

biyoinformatik

Yaklaşık 8700 gen için bir mikrodizi . Bu genlerin ifade oranları ikili logaritmalar kullanılarak karşılaştırılır.

Gelen Biyoinformatik , mikrodiziler , biyolojik bir materyalin bir numunesinden olarak ifade edilmiştir ne kadar güçlü, farklı genler ölçmek için kullanılır. Bir genin farklı ekspresyon oranları, genellikle ekspresyon oranlarının oranının ikili logaritması kullanılarak karşılaştırılır: iki ekspresyon oranının logaritması, iki oranın oranının ikili logaritması olarak tanımlanır. İkili logaritmalar, ifade oranlarının uygun bir şekilde karşılaştırılmasına izin verir: iki katına çıkmış bir ifade hızı 1 log oranı ile tanımlanabilir , yarıya indirilmiş bir ifade oranı -1 log oranı ile tanımlanabilir ve değişmemiş bir ifade oranı bir ile tanımlanabilir. örneğin sıfırın log oranı.

Bu şekilde elde edilen veri noktaları genellikle , koordinat eksenlerinden birinin veya her ikisinin yoğunluk oranlarının ikili logaritmaları olduğu bir dağılım grafiği olarak veya bu log oranı dağılım grafiklerini döndüren ve ölçeklendiren MA grafiği ve RA grafiği gibi görselleştirmelerde görselleştirilir .

Müzik Teorisi

Olarak müzik teorisi , aralık iki ton arasındaki veya algısal bir fark, frekanslarının oranı ile belirlenir. Payları ve paydaları küçük olan rasyonel sayı oranlarından gelen aralıklar özellikle ahenkli olarak algılanır. Bu aralıkların en basiti ve en önemlisi, frekans oranı 2:1 olan oktavdır . İki tonun farklılık gösterdiği oktav sayısı, frekans oranlarının ikili logaritmasıdır.

Tonlar arasında daha ince ayrımlar gerektiren akort sistemlerini ve müzik teorisinin diğer yönlerini incelemek için, bir oktavdan daha ince olan ve çarpımsal (frekans olarak) yerine toplamalı (logaritmalar gibi) olan bir aralığın boyutunun bir ölçüsüne sahip olmak yararlıdır. oranlar). Yani, x , y ve z tonları yükselen bir ton dizisi oluşturuyorsa, x ile y arasındaki aralığın ölçüsü artı y ile z arasındaki aralığın ölçüsü, x ile z arasındaki aralığın ölçüsüne eşit olmalıdır . Bu tür bir önlem ile verilmektedir yüzde içine oktav böler, 1200 eşit aralıklarla ( 12 semitones arasında 100 sent) ekstrakte edildi. Matematiksel olarak, frekans ile birlikte verilen sesleri f ₁ ve f ₂ , aralığı içindeki sent sayısı f ₁ için f ₂ isimli

${\displaystyle \left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\sağ|.}$

Millioctave aynı şekilde tanımlanır, fakat bir çarpanı ile olan 1000 yerine 1200 .

Spor planlaması

Her oyunda veya maçta iki oyuncu veya takımın yer aldığı rekabetçi oyunlarda ve sporlarda, ikili logaritma, bir kazananı belirlemek için gereken tek eleme turnuvasında gerekli olan tur sayısını gösterir . Örneğin, bir turnuva 4 oyuncuları gerektirir log ₂  4 = 2 kazanan, bir turnuva belirlemek için mermi 32 ekipler gerektiren günlük ₂  32 = 5 için, bu durumda vb mermi, n oyuncuların / takımların nerede n bir güç değildir 2'de log ₂  n , kalan tüm yarışmacıların oynamadığı en az bir tur olması gerektiğinden yuvarlanır. Örneğin, log ₂  6 yaklaşık 2.585'tir , bu da 3'e yuvarlanır, bu da 6 takımlı bir turnuvanın 3 tur gerektirdiğini gösterir (ilk turda iki takım veya bir takım ikinci turda tur atar). Bir İsviçre sistemi turnuvasında net bir kazanan belirlemek için aynı sayıda tur da gereklidir .

Fotoğrafçılık

Olarak fotoğraf , maruz kalma değerleri uygun olarak film veya sensör ulaşan ışık miktarının ikili logaritma cinsinden ölçülen Weber-Fechner'in hakları ışık insan görme sistemi logaritmik tepkisini tarif. Tek bir maruz kalma durağı, 2 tabanlı logaritmik ölçekte bir birimdir . Daha doğrusu, bir fotoğrafın pozlama değeri şu şekilde tanımlanır:

${\displaystyle \log _{2}{\frac {N^{2}}{t}}}$

burada N , pozlama sırasında merceğin açıklığını ölçen f sayısıdır ve t , pozlamanın saniye sayısıdır.

Dansitometride , ışığa duyarlı malzemelerin veya dijital sensörlerin dinamik aralığını ifade etmek için ikili logaritmalar (duraklar olarak ifade edilir) de kullanılır .

Hesaplama

TI SR-50 bilimsel hesap makinesi (1974). ln ve log tuşları ikinci satırdadır; günlük ₂  anahtarı yok.

Diğer bazlardan dönüştürme

Hesapla için kolay bir yol günlüğü ₂  n üzerinde hesap makineleri bir yok günlüğü ₂ fonksiyonunu kullanmaktır doğal logaritma ( ln ) ya da ortak logaritmasını ( log veya log ₁₀ ) çoğunda bulunan işlevlerini, bilimsel hesap makineleri . Bunun için logaritma temel formüllerinin özel değişimi :

${\displaystyle \log _{2}n={\frac {\ln n}{\ln 2}}={\frac {\log _{10}n}{\log _{10}2}},}$

veya yaklaşık olarak

${\displaystyle \log _{2}n\yaklaşık 1.442695\ln n\yaklaşık 3.321928\log _{10}n.}$

tamsayı yuvarlama

İkili logaritma, yukarı veya aşağı yuvarlayarak tamsayılardan ve tamsayılardan bir fonksiyon haline getirilebilir . Bu iki tamsayı ikili logaritması şu formülle ilişkilidir:

${\displaystyle \lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{ if }}n\geq 1.}$

Tanım tanımlanarak genişletilebilir . Bu şekilde genişletilen bu işlev, x , nlz( x )' in 32 bitlik işaretsiz ikili gösteriminin baştaki sıfırlarının sayısıyla ilgilidir . ${\displaystyle \lfloor \log _{2}(0)\rfloor =-1}$

${\displaystyle \lfloor \log _{2}(n)\rfloor =31-\operatöradı {nlz} (n).}$

Tamsayı ikili logaritma , girişteki en anlamlı 1 bitin sıfır tabanlı indeksi olarak yorumlanabilir . Bu anlamda , en az anlamlı 1 bitin indeksini bulan ilk kümeyi bul işleminin tamamlayıcısıdır . Birçok donanım platformu, ikili logaritmayı hızlı bir şekilde bulmak için kullanılabilen baştaki sıfırların sayısını veya eşdeğer işlemleri bulmak için destek içerir. Ve fonksiyonlar Linux çekirdeği ve bazı sürümlerinde libc yazılım kitaplığında da ikili logaritma hesaplamak (bir tam sayıya yuvarlanır, artı bir). flsflsl

yinelemeli yaklaşım

Genel bir pozitif gerçek sayı için ikili logaritma iki kısımda hesaplanabilir. İlk olarak, bir hesaplar tamsayı kısmını , (logaritma karakteristik olarak da adlandırılır). Bu, problemi, logaritmanın argümanının sınırlı bir aralıkta, [1, 2) aralığı içinde olduğu bir probleme indirger ve kesirli kısmı hesaplamanın ikinci adımını (logaritmanın mantisi ) basitleştirir. Herhangi biri için x > 0 , benzersiz bir tamsayı vardır N şekilde 2 ⁿ ≤ x <2 ^{, n + 1} ya da eşdeğer 1 ≤ 2 ^{- n} x <2 . Şimdi, logaritmanın tamsayı kısmı basitçe n'dir ve kesirli kısım log _2'dir (2 ^{- n} x ) . Diğer bir deyişle: ${\displaystyle \lfloor \log _{2}x\rfloor }$

${\displaystyle \log _{2}x=n+\log _{2}y\quad {\text{nerede }}y=2^{-n}x{\text{ ve }}y\in [1, 2)}$

Normalleştirilmiş kayan nokta sayıları için, tamsayı kısmı kayan nokta üssü tarafından verilir ve tamsayılar için bir sayım önde gelen sıfır işlemi gerçekleştirilerek belirlenebilir .

Sonucun kesirli kısmı log ₂  y'dir ve yalnızca basit çarpma ve bölme kullanılarak yinelemeli olarak hesaplanabilir. Kesirli kısmı hesaplama algoritması, sözde kodda aşağıdaki gibi açıklanabilir :

1. Yarı açık aralıkta [1, 2) gerçek bir y sayısı ile başlayın . Eğer y = 1 olarak , algoritma yapılır ve kesirli kısmı sıfırdır.
2. Aksi takdirde, sonuç z [2, 4) aralığında kalana kadar y'yi art arda kareleyin . Gerekli kare sayısı m olsun . Diğer bir deyişle, Z = Y ^{2 m} ile m şekilde seçilir z içinde [2, 4) .
3. Her iki tarafın logaritmasını almak ve biraz cebir yapmak:
   $${\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{hizalı}}}$$

   
4. Bir kez daha z /2 , [1, 2) aralığında gerçek bir sayıdır . 1. adıma dönün ve aynı yöntemi kullanarak z /2'nin ikili logaritmasını hesaplayın .

Bunun sonucu , algoritmanın i -inci yinelemesinde gereken kare sayısı olan aşağıdaki özyinelemeli formüllerle ifade edilir : ${\displaystyle m_{i}}$

$${\displaystyle {\begin{aligned}\log _{2}x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{ -m_{3}}\sol(1+\cdots \sağ)\sağ)\sağ)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2 }}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{hizalı}}}$$

1. adımda kesirli kısmın sıfır olduğu özel durumda, bu bir noktada sona eren sonlu bir dizidir. Aksi takdirde, bu bir sonsuz seriler bu yakınsak göre oran testi her bir terim kesinlikle daha öncekinden daha olduğu, (her yana m _i > 0 ). Pratik kullanım için, yaklaşık bir sonuca ulaşmak için bu sonsuz serinin kısaltılması gerekir. Seri, i -inci terimden sonra ^{kesilirse, sonuçtaki} hata 2 ^{−( m ₁ + m ₂ + ⋯ + m _i ) 'den küçüktür} .

Yazılım kitaplığı desteği

log2İşlevleri standart dahildir Cı matematiksel fonksiyonlar . Bu işlevin varsayılan sürümü, çift ​​duyarlıklı bağımsız değişkenler alır, ancak bunun türevleri, bağımsız değişkenin tek duyarlıklı olmasına veya uzun bir çift olmasına izin verir . MATLAB gibi karmaşık sayıları ve örtük tür dönüştürmeyi destekleyen bilgi işlem ortamlarında , işlevin argümanının negatif bir sayı olmasına izin verilir ve karmaşık bir sayı döndürülür. log2

Referanslar

Dış bağlantılar

• Weisstein, Eric W. , "İkili Logaritma" , MathWorld
• Anderson, Sean Eron (12 Aralık 2003), "O(lg(N)) işlemlerinde bir N-bit tamsayının günlük tabanı 2'yi bulun" , Bit Twiddling Hacks , Stanford University , alınan 2015-11-25
• Feynman ve Bağlantı Makinesi