Негативное свойство отрицательных чисел

Тема далеко не новая, но часто упускаемая при обучении программированию, поэтому повторить лишний раз не помешает.

Допустим, вы хотите посчитать вещественный квадратный корень из модуля представимого в машинной архитектуре целого числа n, значение которого может быть любым. Какой код вы для этого напишете (используем синтаксис языка Си, хотя язык здесь не важен)?

1) double f = sqrt( abs(n) );

2) double f = sqrt( (double) abs(n) );

3) double f = sqrt( fabs( (double)n ) );

Разместим здесь КДПВ, чтобы у желающих было время поразмыслить.

Единственным корректным кодом при заданных условиях является ответ номер 3. Для значения n, равного минимальному отрицательному числу (то есть, например, -2147483648 для 32-разрядного типа int), два других ответа дадут значение NaN или приведут к аварийному завершению программы, в зависимости от архитектуры процессора. Строго говоря, это неопределённое поведение.

Почему так происходит? Опытные программисты, конечно, всё поняли, а для менее опытных объясним.

Отрицательные целые числа во всех современных процессорах представляются в дополнительном коде. Преимуществом дополнительного кода перед прямым и обратным кодом является только одно значение для кодирования нуля вместо раздельных +0 и -0. Но так как ноль у нас один, а общее количество значений, кодируемых двоичными разрядами, очевидно, чётно, то получается, что для одного положительного или отрицательного значения в любом случае не найдётся пары среди значений с другим знаком. И действительно, минимальное отрицательное число (-128, -32768, -2147483648 и т.д., в зависимости от разрядности целых) не имеет представимой положительной пары своей разрядности (+128, +32768, +2147483648 и т.д.).

Что же происходит при попытке обратить знак такого непарного числа? А ничего:

-(-2147483648) == -2147483648

abs (-2147483648) == -2147483648

Поэтому наша попытка обезопасить вычисление sqrt при помощи abs проваливается на таком значении, и мы получаем квадратный корень из отрицательного числа. Ну и во всех остальных алгоритмах возможна такая же ерунда.

В вещественных числах такого не происходит, так как они кодируются в прямом коде, и несимметричных вещественных значений нет. Зато есть +0.0 и -0.0.

@vadimr
20.02.2024 13:21 UTC
Первоисточник

Комментарии

@Komrus
20.02.2024 08:29 UTC
+3

В каком-то фантастическом романе герой показывает своему собеседнику некую жутко сложную штуковину (но вполне себе материальную) и говорит, что "Если совсем кратко - это физическое воплощение квадратного корня из единицы, которое на выдали в качестве решения Проблемы эти чёртовы теоретики :)))"

@Sdima1357
20.02.2024 08:48 UTC
+1

Или fabsf и sqrtf или double, Вы уж определитесь, а то потом спрашивают "А почему программы медленно работают?" (:.

@vadimr
20.02.2024 08:54 UTC
0

В C++ fabs и sqrt перегружаются, но для пунктуальности исправил.

@vesper-bot
20.02.2024 09:24 UTC
+1

Будучи математиком изначально, интерпретирую "вещественный корень от Х" как "вещественную часть" и писать буду соответственно, if (x<0) return 0; и все ваши проблемы с интами накрываются медным тазом. Ну и декларирую функцию как принимающую double на вход, ибо нефиг.
Апд: так как там стоит от "модуля Х", то сразу принимаю double на вход, что правда эквивалентно третьему пункту из статьи.

@Ritan
20.02.2024 13:12 UTC
0

А ещё более опытные программисты знают, что у fabs в C++ нет перегрузки, возвращающей целочисленный результат. Так что все три варианта идентичны

https://godbolt.org/z/s57rP1cr3

@vadimr
20.02.2024 16:32 UTC
0

Вы неправильно прочли варианты.

@JordanCpp
20.02.2024 18:23 UTC
+1

Все числа важны:)

@Tishka17
20.02.2024 18:58 UTC
0

используем синтаксис языка Си, хотя язык здесь не важен

Пишу на языке где нет перегрузки функций по типу параметра, поэтому - важен.

@vadimr
20.02.2024 19:19 UTC
+1

Эта проблема возникает независимо от перегрузки. Вопрос здесь в том, что делать первым - вычисление абсолютной величины или преобразование типа. А если смотреть глубже, то просто в том, как работает смена знака для целых чисел.

21.02.2024 12:11 UTC
+1

я переформулировал: вопрос в том, мы вычисляем абсолютную величину для целого или для дробного числа.

ну и в порядке шутки из других языков:

>>> x=-999999999999999999999999999999999999999999999999999999999999
>>> sqrt(abs(x))  
1e+30
>>> sqrt(fabs(x))
1e+30

21.02.2024 12:17 UTC
0

В питоне для расчётов обычно используется numpy и его типы.

@Refridgerator
22.02.2024 04:00 UTC
0

Допустим, вы хотите посчитать вещественный квадратный корень из модуля целого числа n, значение которого может быть любым. Какой код вы для этого напишете (используем синтаксис языка Си, хотя язык здесь не важен)?

Ну раз язык неважен, то правильный ответ должен быть первый. Потому если функция Abs может возвратить отрицательный результат - ну это как бы плохо написанная функция. Исключение в таких случаях должно быть, поскольку получить переполнение не только в целых, но и в вещественных числах миллиард вариантов может быть - гипотенуза там или обратный гиперболический синус.

@vadimr
22.02.2024 07:36 UTC
-1

Потому если функция Abs может возвратить отрицательный результат - ну это как бы плохо написанная функция.

Какая уж есть :) Так работает процессор.

22.02.2024 08:20 UTC
0

Разве? Вроде в ассемблере нет встроенной команды для Abs. Это библиотечная функция, которая ещё и обычно перегружается для разных типов аргумента. Который может быть не только (не)целым, а ещё и комплексным например. С комплексным аргументом, к слову, и Abs не потребуется - нормально корень из отрицательного числа посчитается.

22.02.2024 08:26 UTC
0

Как бы функция abs над целыми числами ни была реализована, она физически не может дать для минимального целого ничего, кроме него самого. Так как математически правильный ответ непредставим.

23.02.2024 10:34 UTC
+1

Она может и должна дать ошибку.

23.02.2024 10:37 UTC
0

Пожелание хорошее, но на практике компьютеры работают не так.

Собственно, по определению abs(x) = x, если x>=0, и abs(x) = -x, если x<0. Но загвоздка здесь в том, что -(-2147483648) = -2147483648. Так что проблема ещё ниже функции abs.

@jsirex
22.02.2024 14:55 UTC
0

Я, конечно, придираюсь, но по условию задачи: "из модуля целого числа n, значение которого может быть любым.", ни один вариант не сработает.

Если там любое, то надо вручную делать или искать правильную библиотеку.
Мне кажется для n = 2279007645453668185114145017513291003363507376616747250010693268623618900370615223998230373477662798335387558274762466365590308838731515811545774503949731972631284542006011254134497909588634455497504486214901024791690722437814790305562844247909532606475014860127053661792793223737910263835915079641001665595452148438273694513739205723331570590842028858688718328845934385802036584155636192354632446998878765497341852127128236912871931393650301018320873342552317012698279875731872640788602798499233565280815130171441147599977981554071506099072164929885670189777720034232522447520753055317561993108010462102156844418522781920979301723483921948236611800085636497253920378486699154258819383911534593038835702980114562066729102412119085962672834866452456030583185667068242596611513523148081786765483315162726085439790331411121974026454104161781128451532959798313772364666631057918648568653801022636407560627870205011283765982512302325433496335639484203654707273074785576598429947063024937751015507313755680261709874747687884708864554794990919390452807733351906515730261926677772808823512818916586137867277739309645421805434953431929661700806190510321304546525463662865011945065756453538615193145845925778465437839293905557820706454703490621576738120805958086585776017271570727945431675143155135458359552417215636899160553305613621475150567033610297610408722465970900788921024525630103187134091101273034459647683103396471781903474564902632628364924168946165725545014435775773374831485661065186945415938719820418846060757455657726924791396656119606433578932105165628696111811767009835942482239807833371479151711830530097294037724941531118055305256126681020982524058422384355659176035631057509252749088243938027240552678125737950293291418055461954706091188694999485175234914509275658772153549144909039318260674471516239196142831166905848694714421981021278072416837597251360111375939527923817956303583202518417792122065207034206968043850386457590399815336725986765937307055053685428547549210596608911464464745812075513046568738468271550691880818952830650999260675832904192795897057799813505952458289136204483141154550476888818200884635774416898746145031194825426504264133595358947446866326604670476298065506111343144120467897524174191538840429924810287342651810538032577496153905267490265128835050343301032604814483211012843771561650999726134660870017146371344855229786830620432302066362204218196030712048897948501793649196267689974276014579566317714192856175785991956222305881924053353789722633325756917536638890347225201592686949789351212944040432329250710252440642128714416090370898602268645631425735168714362648309220753657432762541721649704506745712631022814266448119780497269827489016777465773222222852437718785218887936199844798592016867327853506163407877140732136937117453243175556476672413221428725562861827277343232771973104539396946485270908010140281592142675085401661696156882365053436405229225965570645629909675022843234578208516175070436744841742660423821345061745632993263619564546904488229917713302009128651897930648261609398769492265091754718190350762720918649558547125879009545293852125120132610112029882084240351229100255684951874981579671264801786193618714821759804764934718347152586648508529498699309528332078392134590052120116393901825234526649538456730512006656508949360922120592552358485610475576856728020668251257990875471433159539462683087437764273143903201746903245495189410912757244704009583045603522245228768485831097849510150536154827412229302926139791899404993371017291393026711773989046093356147984894607175406313387961678342802449772383878032772017015985720080692670534767681526828983439680733116267644447458269711297186802683293222727690413831103038332829520382247773568094971224838176431136911133439462014380423959398042165085655322962407566862579857274044991198485610809837996190005393641929075238177368950373857288824816768385578941697506831772626111997863413448214908509223813135528848739737668012216334067217544862740765907099597344902033712008000480981504919131056975416628544666336855857702752724523944494812781649199546340646023185064372035310593071866625967735409027108679544431084015573672607975533529024553402891121470089322636922423603180599528683031795447749816922887554773699546805960211531966476702464665947383269339284289544085979555094359084364970100080384301907781823856821392171724270131752557760400799717801841452716345146267128733121632255160392699001696100645081778490031867798842331164300948067430321877903030566825858730163633642365002726626414246616689515627727399790682109395141624401727059784066748664608857765805303542604789734306475959660113499665012759390055623947952695626006862683528016099069351681136433232001215851383703313531341198852019445235886574962664662366296556087415081621811700280113346202581350963625213538925053664267655346179758007874416300896789426608348046340542636750618793451170851646919221674994974354621555859758701003387106640039035249976304233673723197518924470043693745058972708044295570476429306277765113153982229830291854677346967842728074596706492133161080759032629381122107706299911796747691688922247061167909540085151565392617363658509965857634402805002940901103221845607229300933529236569962107794595617713602015526941343476749049246561293852889583175504881136387556327966487261384477023449228523711911497401014104200335513883200105557516963607204156050143859894566045281129688184219429028450930355617326810028820527985017687743051765979512865704272563763123139417597945444680043521748558780705528631192001225494701374076495210141153674266270254782981579775618825343099947844836024679649498512000819967670553785226054923764872020692214860446429580227637844762298053259058655983201746284232747242263633607088690563110935135601106953780030312250696225985284198531233635166614982149467223081972225549781364803490510555421054107157652187701891238610062851814958179552414107211826984910221873310409596863447447930984567456201048382145380918029014783311753952713883459499240252282863100754098338596817718012916876596902036988369660259486258605123539649945399367819287754790903318181008142646929939329517383473776890837270305878851271664741625993276815330051116109773452128314229729904442687289509967113918948939310425975507572848289358942229531681000927964546284980286682133378878933715483348857330558772322407784871044307345967691626942701714800572625029556610408807237838818856210344525427818054641257363091703536922701074476600670005810035563444933258948710648016132472337445258215862976437420786093570641925522697144349486173870219406405941254541944117232328686340876429476499944324593375343976841663652883905294848476321788358858245142532520095678485405803473450535649263688652304541692594657941305007948812532945904234517211969783715390594349581516233769639321212466921505465398443234894181155144366348509433942210710316495961141044727410249417736321018367906819594608832003919143246847894809513705908831180901205613406582133370453369311269099567451663546115399159751067831651680648142600370612308746535039164082520905556231846896638940683742007637594398608698300141467166596992154134121944091299774645627873013556060120388781584543200662728088528604432817669399890172182260973015666618092424716662487374138084776571443955603547147659873528432366106107608608009661235454308925385140244808765295512265472898299561108128332101705633340866279020568275150759718037237836161 оно не заработает.
Корень: 47738953124819025351628008345542638429421155028137966291758667063884900073076874203478171866599366056296891038301705249919578041821632054104149083241780858332315544539393643098940681767727732468289090775849340681681509732520914296536072195052809816125805260920039326514082515733632459974850137566570078747231372472609078773635746419533441159985042551914746782813360981582648433891741953676492830581941624566292647591527733858191480484166809646874009097741350144110905606542925779660465251271821358250555916528275301008398170529394853259444817488921214614412731869302267458332976206683918276832336306925761347801600674710111430159002007559226455343655645229743154941081992335855623907006982702410282538993351499824663522611075660376016572208636453140324924959419368003465548383282865868954709755752156084633824746319352005241169526783322245359014729571696109505024799518719681169742018738120465883646626788555162574484285998505407016403699482807516154831695725005384549609837220469235685005312182587165919568737191101622020002849026691022069577365686846825516839862946408219805032454153680219112926094586719920695797779529656201125853651398187662122280897496771990943085539028162737156935794134873073013621699916301588414680495129581258924599480589380503198088302740267217371731777257024917608568327918129855554913334895911819467775450249182859624173888855277227121588793428187639750485398521402169839637724003922762336989332949960755244644855480586551648544941606615656939865733787419990266709292839589163369691523951250103404301140804127972833130307842452130247652988709614832044375122807354801256789402604647342709733236783422010398721741695017749972170375003167342222640487728663435318409756977345141796100277222000509543548785893385385335994898948085209645077179338817432253643070219934075358856680420954527375640581770511234594673659634318557253884047778062577501762658073843574689901263214020339266244401704135830414090549931610770746778284735753707011357044244351586378968524094408929274839802969174108952771970951699064706805190356085290508718358893388676344803314637048557955999427383020318431114132727582224589350781407043517474808238614360078500986533364832608845147094537778805746503804081986046199765200907087739378153921471145785745965931959727967888040916432548202362928827982510941206472653861146415407424845962602345231387961703554690885897182357735711191991259152142887903579981113786599790672843056671936040804184583338612287667353711649161668058397644811311652720240006344257765033873221133463402960161662825406076591107804865724451634314277546604191206769080284877493642016717967401714755383725824420622182524057981096012072074271351463512039935987209582678912486039985213408962545841019107988379116889744695653976040225780289827614665594502189761171928324327642083929559515380519251155355447484830257948724480283348597093310083600242916431826759084982536831882355091261309704400875261949921848657667843864995289091684641344329822389791702262486500965185202554401511455746661168143152409674943326812486664480612656645213163096679714775658650388308337397977291847017765584554595457425118495311823090789836378973120085511255147478436877099213731493396736920242151287481105335017638947660481987580487027307981147396231852497021766518681943003269341435172857263407509553978663043870713745178880462272167919223736662233386297106089474801378612636853927542343594483286412935192035063309790846430648601826441520868644073846612550802821863862794638735740007641727024913093871622950816778290284892096476781928009365451898442882768661340345392096764174328838924624449702185041386846083887025438754685156834986098644375276727286352996012610798847822163500912134130881

@vadimr
22.02.2024 15:07 UTC
0

Я бы сказал, что это не целое число в техническом смысле (и в терминологии любой существующей реализации языка Си, используемого для иллюстрации задачи). Тем не менее, я внёс уточнение, спасибо.

К слову, забавно, что в турбо паскале 1990-х годов был тип Comp, который представлял 64-разрядные целые числа, но формально считался вещественным.

P.S. А Ваша замечательная константа имеет какой-то скрытый смысл, или это просто случайные числа?