How to express this function efficiently

Question

int f(int n, int mul) {
    if (abs(n)%mul == 0) return n;
    else return f(n - 1, mul);
}

So it rounds down to the next mul. But obviously isn't good for large values of n. How can it be expressed safely and efficiently?

Answer 1

That's relatively simple, you just evaluate the changing expression while adjusting the variable until the result fulfills the right condition:

while (abs(n) % mul != 0) --n;

Notes:

• While this answers your question, the code is still bad but for different reasons:
  • There are functions that round numbers. Instead of reinventing the wheel, using one of them should be the first, instinctive approach.
  • abs() looks innocent, but what if you give it the smallest possible integer in a twos-complement system? There simply is no absolute value that could be represented as such an integer.
  • Similarly, decrementing n could underflow, causing undefined behaviour (and surprising results).
  • Also, what if mul is not positive? The code doesn't handle this case in any way, while the function signature allows it.
  • Last but not least, writing a loop in the first place is stupid. A modulo operation will give you the distance of the first operand to the next multiple of the second operand! Make sure you understand how this works on negative numbers though. Also, I wouldn't be surprised if modulo caused undefined behaviour when used with some values. Getting this 99% right is easy, the remaining percent is tricky.
• Compilers that optimize tail end recursion might generate the same code, so it's not guaranteed to give you any advantage.

Answer 2

Re

” How can [the recursive function] be expressed safely and efficiently?

For non-negative n and mulyou can just do

return n - n%mul;

I leave the possible adjustments for negative values, and how to handle a zero mul, to the reader.

This is about as efficient as you can get; it's what Euclid would have used, were he alive today and using C++ instead of ^[1]COBOL.

---

An alternative is

return mul*(n/mul);

Whether that is more or less efficient than the first, depends.

But offhand I would think that any difference would be too small measure.

---

You're not asking for most efficient, but merely “efficient”. Which implies just reasonable efficiency. Still I recommend measuring, whenever efficiency is a concern.

Measuring needs not require great effort.

In many cases, just observing that the program performs reasonably well, can be a good enough measurement (of very low resolution and precision, but often good enough).

---

^{[1] Not sure exactly why, but I always think of Euclid as a COBOL guy.}

Answer 3

If you are worried about StackOverflow ... then don't!

Following function is basically a tail recursive function, compilers like GCC automatically convert it into an iterative function for you!

int f(int n, int mul) {
    if (abs(n)%mul == 0) return n;

    return f(n - 1, mul);  //Tail recursion
}

REF:

1. Tail recursion in C++
2. http://32leav.es/?p=674

Hope this helps!

Answer 4

It would only round to a 100 if your second parameter was so. An iterative implementation follows. If you provide further detail I may look at it again.

     int f(int n, int mul)
     {
         while(n%mul != 0)
         {
           n--;
         };

     return n;
     }

Answer 5

What other users have suggested more or less work for limited cases of n.

Where is a solution for the general case:

if (abs(n) % mul == 0)
    return n;
else if (n >= 0)
    return n - abs(n) % mul;
else
    return mul - abs(n) % mul;

or if a oneliner is preferred

return abs(n) % mul == 0 ? n : n - (n >= 0 ? abs(n) % mul : mul - abs(n) % mul);