خلاصه “آنچه هر دانشمند کامپیوتر باید در مورد محاسبات ممیز شناور بداند”

سلام دوباره! آیا تا به حال از یک عدد ممیز شناور در کد خود استفاده کرده اید؟ آنها به شکل ظاهر می شوند float یا double معمولاً، اما اساساً یک نوع داده برای نمایش اعداد واقعی است (مانند 0.1 یا 3.14159653589 یا 123456789 * 10^(-23)). در حالی که می تواند اعداد اعشاری را نشان دهد، می تواند اعداد کامل را نیز انجام دهد 1 یا 12345678.

صرف نظر از اینکه از کدام یک استفاده کرده اید، این احتمال وجود دارد که کد شما با مشکل مواجه شود. وقتی از یک عدد استفاده می کنید (مانند 1.5)، ممکن است رایانه شما در واقع از آن شماره استفاده نکند، اما در عوض چیزی بسیار نزدیک است.

حالا عدد اشتباه خود را چند بار ضرب کنید، آن را با چند عدد اشتباه دیگر اضافه کنید، و به زودی ریاضیتان آشفته است! کامپیوتر شما در واقع به شما گوش نمی دهد.

چگونه خطاها را با عملیات ممیز شناور کاهش دهیم؟

امروز خلاصه “آنچه که هر دانشمند کامپیوتر باید در مورد محاسبات ممیز شناور بداند” توسط دیوید گلدبرگ در سال 1991 را خلاصه خواهم کرد. اگر جرات دارید آن را بخوانید… ههه

خوب، آن وبلاگ بسیار طولانی بود… بنابراین من فقط برخی از نکات اساسی آنچه را که خواندم، پوشش می دهم. اگر می خواهید سعی کنم بخشی از وبلاگ را که پوشش ندادم را توضیح دهم (سعی می کنم) نظر بدهید.

برای باهوش تر شدن آماده شوید 🙂

به نمایندگی از نقاط شناور

نقاط شناور با یک پایه عددی نشان داده می شوند

$\بتا$

(مانند اعشاری یا باینری یا هگزادسیمال)، یک محدوده توان

$e_{دقیقه}$

و

$e_{حداکثر}$

، و یک دقت p (تعداد ارقام). آنها در نماد علمی با یک رقم غیر صفر قبل از نقطه اعشار نشان داده می شوند.

به عنوان مثال، چیزی شبیه به این خواهد بود.

ارقام معنادار

$d_i$

همه در محدوده هستند

$0 \leq d_i \lt \بتا$

جایی که وجود دارد p ارقام (

$0 \leq i \lt p$

).

بنابراین اگر

$\بتا = 2$

و p = 3 و من می خواستم نمایندگی کنم 0.77 چیزی شبیه این خواهد بود

این برابر خواهد بود 0.110 که هست

$1/2 + 1/4$

. این نزدیک ترین چیزی است که می توانیم به آن برسیم 0.77 با دقت 3 رقمی p به صورت دودویی همانطور که می بینید، نمایش های ممیز شناور دروغ می گویند 0.75 نیست 0.77، لب به لب است به اندازه کافی نزدیک.

اگر

$\بتا = 10$

و p = 3 سپس 2734 به عنوان نشان داده می شود

اگر مدام بگوییم نقاط شناور هستند “به اندازه کافی نزدیکبرای اعداد و ارقام ما و شروع به انجام عملیات روی آنها می کنیم، در نهایت نمایش های ما با تعداد واقعی فاصله زیادی خواهد داشت.

خوب، بیایید اندازه گیری کنیم که چقدر با عدد واقعی فاصله داریم. آکا، خطا چیست؟

درک خطا

دو نوع خطای ممیز شناور یا وجود دارد خطاهای گرد کردن که معمولا اندازه گیری می شوند. ulps (واحدها در آخرین مکان) و خطای نسبی.

ulps

واحدهای در آخرین مکان کل خطای رقم آخر در مقایسه با عدد واقعی است. به طور دقیق، می توان آن را با این فرمول پیچیده محاسبه کرد که کجا z عدد واقعی است که ما با آن مقایسه می کنیم.

اگر این گیج کننده به نظر می رسد، بیایید فقط یک مثال بزنیم و خیلی راحت تر خواهد بود. فرض کنید یک عدد داریم 314.09 و ما z = 314.1592653589.

از این رو می دانیم،

$\بتا = 10$

، p = 5، و e = 2.

این تقریبا دارد ulps = 6.965.

خطای نسبی

این خطا خطای مطلق را می گیرد و آن را با بزرگی عدد واقعی متناسب می کند.

فوق العاده ساده ابتدا خطای مطلق (تفاوت بین واقعی و نمایشی) را بگیرید.

حالا آن را بر عدد واقعی تقسیم کنید تا به نسبت محاسبه شود.

ایده این است که اگر من یک عدد بسیار بزرگ مانند یک میلیون داشته باشم. اگر بخواهم خانه ای میلیون دلاری بخرم (اگر زمانی به اندازه کافی ثروتمند باشم)، واقعاً به تفاوت 10 دلاری اهمیت نمی دهم.

تبدیل 0.5 ulps به خطای نسبی

بیایید بگوییم که من یک عدد به عنوان نشان داده شده است

$d.dd…dd * \beta^e$

. اگر این عدد 0.5 ulps داشت، خطا را می توان محدود کرد

$0.00…00\beta'$

کجا

$\beta' = \beta/2$

.

متقاعد کردن شما در مورد خطای مطلق 0.5 ulps

بذار قانعت کنم فرض کنید در پایه 10 هستیم (

$\بتا=10$

) و داشتیم p=3 با شماره 9.97. اگر عدد واقعی به درستی از طریق گرد کردن نشان داده می شد، عدد واقعی بین آن قرار می گرفت >= 9.965 و < 9.975.

محدودیت‌های عدد واقعی با خطا محدود شده‌اند 0.005. این خطا هم 0.5 ulps است. همچنین همان است

$0.00…00\beta'$

چون

$\beta' = \beta/2 = 5$

.

این ممکن است در پایه 10 واضح به نظر برسد، اما بیایید چیزی را در پایه 2 امتحان کنیم (

$\بتا=2$

). فرض کنیم داشتیم 1.11 (1.75 به صورت اعشاری) وقتی

$\بتا=2$

و p = 3. با این حال، عدد واقعی قبل از گرد کردن ممکن است بین باشد < 1.111 و >= 1.110. و البته این محدوده منجر به 0.1 ulps می شود ex. (1.111 - 1.11) در دودویی که 0.5 اولپس در اعشار است که همان است

$0.00…00\beta'$

چون

$\beta' = \beta/2 = 1$

.

بنابراین، اگر یک عدد به درستی به نمایش مناسب خود گرد شود، خطای آن کمتر از 0.5 ulps خواهد بود.

به عبارت دیگر 0.5 ulps همیشه برابر است

$((\beta/2)\beta^{-p}) * \beta^e$

. این خطای مطلق 0.5 ulps خواهد بود.

بر روی خطای نسبی

حالا 0.5 ulps در خطای نسبی چیست؟ به یاد داشته باشید که خطای نسبی، خطای مطلق تقسیم بر عدد واقعی بود.

ما فقط گفتیم که خطای مطلق زمانی که 0.5 ulps داریم این است

$((\beta/2)\beta^{-p}) * \beta^e$

. اما عدد واقعی می تواند هر چیزی باشد.

به طور خاص، می تواند در محدوده باشد

$1 * \beta^e$

و

$\beta * \beta^e$

. بنابراین، اگر 0.5 اولپس بود 0.001 به صورت دودویی (

$1*2^{-3} *2^0$

، سپس p=3 و e=0. در آن صورت عدد واقعی باید بین بوده باشد

$1*2^0$

و

$2*2^0$

که می شود 1 و 2 به صورت اعشاری یا 1 و 10 به صورت دودویی

از مثال قبلی ما، می توانیم ببینیم که درست است. 1.11 (1.75 اعشاری) در واقع بین بود 1 و 10 به صورت دودویی

جالب است، بنابراین ما برخی از محدودیت‌ها را برای عدد واقعی تعیین می‌کنیم، یعنی:

$1 * \beta^e$

و

$\بتا * \beta^e$

.

این بدان معناست که ما می توانیم برای خطای نسبی برای 0.5 ulps تعیین کنیم. پس بیایید خطای مطلق را بر مرزهای عدد واقعی تقسیم کنیم.

کران بالای خطای نسبی:

کران پایینی خطای نسبی:

بنابراین،

اپسیلون ماشینی

خطای نسبی کران بالا برای 0.5 اولپس نامیده می شود اپسیلون ماشینی. این بزرگترین خطای نسبی ممکن است که یک پایه داده شود.

دقت بزرگتر pهمانطور که انتظار می رود، به معنای خطای نسبی کوچکتر/اپسیلون ماشین است. همچنین متوجه می‌شویم که 0.5 اولپس توسط اپسیلون ماشین محدود شده است

$(\frac{1}{2})\beta^{-p}$

. این محدوده ها یک عامل دارند

$\بتا$

که ما به آن می گوییم تکان دادن.

آره… تکون بچه تکون میخوره عزیزم…

BTW، ماشین اپسیلون نام جالبی است. من قضاوت نمی‌کنم که اسم سگ یا بچه‌تان را اپسیلون ماشین بگذارید.

خطاهای نسبی با اپسیلون ماشین

به یاد داشته باشید که اپسیلون ماشین کران بالایی برای خطاهای گرد کردن یا 0.5 اولپس بود. بنابراین اگر واقعاً خطای نسبی بسیار کمتری داشته باشیم، می‌توانیم خطای نسبی را به عنوان نسبت اپسیلون ماشین به صورت زیر نشان دهیم:

بیایید یک مثال بزنیم. اگه شماره رو داشتم 3.14159 برای نمایندگی با

$\بتا=10$

و p = 3، من باید دور بزنم 3.14. این یک خطای مطلق دارد .00159 یا 0.159 اولپس. برای خطای نسبی، انجام می دهم

$0.00159/3.14159$

که من را به یک خطای نسبی سوق می دهد 0.0005.

حال برای یافتن نسبت، باید اپسیلون ماشین را پیدا کنیم:

بنابراین … نسبت این است:

پس می گوییم خطای نسبی است

$0.1\epsilon$

.

را تلو تلو خوردن

برای تکان خوردن چیزها آماده شوید. ابتدا اجازه دهید به شما نشان دهم که چگونه ulps و خطای نسبی به یکدیگر واکنش نشان می دهند.

با استفاده از 1.0 نمایندگی کند 1.04 در اعشار دارای خطای 0.4 اولپس و خطای نسبی 0.038 است. اپسیلون ماشین است 0.05 که باعث خطای نسبی می شود

$0.76\epsilon$

.

عالیه امیدواریم که این تا اینجا منطقی باشد.

حالا بیایید عددمان را در فرض کنیم ضرب کنیم 8. عدد واقعی خواهد بود 8.32 در حالی که عدد محاسبه شده خواهد بود 8.0. این 3.2 ulps دارد که 8 برابر بزرگتر از قبل است! با این حال، خطای نسبی ما همچنان وجود دارد

$0.32/8.32 = 0.038$

که همان است

$0.76\epsilon$

.

وای ulps ما زیاد شد اما خطای نسبی ما یکی بود؟

بله معلوم می‌شود که هر زمان که یک خطای نسبی ثابت داشته باشید، ulps شما می‌تواند تکان بخورد

$\بتا$

.

از طرف دیگر، هر زمان که ما یک اولپس ثابت داشته باشیم (مانند آنچه قبلا با 0.5 اولپس نشان دادیم)، خطای نسبی دارای کرانه هایی بود که نشان می داد می تواند توسط آن نیز تکان بخورد.

$\بتا$

.

بنابراین، کوچکتر

$\بتا$

، تاب خوردن کوچکتر یا محدوده خطا کوچکتر است! استفاده از باینری می تواند خطای ما را به میزان قابل توجهی کاهش دهد.

ارقام آلوده

ما اکنون می دانیم که نسبت ulps و خطای نسبی k با یک ضریب از یکدیگر متفاوت هستند

$\بتا$

، لرزش در نتیجه می توانیم تعداد ارقام آلوده (تعداد ارقام نادرست از نمایش صحیح عدد) را تخمین بزنیم.

n تعداد ulps است. n همچنین می تواند به معنای k، نسبت بین خطای نسبی و

$\epsilon$

. این می تواند به دلیل ضریب لرزش به این معنی باشد.

بنابراین اگر عددی به صورت اعشاری داشتم، 3.10 با p=3 و سعی در نمایندگی داشت 3.1415، خطای 4.15 اولپس خواهد داشت. ارقام آلوده تقریباً خواهند بود

$\log_{10}{4.15}$

که تقریبا 0.61804809 ارقام

LOL ما نمی توانیم ارقام جزئی داشته باشیم! زمانی که خوک ها پرواز کنند، خواهیم دید.

با نگاه بصری، می‌توانیم ببینیم که در 1 رقم، آخرین رقم، اشتباه است، که بسیار نزدیک به چیزی است که از محاسبه‌مان به دست آورده‌ایم.

ارقام نگهبانی

بیایید 2 مقدار را کم کنیم وقتی

$\بتا = 10$

و p=3.

می شود 0.99 و نه 0.993 زیرا مجبور بودیم برخی از داده ها را با آن از دست بدهیم p=3 به طوری که می توان آنها را همزمان از یکدیگر کم کرد

$\beta^{e}$

.

همانطور که می دانید، پاسخ واقعی 0.017، اما پاسخ به این نتیجه رسید 0.02. بنابراین

$2.00 * 10^{-2}$

و

$1.70 * 10^{-2}$

خطای 30 ulps دارید!

خطای نسبی حاصل از این نوع تفریق محدود شده است

$\بتا – 1$

. اجازه دهید به شما نشان دهم چرا.

اگر

$x=1.00…00، y=\rho.\rho\rho…\rho\rho * \beta^{-1}$

کجا

$\rho=\بتا-1$

. (مثلا

$\بتا=10، \rho=9$

). (x و y دارند p ارقام.)

اگر آنها را کم کنم، باید پاسخ واقعی آن را دریافت کنم

$1*\beta^{-p}$

، اما به این دلیل که ما جابه جا می شویم y به سمت راست و از دست دادن یک رقم، در نهایت به دست می آوریم

$1*\beta^{-p+1}$

.

اگر ما

$\بتا=2$

که خطای نسبی ما را 1. از نظر

$\epsilon$

، به این معنی است

$1 = k*\epsilon$

و غیره

$k = 1/\epsilon$

. ارقام آلوده خواهد بود

$log_2{1/\epsilon}=log_2{2^{p}}=p$

. اگر p ارقام آلوده هستند، همه آنها آلوده هستند.

آیا راهی وجود داشت که بتوانیم از برخی از این خطا جلوگیری کنیم؟ خوب، خوب، وجود دارد… وگرنه در مورد این بخش نمی نوشتم…

فقط یک رقم اضافی موقت اضافه کنید. و بیایید آن را یک … صبر کنید … a رقم نگهبانی. غافلگیری غافلگیر کننده

الان هیچ خطایی نداریم. این الان کمی بهتر از قبل شده است.

نشان می دهد که رقم گارد خطای نسبی را محدود می کند

$2\epsilon$

. من تنبل هستم، اما اگر کسی در نظرات بپرسد، دلیل آن را پیدا می کنم و سعی می کنم آن را توضیح دهم (اما در وبلاگ پیوند داده شده است).

لغو خوش خیم و فاجعه بار

وقتی می‌خواهیم دو عدد واقعاً نزدیک را کم کنیم، بسیاری از ارقام باطل می‌شوند و تبدیل می‌شوند 0. ما این را لغو می نامیم. گاهی اوقات لغو می تواند فاجعه بار یا خوش خیم باشد.

گاهی اوقات، هنگامی که ما تفریق را انجام می دهیم، اغلب پس از گرد کردن مقدار یا پس از عملیات قبلی، در ارقام انتهایی سمت راست (کمترین ارقام مهم) خطاهایی وجود دارد. ارقام دقیق تر در جلو هستند (مهمترین ارقام). در حالی که ارقام مهم‌تر در جلو حذف می‌شوند، ارقام با اهمیت پایین‌تر باید کم‌تر شده و مقدار نادرست‌تری تولید کنند. (مثل زمانی که تعیین کننده را محاسبه می کنید

$b^2 – 4ac$

).

لغو فاجعه بار فقط خطاهای گرد کردن عملیات قبلی را آشکار می کند.

لغو خوش خیم زمانی اتفاق می‌افتد که اعدادی را کم کنید که خطای گرد کردن ندارند.

استاندارد IEEE

بنابراین استاندارد IEEE مجموعه ای از قوانین است که بسیاری از سیستم ها برای اطمینان از سازگاری از آن پیروی می کنند. دو استاندارد IEEE وجود دارد که از آنها پیروی می شود: IEEE 754 و IEEE 854. هر دو از نقاط شناور کوچکتر و بزرگتر به نام دقت واحد و دقت دوگانه پشتیبانی می کنند.

IEEE 754

استاندارد اجازه می دهد

$\بتا=2$

. دارای دقت تک بیتی (p=24) و دقت دو بیتی (p=53). همچنین نحوه چیدمان بیت ها را مورد بحث قرار می دهد.

در واقع، در اینجا یک جدول جالب وجود دارد که نشان می دهد چگونه IEEE 754 تمام پارامترهای ممیز شناور خود را تنظیم می کند.

نماها با یک تقسیم علامت / قدر نشان داده می شوند. یک بیت برای علامت توان استفاده می شود. بیت های باقی مانده برای توان برای نشان دادن مقدار آن استفاده می شود. مکمل Two یک رویکرد دیگر است اما توسط هیچ یک از استانداردهای IEEE استفاده نمی شود.

در واقع، در اینجا دقیقاً نحوه چیدمان بیت ها برای نشان دادن انواع مختلف مقادیر است. برای نشان دادن 0، باید از آن استفاده کنید

$e_{\text{min}}-1$

. بی نهایت است

$e_{\text{max}}+1$

بدون بخش کسری 0ed خارج. NaN نوع دیگری است (مثل زمانی که 0 بر 0 تقسیم شود یا بی نهایت ها اضافه شوند). NaN یکسان به عنوان بی نهایت نمایش داده می شود اما با مجموعه بخش کسری.

بخش کسری ارقام بعد از رقم اول است (که معنی‌دار نیز نامیده می‌شود.

IEEE 854

از طرفی این استاندارد اجازه می دهد

$\بتا=2$

یا

$\بتا=10$

. با این حال، هیچ قانونی در مورد نحوه چیدمان بیت ها برای دقت دوگانه و تکی وجود ندارد.

پایه 10 را اجازه می دهد زیرا روش استاندارد شمارش انسان ها نیز هست. پایه 2 نیز به دلیل لرزش کم گنجانده شده است.

نتیجه گیری

خوب، من به نوعی عجله بخش آخر را انجام دادم. اما به طور کلی، می‌خواستم بگویم که امتیاز شناور می‌تواند عدم دقت زیادی داشته باشد. اگر می توانید از آنها اجتناب کنید، به جای آن از اعداد صحیح استفاده کنید.

در صورتی که از آنها استفاده می کنید، سعی کنید لرزش های خود را محدود کنید و از لغو فاجعه آمیز خودداری کنید (راه هایی وجود دارد که می توانید گاهی اوقات با تنظیم مجدد فرمول ها این کار را انجام دهید).

سعی کنید خود وبلاگ اصلی را بخوانید. این وبلاگی که اکنون می خوانید خلاصه ای از کسری از وبلاگ اصلی دیوید گلدبرگ است.

اما مثل همیشه سوالات و نظرات خود را مطرح کنید. و فعلا بیرونم…

صلح
-absterdabster