.
 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!


    Post your Resume to 5800+ Companies

    Reliable Web Hosting

  •  
     
     
    Get 9,000+ Interview Questions with Answers in an eBook


     Home

    Analysis and Design of Algorithms


    Advertisements
    Advertisements

    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.

    Study Notes Home | Next Section>>




     

    Discussion Center

    Discuss

    Query

    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    .

    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

    Copyright ©2003-2024 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy