(^26) | Chapter 2: The Mathematics of Algorithms
In general, howhard is it to add twon-digit numbersan...a 1 +bn...b 1 to result in
acn+1...c 1 digit value? The primitive operations used in this ADDITIONalgorithm
are as follows:
A sample Java implementation of ADDITIONis shown in Example 2-2, where an
n-digit number is represented as an array ofintvalues; for the examples in this
section, it is assumed that each of these values is a decimal digitdsuch that
0 ≤d≤9.
As long as the input problem can be stored in memory,addcomputes the addi-
tion of the two numbers as represented by the input integer arraysn1andn2.
Would this implementation be as efficient as the followinglastalternative, listed
in Example 2-3?
Example 2-2. Java implementation of add
public static void add (int[] n1, int[] n2, int[] sum) {
int position = n1.length-1;
int carry = 0;
while (position >= 0) {
int total = n1[position] + n2[position] + carry;
sum[position+1] = total % 10;
if (total > 9) { carry = 1; } else { carry = 0; }
position--;
}
sum[0] = carry;
}
Example 2-3. Java implementation of last
public static void last(int[] n1, int[] n2, int[] sum) {
int position = n1.length;
int carry = 0;
while (--position >= 0) {
int total = n1[position] + n2[position] + carry;
if (total > 9) {
sum[position+1] = total-10;
carry = 1;
} else {
sum[position+1] = total;
carry = 0;
}
}
sum[0] = carry;
}
ci←()ai+bi+carryi mod10
carryi+ 1
1ifai++bi carryi≥ 10
⎩0 otherwise
⎨
⎧
←
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use