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

---

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

---

أكرر أن هذا ليس مقالًا علميًا ، ولكنه مقال علمي مشهور ، وبعد قراءته ، سوف تتعرف عليه بإيجاز.

• يتم تقريب الدوال الابتدائية المتعالية (exp ، و sin ، و log ، و cosh وغيرها) التي تعمل مع حساب الفاصلة العائمة بشكل غير صحيح ، وأحيانًا ترتكب خطأ في البت الأخير.
• لا يكمن سبب الأخطاء دائمًا في الكسل أو تدني مؤهلات المطورين ، ولكن في ظرف أساسي واحد لم يتمكن العلم الحديث من التغلب عليه بعد.
• «», - .
• , , , , exp2(x) pow(2.0, x).

لفهم محتويات هذه المقالة ، يجب أن تكون على دراية بتنسيق الفاصلة العائمة IEEE-754. سيكون كافيًا إذا فهمت على الأقل أنه ، على سبيل المثال ، هذا هو: 0x400921FB54442D18 - رقم pi بتنسيق مزدوج الدقة (ثنائي 64 أو مزدوج) ، أي أنك تفهم فقط ما أعنيه بهذا السجل ؛ أنا لا أطالب بأن أكون قادرًا على إجراء مثل هذه التحولات بسرعة. وسأذكرك بأوضاع التقريب في هذه المقالة ، هذا جزء مهم من القصة. من المستحسن أيضًا معرفة الإنجليزية "المبرمج" ، لأنه سيكون هناك مصطلحات واقتباسات من الأدب الغربي ، ولكن يمكنك الحصول على مترجم عبر الإنترنت.



الأمثلة أولاً ، حتى تفهم على الفور ماهية موضوع المحادثة. سأقدم الآن الكود بلغة C ++ ، ولكن إذا لم تكن هذه هي لغتك ، فأنا متأكد من أنك ستظل تفهم ما هو مكتوب بسهولة. الرجاء إلقاء نظرة على هذا الرمز:

#include <stdio.h>
#include <cmath>

int main() {
  float x = 0.00296957581304013729095458984375f;  // ,  .
  float z;
  z = exp2f(x);  // z = 2**x  .
  printf ("%.8f\n", z);  //      8   .
  z = powf(2.0f, x);  // z = 2**x  
  printf ("%.8f\n", z);  //   .
  return 0;
}

يتم كتابة الرقم x عن قصد بمثل هذا العدد من الأرقام المهمة بحيث يمكن تمثيله تمامًا في النوع العائم ، أي بحيث يقوم المترجم بتحويله إلى رمز ثنائي بدون التقريب. بعد كل شيء ، أنت تعلم جيدًا أن بعض المترجمين غير قادرين على التقريب بدون أخطاء (إذا كنت لا تعرف ، أشر في التعليقات ، فسأكتب مقالة منفصلة مع أمثلة). بعد ذلك في البرنامج ، نحتاج إلى حساب 2 ^x ، لكن لنقم بذلك بطريقتين: الدالة exp2f (x) ، والأس الصريح لاثنين من powf (2.0f ، x). ستكون النتيجة ، بالطبع ، مختلفة ، لأنني قلت أعلاه أن الوظائف الأولية لا يمكن أن تعمل بشكل صحيح في جميع الحالات ، وقد اخترت مثالاً خصيصًا لإظهار ذلك. إليك ما سيكون الناتج:

1.00206053
1.00206041

أعطاني أربعة مترجمين هذه القيم: Microsoft C ++ (19.00.23026) و Intel C ++ 15.0 و GCC (6.3.0) و Clang (3.7.0). إنها تختلف في بت واحد على الأقل. إليك الكود السداسي العشري لهذه الأرقام:

0x3F804385  // 
0x3F804384  // 

يرجى تذكر هذا المثال ، حيث سننظر في جوهر المشكلة بعد قليل ، ولكن في الوقت الحالي ، حتى تحصل على انطباع أوضح ، يرجى الاطلاع على أمثلة لنوع البيانات مزدوج الدقة (double ، binary64) مع بعض الوظائف الأولية الأخرى. أقدم النتائج في الجدول. الإجابات الصحيحة (عند توفرها) تحتوي على * في النهاية.







آمل ألا يكون لديك انطباع بأنني أجريت عمدا بعض الاختبارات الفريدة التي بالكاد تجدها؟ إذا كان الأمر كذلك ، فلنطبخ على ركبنا تعدادًا كاملاً لجميع الحجج الكسرية الممكنة للدالة 2 ^x لنوع البيانات العائمة. من الواضح أننا مهتمون فقط بقيم x بين 0 و 1 ، لأن الحجج الأخرى ستعطي نتيجة تختلف فقط في القيمة في حقل الأس وليست ذات أهمية. أنت نفسك تفهم:

$$

$$2^x = 2^{[x]}\cdot2^{\{x\}}.$$

بعد كتابة مثل هذا البرنامج (سيكون النص المخفي أدناه) ، راجعت وظيفة exp2f وعدد القيم الخاطئة التي تنتجها على الفاصل الزمني x من 0 إلى 1.







يتضح من البرنامج أدناه أن عدد الوسائط x التي تم اختبارها كان 197612997. اتضح ، على سبيل المثال ، أن Microsoft C ++ تحسب بشكل غير صحيح وظيفة 2 ^x لما يقرب من واحد بالمائة منهم. لا تفرحوا ، أيها المعجبون الأعزاء في GCC و Clang ، إن هذه الوظيفة يتم تنفيذها بشكل صحيح في هذه المجمعين ، ولكنها مليئة بالأخطاء في الآخرين.





لن أتحمل القارئ بهذه الأمثلة ، الشيء الرئيسي هنا هو إظهار أن التطبيقات الحديثة للوظائف المتعالية يمكن أن تقرب الجزء الأخير بشكل غير صحيح ، وأن المترجمين المختلفين يرتكبون أخطاء في أماكن مختلفة ، لكن لن يعمل أي منهم بشكل صحيح. بالمناسبة ، يسمح معيار IEEE-754 بهذا الخطأ في الجزء الأخير (والذي سأتحدث عنه أدناه) ، لكنه لا يزال يبدو غريبًا بالنسبة لي: حسنًا ، هذا نوع بيانات كبير ، ولكن يمكن التحقق من التعويم بالقوة الغاشمة! هل كان من الصعب القيام بذلك؟ ليس صعبًا على الإطلاق ، وقد عرضت بالفعل مثالاً.



يحتوي كود التعداد لدينا على وظيفة "مكتوبة ذاتيًا" للحساب الصحيح 2 ^xباستخدام كثير الحدود التقريبي من الدرجة العاشرة ، وقد تمت كتابته في بضع دقائق ، لأن مثل هذه كثيرات الحدود مشتقة تلقائيًا ، على سبيل المثال ، في نظام الجبر الحاسوبي Maple. يكفي تعيين شرط لكثير الحدود لتوفير 54 بت من الدقة (لهذه الوظيفة ، 2 ^× ). لماذا 54؟ لكنك ستكتشف قريبًا ، مباشرة بعد أن أخبرك بجوهر المشكلة وأخبرك لماذا ، من حيث المبدأ ، من المستحيل الآن إنشاء وظائف متعالية سريعة وصحيحة لنوع البيانات ذي الدقة الرباعية (binary128) ، على الرغم من وجود محاولات بالفعل لمهاجمة هذه المشكلة من الناحية النظرية.

التقريب الافتراضي والمشكلة في ذلك

إذا لم تكن منغمسًا في تطوير المكتبات الرياضية ، فلا حرج في نسيان قاعدة التقريب الافتراضية لأرقام الفاصلة العائمة وفقًا لمعيار IEEE-754. لذلك سوف أذكرك بذلك. إذا كنت تتذكر كل شيء جيدًا ، ألق نظرة على الأقل في نهاية هذا القسم على أي حال ، فأنت في حالة مفاجأة: سأريك موقفًا قد يكون فيه تقريب رقم صعبًا للغاية.



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



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

1. Round 1.00 1 001. البتة الثالثة بعد الفاصلة العشرية هي 1 ، ولكن هناك بتة سادسة أخرى ، وهي 1 ، مما يعني أن التقريب سيرتفع ، لأن الرقم الأصلي أقرب إلى 1.01 من 1.00.
2. 1,001000. , 1,00 1,01, .
3. 1,011000. 1,01 1,10. , .
4. 1,010111. , 1,01, 1,10.

من هذه الأمثلة ، قد يبدو أن كل شيء بسيط ، لكنه ليس كذلك. الحقيقة هي أنه في بعض الأحيان لا يمكننا أن نقول على وجه اليقين ما إذا كنا حقًا في الوسط بين قيمتين. انظر الى مثال. دعنا نرغب مرة أخرى في التقريب إلى بتتين بعد الفاصلة العشرية:



1.00 1 0000000000000000000000000000000000001 من



الواضح لك الآن أن التقريب يجب أن يكون لأعلى ، أي إلى الرقم 1.01. ومع ذلك ، فأنت تنظر إلى رقم مكون من 40 بتًا بعد العلامة العشرية. ماذا لو فشلت الخوارزمية في توفير 40 بتًا من الدقة وحققت 30 بتًا فقط؟ ثم ستعطي رقمًا آخر:



1.00 1 000000000000000000000000000



غير مدرك أنه في المركز 40 (الذي لا تستطيع الخوارزمية حسابه) سيكون هناك رقم عزيز ، تقرب هذا الرقم لأسفل وتحصل على 1.00 ، وهو خطأ. لقد قمت بتقريب الجزء الأخير بشكل غير صحيح - هذا هو موضوع مناقشتنا. مما سبق ، اتضح أنه من أجل الحصول على البت الثاني الصحيح فقط ، يجب عليك حساب الدالة حتى 40 بت! نجاح باهر! وماذا لو كانت "قاطرة" الأصفار أطول من ذلك؟ هذا ما سنتحدث عنه في القسم التالي.



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

جوهر مشكلة تقريب آخر بت مهم

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

السبب الأول

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



على سبيل المثال ، إذا كنا نتحدث عن عدد x من النوع float في الفاصل الزمني (0.5 ؛ 1) ، فإن القيمة ulp = 2 ^-23 . على الفاصل الزمني (1 ؛ 2) ulp = 2 ^-22 . بمعنى آخر ، إذا كانت x على الفترة (0 ؛ 1) فإن 2 ^xسيكون على الفاصل الزمني (1،2) ، ولضمان دقة 0.5ulp ، تحتاج ، تقريبًا ، إلى اختيار EPS = 2 ^-23 (كما سنشير إلى "إبسيلون" الثابت ، في الأشخاص العاديين الذين يطلق عليهم "خطأ" ، أو "دقة" ، لمن كما تحب لا تجد العيب من فضلك).



بالنسبة للحسابات التطبيقية ، هذا كافٍ ، لكن حقيقة أن البتات الأخيرة قد لا تتطابق مع النتيجة المطلقة ليست مهمة لما يقرب من 100٪ من المبرمجين ، لأنه ليس من المهم بالنسبة لهم ما هي البتات ، ولكن ما هي الدقة.



بالنسبة لأولئك الذين لا يفهمون ، سأقدم مثالاً في نظام الأرقام العشري. هنا رقمان: 1.999999 و 2.0. لنفترض أن الأول هو ما حصل عليه المبرمج ، والثاني هو معيار ما كان يجب الحصول عليه إذا كانت لدينا إمكانيات غير محدودة. الفرق بينهما هو واحد على المليون فقط ، أي أن الإجابة تحسب بخطأ EPS = 10 ^-6 . ومع ذلك ، لا يوجد رقم صحيح واحد في هذه الإجابة. هل هو سيء؟ لا ، من وجهة نظر برنامج التطبيق ، هذا لونه أرجواني ، سيقوم المبرمج بتقريب الإجابة ، لنقل ، إلى منزلتين عشريتين وسيتلقى 2.00 (على سبيل المثال ، كان حول العملة ، 2.00 دولار) ، لا يحتاج إلى المزيد ، ولكن حقيقة أنه ضع EPS = 10 ^-6 في برنامجي ، ثم أحسنت ، أخذ هامشًا لخطأ الحسابات الوسيطة وحل المشكلة بشكل صحيح.



بعبارة أخرى ، لا يجب الخلط: الدقة وعدد البتات الصحيحة (أو الأرقام) شيئان مختلفان. أولئك الذين يحتاجون إلى الدقة (هذا ما يقرب من 100 ٪ من المبرمجين) ، فإن المشكلة التي تمت مناقشتها لا تهم هؤلاء على الإطلاق. أي شخص يحتاج إلى تسلسل صغير لمطابقة مرجع مستدير بشكل صحيح يكون قلقًا للغاية بشأن هذه المشكلة ، على سبيل المثال ، مطورو مكتبات الوظائف الأولية. ومع ذلك ، من المفيد للجميع معرفة ذلك من أجل التطوير العام.



دعني أذكرك أن هذا كان الاتجاه الأول للمشكلة: قد تكون الأجزاء الأخيرة من الإجابة خاطئة لأن هذا حل متعمد. الشيء الرئيسي هو الحفاظ على دقة 0.5ulp (أو أعلى). لذلك ، يتم تحديد الخوارزمية العددية فقط من هذا الشرط ، إذا كانت تعمل بسرعة كبيرة فقط. في الوقت نفسه ، يسمح المعيار بتنفيذ الوظائف الأولية دون التقريب الصحيح لآخر بت. أقتبس [1 ، القسم 12.1] (بالانكليزية):

لم تحدد نسخة 1985 من معيار IEEE 754 لحساب الفاصلة العائمة أي شيء يتعلق بالوظيفة الأولية. كان هذا بسبب الاعتقاد السائد منذ سنوات أن الدوال المقربة بشكل صحيح ستكون بطيئة جدًا على الأقل بالنسبة لبعض حجج المدخلات. تغير الوضع منذ ذلك الحين ويوصي إصدار 2008 من المعيار (لكنه لا يتطلب) تقريب بعض الوظائف بشكل صحيح.

فيما يلي الوظائف الموصى بها ولكن لا يلزم تقريبها بشكل صحيح:

السبب الثاني

أخيرًا وصلنا إلى موضوع المحادثة: معضلة صانع المائدة (والمختصرة باسم TMD). لم أتمكن من ترجمة اسمها بشكل مناسب إلى اللغة الروسية ، فقد قدمها ويليام كاهان (الأب المؤسس لـ IEEE-754) في المقالة [2]. ربما إذا قرأت المقال ، ستفهم سبب كون الاسم كذلك. باختصار ، جوهر المعضلة هو أننا بحاجة إلى تقريب دقيق تمامًا للدالة z = f (x) ، كما لو كان لدينا سجل بت غير محدود للنتيجة المحسوبة تمامًا z تحت تصرفنا. لكن من الواضح للجميع أنه لا يمكننا الحصول على تسلسل لا نهائي. كم عدد البتات لاتخاذ ذلك الحين؟ أعلاه ، عرضت مثالاً عندما نحتاج إلى رؤية 40 بت من النتيجة من أجل الحصول على بتتين صحيحتين على الأقل بعد التقريب. وجوهر مشكلة انظمة الدفاع الصاروخى التكتيكى هو أننا لا نعرف مسبقا، حتى عدد البتات المطلوب حساب قيمة z من أجل الحصول على أكبر عدد من البتات الصحيحة بعد التقريب كما نحتاج. ماذا لو كان هناك مائة أو ألف؟ لا نعلم مسبقا!



على سبيل المثال ، كما قلت ، بالنسبة للوظيفة 2 ^x ، بالنسبة لعائم نوع البيانات ، حيث يحتوي الجزء الكسري من الجزء العشري على 23 بتًا فقط ، نحتاج إلى إجراء الحساب بدقة ^2-54 بحيث يحدث التقريب بشكل صحيح لجميع وسائط x الممكنة دون استثناء. ليس من الصعب الحصول على هذا التقدير من خلال البحث الشامل ، ولكن بالنسبة لمعظم الوظائف الأخرى ، خاصة بالنسبة للأنواع مزدوجة أو طويلة مزدوجة (ضع "فئة" إذا كنت تعرف ما هي) ، فإن هذه التقديرات غير معروفة .



دعونا نفهم بالفعل سبب حدوث ذلك. لقد قدمت عن عمد المثال الأول في هذه المقالة بنوع البيانات العائمة وطلبت منك أن تتذكرها ، لأنه في هذا النوع لا يوجد سوى 32 بتًا وسيكون من الأسهل النظر إليها ، وفي أنواع البيانات الأخرى يكون الوضع مشابهًا.



بدأنا بالرقم x = 0.00296957581304013729095458984375 ، هذا رقم يمكن تمثيله بالضبط في نوع البيانات العائمة ، أي أنه مكتوب بحيث يمكن تحويله إلى نظام الطفو الثنائي دون التقريب. نحسب 2 ^س ، وإذا كان لدينا آلة حاسبة مع دقة لانهائية، ثم يجب أن نحصل على (حتى تتمكن من التحقق لي، ويتم حساب في نظام الانترنت ولفرام ألفا ):



1،0020604729652405753669743044108123031635398201893943954577320057 ...



دعنا نترجم هذا الرقم إلى ثنائي ، لنفترض أن 64 بت ستكون كافية:



1.00000000100001110000100 1 000000000000000000000000000001101111101



بتة التقريب (بت 24 بعد الفاصلة العشرية) تم تسطيرها. سؤال: أين جولة؟ صعودا أو هبوطا؟ من الواضح أنك تعرف هذا لأنك ترى عددًا كافيًا من الأجزاء ويمكنك اتخاذ قرار. لكن انظر بعناية ...



بعد لقمة التقريب ، لدينا 29 صفراً. هذا يعني أننا قريبون جدًا جدًا من الوسط بين أقرب رقمين ويكفي التحرك لأسفل قليلاً ، حيث سيتغير اتجاه التقريب. لكن السؤال هو: أين سيكون هذا التحول؟ يمكن للخوارزمية العددية بالتسلسل ، خطوة بخطوة ، الاقتراب من القيمة الدقيقة من جوانب مختلفة ، وحتى نمرر كل هذه الأصفار الـ 29 ونصل إلى دقة تتجاوز قيمة الصفر الأخير في هذه "القاطرة" ، لن نعرف اتجاه التقريب ... ماذا لو كانت الإجابة الصحيحة في الواقع هي:



1.00000000100001110000100 0 111111111111111111111111111؟



ثم سيتم التقريب إلى أسفل.



لا نعرف هذا حتى تصل الدقة إلى 54 بت بعد العلامة العشرية. عندما تُعرف البتة الرابعة والخمسون بالضبط ، سنعرف بالضبط أي من أقرب عددين أقرب إليهما. تسمى هذه الأرقام بالنقاط الأصعب إلى التقريب [1 ، القسم 12.3] (النقاط الحرجة للتقريب) ، والرقم 54 يسمى الصلابة بالتقريب ، ويُشار إليه بالحرف م في الكتاب المذكور.



تعقيد التقريب (m) هو عدد البتات وهو الحد الأدنى الضروري للتأكد من أنه بالنسبة لجميع وسيطات بعض الدالة f (x) ونطاق محدد مسبقًا ، يتم تقريب الوظيفة f (x) بشكل صحيح إلى آخر بت (لأنماط التقريب المختلفة ، قد يكون هناك اختلاف القيمة م). بعبارة أخرى ، بالنسبة لعائم نوع البيانات وللوسيطة x من النطاق (0 ؛ 1) لوضع التقريب "أقرب زوجي" ، يكون تعقيد التقريب m = 54. هذا يعني أنه بالنسبة لكل x تمامًا من الفاصل الزمني (0 ؛ 1) يمكننا وضع نفس الدقة في الخوارزمية ESP = 2 ^-54 ، وسيتم تقريب جميع النتائج بشكل صحيح إلى 23 بت بعد العلامة العشرية الثنائية.



في الواقع ، بعض الخوارزميات قادرة على تقديم نتيجة دقيقة وبناءً على 53 وحتى 52 بتًا ، تُظهر القوة الغاشمة ذلك ، ولكن من الناحية النظرية ، هناك حاجة إلى 54. وحفظ بضع بتات ، كما فعلت في برنامج القوة الغاشمة أعلاه. أخذت كثير الحدود بدرجة أقل مما ينبغي ، لكنها ما زالت تعمل ، لمجرد أنني كنت محظوظًا.



لذلك ، بغض النظر عن وضع التقريب ، لدينا حالتان محتملتان: إما أن تنشأ "قاطرة بخارية" من الأصفار في منطقة التقريب ، أو "قاطرة بخارية" من تلك. تتمثل مهمة الخوارزمية الصحيحة لحساب الدالة المتعالية f (x) في تحسين قيمة هذه الوظيفة حتى تتجاوز الدقة قيمة آخر بت من هذه "القاطرة" ، وحتى يتضح ذلك نتيجة للتقلبات اللاحقة في الخوارزمية العددية لحساب f (x) لن تتحول الأصفار إلى آحاد ، أو العكس. بمجرد أن يستقر كل شيء ، ووصلت الخوارزمية إلى هذه الدقة التي تتجاوز حدود "القاطرة البخارية" ، عندها يمكننا التقريب كما لو كان لدينا عدد لا نهائي من البتات. وهذا التقريب سيكون بالبت الأخير الصحيح. لكن كيف يمكن تحقيق ذلك؟

"عكازات"

كما ذكرنا سابقًا ، تكمن المشكلة الرئيسية في جعل الخوارزمية تتغلب على قاطرة الأصفار أو تلك التي تأتي مباشرة بعد بتة التقريب. عندما يتم التغلب على القاطرة ونراها ككل ، فإن هذا يعادل حقيقة أن هذه الأصفار أو الآحاد قد تم حسابها بالفعل بالضبط ، ونحن نعلم بالفعل بالضبط في أي اتجاه سيحدث التقريب الآن. لكن إذا كنا لا نعرف طول القاطرة ، فكيف يمكننا تصميم خوارزمية؟

أول "عكاز"

قد يبدو للقارئ أن الإجابة واضحة: خذ الحساب بدقة لا نهائية وقم بوضع عدد مفرط من البتات عن عمد ، وإذا لم يكن ذلك كافيًا ، فضع آخر وأعد الحساب. بشكل عام ، هذا صحيح. يتم ذلك عندما لا تلعب سرعة الكمبيوتر وموارده دورًا خاصًا. هذا النهج له اسم: استراتيجية زيف متعددة المستويات [1 ، القسم 12.3]. جوهرها بسيط للغاية. يجب أن تدعم الخوارزمية العمليات الحسابية على عدة مستويات: حساب أولي سريع (في معظم الحالات يتضح أنه نهائي) ، حساب أبطأ ولكن أكثر دقة (يحفظ في معظم الحالات الحرجة) ، حتى أبطأ ، ولكن حتى حساب أكثر دقة (عندما يكون "سيئًا تمامًا" "اضطررت إلى) وما إلى ذلك.



في الغالبية العظمى من الحالات ، يكفي أخذ الدقة أعلى بقليل من 0.5ulp ، ولكن إذا ظهرت "قاطرة" ، فإننا نزيدها. طالما بقيت "القاطرة البخارية" ، نزيد من الدقة حتى يتضح تمامًا أن التقلبات الإضافية في الطريقة العددية لن تؤثر على "القاطرة البخارية". لذلك ، على سبيل المثال ، في حالتنا ، إذا وصلنا إلى ESP = 2 ^-54 ، فستظهر وحدة في الموضع 54 ، والتي ، كما كانت ، "تحمي" القاطرة من الأصفار وتضمن عدم طرح أي قيمة أكبر من أو تساوي 2 ^-53 . ولن تتحول الأصفار إلى الآحاد ، مما يؤدي إلى سحب بت التقريب إلى الصفر معها.



لقد كان عرضًا علميًا شائعًا ، وكل ذلك مع اختبار التقريب لـ Ziv ، حيث يتم عرض مدى السرعة ، في خطوة واحدة ، للتحقق مما إذا كنا قد حققنا الدقة المطلوبة ، ويمكن قراءتها في [1 ، الفصل 12] ، أو في [3 ، القسم 10.5].



مشكلة هذا النهج واضحة. من الضروري تصميم خوارزمية لحساب كل دالة متعالية f (x) بحيث يكون من الممكن زيادة دقة الحسابات أثناء القطعة. بالنسبة لتنفيذ البرنامج ، لا يزال هذا غير مخيف جدًا ، على سبيل المثال ، تسمح طريقة نيوتن ، تقريبًا ، بمضاعفة عدد البتات الدقيقة بعد العلامة العشرية في كل تكرار. يمكنك المضاعفة حتى تصبح "كافية" ، على الرغم من أن هذه عملية تستغرق وقتًا طويلاً ، يجب أن أعترف أن طريقة نيوتن ليست مبررة دائمًا ، لأنها تتطلب حساب الدالة العكسية f ^-1(x) ، والتي في بعض الحالات قد لا تكون أبسط من حساب f (x) نفسها. بالنسبة لتطبيق الأجهزة ، فإن "إستراتيجية Ziva" غير مناسبة تمامًا. يجب أن تقوم الخوارزمية ، المتصلة بالمعالج ، بتنفيذ سلسلة من الإجراءات مع عدد البتات المحدد مسبقًا ، وهذا يمثل مشكلة كبيرة في التنفيذ إذا لم نكن نعرف هذا الرقم مقدمًا. تقييم؟ كم الثمن؟



النهج الاحتمالي لحل المشكلة [1 ، القسم 12.6] يسمح لنا بتقدير قيمة m (تذكر أن هذا هو عدد البتات ، وهو ما يكفي للتقريب الصحيح). اتضح أن طول "القاطرة" بالمعنى الاحتمالي أكبر قليلاً من طول الجزء العشري للعدد. وبالتالي ، في معظم الحالات ، سيكون كافياً أن تأخذ أكثر من ضعف قيمة الجزء العشري بقليل ، وفي حالات نادرة جدًا فقط سيكون من الضروري أخذ المزيد. أقتبس من مؤلفي هذا العمل: "نستنتج أنه من الناحية العملية ، يجب أن يكون m أكبر قليلاً من 2p" (لديهم p - طول الجزء العشري مع الجزء الصحيح ، أي ، p = 24 لـ float). علاوة على ذلك ، يظهرون في النص أن احتمال الخطأ في مثل هذه الاستراتيجية قريب من الصفر ، لكنه لا يزال إيجابيًا ، وهذا ما تؤكده التجارب.



ومع ذلك ، لا تزال هناك حالات يجب فيها أخذ قيمة m بشكل أكبر ، وأسوأ الحالات غير معروفة مسبقًا. توجد تقديرات نظرية لأسوأ الحالات [1 ، القسم 12.7.2] ، لكنها تنتج ملايين البتات التي لا يمكن تصورها ، وهذا أمر غير جيد. فيما يلي جدول من العمل المذكور (هذا خاص بالدالة exp (x) على الفاصل الزمني من -ln (2) إلى ln (2)):

الثاني "عكاز"

في الممارسة العملية ، لن تكون m كبيرة بشكل رهيب. ولتحديد الحالة الأسوأ ، يتم استخدام "عكاز" ثانٍ يسمى "الحساب المسبق الشامل". بالنسبة لنوع البيانات float (32 بت) ، إذا كانت الوظيفة f لها وسيطة واحدة (x) ، فيمكننا بسهولة "تشغيل" جميع قيم x الممكنة. ستنشأ المشكلة فقط مع الوظائف التي لها أكثر من حجة (من بينها pow (x ، y)) ، والتي لا يمكننا التفكير في أي شيء من هذا القبيل. بعد التحقق من جميع قيم x الممكنة ، نحسب ثابتنا m لكل دالة f (x) ولكل وضع تقريب. ثم تم تصميم خوارزميات الحساب التي يجب تنفيذها في الأجهزة لتوفير دقة تبلغ 2 ^م . بعد ذلك ، فإن تقريب f (x) مضمون ليكون صحيحًا في جميع الحالات.



بالنسبة للنوع المزدوج (64 بت) ، يكاد يكون التعداد البسيط مستحيلاً. ومع ذلك ، فهم يقومون بالفرز! ولكن كيف؟ الجواب معطى في [4]. سأخبرك عن ذلك باختصار شديد.



ينقسم مجال الوظيفة f (x) إلى أجزاء صغيرة جدًا بحيث يمكن استبدال f (x) بوظيفة خطية من النموذج b-ax داخل كل مقطع (المعاملان a و b يختلفان بالطبع بالنسبة للقطاعات المختلفة). يتم حساب حجم هذه المقاطع بشكل تحليلي بحيث لا يمكن بالفعل تمييز هذه الوظيفة الخطية عن الأصل في كل مقطع.



بعد ذلك ، بعد بعض عمليات التحجيم والتغيير ، نأتي إلى المشكلة التالية: هل يمكن لفأس خط مستقيم أن يقترب بدرجة كافية من نقطة عدد صحيح؟



اتضح أنه من السهل نسبيًا الإجابة بنعم أو لا. أي "نعم" - إذا كانت النقاط التي يحتمل أن تكون خطرة قريبة من خط مستقيم ، و "لا" - إذا لم تكن مثل هذه النقطة ، من حيث المبدأ ، يمكن أن تقترب من الخط. يكمن جمال هذه الطريقة في أن الإجابة "لا" من الناحية العملية يتم الحصول عليها في الغالبية العظمى من الحالات ، والإجابة بـ "نعم" ، التي نادرًا ما يتم الحصول عليها ، تجبرك على المرور عبر المقطع بقوة غاشمة لتحديد النقاط المحددة التي كانت حاسمة.



ومع ذلك ، فإن التكرار على وسيطات f (x) يتم تقليله عدة مرات ويجعل من الممكن اكتشاف نقاط الانكسار للأرقام مثل double (binary64) و long double (80 بت!). يتم ذلك على أجهزة الكمبيوتر العملاقة وبالطبع بطاقات الفيديو ... في أوقات فراغهم من التعدين. ومع ذلك ، لا أحد يعرف حتى الآن ما يجب فعله بنوع البيانات binary128. اسمحوا لي أن أذكركم أن الجزء الكسري من الجزء العشري لهذه الأرقام هو 112 بت . لذلك ، في الأدبيات الأجنبية حول هذا الموضوع حتى الآن ، لا يمكن للمرء أن يجد سوى التفكير شبه الفلسفي الذي يبدأ بـ "نأمل ..." ("نأمل ...").



تفاصيل الطريقة ، التي تسمح لك بتحديد مرور خط بالقرب من نقاط عدد صحيح ، غير مناسبة هنا. بالنسبة لأولئك الذين يرغبون في تعلم العملية بعناية أكبر ، أوصي بالنظر نحو مشكلة إيجاد المسافة بين خط مستقيم و Z ² ، على سبيل المثال ، في المقالة [5]. يصف خوارزمية محسّنة ، والتي تشبه أثناء البناء خوارزمية إقليدس الشهيرة لإيجاد القاسم المشترك الأكبر. سأقدم نفس الصورة من [4] و [5] ، والتي توضح التحول الإضافي للمشكلة:







هناك جداول ممتدة تحتوي على أسوأ حالات التقريب على فترات مختلفة لكل وظيفة متعالية. تم العثور عليها في [1 القسم 12.8.4] وفي [3 ، القسم 10.5.3.2] ، وكذلك في مقالات منفصلة ، على سبيل المثال ، في [6].



سأقدم بعض الأمثلة عن طريق أخذ صفوف عشوائية من هذه الجداول. أؤكد أن هذه ليست أسوأ الحالات لكل x ، ولكن فقط لبعض الفواصل الزمنية الصغيرة ، انظر المصدر إذا كنت مهتمًا.







كيف تقرأ الجدول؟ تم تحديد القيمة x بالتدوين المزدوج للفاصلة العائمة السداسية العشرية. أولاً ، كما هو متوقع ، هناك واحد بادئ ، ثم 52 بتًا من الجزء الكسري من الجزء العشري والحرف P. هذا الحرف يعني "اضرب في اثنين في أس" متبوعًا بدرجة. على سبيل المثال ، تعني P-23 أن الجزء العشري المحدد يحتاج إلى الضرب في 2 ^-23 .



علاوة على ذلك ، تخيل أن الدالة f (x) تُحسب بدقة غير محدودة وأن أول 53 بتًا مقطوعة عنها (بدون التقريب!). هذه 53 بت (واحد منهم حتى الفاصلة) المشار إليها في العمود f (x). يتم الإشارة إلى البتات اللاحقة في العمود الأخير. تعني علامة "الدرجة" لتسلسل البتات في العمود الأخير عدد مرات تكرار البت ، أي ، على سبيل المثال ، 10 ⁵³1011 يعني أن هناك أولاً قليلاً يساوي 1 ، ثم 53 صفراً ثم 1011. ثم ثلاث نقاط ، مما يعني أننا ، بشكل عام ، لا نحتاج إلى باقي البتات على الإطلاق.



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

لماذا هذا مطلوب؟

سؤال رائع! بعد كل شيء ، لقد تحدثت أعلاه مرارًا وتكرارًا أن ما يقرب من 100 ٪ من المبرمجين لا يحتاجون إلى معرفة دالة أولية بدقة إلى الجزء الأخير الذي تم تقريبه بشكل صحيح (غالبًا لا يحتاجون حتى إلى نصف البتات) ، فلماذا يقود العلماء أجهزة الكمبيوتر العملاقة ويجمعون الجداول لحل مشكلة "عديمة الفائدة"؟



أولاً ، التحدي أساسي. من المثير للاهتمام عدم التقريب الدقيق من أجل التقريب الدقيق ، ولكن من حيث المبدأ لفهم كيف يمكن حل هذه المشكلة المثيرة للاهتمام ، ما هي أسرار الرياضيات الحسابية التي سيكشفها لنا حلها؟ كيف يمكن استخدام هذه الأسرار في مهام أخرى؟ العلوم الأساسية - على هذا النحو ، يمكنك القيام بنوع من "الهراء" لعقود ، ثم بعد مائة عام ، بفضل هذا "الهراء" ، يحدث اختراق علمي في بعض المجالات الأخرى.



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

قائمة المصادر

[1] جان ميشيل مولر ، "الوظائف الأولية: الخوارزميات والتنفيذ" ، 2016



[2] ويليام كاهان ، " لوغاريتم ذكي جدًا بالنصف " ، 2004



[3] جان ميشيل مولر ، "دليل حساب الفاصلة العائمة" ، 2018



[4] فنسنت لوفيفر ، جان ميشيل مولر ، "نحو متسامي دائري بشكل صحيح" ، معاملات IEEE على أجهزة الكمبيوتر ، المجلد. 47 ، لا. 11 ، نوفمبر 1998. ص. 1235-1243



[5] فنسنت لوفيفر. "نتائج جديدة على المسافة بين جزء و Z ² ". التطبيق على التقريب الدقيق. ندوة IEEE السابعة عشر حول حساب الكمبيوتر - Arith'17 ، يونيو 2005 ، كيب كود ، ماساتشوستس ،

الولايات المتحدة. ص 68-75



[6] فنسنت لوفيفر ، جان ميشيل مولر ، "أسوأ الحالات للتقريب الصحيح للوظائف الأولية في الدقة المزدوجة" ، Rapport de recherche (INSTITUT NA TIONAL DE RECHERCHE EN INFORMA TIQUE ET EN AUTOMA TIQUE) n˚4044 - نوفمبر 2000 - 19 صفحة.