2
\$\begingroup\$

I have the following code I am working on, but I think it can be optimised further probably by improving the min/max variable selection, (see below).

The idea is to not use actual division, ('/'), to get the quotient and remainder.

I think there could be a way to improve performance by further minimising the number of loops.

NB The idea is not to have a function faster than Num/Den but rather to have the function running as efficiently as possible.

void DivisionDivideAndConquer(const unsigned int Num, const unsigned int Den, unsigned int& Quo, unsigned int& Rem)
{
  //  short cuts
  if (Num < Den)
  {
    Quo = 0;
    Rem = Den;
    return;
  }

  // R = N - D * Q where 0 <= R < |D|

  // getting us started
  unsigned int min = 0;
  unsigned int max = Num;

  for (;;)
  {
    unsigned int number = static_cast<unsigned int>((min + max) * 0.5);
    int possibleRemainder = (Num - (Den * number));

    // if too small then we have a new max
    if (possibleRemainder < 0) {
      if (number == max) {
        max = max - 1;
      }
      else {
        max = number;
      }
    }
    // too big we have a new min
    else if(possibleRemainder >= static_cast<int>(Den) )
    {
      if (number == max) {
        min = min + 1;
      }
      else {
        min = number;
      }
    }
    else
    {
      //  got it!
      Quo = number;
      Rem = static_cast<unsigned int>(possibleRemainder);
      break;
    }
  }
}

int main(int argc, char** argv)
{
  unsigned int Quo = 0;
  unsigned int Rem = 0;
  DivisionDivideAndConquer(12, 4, Quo, Rem); // Q=3, R=0

  // ...

  DivisionDivideAndConquer(12, 9, Quo, Rem); // Q=1, R=3

}
\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview.SE ! I guess the point of your code is just an exercice and you are aware that this will not get any faster that the out of the box implementation. Out of curiosity, what are the operations you are allowing ? I see you are multiplying by "0.5" which is nothing but a division by 2 . \$\endgroup\$ – SylvainD Jan 16 '16 at 12:55
  • \$\begingroup\$ Thanks @Josay. You are right it is more of a personal exercise than anything else, I read that the divide and conquer method is fast for big numbers, I just wanted to see it in action and understand it myself. The method I have is slow, regardless if it is a big number or not, so I am curious where my function is falling short. As a test, I saw that even long division is faster :) \$\endgroup\$ – Simon Goodman Jan 16 '16 at 13:00
  • 2
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Jan 16 '16 at 14:47
  • 1
    \$\begingroup\$ Sorry about that SimonForsberg, I updated it because the 2 issues picked up by @Josay were not really related to the question itself and I thought they might distract from possible answers. \$\endgroup\$ – Simon Goodman Jan 16 '16 at 15:07
  • 1
    \$\begingroup\$ The whole premise of this site is that no code is perfect… and there is no shame in that. \$\endgroup\$ – 200_success Jan 17 '16 at 19:22
1
\$\begingroup\$

Before optimising your code, it is probably a good idea to write a few tests to ensure you don't break anything as you go. There is something quite good in your situation : your code is supposedly easy to test as you know the mathematical properties that your result should have : a = b * q + r with 0 <= r < b.

Writing something like :

std::cout << "j" << "*" << "q" << "+" << "r" << " = " << "t" << " (" << "i" << ")" << std::endl;
for (uint i = 2; i < 10; i++)
    for (uint j = 2; j < 10; j++)
    {
        uint q = 0;
        uint r = 0;
        DivisionDivideAndConquer(i, j, q, r);
        uint total = j * q + r;
        if (total != i)
                std::cout << j << "*" << q << "+" << r << " = " << total << " (" << i << ")" << std::endl;
    }

shows that there is something wrong in your result which is the first problem (Hint: the problem is in the shortcut). Trying to perform tests with j starting from 1 shows that there is another issue (Hint: a loop does not finish).

Actual optimisation

Think about the cases you are trying to handle or how you are trying to reduce the search range.

With the following code, you compute less in each iteration while making the search range smaller :

    // if too small then we have a new max
    if (possibleremainder < 0) {
        max = number - 1;
    }
    // too big we have a new min
    else if(possibleremainder >= static_cast<int>(den) )
    {
        min = number + 1;
    }
    else
    {
        //  got it!
        quo = number;
        rem = static_cast<uint>(possibleremainder);
        break;
    }
\$\endgroup\$
  • \$\begingroup\$ Thanks for the code, I have updated/fixed the function, but that does not really improve the speed of the function itself. \$\endgroup\$ – Simon Goodman Jan 16 '16 at 14:26
  • \$\begingroup\$ Thanks for adding the code, I am not allowed to do edits as you are. The optimisation(s) you gave might work in cases where a +1/-1 is closer to the solution. In some cases my code is faster where * .5 brings it closer. It's a bit of hit and miss. \$\endgroup\$ – Simon Goodman Jan 18 '16 at 4:13
  • \$\begingroup\$ If you are refering to the (number == max), this is never useful as the condition can only be true in the case where we've found the number (I'd be interested in an example if I am wrong). As for the other (using 'number +/- 1' instead of 'number'), it helps reducing the search space. My assumption was that it'd make things better and I'm glad/surprised to learn that I was wrong. I guess that because all elements of the search space are not equiprobable, things are a bit skewed here (unlike in a binary search in a list for instance). \$\endgroup\$ – SylvainD Jan 18 '16 at 9:56
0
\$\begingroup\$

This function equals to your previous code with some simplification. Never be so aware of performance.

void DivisionDivideAndConquer(const unsigned int Num, const unsigned int Den, unsigned int& Quo, unsigned int& Rem)
{
    //  short cuts
    if (Num < Den)
    {
        Quo = 0;
        Rem = Den;
    }
    else
    {
        unsigned int min = 0;
        unsigned int max = Num;

        while (true)
        {
            unsigned int number = static_cast<unsigned int>((min + max) * 0.5);
            int possibleRemainder = (Num - (Den * number));

            // if too small then we have a new max
            if (possibleRemainder < 0) {
                (number == max ? max-- : max = number);
            }
            // too big we have a new min
            else if (possibleRemainder >= static_cast<int>(Den))
            {
                (number == max ? min++ : min = number);
            }
            else
            {
                //  got it!
                Quo = number;
                Rem = static_cast<unsigned int>(possibleRemainder);
            }
        }
    }
}

We can see:

  • I used ternaries operators.
  • I used a simple while (true) which IMHO is more readable than a for (;;) but the equivalent.

If you want to "improve" greatly or less your performance, you should change the cast static_cast function is the part of your code which affects more to the performance, but you are casting properly.

\$\endgroup\$
  • \$\begingroup\$ Thanks, why did you replace the original if( ... ) { return } with an if (...){ ... } else { ... } NB: There was one or errors in my original function, (unrelated to performance/optimisation), but an other author reverted those changes. So the function you have has some errors. I have re-added the changes as another function. \$\endgroup\$ – Simon Goodman Jan 17 '16 at 4:53
0
\$\begingroup\$
typedef unsigned int uint;

void divideAndConquer(const uint num, const uint den, uint& quo, uint& rem)
{
    if (num < den)
    {
        quo = 0;
        rem = num;
        return;
    }
    if(num == den)
    {
        quo = 1;
        rem = 0;
        return;
    }
    uint min = 0,
         max = num;
    while (1) {
        uint number = (max + min) >> 1;
        int  posRem = num - den * number;
        if(posRem < 0)
            max = number - 1;
        else if(uint(posRem) >= den)
            min = number + 1;
        else {
            quo = number;
            rem = uint(posRem);
            break;
        }
    } // End of while loop!
} // End of divideAndConquer

Names

I used typedef because I was tired of typing unsig.... (Just me being lazy)

I changed the name of the function because I prefer making class names capitalized and functions more of a descriptive action. Also, I felt saying division then divide redundant even though they weren't intended to mean the mathematical division:)

Also, made the variable names all lowercase because of the same reasons pertaining to the classes.

Note, posRem is not a good name... I just liked how it lines up with number:)lol


Dividing By 2

When dividing by two, the fastest way would be to do a bit shift. But, if the values are negative, the bit shift might not work. Since we are using uints we know that we won't get anything funky. (Explained more in the link)


Casting

You won't have any problems doing a normal type cast (unless you start hitting negative numbers) between int and uint. So, what I did was only type cast posRem because I know posRem is positive when I go to cast.


Reduced Logic

I spent a good while reducing the logic that you had and I was so excited and when I broke it down and simplified it (doesn't do the exact same thing but usually does better). Then I realized that @Josay (+1) came up with the same thing way before me...


Steps

I started looking at how many steps it took to do the divide and conquer and noticed something funny. Your code works great when the numbers divide evenly. Usually finishing in about one to three steps! And some do really good even when they don't, for example 100/7 it would take about seven steps. With the updated logic it comes out to five. But, 100/31 takes your logic five and the new one six. That is really bad on both considering that you could just subtract three times and realize you found the remainder and quotient. So, I brought in the old school way to ensure that the largest amount of steps taken will always be the quotient:

typedef unsigned int uint;

void divideAndConquer(const uint num, const uint den, uint& quo, uint& rem)
{
    if (num < den)
    {
        quo = 0;
        rem = num;
        return;
    }
    if(num == den)
    {
        quo = 1;
        rem = 0;
        return;
    }
    quo = 0;
    rem = num;

    uint min = 0,
         max = num;

    while (rem >= den) {
        uint number = (max + min) >> 1;
        int  posRem = num - den * number;
        if(posRem < 0)
            max = number - 1;
        else if(uint(posRem) >= den)
            min = number + 1;
        else {
            quo = number;
            rem = uint(poRem);
            return;
        }
        // Old school:)
        rem -= den;
        ++quo;
    } // End of while loop!
} // End of divideAndConquer

This still doesn't seem like the least amount of steps to accomplish this, but you know now that the time complexity cannot be larger than the quotient.


Hope this helps some!

\$\endgroup\$
  • 1
    \$\begingroup\$ You may already be aware, but unsigned is exactly the same type as unsigned int. I'm lazy, too! \$\endgroup\$ – Edward Jan 18 '16 at 2:12
  • \$\begingroup\$ Yeah, I know:) I actually copied and pasted what he had lol I tried to reduce the time complexity to something simpler but I honestly was having some troubles with it:/ I just kept thinking "If I modulate this I could get the remainder... Then simplify from there..." But I don't think he wants to use modulus:( \$\endgroup\$ – tkellehe Jan 18 '16 at 2:24
  • \$\begingroup\$ poRem is probably a typo. \$\endgroup\$ – SylvainD Jan 18 '16 at 8:48
  • \$\begingroup\$ Also there is still a problem in your code (in the shortcut you've reused from OP's code). Please refer to my answer for a test suite. \$\endgroup\$ – SylvainD Jan 18 '16 at 9:31
  • 1
    \$\begingroup\$ Finally, your Create Vars Once advise is based on non-verified assumptions. If anything, it makes the code very slightly slower (based on a benchmark I've run) divising all i in [2, 10000[ by all j in [2, 10000[. Please see stackoverflow.com/questions/982963/… for more information. Also, it does not respect three of my favorite maintanability rules : 1) do not repeat yourself 2) declare things in the smallest possible scope 3) do not repeat yourself. \$\endgroup\$ – SylvainD Jan 18 '16 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.