Marad´ekos oszt´as nagy sz´amokkal Uray M. J´anos, 2012
1
Bevezet´ es
C´elunk a nagy term´eszetes sz´ amokkal val´o sz´amol´as. A ”nagy” itt azt jelenti, hogy nagyobb, mint amivel a sz´ am´ıt´ og´ep k¨ ozvetlen¨ ul sz´amolni tud. A term´eszetes sz´ amok k¨ or´eben a n´egy alapm˝ uvelet a k¨ovetkez˝o: ¨osszead´as, kivon´as, szorz´ as ´es marad´ekos oszt´ as. Adottnak tekintj¨ uk, hogy a sz´am´ıt´og´ep ezeket kis sz´amokra el tudja v´egezni, ´es c´elunk, hogy ennek seg´ıts´eg´evel nagy sz´amokra is megval´os´ıtsuk a m˝ uveleteket. Hasonl´oan fogunk elj´ arni, ahogy ´ır´ asban szok´as sz´amolni. ´Ir´asban a sz´amol´ast arra vezetj¨ uk vissza, hogy a t´ızes sz´ amrendszer sz´ amjegyeivel tudunk sz´amolni. ´Irjuk fel h´ at mi is a sz´ amainkat egy olyan sz´amrendszerben, amelynek sz´amjegyeivel a g´ep k¨ozvetlen¨ ul sz´ amolni tud. A sz´ amrendszer alapsz´am´at jel¨olj¨ uk q-val, ´es legyen kett˝ohatv´any, m´egpedig 2n . Ha pl. egy 32-bites processzorunk van, akkor n = 32, ´es q = 232 = 4.294.967.296.
1.1
Gond az oszt´ assal
Ha v´egiggondoljuk¸ hogy hogyan v´egezz¨ uk el a m˝ uveleteket ´ır´asban, akkor r´aj¨ov¨ unk, hogy m´egse tudunk mindent visszavezetni a sz´amjegyekkel val´o sz´amol´asra. Az ¨osszead´as, a kivon´ as ´es a szorz´as m´eg megy, az oszt´ assal azonban gond van. Az oszt´assal akkor van gond, ha az oszt´o t¨obb sz´amjegyb˝ol ´all. Ilyenkor ugyanis minden l´ep´esben ezzel a t¨ obb sz´ amjegyes sz´ ammal kell osztani, mert csak az osztand´ot bontjuk fel r´eszekre. Ezt m´eg tov´ abb k´ene bontani, de ez olyan egyszer˝ uen m´ar nem megy. A tov´abbiakban m´ ar csak a marad´ekos oszt´assal foglalkozunk, ´espedig azzal, hogy hogyan lehet az oszt´ ast lebontani eg´eszen a sz´ amjegyekig.
1.2
Megold´ as
A probl´em´ at u ´gy oldjuk meg, hogy az oszt´ot kerek´ıtj¨ uk. A pontatlan, kerek´ıtett oszt´oval osztunk, majd az ´ıgy kapott eredm´enyb˝ol visszak¨ovetkeztet¨ unk az eredeti oszt´as eredm´eny´ere. Nyilv´an azt szeretn´enk, hogy a kerek´ıtett oszt´oval k¨onnyebb legyen sz´amolni, mint az eredetivel. Ez´ert a kerek´ıtett ´ert´ek u ´gy fog kin´ezni, hogy egy kett˝ohatv´any szorz´odik egy el´eg kicsi sz´ammal (olyan kicsivel, amivel m´ar k¨ozvetlen¨ ul tudunk sz´amolni, vagyis q-n´al kisebbel). Hogy a lehet˝ o legkisebb legyen a kerek´ıt´esi hiba, a lehet˝o legnagyobbnak v´alasztjuk az ”el´eg kicsi” sz´amot.
1.3
Kicsit form´ alisabban
Jel¨olj¨ uk az osztand´ ot a-val, az oszt´ ot pedig b-vel. C´elunk az a/b marad´ekos oszt´as h´anyados´ at ´es marad´ek´at meghat´ arozni, ezeket jel¨ olj¨ uk rendre c-vel ´es d-vel. (Mind a n´egy sz´am term´eszetes sz´am.) A marad´ekos oszt´ as azt jelenti, hogy a = bc + d, ´es d < b. Tesz¨ unk egy kik¨ ot´est: a < bq. Mi´ert j´o ez, ´es mi k¨ovetkezik ebb˝ol? ´Irjuk fel, hogy bq > a = bc+d ≥ bc. Ha a k´et v´eg´et ¨ osszeolvassuk, ´es osztjuk a pozit´ıv b-vel, akkor azt kapjuk, hogy c < q.
1
Vagyis, az a < bq felt´etellel azt k¨ ot¨ ott¨ uk ki, hogy a h´anyados, c belef´er egy sz´amjegybe. B´ ar els˝o r´an´ez´esre ez er˝ os megszor´ıt´ asnak t˝ unhet, de az ´altal´anosabb oszt´as mindig visszavezethet˝ o ilyen oszt´asokra (gondoljunk arra, hogy hogyan osztunk ´ır´asban). A felt´etel egy´ebk´ent azt is kik¨oti, hogy b 6= 0, hiszen 0q-n´ al nem lehett kisebb az a. Tegy¨ unk m´eg egy kik¨ ot´est: b ≥ 2q . Ezzel azt ´erj¨ uk el, hogy a b-ben van legal´abb n bit, amit majd a kerek´ıt´es sor´ an igyeksz¨ unk meg˝orizni. Az b < 2q esettel nem foglalkozunk k¨ ul¨on, mert akkor az oszt´ as nyilv´ anval´ o (vagy legal´abbis nem nehezebb, mint mondjuk a szorz´as, amivel szint´en nem foglalkozunk). A b < q esetet am´ ugy is ´erdemes k¨ ul¨on kezelni, mivel l´enyegesen hat´ekonyabb, mint az ´ altal´ anos eset, ´es p´eld´aul sz´amrendszer´atv´alt´asokhoz gyakran van ilyenekre sz¨ uks´eg (pl. ha t´ızes sz´ amrendszerben akarunk ki´ırni egy sz´amot). Jel¨olj¨ uk s-sel, hogy h´ any bitet hanyagolhatunk el legfeljebb a kerek´ıt´es sor´an: s := blog2 bc+ 1 − n. Mivel s + n a b bitjeinek sz´ ama, n bitet fogunk meg˝orizni a kerek´ıt´es sor´an. (A b ≥ 2q felt´etelb˝ol k¨ ovetkezik, hogy s term´eszetes sz´am, teh´at nem negat´ıv.) Az oszt´o kerek´ıtett ´ert´ek´et jel¨ olj¨ uk b0 -vel, ´es az a/b0 oszt´asb´ol sz´armaz´o eredm´enyeket pedig c0 -vel ´es d0 -vel, ´ertelemszer˝ uen. Ez azt jelenti, hogy a = b0 c0 + d0 ´es d0 < b0 . A kerek´ıt´es miatt b0 s oszthat´o 2 -nel, vagyis az als´ o s bitje mind nulla. M´eg k´et jel¨ ol´es: legyen ∆b a k´et oszt´o elt´er´ese, azaz ∆b := |b0 − b|; m´asr´eszt legyen ∆c a k´et h´anyados el˝ojeles elt´er´ese, azaz ∆c := c0 − c.
1.4
A kerek´ıtett oszt´ as
Az´ert kerek´ıtett¨ uk b-t, hogy b0 -vel k¨onnyebb legyen osztani. Val´oban k¨onnyebb osztani vele? A j´o az, hogy b0 oszthat´ o 2s -nel, vagyis szorzatk´ent fel´ırhat´o. A szorzat t´enyez˝oivel pedig k¨ ul¨on-k¨ ul¨on osztunk. De hogyan kell t´enyez˝ onk´ent osztani marad´ekosan? N´ezz¨ uk ´altal´anosan: osszuk el a-t xy-nal marad´ekosan. El˝ osz¨ or x-szel: a = xcx + dx , ahol dx < x. Majd a cx -et osszuk el y-nal is: ´ t˝ cx = ycy + dy , ahol dy < y. Behelyettes´ıtve: a = x(ycy + dy ) + dx = xycy + xdy + dx . Ugy unik, hogy az xy-nal val´ o oszt´ as h´ anyadosa cy , marad´eka pedig xdy + dx . Hogy ez t´enyleg ´ıgy van-e, az m´ar csak att´ ol f¨ ugg, hogy a marad´ek kisebb-e, mint xy. Felhaszn´ aljuk a dx < x ´es a dy < y felt´eteleket. Mivel eg´esz sz´amokr´ol van sz´o, az is igaz, hogy dy ≤ y − 1. x-szel szorozva: xdy ≤ xy − x. Hozz´aadjuk a dx < x egyenl˝otlens´eget: xdy + dx < xy, ´es ezt akartuk megmutatni. Teh´at felbonthatjuk a b0 -vel val´ o oszt´ast k´et r´eszre: el˝osz¨or 2s -nel osztunk, majd a b0 m´asik t´enyez˝oj´evel. A kett˝ ohatv´ annyal val´ o marad´ekos oszt´as nem csin´al m´ast, mint k´et r´eszre osztja az a bitjeit: az als´ o s bit lesz a marad´ek, ´es a t¨obbi a h´anyados. Az a fels˝o bitjeit kell m´ ar b0 csak 2s -nel osztani, ami egy el´eg kicsi eg´esz sz´am. Az ´ıgy kapott marad´ekot pedig csak ki kell eg´esz´ıteni az a als´ o bitjeivel, hogy megkapjuk a b0 -vel val´o oszt´as marad´ek´at.
2
Kerek´ıt´ esi t´ etelek
M´ar tudjuk, hogy hogyan kell osztani b0 -vel, de a legfontosabb k´erd´esre m´eg nem adtunk v´alaszt: hogyan fogjuk a kerek´ıtett oszt´as eredm´eny´eb˝ol, azaz c0 -b˝ol ´es d0 -b˝ol megkapni az eredeti oszt´as eredm´eny´et, c-t ´es d-t? Ehhez el˝ osz¨ or is meg kell mondani, hogy pontosan hogyan kerek´ıtett¨ unk. Azt m´ar mondtuk, hogy b0 -nek oszthat´ onak kell lennie 2s -nel. Az s fenti v´alaszt´asa az´ert nagyon fontos, mert ´ıgy a b-b˝ol a lehet˝ o legt¨ obb ´ert´ekes bit marad meg u ´gy, hogy azok m´eg belef´erjenek egyetlen sz´amjegybe. Azt viszont m´eg nem mondtuk meg, hogy milyen ir´anyban kerek´ıt¨ unk. Ez alapj´an h´arom lehet˝os´eget n´ez¨ unk meg: a lefel´e kerek´ıt´est, a felfel´e kerek´ıt´est ´es a szab´alyos kerek´ıt´est. Lefel´e 2
kerek´ıt´esn´el b0 az a legnagyobb 2s -nel oszthat´o sz´am lesz, mely legfeljebb b. Felfel´e kerek´ıt´esn´el ford´ıtva: b0 az a legkisebb 2s -nel oszthat´o sz´am lesz, mely legal´abb b. Szab´alyos kerek´ıt´esn´el b0 a b-hez legk¨ozelebb ´ all´ o 2s -nel oszthat´ o sz´am lesz. Ha k´et ilyen is van, akkor a nagyobbik. Mindh´arom kerek´ıt´esnek megvan a maga el˝onye ´es h´atr´anya. A lenti t´etelek v´ alaszt fognak adni arra a k´erd´esre, hogy a kerek´ıtett oszt´as h´anyadosa mennyivel t´erhet el az eredeti oszt´ as h´ anyados´at´ol, azaz a ∆c lehets´eges ´ert´ekeit mondj´ak meg.
2.1
Seg´ edt´ etel
El˝osz¨or bizony´ıtunk egy ´ altal´ anos t´etelt, amely egyel˝ore t´avol ´all az eddigi jel¨ol´esekt˝ol. Viszont fel tudjuk haszn´ alni az eredm´enyt a h´arom konkr´et kerek´ıt´esi t´etel bizony´ıt´as´ahoz. Jel¨ ol´ esek 1. a, b1 , b2 , c1 , c2 , d1 , d2 , x, y, z ∈ N 2. ∆b := b2 − b1 3. ∆c := c1 − c2 Felt´ etel 1. Marad´ekos oszt´ as: ∀i ∈ {1, 2} : a = bi ci + di ∧ di < bi . 2. Oszt´ok viszonya: b2 ≥ b1 > 0. 3. Az oszt´ ok elt´er´ese: ∆b ≤ 2x 4. c2 < 2y . 5. blog2 b1 c ≥ z ´ ıt´ All´ as ∆c ∈ [0..2x+y−z ] Bizony´ıt´ as 1. Megmutatjuk, hogy ∆c ≥ 0. Ez az ´all´ıt´as egyik fele. Egyr´eszt a = b2 c2 + d2 ≥ b2 c2 . M´ asr´eszt a = b1 c1 + d1 < b1 c1 + b1 = b1 (c1 + 1) ≤ b2 (c1 + 1). A k´et v´eg´et ¨ osszeolvasva azt kapjuk, hogy b2 (c1 + 1) > b2 c2 . Ezt elosztjuk a pozit´ıv b2 -vel: c1 + 1 > c2 , ´ atrendezve ∆c > −1. De ∆c eg´esz sz´am, ´ıgy ∆c ≥ 0. Ha meggondoljuk, ez el´eg term´eszetes: ha az oszt´ot n¨ovelj¨ uk, akkor a h´anyados legfeljebb cs¨okkenhet. 2. Megmutatjuk, hogy ∆c ≤ 2x+y−z . Ez az ´all´ıt´as m´asik fele, a kev´esb´e nyilv´anval´o r´esz. El˝osz¨or alak´ıtsuk ´ at a b1 ∆c-t: b1 ∆c = b1 (c1 − c2 ) = b1 c1 − b1 c2 = b1 c1 − (b2 − ∆b)c2 = b1 c1 − b2 c2 + ∆b · c2 = (a − d1 ) − (a − d2 ) + ∆b · c2 = d2 − d1 + ∆b · c2 < b2 − d1 + ∆b · c2 ≤ b2 + ∆b · c2 = (b1 + ∆b) + ∆b · c2 = b1 + ∆b · (c2 + 1) ≤ b1 + 2x · 2y = b1 + 2x+y . x+y
Olvassuk ¨ ossze: b1 ∆c < b1 + 2x+y , ´es osszuk el a pozit´ıv b1 -gyel: ∆c < 1 + 2 b1 . A jobb oldalon ´ all´ o kifejez´est tov´ abb becs¨ ulj¨ uk fel¨ ulr˝ol u ´gy, hogy a b1 -t becs¨ ulj¨ uk alulr´ol.
3
Tudjuk, hogy blog2 b1 c ≥ z, amib˝ol k¨ovetkezik, hogy log2 b1 ≥ z, azaz b1 ≥ 2z . Ezt x+y x+y alkalmazzuk: ∆c < 1 + 2 b1 ≤ 1 + 2 2z = 1 + 2x+y−z . Azt kaptuk, hogy ∆c < 1 + 2x+y−z , de mivel eg´esz sz´ amokr´ ol van sz´ o, ∆c ≤ 2x+y−z . Megjegyz´ esek 1. A bizony´ıt´ as els˝ o fel´eben csak az els˝o k´et felt´etelt haszn´altuk. 2. A t´etelben szerepl˝ o ∆b-nek ´es ∆c-nek – egyel˝ore – semmi k¨oze nincs a kor´abban bevezetett ugyanilyen nev˝ u param´eterekhez. Viszont a lenti h´arom t´etelben u ´gy fogjuk haszn´alni ezt a seg´edt´etelt, hogy m´egis lesz k¨oz¨ uk egym´ashoz – m´eg ha nem is felt´etlen¨ ul fognak egybeesni az azonos nev˝ uek (hanem pl. ellentettjei lesznek egym´asnak).
2.2
A lefel´ e kerek´ıt´ es t´ etele
Felt´ etel • b-t lefel´e kerek´ıtj¨ uk: b0 = b − ∆b, • A kerek´ıt´es pontoss´ aga: ∆b ≤ 2s . • A kerek´ıtett oszt´ o is ugyanannyi ´ert´ekes bitet tartalmaz, mint az eredeti: 0 blog2 b c + 1 = s + n ´ ıt´ All´ as ∆c ∈ {0, 1, 2}. Bizony´ıt´ as Felhaszn´ aljuk a seg´edt´etelt, az al´ abbi szereposzt´asokkal: • b1 := b0 , c1 := c0 , d1 := d0 ; • b2 := b, c2 := c, d2 := d; • x := s, y := n, z := s + n − 1. A felt´etelek nyilv´ anval´ oan teljes¨ ulnek. A t´etel azt mondja, hogy ∆c ∈ [0..2x+y−z ]. Most x + y − z = s + n − (s + n − 1) = 1, azaz ∆c ∈ [0..2] = {0, 1, 2}, ´es ezt kellett bizony´ıtani.
2.3
A felfel´ e kerek´ıt´ es t´ etele
Felt´ etel • b-t felfel´e kerek´ıtj¨ uk: b0 = b + ∆b, • A kerek´ıt´es pontoss´ aga: ∆b ≤ 2s . ´ ıt´ All´ as ∆c ∈ {−2, −1, 0}. 4
Bizony´ıt´ as Ism´et felhaszn´ aljuk a seg´edt´etelt, de most a vessz˝os¨ok tekintet´eben ford´ıtott szereposzt´assal: 1. b1 := b, c1 := c, d1 := d; 2. b2 := b0 , c2 := c0 , d2 := d0 ; 3. x := s, y := n, z := s + n − 1. A legt¨obb felt´etel mag´ at´ ol ´ertet˝ od˝ oen itt is teljes¨ ul. Az egyetlen k´erd´es a c2 < 2y , azaz hogy < q. Azt tudjuk, hogy c < q. Megmutatjuk, hogy c0 ≤ c. Azt a tr¨ ukk¨ ot haszn´ aljuk, hogy felhaszn´aljuk a seg´edt´etel els˝o fel´et. Ehhez sz¨ uks´eg van arra y az ´eszrev´etelre, hogy a c2 < 2 felt´etelt ott m´eg nem haszn´alja fel a t´etel, teh´at azt a fel´et nyugodtan alkalmazhatjuk an´elk¨ ul is. Az a r´esz pedig ´eppen azt mondja, hogy c0 ≤ c, ´ıgy 0 megmutattuk, hogy c < q. Most m´ar teljes¨ ul minden felt´etel a seg´edt´etelhez. Ebb˝ol k¨ovetkezik, hogy −∆c ∈ [0..2x+y−z ]. Az´ert −∆c, mert az itteni ∆c = c0 − c, de az ottani ∆c = c − c0 . Most is igaz, hogy x + y − z = s + n − (s + n − 1) = 1, ez´ert −∆c ∈ [0..2], vagyis ∆c ∈ {−2, −1, 0}, ´es ezt kellett bizony´ıtani. c0
2.4
A szab´ alyos kerek´ıt´ es t´ etele
Felt´ etel • A kerek´ıt´es pontoss´ aga: s−1 ∆b ≤ 2 . • A kerek´ıtett oszt´ o nem tartalmaz kevesebb ´ert´ekes bitet, mint az eredeti: 0 blog2 b c + 1 ≥ s + n ´ ıt´ All´ as ∆c ∈ {−1, 0, 1}. Bizony´ıt´ as K´et eset lehets´eges att´ ol f¨ ugg˝ oen, hogy b vagy b0 a nagyobb. Mindk´et r´eszben a seg´edt´etelre hivatkozunk. Ha b0 ≥ b, ekkor ugyanazt a szereposzt´ast haszn´aljuk, mint a felfel´e kerek´ıt´es t´etel´en´el, kiv´eve: x := s − 1. Ekkor x + y − z = (s − 1) + n − (s + n − 1) = 0. A seg´edt´etel szerint −∆c ∈ [0..20 ], azaz ∆c ∈ {−1, 0}. Ha b0 ≤ b, akkor pedig a lefel´e kerek´ıt´es t´etel´enek szereposzt´as´at vessz¨ uk alapul, de itt is 0 van egy kiv´etel: x := s − 1. A c < q felt´etelt is ugyan´ ugy l´atjuk be, mint ott. Az el˝oz˝o esethez hasonl´oan most is x + y − z = 0, teh´ at a t´etel szerint ∆c ∈ [0..20 ] = {0, 1}. Ha ¨osszes´ıtj¨ uk a k´et eredm´enyt: ∆c ∈ {−1, 0, 1}, megkapjuk a bizony´ıtand´o ´all´ıt´ast.
3
Visszak¨ ovetkeztet´ es
Az eddigiek alapj´ an, ha ismerj¨ uk a pontatlan h´anyadost (c0 -t), akkor tudunk mondani egy sz˝ uk (h´ aromelem˝ u) halmazt, amelyben a pontos h´anyados (c) van. De m´eg nem tudjuk megmondani, hogy ´eppen melyik lesz a h´arom k¨oz¨ ul. Arr´ol szint´en nem volt sz´o, hogy a marad´ekot (d-t) hogyan hat´ arozzuk meg. Most ezekr˝ ol lesz sz´ o. 5
Nagy szerencse, hogy a c lehets´eges ´ert´ekei csak h´aromelem˝ u halmazt alkotnak, ´es nem mondjuk t´ızelem˝ ut vagy sz´ azelem˝ ut (ez´ert volt kulcsfontoss´ag´ u, hogy a b0 annyi ´ert´ekes bitet ´ meg˝oriz a b-b˝ ol, amennyit csak lehet). Igy ugyanis mind¨ossze k´et ¨osszehasonl´ıt´assal el tudjuk majd d¨onteni, hogy melyik eset ´ all fenn. A legegyszer˝ ubb m´ odszer az, hogy megszorozzuk c0 -t b-vel, a pontos oszt´oval. Ha t¨obbet kapunk, mint az a, akkor c0 t´ ul sok volt, cs¨okkents¨ uk eggyel. Ha pedig az eredm´eny j´oval kisebb, mint az a (azaz legal´ abb b-vel kisebb), akkor n¨ovelj¨ uk a c0 -t eggyel. (Kerek´ıt´esf¨ ugg˝ o, ´ hogy melyiket kell megvizsg´ alni.) Igy k´et l´ep´esben biztosan eljutunk a j´o c-hez. A marad´ekot pedig az a − bc kifejez´es adja meg. Megn´ez¨ unk egy m´ asik m´ odszert is, egy fokkal hat´ekonyabbat. Ott nem nem b-vel fogjuk szorozni a c0 -t, hanem ∆b-vel, amely egy sz´amjeggyel r¨ovidebb, ´ıgy eggyel kevesebb elemi szorz´ as kell hozz´a. A m´ odszert a h´ aromf´ele kerek´ıt´esre k¨ ul¨on-k¨ ul¨on mutatjuk be.
3.1
Lefel´ e kerek´ıt´ es
Most az a helyzet, hogy ∆c ∈ {0, 1, 2}. Ez azt jelenti, hogy a keresett c vagy egyenl˝o c0 -vel, vagy eggyel kevesebb, vagy kett˝ ovel kevesebb. El˝osz¨or megmutatjuk, hogy c < c0 − k ⇐⇒ ab < c0 − k, ha k egy tetsz˝oleges eg´esz sz´am. Becs¨ ulj¨ uk az ab -t: ab = bc+d = c + db , ´es tudjuk, hogy 0 ≤ d < b, ez´ert c ≤ ab < c + 1. A b ”jobbr´ol balra” ir´ any m´ ar k¨ ovetkezik is ebb˝ol. A ford´ıtotthoz m´eg az kell, hogy a bal oldalon eg´esz sz´amok vannak, ´ıgy c + 1 ≤ c0 − k, ´es ebb˝ol k¨ovetkezik a jobb oldal. Miel˝ott megindokoln´ ank, hogy mi´ert van sz¨ uks´eg erre az ´all´ıt´asra, tov´abb alak´ıtjuk a jobb oldalt. Megszorozzuk mindk´et oldalt a pozit´ıv b-vel, ´es be´ırjuk, hogy a = b0 c0 + d0 : b0 c0 + d0 < bc0 − kb. Ezt ´ atrendezz¨ uk, felhaszn´ alva, hogy ∆b = b − b0 : d0 < ∆b · c0 − kb. A v´egeredm´eny teh´at: c < c0 − k ⇐⇒ d0 < ∆b · c0 − kb. De mi´ert is j´ o ez nek¨ unk? Ha k-t 0-nak vagy 1-nek v´alasztjuk, akkor sz¨ uks´eges ´es el´egs´eges felt´eteleket kapunk arra, hogy c mikor kisebb c0 -n´el legal´abb eggyel, ´es mikor kett˝ovel. A f´elt´etelben pedig, mint ´ıg´ert¨ uk, a ∆b · c0 szorzat szerepel. M´ar csak a d meghat´ aroz´ asa van h´ atra. Ezt a c h´arom lehets´eges ´ert´ek´ere k¨ ul¨on adjuk meg. 0 0 0 Mindh´arom esetben az a k´etf´ele fel´ır´ as´ab´ol indulunk ki: bc + d = b c + d . Ebbe fogjuk a c k¨ ul¨onb¨oz˝o ´ert´ekeit helyettes´ıteni. Pontosan akkor lesz c = c0 , ha d0 ≥ ∆b · c0 . Ezt a fenti felt´etelb˝ol kapjuk a k = 0 helyettes´ıt´essel (´es mindk´et oldal tagad´as´aval). Ekkor az a k´etf´ele fel´ır´asa ´ıgy fog kin´ezni: bc0 + d = b0 c0 + d0 , ´ atrendezve: d = d0 − ∆b · c0 . Egy´ebk´ent, azaz ha d0 < ∆b·c0 , akkor c < c0 . Pontosan akkor lesz c = c0 −1, ha b ≥ ∆b·c0 −d0 (ez a k = 1 helyettes´ıt´esb˝ ol ad´ odik). Ekkor b(c0 −1)+d = b0 c0 +d0 , ´atrendezve: d = b−(∆b·c0 −d0 ). A harmadik esetben, azaz ha b < ∆b · c0 − d0 , lesz c = c0 − 2. Ekkor b(c0 − 2) + d = b0 c0 + d0 , ´atrendezve: d = b − ((∆b · c0 − d0 ) − b). Igyekezt¨ unk k¨ onnyen sz´ amolhat´ o alakban fel´ırni a v´egeredm´enyeket. P´eld´aul a harmadik 0 eset fel´ır´as´ab´ ol l´ atszik, hogy ∆b · c − d0 kifejez´est t¨obbsz¨or is haszn´aljuk, ´ıgy el˝ore ki tudjuk sz´am´ıtani. M´ asr´eszt a r´eszeredm´enyek sosem negat´ıvak, ´es a lehet˝o legkisebbek. ¨ A legv´eg´en, az Osszefoglal´ as c. fejezetben megism´etelj¨ uk a v´egeredm´enyeket.
3.2
Felfel´ e kerek´ıt´ es
Most ∆c ∈ {−2, −1, 0}, vagyis c vagy egyenl˝o c0 -vel, vagy eggyel t¨obb, vagy kett˝ovel t¨obb. Most azt fogjuk el˝ osz¨ or bebizony´ıtani, hogy c > c0 + k ⇐⇒ ab ≥ c0 + k + 1. M´eg mindig igaz, a alva a jobb oldali ´all´ıt´asb´ol k¨ovetkezik, hogy c+1 > c0 +k+1, ami hogy c ≤ b < c+1. Ezt felhaszn´ ugyanaz, mint a bal oldali. Ha a bal oldali egyenl˝otlens´egb˝ol indulunk ki, akkor kihaszn´aljuk,
6
hogy eg´esz sz´ amokr´ ol van sz´ o, ´es ´ at´ırjuk u ´gy, hogy c ≥ c0 + k + 1. Ebb˝ol pedig k¨ovetkezik a jobb oldali ´all´ıt´ as. ´ Atalak´ ıtjuk a jobb oldalt. Megszorozzuk a pozit´ıv b-vel, ´es be´ırjuk az a m´asik alakj´at: ´ b0 c0 + d0 ≥ bc0 + b(k + 1). Atrendezz¨ uk (most ∆b = b0 − b): ∆b · c0 + d0 ≥ b(k + 1). Ezzel megkaptuk az ¨ osszef¨ ugg´est: c > c0 + k ⇐⇒ ∆b · c0 + d0 ≥ b(k + 1). Most j¨on a d meghat´ aroz´ asa, a h´ arom esetben. 0 Pontosan akkor lesz c = c , ha ∆b · c0 + d0 < b (ez a k = 0 eset). Ekkor bc0 + d = b0 c0 + d0 , ´atrendezve: d = ∆b · c0 + d0 . Egy´ebk´ent (azaz ha ∆b · c0 + d0 ≥ b), pontosan akkor lesz c = c0 + 1, ha ∆b · c0 + d0 − b < b (ez a k = 1 eset). Ekkor b(c0 + 1) + d = b0 c0 + d0 , azaz d = ∆b · c0 + d0 − b. K¨ ul¨onben (azaz ha ∆b·c0 +d0 −b ≥ b) c = c0 +2, amib˝ol k¨ovetkezik, hogy b(c0 +2)+d = b0 c0 +d0 , ´es ´atrendezve megkapjuk, hogy d = ∆b · c0 + d0 − 2b.
3.3
Szab´ alyos kerek´ıt´ es
Most ∆c ∈ {−1, 0, 1}, vagyis c vagy egyenl˝o c0 -vel, vagy eggyel t¨obb, vagy eggyel kevesebb. El˝osz¨or azt kell megn´ezni, hogy melyik a nagyobb: b0 vagy b? Ha b ≥ b0 , akkor tulajdonk´eppen lefel´e kerek´ıtett¨ unk. Vagyis haszn´alhatjuk a lefel´e kerek´ıt´es k´epleteit, de most m´eg azt is tudjuk, hogy c nem lehet c0 − 2, teh´at a m´asodik ¨osszehasonl´ıt´ as felesleges. Ha pedig b0 ≥ b, vagyis felfel´e kerek´ıtett¨ unk, akkor ugyan´ ugy kell elj´arni, mint a felfel´e kerek´ıt´esn´el, csak itt sem fordulhat el˝ o az utols´o eset, azaz hogy c = c0 + 2.
4
El˝ ony¨ ok ´ es h´ atr´ anyok
Az´ert vizsg´ altunk meg t¨ obbf´ele kerek´ıt´est is, mert mindegyiknek megvannak a maga el˝onyei ´es h´atr´anyai. Ezeket n´ezz¨ uk most meg, szempontok szerint.
4.1
A kerek´ıt´ es
Melyik ir´ anyba milyen k¨ onny˝ u kerek´ıteni? A legk¨onnyebb a lefel´e kerek´ıt´es: egyszer˝ uen csak elhagyjuk a b als´o s bitj´et, null´at ´ırva a 0 hely¨ ukre. Azt is csak gondolatban, hiszen u ´gyis 2bs -nel fogunk sz´amolni, vagyis a fels˝o n bittel. A felfel´e kerek´ıt´es egy fokkal nehezebb: amellett, hogy az als´o s bitet kinull´azzuk (szint´en csak gondolatban), meg kell n´ezni, hogy eleve mind nulla volt-e; ha nem, akkor az eg´eszhez hozz´ a s kell adni 2 -t. Legal´ abbis, ha a szok´ asos felfel´e kerek´ıt´esre gondolunk. De vegy¨ uk ´eszre, hogy a kerek´ıt´esi t´etelben csak annyit tett¨ uk fel, hogy ∆b ≤ 2s , vagyis ak´ar 2s is lehet a kerek´ıt´es pontatlans´aga. Ezt azt jelenti, hogy val´oj´aban nem kell figyeln¨ unk, hogy az als´o s bit mind nulla-e (ennek az es´elye am´ ugy is eleny´esz˝oen csek´ely) – el´eg, ha felt´etel n´elk¨ ul hozz´aadjuk a 2s -t a sz´amhoz. Ez a hozz´ aad´ as csak a fels˝o n bitet ´erinti: ahhoz kell egyet hozz´aadni. A szab´alyos kerek´ıt´esn´el meg kell n´ezni az s. bitet, mert att´ol f¨ ugg, hogy melyik ir´anyba kerek´ıt¨ unk. Ha 1, akkor felfel´e, k¨ ul¨ onben lefel´e. Itt is kinull´azzuk gondolatban az als´o s bitet, ´es ha felfel´e kerek´ıt¨ unk, akkor hozz´ aadunk 2s -t.
4.2
T´ ulcsordul´ as
Mindeddig nem volt sz´ o egy s´ ulyos probl´em´ar´ol. Ez az elm´eleti sz´amol´asokat nem befoly´asolja, de a sz´am´ıt´og´epes megval´ os´ıt´ ast l´enyegesen – annyira, hogy ak´ar ez lehet a legfontosabb szempont, ami d¨ont a h´ arom kerek´ıt´es k¨ oz¨ ott.
7
Azt feltett¨ uk, hogy c < q, teh´ at c belef´er egyetlen sz´amjegybe (m´as sz´oval g´epi sz´oba). Az b ´gy v´alasztottuk meg, hogy a marad´ek belef´erjen is vil´agos, hogy 2s < q, hiszen az s-et ´eppen u egy sz´amjegybe. Arr´ol azonban nem volt sz´ o, hogy a kerek´ıt´es ut´an is megmaradnak-e ezek a tulajdons´agok, ?
vagyis hogy c0 < q ´es hogy s´er¨ ulhet meg: b0 2s
Lefel´e kerek´ıt´es Felfel´e kerek´ıt´es Szab´alyos kerek´ıt´es
(j´ o) q q
b0 ? 2s <
q. Foglaljuk ¨ossze egy t´abl´azatban, hogy mikor melyik hogyan
c0 q, q + 1 (j´ o) q
L´athat´o, hogy a felfel´e kerek´ıt´es a legjobb, mert ott csak egyf´elek´eppen csordulhat t´ ul valami, ´es az m´ar a kerek´ıt´esn´el kider¨ ul. ´ amikor m´ar tudjuk a A szab´alyos kerek´ıt´esn´el b´ armelyik lehet q, de nem egyszerre. Es kerek´ıt´es ir´any´ at, akkor az egyiket ki tudjuk z´arni. Mivel l´enyegesen k¨ onnyebb (´es hat´ekonyabb) egy sz´amjegy˝ u sz´amokkal sz´amolni, ez´ert a t´ ulcsordul´o eseteket k¨ ul¨ on ´erdemes kezelni. 0 A 2bs = q eset a legegyszer˝ ubb, mert az m´ar a kerek´ıt´es el˝ott l´atszik: akkor fordul el˝o, amikor felfel´e kerek´ıt¨ unk, ´es a b fels˝ o n bitje mind 1. Sz´amolni is k¨onny˝ u vele, hiszen ekkor b0 = 2s+n , ´es kett˝ohatv´ annyal borzaszt´ o egyszer˝ u marad´ekosan osztani. Ha a c0 viselkedik rosszul, azzal az a baj, hogy nehezebb ´eszre venni. Lefel´e kerek´ıt´eskor fordulhat el˝ o. K¨ onnyen l´ athat´ o, hogy c0 < q ⇐⇒ a < b0 q. Ha a vessz˝oket elhagyjuk, akkor tudjuk, hogy mindk´et oldal igaz. Ellen˝orizni kell teh´at, hogy amikor lefel´e kerek´ıt¨ unk, 0 megmarad-e ez a tulajdons´ ag. Ha nem, akkor a c t´ ulcsordul. A szab´alyos kerek´ıt´esn´el tudjuk, hogy ekkor c0 = q, de a lefel´e kerek´ıt´esn´el m´eg q + 1 is lehet. A ∆b · c0 kisz´am´ıt´as´an´al ezeket az eseteket k¨ ul¨ on kell sz´ amolni. Ha c0 = q, akkor k¨onny˝ u, mert q kett˝ohatv´any. Ha c0 = q + 1, akkor sem olyan neh´ez, l´enyeg´eben csak egy ¨osszead´as: ∆b · q + ∆b.
4.3
A visszavezet´ es m˝ uveletig´ enye
A l´enyeges k¨ ul¨ onbs´eg a h´ arom visszavezet´es k¨oz¨ott a felt´etelekben ´es a d kisz´am´ıt´as´aban ¨ van. Ezek a v´eg´en, az Osszefoglal´ as c. fejezetben l´athat´ok rendszerezve. A m˝ uveletek sor´ an nagy sz´ amokat kell ¨osszehasonl´ıtani, ¨osszeadni ´es kivonni. Ezek egyenk´ent t¨obb (s-sel ar´ anyos sz´ am´ u) elemi m˝ uvelettel helyettes´ıthet˝ok. Nem mindegy teh´at, hogy h´any m˝ uvelet kell elv´egezni. Mind a lefel´e, mind a felfel´e kerek´ıt´esn´el egy vagy k´et ¨osszehasonl´ıt´ast kell v´egezni, mert h´arom eset lehets´eges. A szab´ alyos kerek´ıt´esn´el azonban mindig csak egyet kell: ha m´ar tudjuk ugyanis, hogy merre kerek´ıt¨ unk (´es ez egyetlen biten m´ ulik), akkor csak k´et eset van. ´ Erdemes megjegyezni, hogy bizonyos esetekben az els˝o k´et kerek´ıt´esn´el is kik¨ usz¨ob¨olhet˝ o s−1 a m´asodik ¨osszehasonl´ıt´ as. Ha ugyanis kider¨ ul, hogy ∆b < 2 (ami egyetlen bit vizsg´alat´ at jelenti), akkor – a szab´ alyos kerek´ıt´eshez hasonl´oan – nem lehet c ´es c0 elt´er´ese 2, teh´at kiz´artuk a harmadik lehet˝ os´eget. Hasonl´ıts¨ uk m´eg ¨ ossze az els˝ o, nem meg´ uszhat´o ¨osszehasonl´ıt´asokat is. A lefel´e kerek´ıt´esn´el ez a d0 ≥ ∆b · c0 , a felfel´e kerek´ıt´esn´el pedig ∆b · c0 + d0 < b. Ez ut´obbi egy ¨osszead´assal t¨obb, de ezt a szorz´assal p´ arhuzamosan tudjuk v´egezni sz´amjegyenk´ent, ugyanis a ∆b · c0 -re k¨ ul¨on nincs sz¨ uks´eg sehol. A gond azzal lehet, hogy ez az ¨osszeg eggyel t¨obb bitnyi helyet ig´enyel, mint a k´et tagja k¨ ul¨ on-k¨ ul¨ on (azok s + n biten elf´ernek, de az ¨osszeg¨ uk lehet (s + n + 1)-bites is. Ezt az utols´o bitet adott esetben k¨ ul¨ on ´erdemes kezelni. 8
¨ Osszefoglal´ as
5
Feltev´esek, jel¨ ol´esek: • • • • • • • • •
q = 2n a = bc + d ∧ d < b a = b0 c0 + d0 ∧ d0 < b0 a < bq (m´ as sz´ oval c < q) b ≥ 2q s := blog2 bc + 1 − n b0 mod 2s = 0 ∆b := |b0 − b| ∆c := c0 − c
A h´aromf´ele kerek´ıt´es jellemz˝ oi:
Lefel´ e kerek´ıt´ es Felfel´ e kerek´ıt´ es Szab´ alyos kerek´ıt´ es
b0
∆c
b − 2s ≤ b0 ≤ b b ≤ b0 ≤ b + 2s s−1 b−2 ≤ b0 ≤ b + 2s−1
0, 1, 2 −2, −1, 0 −1, 0, 1
t´ ulcsordul´as b0 c0 2s (nincs) q, q + 1 q (nincs) q q
Visszavezet´es:
Lefel´ e kerek´ıt´ es
Felfel´ e kerek´ıt´ es
Szab´ alyos kerek´ıt´ es
felt´etel ha d0 ≥ ∆b · c0 k¨ ul. ha b ≥ ∆b · c0 − d0 k¨ ul¨onben 0 ha ∆b · c + d0 < b k¨ ul. ha ∆b · c0 + d0 − b < b k¨ ul¨onben 0 ha d ≥ ∆b · c0 ha b0 < b k¨ ul¨onben ha ∆b · c0 + d0 < b k¨ ul¨ onben k¨ ul¨onben
9
c c0 c0 − 1 c0 − 2 c0 c0 + 1 c0 + 2 c0 c0 − 1 c0 c0 + 1
d d0
c0
− ∆b · b − (∆b · c0 − d0 ) b − ((∆b · c0 − d0 ) − b) ∆b · c0 + d0 ∆b · c0 + d0 − b ∆b · c0 + d0 − 2b d0 − ∆b · c0 b − (∆b · c0 − d0 ) ∆b · c0 + d0 ∆b · c0 + d0 − b
