Algorithm help

This is a discussion on Algorithm help within the C++ Programming forums, part of the General Programming Boards category; I have to write a program that multiplies two unsigned ints w/o using the * operator. Simple really, but there ...

  1. #1
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56

    Unhappy Algorithm help

    I have to write a program that multiplies two unsigned ints w/o using the * operator. Simple really, but there is a constraint on the algorthm. Although a simple way to go is

    Code:
    for (int i = 0; i < small_int; i++)
      {
       product = product + large_int;
       }
    I cannot do that. The algorithm must run in time log2(min(x,y). I am slightly confused about how to go about this.

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    One way you could do this is store a mutliplication table in
    a 2d array. Then just use the old grade school multiplication
    method.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I don't have time to calculate it all out right now off the top of my head, but since it must be in log2 time then it would probably be something like keep doubling product floor(log2(min(x,y))) times and then finishing up with a straight loop. Like 8*10 would translate to 10+10+20+40 -- hope this helps.

  4. #4
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56
    Sounds like an original solution, but I doubt that is really what is asked for. I forgot to mention that the program multiplies unsigned integers. It should also simulate a binary multiplication method as well.
    I am Error. When all else fails, use fire.

    My Current Screenshot

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I think this is what it wants take
    x = 10011
    y = 100111
    Since x < y
    Code:
    100111
      10011
    And you just do a normal binary multiplication. If x and
    y are representive of the numbers then this algorithm
    will do about lg(min(x, y)) additions. This
    is since x is represented by about lg x bits.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21