Thread: Hodor Can Multiply

  1. #1
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795

    Hodor Can Multiply

    I'm think about adding a test for overflow but not 100% sure.

    Code:
    /*
     * Function to multiply two integers without using the * or / operators.
     * Uses the "Egyptian Method" of multiplication.
     * 
     * By Hodor, 2013
     * 
     */
    #include <stdio.h>
    #include <assert.h>
    
    #define ZMIN(a,b)   ( (a) < (b) ? (a) : (b) )
    #define ZMAX(a,b)   ( (a) > (b) ? (a) : (b) )
    #define ZABS(n)     ( (n) < 0 ? (-n) : (n) )
    
    long multiply(int a, int b);
    
    int main(void)
    {
        int i, j;
        for (i = -6000; i < 6000; i++)
            for (j = -6000; j < 6000; j++)
                assert(multiply(i,j) == i*j);
        
        return 0;
    }
    
    long multiply(int a, int b)
    {
        unsigned short aneg = a < 0, bneg = b < 0;
        unsigned long total = 0;
        unsigned long c = ZMIN(ZABS(a), ZABS(b)), 
                      d = ZMAX(ZABS(a), ZABS(b));
    
        while (c > 0) {
            total += c & 1 ? d : 0;   
            c >>= 1;
            d <<= 1;
        }
        
        return aneg ^ bneg ? -total : total;
    }

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Hodor View Post
    I'm think about adding a test for overflow but not 100% sure.
    Assuming sizeof(long) > sizeof(int), that shouldn't be necessary (since the result of the multiplication two N-bit numbers can never exceed 2N bits). There may be a corner case involving negative numbers, but my brain is too fried to work that out at the moment...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by Sebastiani View Post
    Assuming sizeof(long) > sizeof(int), that shouldn't be necessary (since the result of the multiplication two N-bit numbers can never exceed 2N bits). There may be a corner case involving negative numbers, but my brain is too fried to work that out at the moment...
    That's exactly what I'm unsure about as well. Possibly sleep will help

  4. #4
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Actually, thinking about it I don't think overflow can possibly occur (with the same assumptions you stated).

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Sebastiani View Post
    Assuming sizeof(long) > sizeof(int), that shouldn't be necessary (since the result of the multiplication two N-bit numbers can never exceed 2N bits).
    The catch is that sizeof(long) can be equal to sizeof(int).

    Quote Originally Posted by Sebastiani View Post
    There may be a corner case involving negative numbers, but my brain is too fried to work that out at the moment...
    The "corner case" you need to worry about if abs(INT_MIN) exceeds abs(INT_MAX), and if you are multiplying by one of them. That is practically quite common.

    In terms of the OP, I don't tend to be in favour of using bitshift operations as a shortcut to multiplication or division by two. Yes, I know they are equivalent on unsigned types. But it is clearer to do what you mean (i.e. your code is working to achieve a numeric result, so it is clearer to use numeric operations) and most modern compilers will pick the fastest operation possible (i.e. you are indulging in premature optimisation).

    And using xor (^ operator) to check for inequality is hideous.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by grumpy View Post
    In terms of the OP, I don't tend to be in favour of using bitshift operations as a shortcut to multiplication or division by two. Yes, I know they are equivalent on unsigned types. But it is clearer to do what you mean (i.e. your code is working to achieve a numeric result, so it is clearer to use numeric operations) and most modern compilers will pick the fastest operation possible (i.e. you are indulging in premature optimisation).
    Note that I set myself the restriction not to use * or /. I admit that using the bitshift operators is (probably) a bit of a cheat. It's safe as you say, but anyway. To multiply d by two I can change the code to d += d. That's easy enough. To divide c by 2, though, I'd probably have to do something like

    Code:
            count = 0;
            while (c > 1) { /* Divide c by 2 */
                count++; 
                c -= 2;
            }
            c = count;
    Which I guess has advantages applicable to my original goal, but it's obviously going to be slower. Maybe there's another way to divide something by 2 that I don't know of?


    Quote Originally Posted by grumpy View Post
    And using xor (^ operator) to check for inequality is hideous.
    It's not checking for inequality. Two numbers multiplied together give a negative answer if only ONE (but not both) of the operands are negative; and this is, well, what XOR does.
    Last edited by Hodor; 11-21-2013 at 04:54 AM.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Hodor View Post
    It's not checking for inequality. Two numbers multiplied together give a negative answer if only ONE (but not both) of the operands are negative; and this is, well, what XOR does.
    Either you are bluffing or you don't understand your own code.

    aneg and bneg are unsigned shorts initialised with values 0 or 1 (the result of expressions "a < 0" and "b < 0", respectively). The expression aneg ^ bneg therefore produces the same result as "aneg != bneg".
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  8. #8
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    You're right. Thanks.
    Last edited by Hodor; 11-21-2013 at 08:44 AM.

  9. #9
    Registered User
    Join Date
    Jun 2011
    Posts
    4,508
    It appears you have your "!=" logic backwards in your example

    [edit] Never mind, seems you realized this.

  10. #10
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by Matticus View Post
    It appears you have your "!=" logic backwards in your example

    [edit] Never mind, seems you realized this.
    Yeah, sorry.

  11. #11
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Code updated

    Code:
    /*
     * Function to multiply two integers without using the * or / operators.
     * Uses the "Egyptian Method" of multiplication.
     * 
     * By Hodor, 2013
     * 
     */
    #include <stdio.h>
    #include <assert.h>
    
    #define ZMIN(a,b)   ( (a) < (b) ? (a) : (b) )
    #define ZMAX(a,b)   ( (a) > (b) ? (a) : (b) )
    #define ZABS(n)     ( (n) < 0 ? (-n) : (n) )
    
    long multiply(int a, int b);
    
    int main(void)
    {
        int i, j;
        for (i = -6000; i < 6000; i++)
            for (j = -6000; j < 6000; j++)
                assert(multiply(i,j) == i*j);
        
        return 0;
    }
    
    long multiply(int a, int b)
    {
        unsigned short aneg = a < 0, bneg = b < 0;
        unsigned long total = 0;
        unsigned long c = ZMIN(ZABS(a), ZABS(b)), 
                      d = ZMAX(ZABS(a), ZABS(b));
    
        while (c > 0) {
            total += c & 1 ? d : 0;   
            c >>= 1;
            d <<= 1;
        }
        
        return aneg != bneg ? -total : total;
    }

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    signed 16 bit by 16 bit multiply producing 32 bit product code example, using classic method. (shorts are assumed to be 16 bit, ints are assumed to be 32 bit). Note that casting short to int extends the sign bit. For faster speed, this could be done only once.

    Code:
    #include <stdio.h>
    
    int multiply(short m0, short m1)
    {
    int i, p;
        p = 0;
        for(i = 0; i < 15; i++)
            if(m1 & (1<<i))
                p += (int)m0 << i;
        if(m1 & (1<<i))
            p -= (int)m0 << i;
        return p;
    }
    
    int main(){
    char buffer[80];
    int m0, m1;
        while(1){
            printf("enter numbers in hex: ");
            fgets(buffer, sizeof(buffer), stdin);
            if(2 != sscanf(buffer, "%x %x", &m0, &m1))
                break;
            printf("product is: %x\n", multiply((short) m0, (short) m1));
        }
        return 0;
    }
    Last edited by rcgldr; 11-21-2013 at 08:01 PM.

  13. #13
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by rcgldr View Post
    signed 16 bit by 16 bit multiply producing 32 bit product code example, using classic method. (shorts are assumed to be 16 bit, ints are assumed to be 32 bit). Note that casting short to int extends the sign bit. For faster speed, this could be done only once.
    Nice!

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    There must be super special trick to make p not always equal to zero, but I don't see it.

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    In hardware, the sign extension can be avoided by manipulating the bits. (note, this is still a signed multiply, the unsigned variables are used to avoid sign extension).

    Code:
    #include <stdio.h>
    
    unsigned int multiply(unsigned short m0, unsigned short m1)
    {
    unsigned int i, p;
        p = 0x10000;
        for(i = 0; i < 15; i++)
            p += ((m1 & (1<<i)) ? ((unsigned)m0 ^ 0x8000) : 0x8000)<<i;
        p += ((m1 & (1<<i)) ? ((unsigned)m0 ^ 0x17fff) : 0x17fff)<<i;
        return p;
    }
    
    int main(){
    char buffer[80];
    unsigned int m0, m1;
        while(1){
            printf("enter numbers in hex: ");
            fgets(buffer, sizeof(buffer), stdin);
            if(2 != sscanf(buffer, "%x %x", &m0, &m1))
                break;
            printf("product is: %x\n", multiply((unsigned short) m0, (unsigned short) m1));
        }
        return 0;
    }
    Wiki article:

    Binary multiplier - Wikipedia, the free encyclopedia

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. multiply by 7
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 05-22-2006, 02:19 PM
  2. program won't multiply right
    By Will_rookwood in forum C++ Programming
    Replies: 5
    Last Post: 04-11-2006, 07:28 PM
  3. Multiply it by 10 then Int to Hex
    By Mr. Acclude in forum C Programming
    Replies: 16
    Last Post: 09-23-2004, 08:15 PM
  4. multiply int..
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 04-14-2002, 08:23 AM
  5. how to multiply 2 matrices
    By newguy in forum C Programming
    Replies: 1
    Last Post: 10-29-2001, 03:48 AM