Vyom World.com Let's Touch the Sky Together!
 Home VyomWorld.com Home Free Magazines! VyomLinks.com Home JobsAssist.com Home Vyom Network Contact Us Jobs & Careers Resume Submitter Placement Papers IT Companies Directory Computer Jobs Interview Questions Online Exams Vyom Career eMag. Fun Screensavers New! Send FREE SMS! SMS Jokes Source Codes Library Source Codes Home ASP Source Codes C Source Codes C++ Source Codes COBOL Source Codes Java Source Codes Pascal Source Codes Submit Source Codes GATE GATE an Overview GATE Preparation Study Materal GRE GRE an Overview GRE Questions GRE Preparation GRE Universities TOEFL Preparation TOEFL Resources GMAT Preparation GMAT Resources MBA Preparation MBA Resources Networking Concepts Networking Concepts Testing Preparation Testing Resources Webmasters Free Traffic Builder Webmaster Articles Web Hosting Tutorials Hardware Tutorial 1500 Free eBooks New! FREE Publications
Vyom Career eMag.
 Get 9,000+ Interview Questions & Answers in an eBook. 9,000+ Interview Questions All Questions Answered 5 FREE Bonuses Free Upgrades Get it now!
Get 9,000+ Interview Questions with Answers in an eBook

### Analysis and Design of Algorithms

4.3 Integer multiplication

There are various methods of obtaining the product of two numbers. The repeated addition method is left as an assignment for the reader. The reader is expected to find the product of some bigger numbers using the repeated addition method.

Another way of finding the product is the one we generally use i.e., the left shift method.

4.3.1 left shift method

981*1234

3924

2943*

1962**

981***

1210554

In this method, a=981 is the multiplicand and b=1234 is the multiplier. A is multiplied by every digit of b starting from right to left. On each multiplication the subsequent products are shifted one place left. Finally the products obtained by multiplying a by each digit of b is summed up to obtain the final product.

The above product can also be obtained by a right shift method, which can be illustrated as follows,

4.3.2 right shift method

981*1234

981

1962

*2943

**3924

1210554

In the above method, a is multiplied by each digit of b from leftmost digit to rightmost digit. On every multiplication the product is shifted one place to the right and finally all the products obtained by multiplying ‘a’ by each digit of ‘b’ is added to obtain the final result.

The product of two numbers can also be obtained by dividing ‘a’ and multiplying ‘b’ by 2 repeatedly until a<=1.

4.3.3 halving and doubling method

Let a=981 and b=1234

The steps to be followed are

1. If a is odd store b
2. A=a/2 and b=b*2
3. Repeat step 2 and step 1 till a<=1

 a b result 981 1234 1234 490 2468 ------------ 245 4936 4936 122 9872 --------- 61 19744 19744 30 39488 ------------ 15 78976 78976 7 157952 157952 3 315904 315904 1 631808 631808

Sum=1210554

The above method is called the halving and doubling method.

4.3.4 Speed up algorithm:

In this method we split the number till it is easier to multiply. i.e., we split 0981 into 09 and 81 and 1234 into 12 and 34. 09 is then multiplied by both 12 and 34 but, the products are shifted ‘n’ places left before adding. The number of shifts ‘n’ is decided as follows

 Multiplication sequence shifts 09*12 4 108**** 09*34 2 306** 81*12 2 972** 81*34 0 2754

Sum=1210554

For 0981*1234, multiplication of 34 and 81 takes zero shifts, 34*09 takes 2 shifts, 12 and 81 takes 2 shifts and so on.

Exercise 4

1. Write the algorithm to find the product of two numbers for all the methods explained.
2. Hand simulate the algorithm for atleast 10 different numbers.
3. Implement the same for verification.
4. Write a program to find the maximum and minimum of the list of n element with and without using recursion.

 Discussion Center

Recently Updated: New Placement Papers added.
Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory