11.3 Addition and Subtraction

11 Big Integers

$\newcommand{\footnotename}{footnote}$ $\def \LWRfootnote {1}$ $\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}$ $\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}$ $\let \LWRorighspace \hspace $ $\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }$ $\newcommand {\TextOrMath }[2]{#2}$ $\newcommand {\mathnormal }[1]{{#1}}$ $\newcommand \ensuremath [1]{#1}$ $\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } $ $\newcommand {\setlength }[2]{}$ $\newcommand {\addtolength }[2]{}$ $\newcommand {\setcounter }[2]{}$ $\newcommand {\addtocounter }[2]{}$ $\newcommand {\arabic }[1]{}$ $\newcommand {\number }[1]{}$ $\newcommand {\noalign }[1]{\text {#1}\notag \\}$ $\newcommand {\cline }[1]{}$ $\newcommand {\directlua }[1]{\text {(directlua)}}$ $\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}$ $\newcommand {\protect }{}$ $\def \LWRabsorbnumber #1 {}$ $\def \LWRabsorbquotenumber "#1 {}$ $\newcommand {\LWRabsorboption }[1][]{}$ $\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }$ $\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }$ $\def \mathcode #1={\mathchar }$ $\let \delcode \mathcode $ $\let \delimiter \mathchar $ $\def \oe {\unicode {x0153}}$ $\def \OE {\unicode {x0152}}$ $\def \ae {\unicode {x00E6}}$ $\def \AE {\unicode {x00C6}}$ $\def \aa {\unicode {x00E5}}$ $\def \AA {\unicode {x00C5}}$ $\def \o {\unicode {x00F8}}$ $\def \O {\unicode {x00D8}}$ $\def \l {\unicode {x0142}}$ $\def \L {\unicode {x0141}}$ $\def \ss {\unicode {x00DF}}$ $\def \SS {\unicode {x1E9E}}$ $\def \dag {\unicode {x2020}}$ $\def \ddag {\unicode {x2021}}$ $\def \P {\unicode {x00B6}}$ $\def \copyright {\unicode {x00A9}}$ $\def \pounds {\unicode {x00A3}}$ $\let \LWRref \ref $ $\renewcommand {\ref }{\ifstar \LWRref \LWRref }$ $ \newcommand {\multicolumn }[3]{#3}$ $\require {textcomp}$ $\newcommand {\intertext }[1]{\text {#1}\notag \\}$ $\let \Hat \hat $ $\let \Check \check $ $\let \Tilde \tilde $ $\let \Acute \acute $ $\let \Grave \grave $ $\let \Dot \dot $ $\let \Ddot \ddot $ $\let \Breve \breve $ $\let \Bar \bar $ $\let \Vec \vec $ $\renewcommand {\vec }{\boldsymbol }$ $\newcommand {\Edge }{\ensuremath {\,\textemdash \,}}$ $\newcommand \Const [1]{\text {\textsf {#1}}}$ $\DeclareMathOperator {\lerp }{lerp}$ $\DeclareMathOperator {\bitlen }{bitlen}$ $\DeclareMathOperator {\sign }{sign}$ $\newcommand {\I }{\mathrm {i}}$ $\newcommand \AND {\mathbin {\&}}$ $\newcommand \OR {\mathbin {|}}$ $\newcommand \XOR {\mathbin {{}^{\wedge }}}$ $\newcommand \shl {\ll }$ $\newcommand \shr {\ggg }$ $\newcommand \asr {\gg }$ $\newcommand \NOT {\ensuremath {\mathord {\sim }}}$ $\newcommand {\isep }{\mathrel {{.}\,{.}}}$ $\newcommand {\Id }[1]{\mathit {#1}}$ $\newcommand {\const }[1]{\mathsf {#1}}$ $\newcommand {\algorithmname }[1]{\text {\textsc {#1}}}$ $\newcommand {\bits }[1]{\text {#1}}$ $\newcommand {\hexa }[1]{\mathtt {0x#1}}$ $\newcommand {\num }[1]{#1}$ $\newcommand {\qed }{\quad \square }$ $\newcommand {\idiv }[2]{\lfloor #1/#2\rfloor }$ $\newcommand \attribdot {\ensuremath {\mkern 1.5mu.\mkern 1.5mu}}$ $\newcommand \attribxr [2]{#1\attribdot \text {#2}}$ $\newcommand \attribir [2]{\Id {#1}\attribdot \text {#2}}$ $\newcommand \attribii [2]{\Id {#1}\attribdot \Id {#2}}$ $\newcommand \textsc [1]{#1}$ $\require {colortbl}$ $\let \LWRorigcolumncolor \columncolor $ $\renewcommand {\columncolor }[2][named]{\LWRorigcolumncolor [#1]{#2}\LWRabsorbtwooptions }$ $\let \LWRorigrowcolor \rowcolor $ $\renewcommand {\rowcolor }[2][named]{\LWRorigrowcolor [#1]{#2}\LWRabsorbtwooptions }$ $\let \LWRorigcellcolor \cellcolor $ $\renewcommand {\cellcolor }[2][named]{\LWRorigcellcolor [#1]{#2}\LWRabsorbtwooptions }$ $\newcommand {\tcbset }[1]{}$ $\newcommand {\tcbsetforeverylayer }[1]{}$ $\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}$ $\newcommand {\tcboxfit }[2][]{\boxed {#2}}$ $\newcommand {\tcblower }{}$ $\newcommand {\tcbline }{}$ $\newcommand {\tcbtitle }{}$ $\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}$ $\newcommand {\tcboxmath }[2][]{\boxed {#2}}$ $\newcommand {\tcbhighmath }[2][]{\boxed {#2}}$ $\newcommand {\toprule }[1][]{\hline }$ $\let \midrule \toprule $ $\let \bottomrule \toprule $ $\def \LWRbooktabscmidruleparen (#1)#2{}$ $\newcommand {\LWRbooktabscmidrulenoparen }[1]{}$ $\newcommand {\cmidrule }[1][]{\ifnextchar (\LWRbooktabscmidruleparen \LWRbooktabscmidrulenoparen }$ $\newcommand {\morecmidrules }{}$ $\newcommand {\specialrule }[3]{\hline }$ $\newcommand {\addlinespace }[1][]{}$ $\newcommand {\LWRsubmultirow }[2][]{#2}$ $\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }$ $\newcommand {\multirow }[2][]{\LWRmultirow }$ $\newcommand {\mrowcell }{}$ $\newcommand {\mcolrowcell }{}$ $\newcommand {\STneed }[1]{}$ $\newcommand {\LWRldelimtwo }[1][]{\text {#1}~\LWRbigdelim }$ $\newcommand {\LWRldelimone }[2][]{\LWRldelimtwo }$ $\def \ldelim #1#2{\def \LWRbigdelim {#1}\LWRldelimone }$ $\newcommand {\LWRrdelimtwo }[1][]{\LWRbigdelim ~\text {#1}}$ $\newcommand {\LWRrdelimone }[2][]{\LWRrdelimtwo }$ $\def \rdelim #1#2{\def \LWRbigdelim {#1}\LWRrdelimone }$ $\let \symnormal \mathit $ $\let \symliteral \mathrm $ $\let \symbb \mathbb $ $\let \symbbit \mathbb $ $\let \symcal \mathcal $ $\let \symscr \mathscr $ $\let \symfrak \mathfrak $ $\let \symsfup \mathsf $ $\let \symsfit \mathit $ $\let \symbfsf \mathbf $ $\let \symbfup \mathbf $ $\newcommand {\symbfit }[1]{\boldsymbol {#1}}$ $\let \symbfcal \mathcal $ $\let \symbfscr \mathscr $ $\let \symbffrak \mathfrak $ $\let \symbfsfup \mathbf $ $\newcommand {\symbfsfit }[1]{\boldsymbol {#1}}$ $\let \symup \mathrm $ $\let \symbf \mathbf $ $\let \symit \mathit $ $\let \symsf \symsfit $ $\let \symtt \mathtt $ $\let \symbffrac \mathbffrac $ $\newcommand {\mathfence }[1]{\mathord {#1}}$ $\newcommand {\mathover }[1]{#1}$ $\newcommand {\mathunder }[1]{#1}$ $\newcommand {\mathaccent }[1]{#1}$ $\newcommand {\mathbotaccent }[1]{#1}$ $\newcommand {\mathalpha }[1]{\mathord {#1}}$ $\def\Alpha{\unicode{x1D6E2}}$ $\def\Beta{\unicode{x1D6E3}}$ $\def\Gamma{\unicode{x1D6E4}}$ $\def\Digamma{\mathit{\unicode{x03DC}}}$ $\def\Delta{\unicode{x1D6E5}}$ $\def\Epsilon{\unicode{x1D6E6}}$ $\def\Zeta{\unicode{x1D6E7}}$ $\def\Eta{\unicode{x1D6E8}}$ $\def\Theta{\unicode{x1D6E9}}$ $\def\Vartheta{\unicode{x1D6F3}}$ $\def\Iota{\unicode{x1D6EA}}$ $\def\Kappa{\unicode{x1D6EB}}$ $\def\Lambda{\unicode{x1D6EC}}$ $\def\Mu{\unicode{x1D6ED}}$ $\def\Nu{\unicode{x1D6EE}}$ $\def\Xi{\unicode{x1D6EF}}$ $\def\Omicron{\unicode{x1D6F0}}$ $\def\Pi{\unicode{x1D6F1}}$ $\def\Rho{\unicode{x1D6F2}}$ $\def\Sigma{\unicode{x1D6F4}}$ $\def\Tau{\unicode{x1D6F5}}$ $\def\Upsilon{\unicode{x1D6F6}}$ $\def\Phi{\unicode{x1D6F7}}$ $\def\Chi{\unicode{x1D6F8}}$ $\def\Psi{\unicode{x1D6F9}}$ $\def\Omega{\unicode{x1D6FA}}$ $\def\alpha{\unicode{x1D6FC}}$ $\def\beta{\unicode{x1D6FD}}$ $\def\varbeta{\unicode{x03D0}}$ $\def\gamma{\unicode{x1D6FE}}$ $\def\digamma{\mathit{\unicode{x03DD}}}$ $\def\delta{\unicode{x1D6FF}}$ $\def\epsilon{\unicode{x1D716}}$ $\def\varepsilon{\unicode{x1D700}}$ $\def\zeta{\unicode{x1D701}}$ $\def\eta{\unicode{x1D702}}$ $\def\theta{\unicode{x1D703}}$ $\def\vartheta{\unicode{x1D717}}$ $\def\iota{\unicode{x1D704}}$ $\def\kappa{\unicode{x1D705}}$ $\def\varkappa{\unicode{x1D718}}$ $\def\lambda{\unicode{x1D706}}$ $\def\mu{\unicode{x1D707}}$ $\def\nu{\unicode{x1D708}}$ $\def\xi{\unicode{x1D709}}$ $\def\omicron{\unicode{x1D70A}}$ $\def\pi{\unicode{x1D70B}}$ $\def\varpi{\unicode{x1D71B}}$ $\def\rho{\unicode{x1D70C}}$ $\def\varrho{\unicode{x1D71A}}$ $\def\sigma{\unicode{x1D70E}}$ $\def\varsigma{\unicode{x1D70D}}$ $\def\tau{\unicode{x1D70F}}$ $\def\upsilon{\unicode{x1D710}}$ $\def\phi{\unicode{x1D719}}$ $\def\varphi{\unicode{x1D711}}$ $\def\chi{\unicode{x1D712}}$ $\def\psi{\unicode{x1D713}}$ $\def\omega{\unicode{x1D714}}$ $\def\upAlpha{\unicode{x0391}}$ $\def\upBeta{\unicode{x0392}}$ $\def\upGamma{\unicode{x0393}}$ $\def\upDigamma{\unicode{x03DC}}$ $\def\upDelta{\unicode{x0394}}$ $\def\upEpsilon{\unicode{x0395}}$ $\def\upZeta{\unicode{x0396}}$ $\def\upEta{\unicode{x0397}}$ $\def\upTheta{\unicode{x0398}}$ $\def\upVartheta{\unicode{x03F4}}$ $\def\upIota{\unicode{x0399}}$ $\def\upKappa{\unicode{x039A}}$ $\def\upLambda{\unicode{x039B}}$ $\def\upMu{\unicode{x039C}}$ $\def\upNu{\unicode{x039D}}$ $\def\upXi{\unicode{x039E}}$ $\def\upOmicron{\unicode{x039F}}$ $\def\upPi{\unicode{x03A0}}$ $\def\upVarpi{\unicode{x03D6}}$ $\def\upRho{\unicode{x03A1}}$ $\def\upSigma{\unicode{x03A3}}$ $\def\upTau{\unicode{x03A4}}$ $\def\upUpsilon{\unicode{x03A5}}$ $\def\upPhi{\unicode{x03A6}}$ $\def\upChi{\unicode{x03A7}}$ $\def\upPsi{\unicode{x03A8}}$ $\def\upOmega{\unicode{x03A9}}$ $\def\itAlpha{\unicode{x1D6E2}}$ $\def\itBeta{\unicode{x1D6E3}}$ $\def\itGamma{\unicode{x1D6E4}}$ $\def\itDigamma{\mathit{\unicode{x03DC}}}$ $\def\itDelta{\unicode{x1D6E5}}$ $\def\itEpsilon{\unicode{x1D6E6}}$ $\def\itZeta{\unicode{x1D6E7}}$ $\def\itEta{\unicode{x1D6E8}}$ $\def\itTheta{\unicode{x1D6E9}}$ $\def\itVartheta{\unicode{x1D6F3}}$ $\def\itIota{\unicode{x1D6EA}}$ $\def\itKappa{\unicode{x1D6EB}}$ $\def\itLambda{\unicode{x1D6EC}}$ $\def\itMu{\unicode{x1D6ED}}$ $\def\itNu{\unicode{x1D6EE}}$ $\def\itXi{\unicode{x1D6EF}}$ $\def\itOmicron{\unicode{x1D6F0}}$ $\def\itPi{\unicode{x1D6F1}}$ $\def\itRho{\unicode{x1D6F2}}$ $\def\itSigma{\unicode{x1D6F4}}$ $\def\itTau{\unicode{x1D6F5}}$ $\def\itUpsilon{\unicode{x1D6F6}}$ $\def\itPhi{\unicode{x1D6F7}}$ $\def\itChi{\unicode{x1D6F8}}$ $\def\itPsi{\unicode{x1D6F9}}$ $\def\itOmega{\unicode{x1D6FA}}$ $\def\upalpha{\unicode{x03B1}}$ $\def\upbeta{\unicode{x03B2}}$ $\def\upvarbeta{\unicode{x03D0}}$ $\def\upgamma{\unicode{x03B3}}$ $\def\updigamma{\unicode{x03DD}}$ $\def\updelta{\unicode{x03B4}}$ $\def\upepsilon{\unicode{x03F5}}$ $\def\upvarepsilon{\unicode{x03B5}}$ $\def\upzeta{\unicode{x03B6}}$ $\def\upeta{\unicode{x03B7}}$ $\def\uptheta{\unicode{x03B8}}$ $\def\upvartheta{\unicode{x03D1}}$ $\def\upiota{\unicode{x03B9}}$ $\def\upkappa{\unicode{x03BA}}$ $\def\upvarkappa{\unicode{x03F0}}$ $\def\uplambda{\unicode{x03BB}}$ $\def\upmu{\unicode{x03BC}}$ $\def\upnu{\unicode{x03BD}}$ $\def\upxi{\unicode{x03BE}}$ $\def\upomicron{\unicode{x03BF}}$ $\def\uppi{\unicode{x03C0}}$ $\def\upvarpi{\unicode{x03D6}}$ $\def\uprho{\unicode{x03C1}}$ $\def\upvarrho{\unicode{x03F1}}$ $\def\upsigma{\unicode{x03C3}}$ $\def\upvarsigma{\unicode{x03C2}}$ $\def\uptau{\unicode{x03C4}}$ $\def\upupsilon{\unicode{x03C5}}$ $\def\upphi{\unicode{x03D5}}$ $\def\upvarphi{\unicode{x03C6}}$ $\def\upchi{\unicode{x03C7}}$ $\def\uppsi{\unicode{x03C8}}$ $\def\upomega{\unicode{x03C9}}$ $\def\italpha{\unicode{x1D6FC}}$ $\def\itbeta{\unicode{x1D6FD}}$ $\def\itvarbeta{\unicode{x03D0}}$ $\def\itgamma{\unicode{x1D6FE}}$ $\def\itdigamma{\mathit{\unicode{x03DD}}}$ $\def\itdelta{\unicode{x1D6FF}}$ $\def\itepsilon{\unicode{x1D716}}$ $\def\itvarepsilon{\unicode{x1D700}}$ $\def\itzeta{\unicode{x1D701}}$ $\def\iteta{\unicode{x1D702}}$ $\def\ittheta{\unicode{x1D703}}$ $\def\itvartheta{\unicode{x1D717}}$ $\def\itiota{\unicode{x1D704}}$ $\def\itkappa{\unicode{x1D705}}$ $\def\itvarkappa{\unicode{x1D718}}$ $\def\itlambda{\unicode{x1D706}}$ $\def\itmu{\unicode{x1D707}}$ $\def\itnu{\unicode{x1D708}}$ $\def\itxi{\unicode{x1D709}}$ $\def\itomicron{\unicode{x1D70A}}$ $\def\itpi{\unicode{x1D70B}}$ $\def\itvarpi{\unicode{x1D71B}}$ $\def\itrho{\unicode{x1D70C}}$ $\def\itvarrho{\unicode{x1D71A}}$ $\def\itsigma{\unicode{x1D70E}}$ $\def\itvarsigma{\unicode{x1D70D}}$ $\def\ittau{\unicode{x1D70F}}$ $\def\itupsilon{\unicode{x1D710}}$ $\def\itphi{\unicode{x1D719}}$ $\def\itvarphi{\unicode{x1D711}}$ $\def\itchi{\unicode{x1D712}}$ $\def\itpsi{\unicode{x1D713}}$ $\def\itomega{\unicode{x1D714}}$ $\let \lparen ($ $\let \rparen )$ $\newcommand {\cuberoot }[1]{\,{}^3\!\!\sqrt {#1}}\,$ $\newcommand {\fourthroot }[1]{\,{}^4\!\!\sqrt {#1}}\,$ $\newcommand {\longdivision }[1]{\mathord {\unicode {x027CC}#1}}$ $\newcommand {\mathcomma }{,}$ $\newcommand {\mathcolon }{:}$ $\newcommand {\mathsemicolon }{;}$ $\newcommand {\overbracket }[1]{\mathinner {\overline {\ulcorner {#1}\urcorner }}}$ $\newcommand {\underbracket }[1]{\mathinner {\underline {\llcorner {#1}\lrcorner }}}$ $\newcommand {\overbar }[1]{\mathord {#1\unicode {x00305}}}$ $\newcommand {\ovhook }[1]{\mathord {#1\unicode {x00309}}}$ $\newcommand {\ocirc }[1]{\mathord {#1\unicode {x0030A}}}$ $\newcommand {\candra }[1]{\mathord {#1\unicode {x00310}}}$ $\newcommand {\oturnedcomma }[1]{\mathord {#1\unicode {x00312}}}$ $\newcommand {\ocommatopright }[1]{\mathord {#1\unicode {x00315}}}$ $\newcommand {\droang }[1]{\mathord {#1\unicode {x0031A}}}$ $\newcommand {\leftharpoonaccent }[1]{\mathord {#1\unicode {x020D0}}}$ $\newcommand {\rightharpoonaccent }[1]{\mathord {#1\unicode {x020D1}}}$ $\newcommand {\vertoverlay }[1]{\mathord {#1\unicode {x020D2}}}$ $\newcommand {\leftarrowaccent }[1]{\mathord {#1\unicode {x020D0}}}$ $\newcommand {\annuity }[1]{\mathord {#1\unicode {x020E7}}}$ $\newcommand {\widebridgeabove }[1]{\mathord {#1\unicode {x020E9}}}$ $\newcommand {\asteraccent }[1]{\mathord {#1\unicode {x020F0}}}$ $\newcommand {\threeunderdot }[1]{\mathord {#1\unicode {x020E8}}}$ $\newcommand {\Bbbsum }{\mathop {\unicode {x2140}}\limits }$ $\newcommand {\oiint }{\mathop {\unicode {x222F}}\limits }$ $\newcommand {\oiiint }{\mathop {\unicode {x2230}}\limits }$ $\newcommand {\intclockwise }{\mathop {\unicode {x2231}}\limits }$ $\newcommand {\ointclockwise }{\mathop {\unicode {x2232}}\limits }$ $\newcommand {\ointctrclockwise }{\mathop {\unicode {x2233}}\limits }$ $\newcommand {\varointclockwise }{\mathop {\unicode {x2232}}\limits }$ $\newcommand {\leftouterjoin }{\mathop {\unicode {x27D5}}\limits }$ $\newcommand {\rightouterjoin }{\mathop {\unicode {x27D6}}\limits }$ $\newcommand {\fullouterjoin }{\mathop {\unicode {x27D7}}\limits }$ $\newcommand {\bigbot }{\mathop {\unicode {x27D8}}\limits }$ $\newcommand {\bigtop }{\mathop {\unicode {x27D9}}\limits }$ $\newcommand {\xsol }{\mathop {\unicode {x29F8}}\limits }$ $\newcommand {\xbsol }{\mathop {\unicode {x29F9}}\limits }$ $\newcommand {\bigcupdot }{\mathop {\unicode {x2A03}}\limits }$ $\newcommand {\bigsqcap }{\mathop {\unicode {x2A05}}\limits }$ $\newcommand {\conjquant }{\mathop {\unicode {x2A07}}\limits }$ $\newcommand {\disjquant }{\mathop {\unicode {x2A08}}\limits }$ $\newcommand {\bigtimes }{\mathop {\unicode {x2A09}}\limits }$ $\newcommand {\modtwosum }{\mathop {\unicode {x2A0A}}\limits }$ $\newcommand {\sumint }{\mathop {\unicode {x2A0B}}\limits }$ $\newcommand {\intbar }{\mathop {\unicode {x2A0D}}\limits }$ $\newcommand {\intBar }{\mathop {\unicode {x2A0E}}\limits }$ $\newcommand {\fint }{\mathop {\unicode {x2A0F}}\limits }$ $\newcommand {\cirfnint }{\mathop {\unicode {x2A10}}\limits }$ $\newcommand {\awint }{\mathop {\unicode {x2A11}}\limits }$ $\newcommand {\rppolint }{\mathop {\unicode {x2A12}}\limits }$ $\newcommand {\scpolint }{\mathop {\unicode {x2A13}}\limits }$ $\newcommand {\npolint }{\mathop {\unicode {x2A14}}\limits }$ $\newcommand {\pointint }{\mathop {\unicode {x2A15}}\limits }$ $\newcommand {\sqint }{\mathop {\unicode {x2A16}}\limits }$ $\newcommand {\intlarhk }{\mathop {\unicode {x2A17}}\limits }$ $\newcommand {\intx }{\mathop {\unicode {x2A18}}\limits }$ $\newcommand {\intcap }{\mathop {\unicode {x2A19}}\limits }$ $\newcommand {\intcup }{\mathop {\unicode {x2A1A}}\limits }$ $\newcommand {\upint }{\mathop {\unicode {x2A1B}}\limits }$ $\newcommand {\lowint }{\mathop {\unicode {x2A1C}}\limits }$ $\newcommand {\bigtriangleleft }{\mathop {\unicode {x2A1E}}\limits }$ $\newcommand {\zcmp }{\mathop {\unicode {x2A1F}}\limits }$ $\newcommand {\zpipe }{\mathop {\unicode {x2A20}}\limits }$ $\newcommand {\zproject }{\mathop {\unicode {x2A21}}\limits }$ $\newcommand {\biginterleave }{\mathop {\unicode {x2AFC}}\limits }$ $\newcommand {\bigtalloblong }{\mathop {\unicode {x2AFF}}\limits }$ $\newcommand {\arabicmaj }{\mathop {\unicode {x1EEF0}}\limits }$ $\newcommand {\arabichad }{\mathop {\unicode {x1EEF1}}\limits }$

11.3 Addition and Subtraction¶

We can now turn to the problem of implementing the four basic arithmetic operations addition, subtraction, multiplication, and division. The algorithms for these operations resemble the familiar pen-and-paper methods for decimal arithmetic and mainly differ in the radix being used and in the way digits are stored and handled.

Example 11.2. To compute the sum of two positive decimal numbers, say $x=278$ and $y=124$, we can proceed as follows. Start with the two rightmost digits and compute their sum $8+4=12$. Write down the trailing digit $2$ as the last digit of $x+y$ and remember the leading digit 1 as a carry. This carry is included when adding the next pair of digits, $7$ and $2$, which gives us $7 + 2 + 1=10$; again, write down the trailing digit 0 and set the carry to 1. Continue in this way until all digits have been added:

.

2 7 8 $x$

$+$ 1 2 4 $y$

$+$ 0 1 1 0 carry term

0 4 0 2 $x+y$

The final value of the carry term is written down as the most significant digit of the result.

.
		2	7	8	\(x\)
\(+\)		1	2	4	\(y\)
\(+\)	0	1	1	0	carry term
	0	4	0	2	\(x+y\)

Even though the algorithm is traditionally taught using decimal numbers, it works almost identically in other number systems. Assume the numbers to be added are $x=(x_{n-1} x_{n-2}\dots x_0)_B$ and $y=(y_{n-1} y_{n-2}\dots y_0)_B$ to some base $B$ and that both numbers have the same number of digits. (If one number has more digits, we simply extend the shorter one with additional zeros.) To find the least significant digit of the sum $x+y$, we first add the corresponding digits $t=x_0+y_0$. As with decimal numbers, we write down the lower digit $t \bmod B$ as the next digit and remember the upper digit $\lfloor t / B\rfloor $ as a carry $c$, which is carried over to the next digit. The remaining digits are handled in the same way, except that the carry is included in the sum of digits $x_k+y_k+c$. A formal description of this method is shown in Algorithm 11.1. The sum of two $n$-digit numbers satisfies $x+y<2B^n\le B^{n+1}$, so the result of the addition algorithm always fits into $n+1$ digits.

Algorithm 11.1

Compute the sum $x+y$ of two base-$B$ numbers $x=(x_{n-1}\ldots x_0)_B$ and $y=(y_{n-1}\ldots y_0)_B$.

(image)

The plus() method in Listing 11.9 implements this algorithm for BigNats. We first allocate a new array for the digits of the result; its size is determined by the larger of the two numbers being added. We then compute each digit of the result, starting with the least significant digit. First, we compute $r_k$ by adding pairs of digits and the carry and then store the remainder $r_k\bmod B$ as the next digit in result[] and the quotient $\lfloor r_k/B\rfloor $ as the carry for the next iteration. Since $B=2^{31}$ is a power of 2, we can compute the quotient and the remainder using bit operations.

Listing 11.9ch11 / BigNat

// Add two big integers.
public BigNat plus(BigNat y) {
    int[] result = new int[Math.max(size, y.size) + 1];
    int carry = 0;
    for (int i = 0; i < result.length; i++) {
        int tmp = digitOr0(i) + y.digitOr0(i) + carry;  // can overflow
        result[i] = tmp & (int) DIGIT_MASK;
        carry = tmp >>> DIGIT_BITS;
    }
    return new BigNat(result);
}

•BigNat: BigNat(), DIGIT_BITS, DIGIT_MASK, digitOr0()

Alert readers may be wondering whether it is safe to define tmp as an int in Listing 11.9, considering that the sum of two digits and the carry can be as large as

\begin{equation*} (2^{31}-1) + (2^{31}-1) + 1 = 2^{32} - 1, \end{equation*}

which does not fit into a signed 32-bit integer. This is a valid concern, and in programming languages that handle integer overflow more strictly, it may be necessary to perform the computation using 64-bit arithmetic. In Java, however, everything works out correctly since arithmetic operations are guaranteed to return the 32 lowest bits of the correct result — and 32 bits is all we need in this case, even if barely. Since we treat tmp as an unsigned quantity, we have to use an unsigned shift ‘>>>’ to compute carry.

What happens if we use ordinary arithmetic operations instead of bit operations to compute the remainder and the carry in Listing 11.9? In this case, we run into problems if the computation of tmp overflows:

int tmp = digitOr0(i) + y.digitOr0(i) + carry;  // can overflow
result[i] = tmp % base;  // WRONG if tmp overflows
carry = tmp / base;  // WRONG  if tmp overflows

In the case of an overflow, the division and remainder operators interpret tmp as a negative number and therefore produce negative results. In Java, the correct solution is to perform the computations using 64-bit integers:

long tmp = digitOr0(i) + y.digitOr0(i) + carry;
result[i] = (int)(tmp % base);
carry = (int)(tmp / base);

Subtraction

A similar method is used to subtract two unsigned numbers. Again, the digits of the result are computed one by one, by subtracting individual digits. Similar to the way the addition algorithm uses a carry term if the sum of two digits is too large, the subtraction algorithm uses a borrow term if the difference of two digits is too small: If the difference $x_k-y_k$ of two digits is negative, we borrow one unit from the next digit and instead compute $(B+x_k)-y_k$ for this digit and $x_{k+1}-y_{k+1}-1$ for the next digit.

Example 11.3. Let’s compute the difference of $x=228$ and $y=174$. We write the two numbers with their digits aligned below each other and add a third row for the borrow terms:

.

2 2 8 $x$

$-$ 1 7 4 $y$

$-$ 1 0 0 borrow term

0 5 4 $x-y$

The rightmost digit of the result is obtained by subtracting the rightmost digits of $x$ and $y$, which gives us $8-4=4$. The result of subtracting the next two digits is $2-7=-5$, which is negative. In this case, we obtain the correct result by adding 10. This is analogous to “borrowing” one unit from the next digit of $x$ and computing $12-7$ instead of $2-7$; to compensate, we set the borrow term for the next digit to 1. The final digit of $x-y$ is obtained by subtracting the final digit of $y$ and the borrow term from the final digit of $x$, which gives us $2-1-1=0$.

.
	2	2	8	\(x\)
\(-\)	1	7	4	\(y\)
\(-\)	1	0	0	borrow term
	0	5	4	\(x-y\)

Generalizing this procedure from decimal numbers to an arbitrary base $B$ is again straightforward. Given two nonnegative base-$B$ digits $x$ and $y$ with $x\ge y$, the digits of $x-y$ are

\begin{equation} r_k = (x_k - y_k + b_{k-1}) \bmod B. \end{equation}

The borrow term $b_k$ is $-1$ if there was an underflow while computing the previous digit and 0 otherwise. We have $b_0=0$ at the beginning since there is no borrow term for the least significant digit. For every other digit, the borrow is defined recursively as

\begin{equation*} b_{k} = \begin{cases} -1 & \text {if $x_k - y_k + b_{k-1} < 0$}\\ 0 & \text {otherwise} \end {cases} \end{equation*}

This can also be written more simply as

\begin{equation*} b_{k} = \bigl \lfloor (x_k - y_k + b_{k-1}) / B\bigr \rfloor \end{equation*}

since the smallest possible value of $x_k - y_k + b_{k-1}$ is $-B$ (see Exercise 11.3.) This algorithm for subtracting base-$B$ integers is summarized in Algorithm 11.2.

Algorithm 11.2

Compute the difference $x-y$ of two base-$B$ numbers $x=(x_{n-1}\ldots x_0)_B$ and $y=(y_{n-1}\ldots y_0)_B$. The algorithm assumes that $x\ge y$.

(image)

Box 11.2: Complementation In our discussion of the Subtract algorithm we assumed that $x\ge y$: in this case, the result of the subtraction is non-negative and the final value of the borrow term is 0. But what happens if $x<y$? In this case, subtraction produces a somewhat unexpected result. For example, if we try to subtract $65$ from $23$, we obtain the following:

.
		2	3	$x$
$-$		6	5	$y$
$-$	1	1	0	borrow term
		5	8	$x-y$

The output is $58$ instead of the correct result $23-65=-42$, and the only indication that the subtraction underflowed is that the borrow term is 1 at the end of the algorithm.

The incorrect result $58$ isn’t an arbitrary number but is related to the correct result $-42$ by the simple equation $100-42=58$. This is a special case of a more general result: Whenever we subtract a large $y$ from a smaller number $x$, Subtract produces a nonzero borrow term and the digits of the number $B^n-|d|$, where $B$ is the base of the number system, $d=x-y$ the correct result, and $n$ is the number of digits computed. The number $B^n-x$ is also known as the complement of $x$ in base-$B$. We can recover the magnitude of the correct result by complementing a second time, which yields $B^n-(B^n-|d|)=|d|$.

We already met a special case of complementation in Section 5.2, where we used the two’s-complement $2^w-x$ to represent negative integers using $w$ binary digits. We now see why this representation is convenient: If we negate a positive binary number $x$ by computing $0-x$ using Subtract, the result is the two’s-complement representation of $x$. In other words, this is the only representation that is consistent with the standard bitwise subtraction algorithm.

Listing 11.10 shows the implementation of Subtract for big integers. One important difference compared to the implementation of plus() is that $t=x_k - y_k + b$ can now be negative. As we explained in Section 5.3, the remainder $t \bmod 2^{31}$ can still be computed using the bitwise AND operator in this case, but to compute the borrow term $\lfloor t / 2^{31}\rfloor $, we now have to use the arithmetic shift operator ‘>>’. After computing all digits, the method checks whether the final value of the borrow term is nonzero. If it is, the result of the subtraction is not a nonnegative number and cannot be represented as a BigNat; the function throws an exception instead. We will return to the problem of computing with signed integers in Section 11.8.

Listing 11.10ch11 / BigNat

// Subtract two big integers.
public BigNat minus(BigNat y) {
    if (y.size > size)
        throw new ArithmeticException("Underflow");
    int[] result = new int[size];
    int borrow = 0;
    for (int i = 0; i < result.length; i++) {
        int tmp = digit(i) - y.digitOr0(i) + borrow;
        result[i] = tmp & (int) DIGIT_MASK;
        borrow = tmp >> DIGIT_BITS;
    }
    if (borrow != 0)
        throw new ArithmeticException("Underflow");
    return new BigNat(result);
}

•BigNat: BigNat(), digit(), DIGIT_BITS, DIGIT_MASK, digitOr0()

Exercises

Exercise 11.2. Use induction to show that the carry term $c$ in algorithm Add is always 0 or 1, regardless of the base $B$.

Exercise 11.3. Use induction to show that the borrow term $b$ in algorithm Subtract is always 0 or $-1$, regardless of the base $B$.