CODEWITHSUNDEEP
crounding
Jeff L
Jeff L

Reputation: 623

C: Round signed integer to nearest multiple

This feels like a basic question but I couldn't find a definitive answer so far.

I would like to implement an efficient function round_to_nearest(int x, int multiple), that rounds a signed integer x to the nearest multiple of multiple, avoiding using floating point arithmetic if possible.

Example output:

round_to_nearest(14, 5);
15

round_to_nearest(16, 5);
15

round_to_nearest(23, 5);
25

round_to_nearest(22, 5);
20

round_to_nearest(-23, 5);
-25

round_to_nearest(-22, 5);
-20

Upvotes: 6

Views: 735

Answers (4)

Andreas Wenzel
Andreas Wenzel

Reputation: 24921

In order to round to the next multiple in the direction of zero (i.e. down for positive numbers and up for negative numbers), all you have to do is to divide by that multiple and then multiply the result with the multiple. The rounding towards zero will be accomplished by the truncation in the division.

int round_toward_zero( int num, int multiple )
{
    int quotient;

    quotient  = num / multiple;

    return quotient * multiple;
}

However, since you stated that you wanted to round to the nearest multiple instead of the next multiple in the direction of zero, we must do the same thing, but we must add a small correction in cases in which we want to round in the other direction:

  • For positive numbers, if the remainder of the division is at least half of the multiple, then we must add 1 to the quotient before multiplying with the multiple, so that it is rounded away from zero.
  • For negative numbers, if the remainder of the devision is not more than half of the multiple we must add -1 to the quotient before multiplying with the multiple, so that it is rounded away from zero.

Therefore, in the following code, the variable correction can have the value -1, 0 or +1. For positive numbers, it will be either 0 or +1, and for negative numbers, it will be either -1 or 0.

#include <stdio.h>

int round_to_nearest( int num, int multiple )
{
    int quotient, remainder, correction;

    quotient  = num / multiple;
    remainder = num % multiple;

    correction = remainder / ( (multiple + 1 ) / 2 );

    return (quotient + correction) * multiple;
}

int main( void )
{
    printf( "%d\n", round_to_nearest(14, 5) );
    printf( "%d\n", round_to_nearest(16, 5) );
    printf( "%d\n", round_to_nearest(23, 5) );
    printf( "%d\n", round_to_nearest(22, 5) );
    printf( "%d\n", round_to_nearest(-23, 5) );
    printf( "%d\n", round_to_nearest(-22, 5) );
}

Output:

15
15
25
20
-25
-20

Upvotes: 1

Clifford
Clifford

Reputation: 93476

In integer arithmetic, if n is positive, add m/2, else subtract m/2, then divide by m (truncating integer divide), then multiply by m:

int round_to_nearest( int n, int m )
{
    return (( n + ((n < 0) ? -m : m) / 2) / m ) * m ;
}

int main()
{
    int test[] = {16, 23, 22, -23, -22} ;
    int m = 5 ;
    
    for( int i = 0; i < sizeof(test) / sizeof(*test); i++ )
    {
        printf(" round_to_nearest( %d, %d ) = %d\n", test[i], m, 
                                                     round_to_nearest( test[i], m ) ) ;
    }

    return 0;
}

Output of test:

 round_to_nearest( 16, 5 ) = 15
 round_to_nearest( 23, 5 ) = 25
 round_to_nearest( 22, 5 ) = 20
 round_to_nearest( -23, 5 ) = -25
 round_to_nearest( -22, 5 ) = -20

One caveat is that m must be > 0 - which in this context makes sense, I would accept that as a precondition for correct operation; checking for it as a runtime error is probably unnecessary, but you might include an assert to protect against programmer semantic error:

assert( m > 0 ) ;

Standard library asserts are removed when NDEBUG is defined - normally when debug support is disabled.

Upvotes: 5

Brendan
Brendan

Reputation: 37222

Integer division truncates towards zero; which is 0.5 smaller (in magnitude, on average) than a rounded to nearest result.

If you add the magnitude of 0.5 * divisor to the magnitude of the numerator, then the result will be 0.5 larger.

In other words, for unsigned integers:

    result = (numerator + divisor/2) / divisor;

..or alternatively (with less rounding error when the divisor is odd, and higher risk of overflow - e.g. if numerator is INT_MAX):

    result = (numerator*2 + divisor) / (divisor * 2);

For signed integers "magnitude" isn't "value"; and it becomes a mess when the numerator and divisor have a different sign. To fix that:

    if( (numerator < 0) && (divisor < 0) ||
        (numerator >= 0) && (divisor |= 0) ) {
        /* Numerator and divisor have same sign */
        result = (numerator*2 + divisor) / (divisor * 2);
    } else {
        /* Numerator and divisor have different sign */
        result = (numerator*2 - divisor) / (divisor * 2);
    }

To round to the nearest multiple, you just multiply by the divisor after the "round to nearest". The code becomes:

    if( (numerator < 0) && (multiple < 0) ||
        (numerator >= 0) && (multiple |= 0) ) {
        /* Numerator and multiple have same sign */
        result = (numerator*2 + multiple) / (multiple * 2);
    } else {
        /* Numerator and multiple have different sign */
        result = (numerator*2 - multiple) / (multiple * 2);
    }
    result *= multiple;

Upvotes: 0

user3386109
user3386109

Reputation: 34829

For positive numbers:

  • add half of the multiple to x
  • then perform integer division, which drops the fractional part
  • then multiply by the multiple to get the final answer

For negative numbers, the first step is a subtraction, instead of addition.

int round_to_nearest(int x, int multiple)
{
    if (x >= 0)
        return ((x + multiple / 2) / multiple) * multiple;
    else
        return ((x - multiple / 2) / multiple) * multiple;
}

Upvotes: 2

Related Questions