Optimise Division function using divide and conquer, (and multiplication only) 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&amp; Quo, unsigned int&amp; Rem)
{
  //  short cuts
  if (Num &lt; Den)
  {
    Quo = 0;
    Rem = Den;
    return;
  }

  // R = N - D * Q where 0 &lt;= R &lt; |D|

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

  for (;;)
  {
    unsigned int number = static_cast&lt;unsigned int&gt;((min + max) * 0.5);
    int possibleRemainder = (Num - (Den * number));

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

}
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 &lt;= r &lt; b.

Writing something like :

std::cout &lt;&lt; "j" &lt;&lt; "*" &lt;&lt; "q" &lt;&lt; "+" &lt;&lt; "r" &lt;&lt; " = " &lt;&lt; "t" &lt;&lt; " (" &lt;&lt; "i" &lt;&lt; ")" &lt;&lt; std::endl;
for (uint i = 2; i &lt; 10; i++)
    for (uint j = 2; j &lt; 10; j++)
    {
        uint q = 0;
        uint r = 0;
        DivisionDivideAndConquer(i, j, q, r);
        uint total = j * q + r;
        if (total != i)
                std::cout &lt;&lt; j &lt;&lt; "*" &lt;&lt; q &lt;&lt; "+" &lt;&lt; r &lt;&lt; " = " &lt;&lt; total &lt;&lt; " (" &lt;&lt; i &lt;&lt; ")" &lt;&lt; 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 &lt; 0) {
        max = number - 1;
    }
    // too big we have a new min
    else if(possibleremainder &gt;= static_cast&lt;int&gt;(den) )
    {
        min = number + 1;
    }
    else
    {
        //  got it!
        quo = number;
        rem = static_cast&lt;uint&gt;(possibleremainder);
        break;
    }