Problem 1.8. As in Problem 1.6, suppose you have available a pocket calculator t

Question

Problem 1.8. As in Problem 1.6, suppose you have available a pocket calculator that can multiply a four-figure number by a four-figure number and get the cor- rect eight-figure answer. Devise an algorithm for multiplying two large numbers based on the classic algorithm, but using blocks of four figures at a time instead of just one. (If you like, think of it as doing your calculation in base 10000 arith- metic.) For instance, when multiplying 1234567 by 9876543, you might obtain the arrangement shown in Figure 1.11. 0123 4567 0987 6543 0080 7777 1881 0012 1851 7629 0012 1932 5406 1881 Figure 1.11. Multiplication in base 10000 Here the first line of the calculation is obtained, from right to left, as 4567 × 6543-2988 1881 (that is, a result of 1881 and a carry of 2988), followed by 0123x6543+2988 80777 (that is, a result of 7777 and a carry of 0080). The second line of the calculation is obtained similarly, and the final result is found by adding the columns. All the necessary arithmetic can be done with your calculator. Use your algorithm to multiply 31415975 by 8182818. Check that your answer is the same as the one you found in Problem 1.6

Explanation / Answer

ALGORITHEM FOR MULTIPLICATION OF BIG NUMBER

______________________________________________

take the 2 number and find the length of the larger number suppose the length of the larger number is 'n' and numbers are 'x' and 'y'

create 2 array of size <int>(n/4)+1 and fill the array with 0 initially

now look at the following algo

void fillArray(int[] A,int x)

{

int a= A.length();

int i=0;

while(i<a)

{

A[i]=x%10000;

x=x/10000;

i++;

}

}

the function fills the array according to our requirement i.e continuously from the LSB size fill the array with 4 digit substring

after passing both no into the method fillArray we have 2 arrays A and B both contain 4 digit numbers

the array who is store the multiplication has an array size = <int>(2n/4)+1

now look at the following method

int[] mulOfBigNumber(int[] A,int[] B)

{

int[] c=new int[<int>(2*A.length()/4)+1]; //set c who store the output

int temp;

for(int i=0;i<A.length();i++)

{

for(int j=0;j<B.length();j++)

{

temp=A[i]*B[j];

fillC(c,temp,i+j); //fill c starting from i+j

}

}

}

void fillC(int[] C,int x,int start)

{

int overflow=0;

for(int i=start;i<x/4+1;i++)

{

C[i]=(C[i]+(x%100000)+overflow)%10000; //limit size to 4 disit

overflow=(C[i]+(x%100000))/10000; //check if sum is more or less than 4 disit

}

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.