Next: 1.2 Multiplication Algorithm
Up: 1 Multiple Precision Arithmetic
Previous: 1 Multiple Precision Arithmetic
We now write the addition recipe using the usual method

u_{1} 
u_{2} 
^{ ... } 
u_{p} 

v_{1} 
v_{2} 
^{ ... } 
v_{p} 

w_{1} 
w_{2} 
^{ ... } 
w_{p} 
Or more concisely
(
u_{1}^{ ... }u_{p}) + (
v_{1}^{ ... }v_{p}) = (
w_{1}^{ ... }w_{p}) +
M^{p} = (
w_{1}^{ ... }w_{p})
The identities that are satisfied are
(w_{p},) 
= 
(u_{p}, v_{p}, 0) 

(w_{p  i},) 
= 
(u_{p  i}, v_{p  i},) 

We can clearly write these identities quite concisely by defining
= 0. It is thus clear how to calculate this
inductively for all i upto i = p. At the last stage the carry over
is the extra
= in the answer.
A similar technique applies to the subtraction method. We write the
identity
(
u_{1}^{ ... }u_{p})  (
v_{1}^{ ... }v_{p}) = (
w_{1}^{ ... }w_{p}) 
M^{p}
And find the identities
(w_{p},) 
= 
(u_{p}, v_{p}, 0) 

(w_{p  i},) 
= 
(u_{p  i}, v_{p  i},) 

Again, putting
= 0 combines the identities and we can easily
compute these inductively. Note that
= is the ``extra''
borrow element and so if this is nonzero then
(v_{1}^{ ... }v_{p}) is in
fact more than
(u_{1}^{ ... }u_{p}). We will see that this calculation is
useful even in this case.
We note that the number of steps taken by both methods is equal to p.
Next: 1.2 Multiplication Algorithm
Up: 1 Multiple Precision Arithmetic
Previous: 1 Multiple Precision Arithmetic
Kapil Hari Paranjape
20021020