Сандық арифметикада қателер және тұспалдау

Кіріспе

Компьютерлік арифметикалық қате

Компьютерлік бағдарламалауда бүтін санның шектен шығуы (overflow) арифметикалық операция белгілі бір санмен бейнеленетін диапазоннан тыс сандық мәнді жасауға тырысқанда пайда болады – ең жоғары немесе ең төменгі бейнеленетін мәннен жоғары немесе төмен. Шектен шығудың ең көп таралған салдары – нәтижедегі ең кіші маңызды разрядтар сақталады; нәтиже ең жоғары мәнге дейін «оралады» (яғни, радикстің модулі бойынша, әдетте заманауи компьютерлерде екі, бірақ кейде он немесе басқа радикс). Шектен шығу жағдайы күтпеген мінез-құлыққа әкелуі мүмкін. Атап айтқанда, егер бұл мүмкіндік ескерілмесе, шектен шығу бағдарламаның сенімділігі мен қауіпсіздігіне қауіп төндіруі мүмкін. Кейбір қолданбалар үшін, мысалы таймерлер мен сағаттар үшін, шектен шығу кезінде оралу қажет болуы мүмкін. C11 стандартында белгісіз бүтін сандар үшін модульдік оралу анықталған мінез-құлық болып табылады және «шектен шығу» термині қолданылмайды: «белгісіз операндармен есептеу ешқашан шектен шыға алмайды». Графикалық процессорлар (GPU) және цифрлық сигнал процессорлары (DSP) сияқты қанығу арифметикасын қолдайтын процессорларда, шектен шыққан нәтижелер «шектеледі», яғни бейнеленетін диапазонның ең төменгі немесе ең жоғары мәніне орнатылады, оралудың орнына.

Тулар

Көптеген компьютерлерде ағып кету жағдайларын тексеру үшін екі арнайы процессор туы бар. Көтерілу туы қосылу немесе азайту операциясының нәтижесі, егер операндтар мен нәтижелер қолтаңбасыз сандар ретінде қарастырылса, белгілі бір бит санына сыймаған жағдайда қойылады. Бұл ең маңызды биттен ағып кетуді немесе қарызды көрсетеді. Көтерілу туымен қосу немесе қарызды азайту операциясы осы тудың мазмұнын көп сөздік мәннің жоғарғы бөлігін сақтайтын тіркегішті немесе жад орнын өзгерту үшін пайдаланады. Ағып кету туы қолтаңбалы сандардағы операцияның нәтижесі операндтардың таңбаларынан күтілетін таңбаға ие болмаған кезде қойылады, мысалы, екі оң санды қосудан теріс нәтиже шығу. Бұл ағып кетудің болғанын және екілік толықтыру түрінде көрсетілген қолтаңбалы нәтиже белгілі бір бит санына сыймайтынын көрсетеді.

Анықтамалардың өзгеруі және түсініксіздігі

Белгісіз тип үшін, операцияның идеалдық нәтижесі типтің бейнеленетін диапазонынан тыс болса және қайтарылған нәтиже орау арқылы алынса, онда бұл оқиға әдетте ағып кету деп анықталады. Керісінше, C11 стандарты бұл оқиға ағып кету емес екенін анықтайды және "белгісіз операндармен есептеу ешқашан ағып кетпейді" деп мәлімдейді, сондай-ақ қанықтыру арқылы ағып кетуді пайдалануға болады. Сандық ағындылық туралы көптеген сілтемелер кездеседі. "Бүтін санның төмен ағындылығы" термині қолданылғанда, идеалдық нәтиже шығыс түрінің ең төменгі мәнінен теріс шексіздікке жақын болып табылады делінеді. Контекстке байланысты, ағып кету анықтамасы барлық типтерді, соның ішінде төмен ағындылықты қамтуы мүмкін, немесе тек идеалдық нәтиже шығыс түрінің ең жоғары мәнінен оң шексіздікке жақын болған жағдайларды ғана қамтуы мүмкін. Операцияның идеалдық нәтижесі нақты бүтін сан болмаған жағдайда, ағып кету мағынасы шектен шыққан жағдайларда беймағына болуы мүмкін. Мысалы, идеалдық нәтиже 127,25 мәніне тең болса және шығыс түрінің ең жоғары мәні 127 болса, онда ағып кету шығыс түрінің бейнеленетін диапазонынан тыс идеалдық мән ретінде анықталса, бұл жағдай ағып кету ретінде жіктеледі. Дөңгелектеу әдісі анықталған операцияларда ағып кетуді жіктеуді дөңгелектеу қолданылғаннан кейін кейінге қалдыру қажет болуы мүмкін. C11 стандарты бойынша, C тілінде белгісіз бүтін сан ағып кетсе, оралу болады, ал белгісі бар бүтін сан ағып кетсе, мінез-құлқы анықталмайды.

Бүкіл сандар ағып кету проблемасын шешу әдістері

+ Тілдердің әртүрлі бағдарламалау тілдерінде бүтін сан ағынын басқару Тіл Белгісіз бүтін сан Белгілі бүтін сан Ada типтің модулі бойынша модульдеу, Шектеу қатесі тудырады C, C++ екінің дәрежесі бойынша модульдеу, анықталмаған мінез-құлық C# екінің дәрежесі бойынша модульдеу (тексерілмеген контекстте); Жүйе. OverflowException (тексерілген контекстте) Java екінің дәрежесі бойынша модульдеу (char - Java-дағы жалғыз қолтаңбасыз примитивті тип) JavaScript барлық сандар қос дәлдікті қозғалатын нүктелі сан, BigInt жаңадан енгізілді MATLAB кіріктірілген бүтін сандар қанығады, қалыпты сандар оралуға немесе қанығуға конфигурацияланады Python 2 ұзын типке (bigint) түрлендіріледі Seed7 OVERFLOW ERROR қатесін тудырады Scheme bigNum-ге түрлендіріледі Simulink оралуға немесе қанығуға конфигурацияланады Smalltalk LargeInteger-ге түрлендіріледі Swift ерекше ағын операторларын қолданбаса, қате тудырады.

Анықтау

C компиляторлары үшін UBSan (белгісіз мінез-құлықты санитайзер) орындалу уақытындағы ағып кетуді анықтау мүмкіндігі бар. Java 8-де, мысалы, ағып кету жағдайында қате шығаратын артық жүктелген әдістер бар. Компьютерлік төтенше жағдайларға жауап беру тобы (CERT) «Шексіз Диапазонды Дәл» (AIR) бүтін сан моделін жасады, бұл C/C++ тіліндегі бүтін санның ағып кетуі мен уысып кетуін жоюға бағытталған, көбінесе автоматтандырылған механизм.

Қауіпсіздік

Мүмкін болатын барлық есептелген және сақталатын мәндерді қамтуға жеткілікті дерек типі бар айнымалыларды бөлу арқылы, үзілістен әрқашан аулақ болуға болады. Бағдарламалау тілі немесе орта ұсынатын қолжетімді жад немесе тұрақты дерек түрлері айнымалыларды қауіпсіздік үшін үлкен көлемде бөлуге жеткіліксіз болған жағдайда да, операцияларды сақтықпен реттеу және операндарды алдын ала тексеру арқылы нәтиже сақталынатын көлемнен аспайтынын алдын ала қамтамасыз ету жиі мүмкін. Статикалық талдау құралдарын, формальды тексеруді және келісімшарт бойынша жобалау техникаларын қолдану арқылы, үзіліс кездейсоқ орын алмауына сенімді және берік түрде көз жеткізуге болады.

Қолдану

Егер ағып кету мүмкін деп күтілсе, бағдарламаға ол қашан болатынын немесе бола жазуын анықтау үшін тесттер енгізілуі мүмкін, сондай-ақ оны жеңілдету үшін басқа өңдеулер жасалуы мүмкін. Мысалы, егер пайдаланушы енгізген деректерден есептелген маңызды нәтиже ағып кетсе, бағдарлама тоқтатылып, деректер қабылданбауы мүмкін, және мүмкін пайдаланушыдан басқа деректер енгізу сұралуы мүмкін, нәтижесінде жарамсыз ағып кеткен деректермен жұмыс істеп, қателіктерге себеп болудың орнына. Процессорлар әдетте, олардың тіркелгіше өлшемдерінен үлкен сандарды қосуды қолдау үшін, әдетте, күй битін пайдалану арқылы мұны анықтаудың жолына ие. Бұл әдіс көп дәлдік арифметикасы деп аталады. Осылайша, байттан кең операндтарды байт енімен қосуға болады: біріншіден, төмен байттар қосылып, нәтиже сақталады және ағып кету тексеріледі; содан кейін жоғары байттар қосылады, қажет болса төмен байттардан алынған тасымалдау қосылады, содан кейін нәтиже сақталады. Есептеудің мүмкін ағып кетуін басқару кейде есептеу алдында тексеруді (ағып кету бола ма, жоқ па, анықтау үшін) немесе одан кейін (нәтижелі мәнге сүйене отырып, ағып кету болу ықтималдығын қарастыру үшін) таңдау мүмкіндігін ұсынады. Кейбір жүзеге асырулар бүтін сан ағып кеткенде қателік тудыруы мүмкін болғандықтан, ең сенімді бағдарламалар ағып кетуге ұшырауы мүмкін операцияны орындау алдында тексереді.

Жауапты таралу

Егер мән сақтауға тым үлкен болса, оған арнайы мән тағайындалуы мүмкін, бұл ағып кетудің болғанын көрсетеді, содан кейін барлық келесі операциялар осы белгіні қайтарады. Мұндай мәндер кейде "саны емес" дегенді білдіретін NaN деп аталады. Бұл ұзақ есептеудің соңында мәселені бір рет тексеруге мүмкіндік береді, әр қадамнан кейін тексерудің қажетін жояды. Мұндай мүмкіндіктер көбінесе FPU деп аталатын қозғалатын нүктелі аппараттық құралдарда қолдауға ие.

Бағдарламалау тілдерін қолдау

Бағдарламалау тілдері кездейсоқ ағып кетуге қарсы әртүрлі жеңілдету әдістерін іске асырады: Ada, Seed7 және функционалдық тілдердің кейбір түрлері ағып кету кезінде ерекше жағдай тудырады, ал Python (2.4 нұсқасынан бастап) санның ішкі өрнегін оның өсуіне сәйкес тегіс түрлендіреді, соңында оны ұзын сан ретінде көрсетеді, оның мүмкіндіктері тек қол жетімді жад көлемімен шектеледі. Кездейсоқ дәлдік арифметикасы және типтік қауіпсіздік қолдауы бар тілдерде (мысалы, Python, Smalltalk немесе Common Lisp) сандар ағып кету кезінде автоматты түрде үлкен өлшемге көтеріледі немесе ауқымдық шектеулер болған жағдайда ерекшеліктер (шарттар) шығарылады. Осылайша, мұндай тілдерді пайдалану осы мәселені жеңілдетуге көмектеседі. Дегенмен, кейбір тілдерде бүтін сан ағып кетуіне әлі де мүмкіндік бар. Мысалы, профильдеушінің бөтелке мойны деп табатын код жолының нақты оптимизациясы. Common Lisp жағдайында, бұл машиналық өлшемдегі сөзді (fixnum) түрге түсіру үшін нақты декларацияны пайдалану арқылы және нақты код блогы үшін типтік қауіпсіздік деңгейін нөлге дейін төмендету арқылы мүмкін. C сияқты ескі тілдерден өзгеше, Rust сияқты кейбір жаңа тілдер ағып кетуді оңай анықтауға және пайдаланушыға оны қалай шешуді таңдауға мүмкіндік беретін кіріктірілген функцияларды ұсынады. Rust-та, негізгі математикалық операторларды пайдалануда мұндай икемділік болмаса да, пайдаланушылар есептеулерді бүтін санның бастапқы түрлері ұсынатын әдістер жиынтығы арқылы жүзеге асыра алады. Бұл әдістер пайдаланушыларға тексерілген (немесе ағып кету) операцияны орындау (қайтару түрі арқылы ағып кетудің болғандығын немесе болмағандығын көрсетеді); «тексерілмеген» операция; орау операциясын орындау немесе сандық шектеулерде қанығу операциясын орындау арасында таңдау жасауға мүмкіндік береді.

Қаныққан арифметика

Компьютерлік графикада немесе сигналдарды өңдеуде 0-ден 1-ге дейін немесе -1-ден 1-ге дейін диапазондағы деректермен жұмыс істеу қалыпты жағдай. Мысалы, 0 қара түсті, 1 ақ түсті, ал арадағы мәндер сұр түстердің әртүрлі деңгейлерін көрсететін сұр түсті суретті қарастырайық. Бір қолдауға болатын операция – суретті әр пикселді тұрақты санға көбейту арқылы жарықтандыру. Қаныққан арифметика, пикселдердің кез келгенін осы тұрақты санға еш ойланбастан көбейтіуге мүмкіндік береді, себебі 1-ден жоғары мәндер (яғни, "ақтан аспан") ақ түске, ал 0-ден төмен мәндер ("қарадан қара") қара түске айналады, нәтижеде мағыналы нәтижеге қол жеткізіледі.

Мысалдар

Күтпеген арифметикалық ағындылық бағдарлама қателіктерінің жиі кездесетін себебі болып табылады. Мұндай ағынды қателерді анықтау және диагностикалау қиын болуы мүмкін, өйткені олар тек үлкен кіріс деректер жиынтықтарында ғана пайда болуы мүмкін, ал мұндай деректер валидациялау сынақтарында сирек қолданылады. Көптеген іздеу алгоритмдеріндегідей, екі санды қосып, екіге бөлу арқылы олардың арифметикалық ортасын табу, егер қосынды (әлі орташа мән болмаса да) өте үлкен болып, көрсетілмегендіктен ағып кетсе, қатеге әкеледі. 1985 және 1987 жылдар аралығында Therac 25 сәулелік терапия машиналарындағы арифметикалық ағындылық, аппараттық қауіпсіздік бақылауларының болмауы салдарынан кем дегенде алты адамның сәулеленудің қалыптан тыс дозасынан қаза табуына себеп болды. 1996 жылы Ariane 5 зымыранының алғашқы ұшуындағы апаттың басты себебі – қозғалтқышты басқару бағдарламалық жасақтамасындағы арифметикалық қателік болды. Бағдарламалық жасақтама бұрынғы ұшуларда қолданылғандықтан қатесіз деп есептелді, бірақ ол кішірек зымырандарда қолданылды, олар Ariane 5-ке қарағанда төмен үдеу тудырды. Ағындылық қатесі бар бағдарламалық жасақтаманың бөлігі ракета сәтсіздікке ұшыраған кезде Ariane 5 үшін жұмыс істеуі қажет болмады: ол жаңа зымыранға бейімделген кезде сақталған, Ariane 5-тің кішігірім алдыңғы нұсқасының ұшу режимі процесі болды. Сонымен қатар, қателіктің нақты себебі бағдарламалық жасақтама ағындылықты қалай өңдегеніне қатысты инженерлік сипаттамадағы кемшілік болды: ол бағдарламалық жасақтаманы әзірлеу кезінде сынақ жабдықтарына қосылатын, бірақ ұшу кезінде зымыранның басқару қозғалтқыштарына қосылған диагностикалық төңкеру жасады; деректерді төңкеру қозғалтқыш мүндерін бір жаққа күшпен итеріп, ракетаның аэродинамикалық бақылауын жойып, ауада тез ыдырауына себеп болды. 2015 жылдың 30 сәуірінде АҚШ Федералдық авиация басқармасы Boeing 787 операторларына электр жүйесін мерзімді түрде қайта орнатуды бұйырды, электр қуатының жоғалуына және қосымша электр қуат генераторын іске қосуға әкелетін бүтін санның ағып кетуін болдырмау үшін. Еуропалық авиациялық қауіпсіздік агенттігі 2015 жылдың 4 мамырында осыған сәйкес әрекет етті. Қате секундтың 231-ші бөлігінен кейін (шамамен 3 күн) пайда болады, бұл 32 биттік таңбаланған бүтін санды көрсетеді. Ағындылық қателері кейбір компьютерлік ойындарда да кездеседі. Super Mario Bros. for the NES ойынында өмір санының көрсеткіші таңбаланған байт (–128-ден 127-ге дейін) болып табылады, яғни ойыншы 127 өмірге ие болуы мүмкін, бірақ ойыншы 128-ші өмірге жеткенде, санаушы 0 өмірге қайта оралады (бұл орын алудан бұрын санау көрсеткішінде қате пайда болса да) және санауды тоқтатады. Ойыншы өлген жағдайда ойын бірден аяқталады. Бұл ойын деректерінің ағып кетуінен туындаған бағдарламалау қатесі, өйткені әзірлеушілер мұндай өмір санына жету мүмкін емес деп ойлаған болуы мүмкін. Donkey Kong аркадалық ойынында уақыт/бонус көрсеткішіндегі бүтін санның ағып кетуіне байланысты 22-деңгейден асып өту мүмкін емес. Ойын пайдаланушының деңгейін алып, оны 10-ға көбейтіп, 40-ты қосу арқылы уақыт/бонусты есептейді. Олар 22-деңгейге жеткенде, уақыт/бонус саны 260-қа жетеді, бұл 8 биттік 256 мән тіркегіші үшін тым үлкен, сондықтан ол 4 мәніне дейін ағып кетеді – деңгейді аяқтау үшін жеткіліксіз. Donkey Kong Jr. Math ойынында 10 000-нан артық санды есептеу кезінде тек алғашқы 4 цифр ғана көрсетіледі. Pac Man ойынындағы әйгілі "екіге бөлінген экран" деңгейінің себебі – ағындылық. Мұндай қате сонымен қатар Infdev-тен Beta 1.7.3-ке дейін болған Minecraft Java Edition-дағы Far Lands-қа да себеп болды; ол кейін Beta 1.8-де түзетілді. Осы қате Minecraft Bedrock Edition-да да болған, бірақ содан бері түзетілді. Super Nintendo Entertainment System (SNES) ойыны Lamborghini American Challenge-те ойыншы жарыс төлемдерінен кейін қалған ақшасының шегінен асып, жарыста 0 доллардан төмен ақша сомасына түсуі мүмкін, бұл бүтін санды бұзады және ойыншыға теріс мәннен кейін 65 535 000 долларға артық ақша береді. IBM–Microsoft Macro Assembler (MASM) 1.00 нұсқасы, және, мүмкін, сол Pascal компиляторымен құрастырылған барлық басқа бағдарламалар, стек орнату кодында бүтін санның ағып кетуіне және таңбалау қатесіне тап болды, бұл оларды 512 КБ-тан астам жады бар кейбір кең таралған конфигурацияларда жаңа DOS машиналарында немесе эмуляторларда жұмыс істеуге кедергі келтірді. Бағдарлама тоқтап қалады немесе қате хабарламасын көрсетеді және DOS-қа шығады. 2016 жылдың тамызында Resorts World казиносындағы казино автоматы ағындылық қатесінің нәтижесінде 42 949 672,76 долларлық ұтыс билетін басып шығарды. Казино бұл соманы төлеуден бас тартты, оны бұзушылық деп атады, қорғаныс ретінде машинаның ең жоғары төлемақысы 10 000 доллар екенін айтты, сондықтан одан асып түсетін кез келген сыйлық бағдарламалау қатесінің нәтижесі болуы керек екенін мәлімдеді. Нью-Йорк штатының ойын комиссиясы казиноның пайдасына шешім шығарды.

Unanticipated arithmetic overflow is a fairly common cause of program errors. Such overflow bugs may be hard to discover and diagnose because they may manifest themselves only for very large input data sets, which are less likely to be used in validation tests. Taking the arithmetic mean of two numbers by adding them and dividing by two, as done in many search algorithms, causes error if the sum (although not the resulting mean) is too large to be represented and hence overflows. Between 1985 and 1987, arithmetic overflow in the Therac 25 radiation therapy machines, along with a lack of hardware safety controls, caused the death of at least six people from radiation overdoses. An unhandled arithmetic overflow in the engine steering software was the primary cause of the crash of the 1996 maiden flight of the Ariane 5 rocket. The software had been considered bug free since it had been used in many previous flights, but those used smaller rockets which generated lower acceleration than Ariane 5. Frustratingly, the part of the software in which the overflow error occurred was not even required to be running for the Ariane 5 at the time that it caused the rocket to fail: it was a launch regime process for a smaller predecessor of the Ariane 5 that had remained in the software when it was adapted for the new rocket. Further, the true cause of the failure was a flaw in the engineering specification of how the software dealt with the overflow when it was detected: it did a diagnostic dump to its bus, which would have been connected to test equipment during software testing during development but was connected to the rocket steering motors during flight; the data dump drove the engine nozzle hard to one side which put the rocket out of aerodynamic control and precipitated its rapid breakup in the air. On 30 April 2015, the U. S. Federal Aviation Administration announced it will order Boeing 787 operators to reset its electrical system periodically, to avoid an integer overflow which could lead to loss of electrical power and ram air turbine deployment, and Boeing deployed a software update in the fourth quarter. The European Aviation Safety Agency followed on 4 May 2015. The error happens after 231 hundredths of a second (about days), indicating a 32 bit signed integer. Overflow bugs are evident in some computer games. In Super Mario Bros. for the NES, the stored number of lives is a signed byte (ranging from −128 to 127) meaning the player can safely have 127 lives, but when the player reaches their 128th life, the counter rolls over to zero lives (although the number counter is glitched before this happens) and stops keeping count. As such, if the player then dies it's an immediate game over. This is caused by the game's data overflow that was an error of programming as the developers may not have thought said number of lives could be earned. In the arcade game Donkey Kong, it is impossible to advance past level 22 due to an integer overflow in its time/bonus. The game calculates the time/bonus by taking the level number a user is on, multiplying it by 10, and adding 40. When they reach level 22, the time/bonus number is 260, which is too large for its 8 bit 256 value register, so it overflows to a value of 4 – too short to finish the level. In Donkey Kong Jr. Math, when trying to calculate a number over 10,000, it shows only the first 4 digits. Overflow is the cause of the famous "split screen" level in Pac Man. Such a bug also caused the Far Lands in Minecraft Java Edition which existed from the Infdev development period to Beta 1.7.3; it was later fixed in Beta 1.8. The same bug also existed in Minecraft Bedrock Edition but has since been fixed. In the Super Nintendo Entertainment System (SNES) game Lamborghini American Challenge, the player can cause their amount of money to drop below $0 during a race by being fined over the limit of remaining money after paying the fee for a race, which glitches the integer and grants the player $65,535,000 more than it would have had after going negative. IBM–Microsoft Macro Assembler (MASM) version 1.00, and likely all other programs built by the same Pascal compiler, had an integer overflow and signedness error in the stack setup code, which prevented them from running on newer DOS machines or emulators under some common configurations with more than 512 KB of memory. The program either hangs or displays an error message and exits to DOS. In August 2016, a casino machine at Resorts World casino printed a prize ticket of $42,949,672.76 as a result of an overflow bug. The casino refused to pay this amount, calling it a malfunction, using in their defense that the machine clearly stated that the maximum payout was $10,000, so any prize exceeding that had to be the result of a programming bug. The New York State Gaming Commission ruled in favor of the casino.