COME ON CODE ON

A blog about programming and more programming.

Multiply two Numbers Without Using * Operator

with 7 comments

Lets have a fun question. Multiply two numbers without using the * operator.
Here’s the code in C/C++:

main(a,b,m)
{
    while (~scanf("%d%d",&a,&b))
    {
          m=0;
          while (a)
          {
                if (a&1)
                   m+=b;
                a>>=1;
                b<<=1;
          }
          printf("%d\n",m);
    }
}

The above code is a implementation of an algorithm better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.
Here’s the algorithm :

  1. Let the two numbers to be multiplied be a and b.
  2. If a is zero then break and print the result.
  3. If a is odd then add b to the result.
  4. Half a, Double b. Goto Step 2.


NJOY!
-fR0DDY

About these ads

Written by fR0DDY

April 8, 2010 at 10:05 AM

Posted in Beautiful Codes

Tagged with , ,

7 Responses

Subscribe to comments with RSS.

  1. nice logic :).I hope that u will come up with some new posts too.

    speed

    April 8, 2010 at 12:53 PM

    • dear i guess this wont work if a is -ve no. so condition to check that must be applied before carrying out multiplication
      here is same code with some modification

      #include
      using namespace std;

      int main()
      {
      int a=5,b=7,c=0,ch=5,flag;
      while(ch)
      { flag=0;
      cout<>a>>b;
      c=0;
      if(a0)
      {
      if(a & 1)
      c=c+b;

      a>>=1;
      b<<=1;

      cout<<"\n loop executed";
      }
      if(flag)
      {c=-c;}
      cout<<"\n *** multi plication of the 2 is : "<>a;
      return 0;
      }

      rahul

      August 22, 2012 at 1:39 PM

      • 2. number multiply by 2 with out using * operator
        #include
        main()
        {
        int num = 5;
        num = num<<1;
        printf("%d",num);
        }
        Op : 10
        Exp : num number left shift by the 1 position we can get.
        1st—————0101
        2nd————–1010

        prawin

        February 12, 2013 at 1:01 PM

  2. Hi gaurav…
    Nice coding :) . I enjoyed working around the codes tried an extended version of the code above.. can you suggest me which of the codes will take less resources…?

    main()
    {
        int a,b;
        int m=0;
        while (~scanf("%d%d",&a,&b))
        {
         m=0;
          while (a)
          {
            if (a&2)
            {
              if (a&1) m+=b+b+b;//remain 3
              else m+=b+b;//remain 2
            }
            else if(a&1)//remain 1
             m+=b;
            a>>=2;
            b<<=2;
            //printf("%d,%d,%d\n",a,b,m); //to see intermediate values               
          }
            printf("(%d)\n",m);                
        }
    }
    

    As you can see that this algorithm can be extented to higher form in (multiple of 8,16,32,64..). which of the algorithm will be best suited for normal calculations??

    Ritesh

    September 27, 2010 at 12:33 AM

  3. [...] this I like Categories: Code LikeBe the first to like this post. Comments (0) Trackbacks (0) Leave a [...]

  4. #include

    main()
    {
    int x=10, y=10, z;
    int mult = 0;

    for ( z = 1 ; z <= x ; z++)
    mult = mult + y;

    printf("The multiplication of two numbers: %ld\n",mult);
    return 0;
    }

    usuf16

    March 8, 2013 at 8:03 PM

    • thanxx for such a easy way…

      neha

      October 13, 2013 at 12:59 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 230 other followers

%d bloggers like this: