How do I find the next multiple of 10 of any integer?
CAlgorithmMathC Problem Overview
Dynamic integer will be any number from 0 to 150.
i.e. - number returns 41, need to return 50. If number is 10 need to return 10. Number is 1 need to return 10.
Was thinking I could use the ceiling function if I modify the integer as a decimal...? then use ceiling function, and put back to decimal?
Only thing is would also have to know if the number is 1, 2 or 3 digits (i.e. - 7 vs 94 vs 136)
Is there a better way to achieve this?
Thank You,
C Solutions
Solution 1 - C
n + (10 - n % 10)
How this works. The % operator evaluates to the remainder of the division (so 41 % 10 evaluates to 1, while 45 % 10 evaluates to 5). Subtracting that from 10 evaluates to how much how much you need to reach the next multiple.
The only issue is that this will turn 40 into 50. If you don't want that, you would need to add a check to make sure it's not already a multiple of 10.
if (n % 10)
n = n + (10 - n % 10);
Solution 2 - C
You can do this by performing integer division by 10 rounding up, and then multiplying the result by 10.
To divide A by B rounding up, add B - 1 to A and then divide it by B using "ordinary" integer division
Q = (A + B - 1) / B
So, for your specific problem the while thing together will look as follows
A = (A + 9) / 10 * 10
This will "snap" A to the next greater multiple of 10.
The need for the division and for the alignment comes up so often that normally in my programs I'd have macros for dividing [unsigned] integers with rounding up
#define UDIV_UP(a, b) (((a) + (b) - 1) / (b))
and for aligning an integer to the next boundary
#define ALIGN_UP(a, b) (UDIV_UP(a, b) * (b))
which would make the above look as
A = ALIGN_UP(A, 10);
P.S. I don't know whether you need this extended to negative numbers. If you do, care should be taken to do it properly, depending on what you need as the result.
Solution 3 - C
What about ((n + 9) / 10) * 10 ?
Yields 0 => 0, 1 => 10, 8 => 10, 29 => 30, 30 => 30, 31 => 40
Solution 4 - C
tl;dr: ((n + 9) / 10) * 10 compiles to the nicest (fastest) asm code in more cases, and is easy to read and understand for people that know what integer division does in C. It's a fairly common idiom.
I haven't investigated what the best option is for something that needs to work with negative n, since you might want to round away from zero, instead of still towards +Infinity, depending on the application.
Looking at the C operations used by the different suggestions, the most light-weight is Mark Dickinson's (in comments):
(n+9) - ((n+9)%10)
It looks more efficient than the straightforward divide / multiply suggested by a couple people (including @bta): ((n + 9) / 10) * 10, because it just has an add instead of a multiply. (n+9 is a common subexpression that only has to be computed once.)
It turns out that both compile to literally identical code, using the compiler trick of converting division by a constant into a multiply and shift, see this Q&A for how it works. Unlike a hardware div instruction that costs the same whether you use the quotient, remainder, or both results, the mul/shift method takes extra steps to get the remainder. So the compiler see that it can get the same result from a cheaper calculation, and ends up compiling both functions to the same code.
This is true on x86, ppc, and ARM, and all the other architectures I've looked at on the Godbolt compiler explorer. In the first version of this answer, I saw an sdiv for the %10 on Godbolt's gcc4.8 for ARM64, but it's no longer installed (perhaps because it was misconfigured?) ARM64 gcc5.4 doesn't do that.
Godbolt has MSVC (CL) installed now, and some of these functions compile differently, but I haven't taken the time to see which compile better.
Note that in the gcc output for x86, multiply by 10 is done cheaply with lea eax, [rdx + rdx*4] to do n*5, then add eax,eax to double that. imul eax, edx, 10 would have 1 cycle higher latency on Intel Haswell, but be shorter (one less uop). gcc / clang don't use it even with -Os -mtune=haswell :/
The accepted answer (n + 10 - n % 10) is even cheaper to compute: n+10 can happen in parallel with n%10, so the dependency chain is one step shorter. It compiles to one fewer instruction.
However, it gives the wrong answer for multiples of 10: e.g. 10 -> 20. The suggested fix uses an if(n%10) to decide whether to do anything. This compiles into a cmov, so it's longer and worse than @Bta's code. If you're going to use a conditional, do it to get sane results for negative inputs.
Here's how all the suggested answers behave, including for negative inputs:
./a.out | awk -v fmt='\t%4s' '{ for(i=1;i<=NF;i++){ a[i]=a[i] sprintf(fmt, $i); } } END { for (i in a) print a[i]; }'
i -22 -21 -20 -19 -18 -12 -11 -10 -9 -8 -2 -1 0 1 2 8 9 10 11 12 18 19 20 21 22
mark -10 -10 -10 -10 0 0 0 0 0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30
igna -10 -10 -10 0 0 0 0 0 10 10 10 10 10 10 10 10 10 20 20 20 20 20 30 30 30
utaal -20 -20 -20 -10 -10 -10 -10 -10 0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30
bta -10 -10 -10 -10 0 0 0 0 0 10 10 10 10 10 10 10 10 10 20 20 20 20 20 30 30
klatchko -10 -10 -10 -10 0 0 0 0 0 0 0 0 0 10 10 10 10 10 20 20 20 20 20 30 30
branch -10 -10 -20 0 0 0 0 -10 10 10 10 10 0 10 10 10 10 10 20 20 20 20 20 30 30
Ignacio's n + (((9 - (n % 10)) + 1) % 10) works "correctly" for negative integers, rounding towards +Infinity, but is much more expensive to compute. It requires two modulo operations, so it's essentially twice as expensive. It compiles to about twice as many x86 instructions, doing about twice the work of the other expressions.
Result-printing program (same as the godbolt links above)
#include <stdio.h>
#include <stdlib.h>
int f_mark(int n) { return (n+9) - ((n+9)%10); } // good
int f_bta(int n) { return ((n + 9) / 10) * 10; } // compiles to literally identical code
int f_klatchko(int n) { return n + 10 - n % 10; } // wrong, needs a branch to avoid changing multiples of 10
int f_ignacio(int n) { return n + (((9 - (n % 10)) + 1) % 10); } // slow, but works for negative
int roundup10_utaal(int n) { return ((n - 1) / 10 + 1) * 10; }
int f_branch(int n) { if (n % 10) n += (10 - n % 10); return n; } // gcc uses cmov after f_accepted code
int main(int argc, char**argv)
{
puts("i\tmark\tigna\tutaal\tbta\tklatch\tbranch");
for (int i=-25 ; i<25 ; i++)
if (abs(i%10) <= 2 || 10 - abs(i%10) <= 2) // only sample near interesting points
printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\n", i, f_mark(i), f_accepted(i),
f_ignacio(i), roundup10_utaal(i), f_bta(i), f_branch(i));
}
Solution 5 - C
How about using integer math:
N=41
N+=9 // Add 9 first to ensure rounding.
N/=10 // Drops the ones place
N*=10 // Puts the ones place back with a zero
Solution 6 - C
in C, one-liner:
int inline roundup10(int n) {
return ((n - 1) / 10 + 1) * 10;
}
Solution 7 - C
Be aware that answers based on the div and mod operators ("/" and "%") will not work for negative numbers without an if-test, because C and C++ implement those operators incorrectly for negative numbers. (-3 mod 5) is 2, but C and C++ calculate (-3 % 5) as -3.
You can define your own div and mod functions. For example,
int mod(int x, int y) {
// Assert y > 0
int ret = x % y;
if(ret < 0) {
ret += y;
}
return ret;
}
Solution 8 - C
You could do the number mod 10. Then take that result subtract it from ten. Then add that result to the original.
if N%10 != 0 #added to account for multiples of ten
a=N%10
N+=10-a
Solution 9 - C
n + (((9 - (n % 10)) + 1) % 10)
Solution 10 - C
int n,res;
...
res = n%10 ? n+10-(n%10) : n;
or
res = (n / 10)*10 + ((n % 10) ? 10:0);
Solution 11 - C
In pseudo code:
number = number / 10
number = ceil(number)
number = number * 10
In Python:
import math
def my_func(x):
return math.ceil(x / 10) * 10
That should do it. Keep in mind that the above code will cast an integer to a float/double for the arithmetic, and it can be changed back to an integer for the final return. Here's an example with explicit typecasting
In Python (with typecasting):
import math
def my_func(x):
return int(math.ceil(float(x) / 10) * 10)
Solution 12 - C
round_up(int i)
{
while(i%10) {
i++;
}
return(i);
}