خوارزمية BKM

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 29 صور
الموسوعة الحرة

خوارزمية BKM هي خوارزمية إزاحة وجمع لحساب الدوال الأولية ، نُشرت لأول مرة عام 1994 على يد جان كلود باجارد، وسيلفانوس كلا، وجان ميشيل مولر . تعتمد خوارزمية BKM على حساب اللوغاريتمات المركبة ( النمط L ) والدوال الأسية ( النمط E ) باستخدام طريقة مشابهة للخوارزمية التي استخدمها هنري بريغز لحساب اللوغاريتمات. باستخدام جدول مُعدّ مسبقًا للوغاريتمات القوى السالبة للعدد اثنين، تحسب خوارزمية BKM الدوال الأولية باستخدام عمليات الجمع والإزاحة والمقارنة للأعداد الصحيحة فقط.

تُشبه خوارزمية BKM خوارزمية CORDIC ، لكنها تستخدم جدولًا للوغاريتمات بدلًا من جدول لظلال الدوال . في كل تكرار، يُختار مُعامل من مجموعة تسعة أعداد مركبة: 1، 0، -1، i، -i، 1+i، 1-i، -1+i، -1-i، بدلًا من -1 أو +1 فقط كما في خوارزمية CORDIC. تُوفر BKM طريقةً أبسط لحساب بعض الدوال الأساسية، وعلى عكس CORDIC، لا تحتاج BKM إلى عامل قياس للنتائج. يبلغ معدل تقارب BKM بتًا واحدًا تقريبًا لكل تكرار، مثل CORDIC، لكن BKM تتطلب عددًا أكبر من عناصر الجدول المُحسوبة مُسبقًا للحصول على نفس الدقة، لأن الجدول يخزن لوغاريتمات المعاملات المركبة.

كما هو الحال مع الخوارزميات الأخرى في فئة الإزاحة والجمع، فإن خوارزمية BKM مناسبة بشكل خاص للتنفيذ على مستوى الأجهزة. يعتمد الأداء النسبي لتنفيذ BKM برمجياً مقارنةً بطرق أخرى مثل التقريبات متعددة الحدود أو النسبية على توفر عمليات إزاحة سريعة متعددة البتات (أي مُزحزح برميلي ) أو عمليات حسابية للفاصلة العائمة على مستوى الأجهزة .

ملخص

لحل المعادلة

ln⁡(x)=y{\displaystyle \ln(x)=y}

تستفيد خوارزمية BKM من خاصية أساسية للوغاريتمات

ln⁡(أب)=ln⁡(أ)+ln⁡(ب){\displaystyle \ln(ab)=\ln(a)+\ln(b)}

باستخدام رمز باي ، يمكن تعميم هذه المتطابقة إلى

ln⁡(∏ك=0نأك)=∑ك=0نln⁡(أك){\displaystyle \ln \left(\prod _{k=0}^{n}a_{k}\right)=\sum _{k=0}^{n}\ln(a_{k})}

لأن أي عدد يمكن تمثيله بضرب عدد، فإن هذا يسمح لنا باختيار أي مجموعة من القيمأك{\displaystyle a_{k}}والتي تُضرب للحصول على القيمة التي بدأنا بها. في أنظمة الحاسوب، يكون الضرب والقسمة على مضاعفات العدد 2 أسرع بكثير، ولكن نظرًا لأن ليس كل عدد من مضاعفات العدد 2، فإن استخدامأك=1+2م{\displaystyle a_{k}=1+2^{m}}يُعد خيارًا أفضل من خيار أبسط هوأك=2م{\displaystyle a_{k}=2^{m}}بما أننا نريد أن نبدأ بتغييرات كبيرة ونصبح أكثر دقة كلماك{\displaystyle k}مع زيادة عدد الزيادات، يمكننا استخدام ذلك بشكل أكثر تحديدًاأك=1+2-ك{\displaystyle a_{k}=1+2^{-k}}مما يسمح للمنتج بالاقتراب من أي قيمة بين 1 و 4.768 تقريبًا، اعتمادًا على المجموعة الفرعية التيأك{\displaystyle a_{k}}نستخدمها في المنتج النهائي. عند هذه النقطة، تبدو المعادلة أعلاه كما يلي:

ln⁡(∏ك∈ك⊂Z0+1+2-ك)=∑ك∈ك⊂Z0+ln⁡(1+2-ك){\displaystyle \ln \left(\prod _{k\in K\subset \mathbb {Z} _{0}^{+}}1+2^{-k}\right)=\sum _{k\in K\subset \mathbb {Z} _{0}^{+}}\ln(1+2^{-k})}

هذا الاختيار لـأك{\displaystyle a_{k}}يقلل ذلك من التعقيد الحسابي للمنتج من الضرب المتكرر إلى الجمع البسيط وإزاحة البتات اعتمادًا على التنفيذ. وأخيرًا، عن طريق تخزين القيمln⁡(1+2-ك){\displaystyle \ln(1+2^{-k})}في الجدول، يُعد حساب الحل مسألة جمع بسيطة. وبالتكرار، نحصل على سلسلتين منفصلتين. تقترب إحدى السلسلتين من قيمة الإدخال.x{\displaystyle x}بينما يقترب الآخر من قيمة الإخراجln⁡(x)=y{\displaystyle \ln(x)=y}:

xك={1لو ك=0xك-1⋅(1+2-ك)لو xك سيكون≤xxك-1خلاف ذلك{\displaystyle x_{k}={\begin{cases}1&{\text{if }}k=0\\x_{k-1}\cdot (1+2^{-k})&{\text{if }}x_{k}{\text{ would be}}\leq x\\x_{k-1}&{\text{otherwise}}\end{cases}}}

بالنظر إلى هذا التعريف التكراري ولأنxك{\displaystyle x_{k}}إذا كانت الدالة متزايدة تمامًا، فيمكن إثبات ذلك بالاستقراء والتقارب .

ليمك→∞xك=x{\displaystyle \lim _{k\to \infty }x_{k}=x}

لأي1≤x≲4.768{\displaystyle 1\leq x\lesssim 4.768}لحساب الناتج، نقوم أولاً بإنشاء جدول مرجعي

أك=ln⁡(1+2-ك){\displaystyle A_{k}=\ln(1+2^{-k})}

ثم يتم حساب الناتج بشكل تكراري وفقًا للتعريف yك={0لو ك=0yك-1+أكلو xك سيكون≤xyك-1خلاف ذلك{\displaystyle y_{k}={\begin{cases}0&{\text{if }}k=0\\y_{k-1}+A_{k}&{\text{if }}x_{k}{\text{ would be}}\leq x\\y_{k-1}&{\text{otherwise}}\end{cases}}} الشروط في هذه الدورة هي نفسها شروط الإدخال. ومثل الإدخال، فإن هذه المتتالية متزايدة تمامًا، لذا يمكن إثبات أن

ليمك→∞yك=y{\displaystyle \lim _{k\to \infty }y_{k}=y}

لأي0≤y≲1.562{\displaystyle 0\leq y\lesssim 1.562}.

لأن الخوارزمية المذكورة أعلاه تحسب كلاً من المدخلات والمخرجات في وقت واحد، فمن الممكن تعديلها قليلاً بحيثy{\displaystyle y}هي القيمة المعروفة وx{\displaystyle x}هي القيمة التي نريد حسابها، وبالتالي نحسب الدالة الأسية بدلاً من اللوغاريتمية. وبما أن x تصبح مجهولة في هذه الحالة، فإن الشرط يتغير من

...لو xك سيكون≤x{\displaystyle \dots {\text{if }}x_{k}{\text{ would be}}\leq x}

ل

...لو yك سيكون≤y{\displaystyle \dots {\text{if }}y_{k}{\text{ would be}}\leq y}

دالة اللوغاريتم

لحساب دالة اللوغاريتم (النمط L)، تختبر الخوارزمية في كل تكرار ما إذا كانxن⋅(1+2-ن)≤x{\displaystyle x_{n}\cdot (1+2^{-n})\leq x}إذا كان الأمر كذلك، فإنه يحسبxن+1{\displaystyle x_{n+1}}وyن+1{\displaystyle y_{n+1}}. بعدشمال{\displaystyle N}بعد عدد معين من التكرارات، تُعرف قيمة الدالة مع هامش خطأ قدرهΔln⁡(x)≤2-شمال{\displaystyle \Delta \ln(x)\leq 2^{-N}}.

مثال لبرنامج اللوغاريتم الطبيعي في لغة C++ (انظر A_eالجدول):

دالة log_e المزدوجة ( وسيط مزدوج ثابت ، عدد صحيح ثابت بتات = 53 ) // 1 <= وسيط <= 4.768462058 { x = 1.0 ، y = 0.0 ، s = 1.0 ؛for ( int k = 0 ; k < bits ; k ++ ) { double const z = x + x * s ; if ( z <= argument ) { x = z ; y += A_e [ k ]; } s *= 0.5 ; } return y ; }

يمكن حساب اللوغاريتمات للأساسات الأخرى غير e بجهد مماثل.

مثال لبرنامج اللوغاريتم الثنائي في لغة C++ (انظر A_2الجدول):

double log_2 ( const double argument , const int bits = 53 ) // 1 <= argument <= 4.768462058 { double x = 1.0 , y = 0.0 , s = 1.0 ;for ( int k = 0 ; k < bits ; k ++ ) { double const z = x + x * s ; if ( z <= argument ) { x = z ; y += A_2 [ k ]; } s *= 0.5 ; } return y ; }

نطاق الوسيط المسموح به هو نفسه في كلا المثالين (1  ≤ 4.768462058 ...). في حالة اللوغاريتم ذي الأساس 2، يمكن فصل الأس مسبقًا (للحصول على الجزء الصحيح) بحيث يمكن تطبيق الخوارزمية على الباقي (بين 1 و2). بما أن الوسيط أصغر من 2.384231...، يمكن أن تبدأ عملية تكرار k من 1. عند العمل بأي أساس، يمكن استبدال الضرب في s بتعديل مباشر للأس ذي الفاصلة العائمة، بطرح 1 منه في كل تكرار. ينتج عن ذلك أن الخوارزمية تستخدم الجمع فقط دون الضرب. Argument  

الدالة الأسية

لحساب الدالة الأسية (النمط E)، تختبر الخوارزمية في كل تكرار ما إذا كانyن+ln⁡(1+2-ن)≤y{\displaystyle y_{n}+\ln(1+2^{-n})\leq y}إذا كان الأمر كذلك، فإنه يحسبxن+1{\displaystyle x_{n+1}}وyن+1{\displaystyle y_{n+1}}. بعدشمال{\displaystyle N}بعد عدد معين من التكرارات، تُعرف قيمة الدالة مع هامش خطأ قدرهΔخبرة⁡(x)≤2-شمال{\displaystyle \Delta \exp(x)\leq 2^{-N}}.

مثال لبرنامج مكتوب بلغة C++ (انظر A_eالجدول):

double exp ( const double argument , const int bits = 54 ) // 0 <= argument <= 1.5620238332 { double x = 1.0 , y = 0.0 , s = 1.0 ;for ( int k = 0 ; k < bits ; k ++ ) { double const z = y + A_e [ k ]; if ( z <= argument ) { y = z ; x = x + x * s ; } s *= 0.5 ; } return x ; }

جداول للأمثلة

ملحوظات

مراجع

للمزيد من القراءة