اللوغاريتم الثنائي

عدد الأرقام ( البتات ) في التمثيل الثنائي لعدد صحيح موجب n هو الجزء الصحيح من 1 + log ₂ n ، أي ^{[ 12 ]}

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

في نظرية المعلومات، يُعبَّر عن مقدار المعلومات الذاتية وإنتروبيا المعلومات غالبًا باللوغاريتم الثنائي، ما يجعل البت الوحدة الأساسية للمعلومات . وباستخدام هذه الوحدات، تُعبِّر نظرية شانون-هارتلي عن سعة المعلومات لقناة ما على أنها اللوغاريتم الثنائي لنسبة الإشارة إلى الضوضاء، مضافًا إليه واحد. مع ذلك، يُستخدم اللوغاريتم الطبيعي و √nat أيضًا في تدوينات بديلة لهذه التعريفات. ^{[ 26 ]}

على الرغم من أن اللوغاريتم الطبيعي أكثر أهمية من اللوغاريتم الثنائي في العديد من مجالات الرياضيات البحتة مثل نظرية الأعداد والتحليل الرياضي ، ^{[ 27 ]} فإن للوغاريتم الثنائي العديد من التطبيقات في التوافقية :

• كل شجرة ثنائية ذات n ورقة يكون ارتفاعها على الأقل log₂n _، ويتحقق التساوي عندما يكون n قوة للعدد اثنين وتكون الشجرة شجرة ثنائية كاملة . ^{[ 28 ]} وبالمثل، فإن ^عدد ستراهلر لنظام نهري ذي n رافد هو على ^الأكثر log₂n + 1. ^[ ₂₉ ]
• كل عائلة من المجموعات التي تحتوي على n مجموعة مختلفة تحتوي على ما لا يقل عن log ₂ n عنصرًا في اتحادها، مع المساواة عندما تكون العائلة مجموعة قوى . ^{[ 30 ]}
• كل مكعب جزئي ذو n رأس له بُعد متساوي القياس لا يقل عن log ₂ n ، وله على الأكثر 1 / 2 n log ₂ n من الحواف ، مع المساواة عندما يكون المكعب الجزئي عبارة عن رسم بياني مكعب فائق . ^{[ 31 ]}
• وفقًا لنظرية رامزي ، فإن كل رسم بياني غير موجه ذي n رأسًا يحتوي إما على زمرة أو مجموعة مستقلة بحجم لوغاريتمي بالنسبة لـ _n . الحجم الدقيق الذي يمكن ضمانه غير معروف، لكن أفضل الحدود المعروفة لحجمه تتضمن اللوغاريتمات الثنائية. على وجه الخصوص، تحتوي جميع الرسوم البيانية على زمرة أو مجموعة مستقلة بحجم لا يقل عن 1/2 log₂ n ( 1 - o ( 1))، ولا تحتوي معظم الرسوم البيانية على زمرة أو مجموعة مستقلة بحجم أكبر من 2 log₂ _n ( 1 + o (1)) . ^{[ 32 ]}
• من خلال تحليل رياضي لنموذج جيلبرت-شانون-ريدز للخلط العشوائي، يمكن إثبات أن عدد مرات خلط مجموعة أوراق لعب مكونة من n ورقة، باستخدام خلطات ريفيل ، للحصول على توزيع للتباديل قريب من التوزيع العشوائي المنتظم، يساوي تقريبًا 3/2 log₂ _n . وتشكل هذه الحسابات أساسًا لتوصية بخلط مجموعات أوراق اللعب المكونة من 52 ورقة سبع مرات . ^{[ 33 ]}

يظهر اللوغاريتم الثنائي بكثرة في تحليل الخوارزميات ، ^{[ 19 ]} ليس فقط بسبب الاستخدام المتكرر للحساب الثنائي في الخوارزميات، بل أيضًا لأن اللوغاريتم الثنائي يظهر في تحليل الخوارزميات القائمة على التفرع ثنائي الاتجاه. ^{[ 14 ]} إذا كانت المسألة تحتوي في البداية على n خيارًا لحلها، وكل تكرار للخوارزمية يقلل عدد الخيارات إلى النصف، فإن عدد التكرارات اللازمة لاختيار خيار واحد هو الجزء الصحيح من log₂n . تُستخدم هذه الفكرة في تحليل العديد من الخوارزميات وهياكل البيانات . على سبيل المثال، في البحث الثنائي ، يُقسم حجم المسألة المراد حلها إلى النصف مع كل تكرار، وبالتالي يلزم ما يقارب log₂n _{تكرارًا للحصول} على حل لمسألة حجمها n . ^{[ 34 ]} وبالمثل، فإن شجرة البحث الثنائية المتوازنة تمامًا التي تحتوي على n عنصرًا يكون ارتفاعها _log₂ ( n + 1) - 1. ^{[ 35 ]}

يُعبّر عادةً عن زمن تشغيل الخوارزمية باستخدام ترميز Big O ، الذي يُستخدم لتبسيط التعبيرات بحذف العوامل الثابتة والحدود ذات الرتبة الأدنى. ولأن اللوغاريتمات في قواعد مختلفة لا تختلف عن بعضها إلا بعامل ثابت، يُمكن القول إن الخوارزميات التي تعمل في زمن O (log₂n ₎ تعمل أيضًا في زمن O (log¹³n ) ، _على سبيل المثال. لذا ، فإن أساس اللوغاريتم في تعبيرات مثل O (log n ) أو O ( n log n ) ليس مهمًا ويمكن حذفه. ^{[ 11 ] [ 36 ]} مع ذلك، بالنسبة للوغاريتمات التي تظهر في أس حد زمني، لا يُمكن حذف أساس اللوغاريتم. على سبيل المثال، O (2 ^log₂n ) ليس هو نفسه O (2 ^{ln _n ) لأن} الأول يساوي O ( n ) والثاني يساوي O ( n ^0.6931... ) .

تُسمى الخوارزميات التي يكون زمن تشغيلها O ( n  log n ) أحيانًا  بالخوارزميات الخطية . ^{[ 37 ]} ومن أمثلة الخوارزميات التي يكون زمن تشغيلها O (log n ) أو O ( n log n ) :

• متوسط ​​الوقت للفرز السريع وخوارزميات الفرز المقارنة الأخرى ^{[ 38 ]}
• البحث في أشجار البحث الثنائية المتوازنة ^{[ 39 ]}
• الأسس عن طريق التربيع ^{[ 40 ]}
• أطول سلسلة فرعية متزايدة ^{[ 41 ]}

تظهر اللوغاريتمات الثنائية أيضًا في أسس حدود الوقت لبعض خوارزميات فرق تسد ، مثل خوارزمية كاراتسوبا لضرب أعداد مكونة من n بت في زمن ^O ( ⁿ log₂³ ) ، ^[ 42 ] ^{وخوارزمية ستراسن لضرب} مصفوفات n × n في زمن O ( n log₂ ^{_· )} . [ ^{43 ] _ويمكن} تفسير ظهور اللوغاريتمات الثنائية في أزمنة التشغيل هذه بالرجوع إلى ^{النظرية} الرئيسية لتكرارات فرق تسد .

في المعلوماتية الحيوية ، تُستخدم المصفوفات الدقيقة لقياس قوة التعبير عن الجينات المختلفة في عينة من المادة البيولوجية. غالبًا ما تُقارن معدلات التعبير المختلفة لجين ما باستخدام اللوغاريتم الثنائي لنسبة معدلات التعبير: يُعرَّف لوغاريتم نسبة معدلي تعبير بأنه اللوغاريتم الثنائي لنسبة هذين المعدلين. تُتيح اللوغاريتمات الثنائية مقارنة سهلة لمعدلات التعبير: على سبيل المثال، يمكن وصف معدل التعبير المضاعف بنسبة لوغاريتم تساوي 1 ، ومعدل التعبير المتناقص إلى النصف بنسبة لوغاريتم تساوي -1 ، ومعدل التعبير الثابت بنسبة لوغاريتم تساوي صفر. ^{[ 44 ]}

غالباً ما يتم تمثيل نقاط البيانات التي تم الحصول عليها بهذه الطريقة على شكل مخطط انتشار يكون فيه أحد محوري الإحداثيات أو كلاهما عبارة عن لوغاريتمات ثنائية لنسب الشدة، أو في تمثيلات مرئية مثل مخطط MA ومخطط RA التي تقوم بتدوير وتغيير مقياس مخططات الانتشار هذه لنسب اللوغاريتم. ^{[ 45 ]}

في نظرية الموسيقى ، تُحدد المسافة أو الفرق الإدراكي بين نغمتين بنسبة تردداتهما. وتُعتبر المسافات الناتجة عن نسب أعداد نسبية ذات بسط ومقام صغيرين ذات تناغم موسيقي خاص. أبسط هذه المسافات وأهمها هي الأوكتاف ، وهي نسبة تردد 2:1 . عدد الأوكتافات التي تختلف بها نغمتان هو اللوغاريتم الثنائي لنسبة تردداتهما. ^{[ 46 ]}

لدراسة أنظمة الضبط وجوانب أخرى من نظرية الموسيقى التي تتطلب تمييزًا أدق بين النغمات، من المفيد وجود مقياس لحجم الفاصل الموسيقي يكون أدق من الأوكتاف ويكون جمعيًا (كما هو الحال في اللوغاريتمات) وليس ضربيًا (كما هو الحال في نسب الترددات). أي، إذا كانت النغمات س ، ص ، ع تُشكّل تسلسلًا تصاعديًا، فإن مجموع قياس الفاصل الموسيقي من س إلى ص وقياس الفاصل الموسيقي من ص إلى ع يجب أن يساوي قياس الفاصل الموسيقي من س إلى ع . يُعطى هذا المقياس بواسطة السنت ، الذي يقسم الأوكتاف إلى 1200 فاصل موسيقي متساوٍ ( 12 نصف نغمة ، كل منها 100 سنت). رياضيًا، إذا ^كانت لدينا نغمات بترددين f1 و f2 _{، فإن} عدد السنتات في الفاصل الموسيقي من f1 إلى f2 هو ^{[ 46} _{] .}

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

يتم تعريف الميلي أوكتاف بنفس الطريقة، ولكن بمعامل ضرب ¹⁰⁰⁰ بدلاً من 1200. ^[ 47 ^]

في الألعاب والرياضات التنافسية التي تضم لاعبين أو فريقين في كل مباراة، يشير اللوغاريتم الثنائي إلى عدد الجولات اللازمة في بطولة خروج المغلوب لتحديد الفائز. على سبيل المثال، تتطلب بطولة تضم 4 لاعبين جولتين (log₂ ₄ = 2) لتحديد الفائز، بينما تتطلب بطولة تضم 32 فريقًا 5 جولات (log₂ ₃₂ = 5) _، وهكذا. في هذه الحالة، بالنسبة لعدد n من اللاعبين/الفرق حيث n ليس قوة للعدد 2، يتم تقريب log₂ n إلى الأعلى لأنه من الضروري وجود جولة واحدة على الأقل لا يشارك فيها جميع المتنافسين المتبقين. على سبيل المثال، log₂ ₆ يساوي تقريبًا 2.585 ، والذي يُقرّب إلى 3 ، مما يشير إلى أن بطولة تضم 6 فرق تتطلب 3 جولات (إما أن يغيب فريقان عن الجولة الأولى، أو يغيب فريق واحد عن الجولة الثانية). يلزم نفس عدد الجولات لتحديد فائز واضح في بطولة بنظام سويسري . ^{[ 48 ]}

في التصوير الفوتوغرافي ، تُقاس قيم التعريض الضوئي باستخدام اللوغاريتم الثنائي لكمية الضوء الواصلة إلى الفيلم أو المستشعر، وفقًا لقانون ويبر-فيشنر الذي يصف الاستجابة اللوغاريتمية للجهاز البصري البشري للضوء. وتُمثل درجة التعريض الضوئي الواحدة وحدةً واحدةً على مقياس لوغاريتمي أساسه 2. ^{[ 49 ] [ 50 ]} وبشكل أدق، تُعرَّف قيمة التعريض الضوئي للصورة الفوتوغرافية على النحو التالي:

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

حيث N هو رقم البؤرة الذي يقيس فتحة العدسة أثناء التعريض، و t هو عدد ثواني التعريض. ^{[ 51 ]}

تُستخدم اللوغاريتمات الثنائية (المعبر عنها بالتوقفات) أيضًا في قياس الكثافة الضوئية ، للتعبير عن النطاق الديناميكي للمواد الحساسة للضوء أو أجهزة الاستشعار الرقمية. ^{[ 52 ]}

إحدى الطرق السهلة لحساب لوغاريتم _{n للعدد} n على الآلات الحاسبة التي لا تحتوي على دالة لوغاريتم ₂ هي استخدام دالة اللوغاريتم الطبيعي ( ln ) أو دالة اللوغاريتم العشري ( log أو log ₁₀ )، الموجودة في معظم الآلات الحاسبة العلمية . لتغيير أساس اللوغاريتم إلى 2 من e أو 10 أو أي أساس آخر b ، يمكن استخدام الصيغتين التاليتين : ^{[ 50 ] [ 53 ]}

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

تقريبًا، ^{[ 54 ] [ 55 ]}

${\displaystyle \log _{2}n\approx 1.442695\ln n\approx 3.321928\log _{10}n\,.}$

يمكن تحويل اللوغاريتم الثنائي إلى دالة من الأعداد الصحيحة وإليها عن طريق تقريبه لأعلى أو لأسفل. ويرتبط هذان الشكلان من اللوغاريتم الثنائي للأعداد الصحيحة بهذه الصيغة:

${\displaystyle \lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{ إذا كان }}n\geq 1.}$^{[ 56 ]}

يمكن توسيع التعريف من خلال تعريف${\displaystyle \lfloor \log _{2}(0)\rfloor =-1}$. بهذه الطريقة، ترتبط هذه الوظيفة بعدد الأصفار البادئة للتمثيل الثنائي غير الموقع 32 بت لـ x ، nlz( x ) .

${\displaystyle \lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (n).}$^{[ 56 ]}

يمكن تفسير اللوغاريتم الثنائي الصحيح على أنه فهرس البت ذي القيمة 1 الأكثر أهمية في المدخلات، بدءًا من الصفر. وبهذا المعنى، فهو مكمل لعملية البحث عن أول مجموعة ، التي تحدد فهرس البت ذي القيمة 1 الأقل أهمية . تدعم العديد من منصات الأجهزة إيجاد عدد الأصفار البادئة، أو عمليات مكافئة، والتي يمكن استخدامها لإيجاد اللوغاريتم الثنائي بسرعة. كما تقوم الدالتان ` flslog` و`log` flslفي نواة لينكس ^{[ 57 ]} وفي بعض إصدارات مكتبة libc البرمجية بحساب اللوغاريتم الثنائي (مقربًا إلى عدد صحيح، زائد واحد).

لعدد${\displaystyle x}$ممثلة بالأرقام العشرية كـ${\displaystyle x=2^{E}(1+m)}$، مع أس صحيح${\displaystyle E}$والمانتيسا​${\displaystyle m}$في النطاق${\displaystyle 0\leq m<1}$يمكن تقريب اللوغاريتم الثنائي تقريبًا على النحو التالي:${\displaystyle \log _{2}x\approx E+m}$[ ^{16 ] هذا التقريب دقيق عند طرفي نطاق قيم الجزء الكسري ،} ولكنه يقلل من قيمة اللوغاريتم في منتصف النطاق، حيث يصل الخطأ الأقصى إلى حوالي 0.086 عند قيمة جزء كسري تقارب 0.44. ويمكن تحسين دقته باستخدام دالة خطية مجزأة .${\displaystyle m}$[ ^{58 ] أو بشكل أبسط} عن طريق إضافة حد تصحيح ثابت${\displaystyle \log _{2}x\approx E+m+\sigma }$على سبيل المثال، اختيار${\displaystyle \sigma \approx 0.043}$سيؤدي ذلك إلى تقليل الخطأ الأقصى إلى النصف. تستخدم خوارزمية الجذر التربيعي العكسي السريع هذه الفكرة، مع حد تصحيح مختلف يمكن استنتاجه على أنه${\displaystyle \sigma \approx 0.0450466}$، من خلال التلاعب المباشر بالتمثيل الثنائي لـ${\displaystyle x}$لضرب هذا اللوغاريتم التقريبي في${\displaystyle -{\tfrac {1}{2}}}$، والحصول على قيمة فاصلة عائمة تقارب${\displaystyle 1/{\sqrt {x}}}$[ ^{59 ]​}

بالنسبة لأي عدد حقيقي موجب عام ، يمكن حساب اللوغاريتم الثنائي على مرحلتين. ^{[ 60 ]} أولاً، يتم حساب الجزء الصحيح ،${\displaystyle \lfloor \log _{2}x\rfloor }$(تُسمى خاصية اللوغاريتم). هذا يُبسط المسألة إلى مسألة يكون فيها وسيط اللوغاريتم ضمن نطاق محدود، وهو الفترة [ 1، 2) ، مما يُسهل الخطوة الثانية لحساب الجزء الكسري (مانتيسا اللوغاريتم). لأي قيمة x > 0 ، يوجد عدد صحيح وحيد n بحيث يكون 2n ≤ x < 2n ^{+ 1} ، أو بصورة مكافئة ¹ ≤ 2 ^{− n} x < 2. الآن، الجزء الصحيح من اللوغاريتم هو n ، والجزء الكسري هو _log₂ ( 2 ^{− n} x ) . ^{[ 60 ]} بعبارة أخرى:

${\displaystyle \log _{2}x=n+\log _{2}y\quad {\text{حيث ​​}}y=2^{-n}x{\text{ و }}y\in [1,2)}$

بالنسبة للأعداد العشرية المعيارية ، يُعطى الجزء الصحيح بواسطة أس العدد العشري، ^{[ 61 ]} وبالنسبة للأعداد الصحيحة، يمكن تحديده عن طريق إجراء عملية عد الأصفار البادئة . ^{[ 62 ]}

الجزء الكسري من النتيجة هو لوغاريتم ₂ ص ، ويمكن حسابه تكراريًا باستخدام عمليتي الضرب والقسمة الأساسيتين فقط. ^{[ 60 ]} يمكن وصف خوارزمية حساب الجزء الكسري بلغة شبه رمزية كما يلي:

1. ابدأ بعدد حقيقي y في الفترة نصف المفتوحة [ 1، 2) . إذا كانت y = 1 ، فإن الخوارزمية تكون قد انتهت، ويكون الجزء الكسري صفرًا.
2. وإلا، قم بتربيع y بشكل متكرر حتى تقع النتيجة z في الفترة [ 2، 4) . ليكن m عدد عمليات التربيع المطلوبة. أي أن z = y² ^{/ m،} حيث يتم اختيار m بحيث تكون z في الفترة [ 2، 4] .
3. بأخذ اللوغاريتم لكلا الطرفين وإجراء بعض العمليات الجبرية:$$\displaystyle \begin{aligned}\log_2z=2^m\log_2y\log_2y=\frac{\log_2z}{2^m}\&=\frac{1+\log_2(z/2)}{2^m}\&=2^-m+2^-m\log_2(z/2).\end{aligned}}}$$
4. مرة أخرى ، z /2 عدد حقيقي في الفترة [ 1، 2) . ارجع إلى الخطوة 1 واحسب اللوغاريتم الثنائي لـ z /2 باستخدام نفس الطريقة.

تُعبّر الصيغ التكرارية التالية عن نتيجة ذلك، حيث${\displaystyle m_{i}}$يمثل عدد عمليات التربيع المطلوبة في التكرار رقم i من الخوارزمية: $${\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}}}$$

في الحالة الخاصة التي يكون فيها الجزء الكسري في الخطوة 1 مساويًا للصفر، تكون هذه متتالية منتهية تنتهي عند نقطة ما. وإلا، فهي متسلسلة لانهائية تتقارب وفقًا لاختبار النسبة ، لأن كل حد أصغر تمامًا من الحد السابق (لأن كل mᵢ _> 0 ). انظر طريقة هورنر . وللاستخدام العملي، يجب اقتطاع ^{_{هذه المتسلسلة اللانهائية للوصول} إلى} نتيجة تقريبية. إذا اقتُطعت المتسلسلة بعد الحد i ، فإن الخطأ في النتيجة يكون أقل من 2 ^{− ( m₁ ₊ m₂ + ... + mᵢ ₎} . ^{[ 60 ]}

log2تُعدّ هذه الدالة جزءًا من دوال الرياضيات القياسية في لغة C. تأخذ النسخة الافتراضية منها وسائط ذات دقة مزدوجة، لكن بعض المتغيرات تسمح بأن تكون الوسائط ذات دقة مفردة أو من نوع long double . ^{[ 63 ]} في بيئات الحوسبة التي تدعم الأعداد المركبة والتحويل الضمني للأنواع، مثل MATLAB،log2 يُسمح بأن يكون وسيط الدالة عددًا سالبًا ، مع إرجاع عدد مركب. ^{[ 64 ]}