6

How to check whether a number is divisible by 5 or not without using % and / operator?
I want a quickest algorithm for this problem.

I tried subtracting 5 from the number until I get 0 or a negative number. 0 means divisible by 5, negative means not divisible by 5.
But for a big number this will take too much time.

10
  • 5
    Great! Why do you need to do this? What have you tried so far? Jun 14, 2013 at 17:00
  • 1
    Cast number into a string, extract last “character” and see whether it’s a 0 or 5 – or something else …?
    – CBroe
    Jun 14, 2013 at 17:00
  • 5
    @user2484070: There is no mechanism that is going to be as fast as simply doing %. So I would suggest using %! Jun 14, 2013 at 17:05
  • 2
    +1 The questing is not clear, and probably the OP wants someone to do their homework, but we had some good answer that may be very helpful for people that have this as a real issue. Jun 14, 2013 at 17:37
  • 1
    If is a real issue, you need to give us more information about what you are doing. The fastest algorithm is platform dependent, so we cannot help you if we do not know exactly what you want to do. Jun 14, 2013 at 18:00

9 Answers 9

12

A good starting point is to look into how division can be accomplished with multiplication and bit-shifts. This question is one place to look.

In particular, you can follow the attached post to hit upon the following strategy. First, "divide by 5" using multiplication and bit-shifts:

 int32_t div5(int32_t dividend) {
     int64_t invDivisor = 0x33333333;
     return 1 + (int32_t) ((invDivisor * dividend) >> 32);
 }

Then, take the result and multiply by 5:

int result = div5(dividend) * 5;

Then, result == dividend if and only dividend is divisible by 5.

if(result == dividend) {
    // dividend is divisible by 5
}
else {
    // dividend is not divisible by 5
}
4
  • You have to run this in a loop if say, the dividend is 5^5 right? I guess that's still a pretty good runtime.
    – rliu
    Jun 14, 2013 at 17:44
  • @roliu: No, no loop. The result of div5(3125) will be 625, which multiplied by 5 is 3125 which is equal to the dividend which says 3125 is divisible by 5. Note the result of div5(3125 + 1) will be 625 but multiplied by 5 gives 3125 which is not 3125 + 1 which says 3125 + 1 is not divisible by 5.
    – jason
    Jun 14, 2013 at 17:47
  • 1
    This formula gives an approximation, int fact, it will return num/5 - 1. So you need a + 1 in the return statement. This is valid only for the special case where the divisor is 5. Jun 14, 2013 at 17:57
  • @Jason Oh right. For some reason I read dividend as quotient... not really sure why. So basically this can be summed up as x / 5 * 5 = x (with integer division) iff x % 5 = 0. And then you replace integer division with fanciness.
    – rliu
    Jun 14, 2013 at 18:01
6

There are two reasons I can see for wanting such an algorithm: (1) homework, or (2) writing efficient code for a microcontroller which does not have efficient division instructions. Assuming your reason is the second, but allowing for the possibility that it might be the first, I won't give you a full solution, but will suggest that if you divide your number into chunks that are a multiple of four bits each, the sum of all those chunks will be divisible by five only if the original number was; note that when performing such computation you must either avoid overflows or else add to your result the number of overflows that have occurred. I don't know any efficient way to do the latter in C, but in many machine languages it is easy. As a simple example, on the 8051 if one had a 32-bit integer, one could so something like:

    mov a,Number   ; Byte 0
    add a,Number+1 ; Byte 1
    adc a,Number+2 ; Byte 2, plus carry from last add
    adc a,Number+3 ; Byte 3, plus carry from last add
    adc a,#0       ; Add in carry, if any (might overflow)
    adc a,#0       ; Add in carry, if any (can't overflow)

Note that in the machine code, adding the carries back into the number is much faster than performing 16-bit math would be.

Once the value has been reduced to the range 0-255, one could add the upper four bits to the lower 4 bits to get a value in the range 0 to 30. One could either test for the seven such values that are multiples of five, or work to reduce the number of possible values further [e.g. if the value is at least 15, subtract 15; if at least 10, subtract 10; if 5, subtract five; if zero, it's a multiple of five].

3
  • @OliCharlesworth: What is the value of (16%5)? What is the value of (16%5) squared? Cubed? Raised to the 492nd power? What is the value of 255%5? Making a carry add one to a value instead of 256 will cause the value to be 255 less after each overflow than it would be if the carry added 256. What's the value of 255%5?
    – supercat
    Jun 14, 2013 at 17:33
  • Aha, yes, that makes sense. (a+16)%5 == (a+1)%5. Good stuff! Jun 14, 2013 at 17:35
  • I find the overflow argument in the code comments convincing, if not stringent. "Working backwards", the result of adc  A, Number+3 may look as large as 0x1ff, necessitating both adc  A, #0. But working forwards, A(and carry) will contain at least one zero bit starting with the result of add  A, Number+1 - here for no carry being added in, in bytes to follow for a zero having been somewhere.
    – greybeard
    Mar 24, 2019 at 9:35
3

Let's represent the number in base 2. We have:

abcdefgh*101 = ABCDEFGHIJ

or

+abcdefgh00
+  abcdefgh
 ----------
 ABCDEFGHIJ

We are given ABCDEFGHIJ and want to find abcdefgh.

If you alternately - and + ABCDEFGH with its successive rightshift-by-2, you will get...

+  ABCDEFGH
-    ABCDEF
+      ABCD
-        AB
-----------
+  abcdefgh
+    abcdef
-    abcdef
-      abcd
+      abcd
+        ab
-        ab
-----------
   abcdefgh

The answer!

1
  • When you have the division result you can multiply it back with 5 to check the remainder
    – phuclv
    Aug 2, 2013 at 14:54
2

It finally got unlocked, so I can explain my comment, which incidentally turns out to generate better code than GCC does for x % 5 == 0. See here, fill in

#include <stdint.h>
bool divisible_by_5(uint32_t x)
{
   return x % 5 == 0;
}
bool divisible_by_5_fast(uint32_t x)
{
   return x * 0xCCCCCCCD <= 0x33333333;
}

I'll assume unsigned input, because the OP suggested an algorithm that only works with positive input. This method can be extended to signed input, but it's a little messy.

0xCCCCCCCD is the modular multiplicative inverse of 5, modulo 232. Multiplying a multiple of k (for example, n * k) by the (modular) multiplicative inverse is equivalent to dividing by k, because

(n * k) * inv(k) =
// use associativity
n * (k * inv(k)) =
// use definition of multiplicative inverse
n * 1 =
// multiplicative identity
n

Modulo powers of two, a number has a modular multiplicative inverse iff it is odd.

Since multiplying by an odd number is invertible and is actually a bijection, it can't map any non-multiples of k to the 0 - (232-1)/k range.

So when it's outside that range, it can't have been a multiple of k.

0x33333333 is (232-1)/5, so if x * 0xCCCCCCCD higher, x can't have been a multiple of 5.

4
  • 1
    @phuclv it's a different technique, but there may be some deep and interesting reason why they look so similar. The method I show uses only narrow multiplication, but on the other hand cannot easily be adapted to give the remainder or quotient in cases where the remainder isn't zero and does not immediately apply to even divisors (there is a variant with a rotate for that)
    – harold
    Mar 7, 2019 at 15:39
  • turns out to generate better code than GCC does for x % 5 == 0 for such comparisons, I find it fair to include "-O3" in the compiler options.
    – greybeard
    Mar 5 at 8:47
  • This code assumes INT_MAX == INT32_MAX. You might want to add a cast: return (uint32_t)(x * 0xCCCCCCCD) <= 0x33333333;
    – chqrlie
    Mar 5 at 9:00
1

In decimal, a number is divisible by 3 or 9 if the sum of the digits is divisible by 3 or 9

The same applies to any divisors of b - 1 in base b. For example we can sum the digits in base 16 and take modulo 3, 5 or 15 to get the number modulo 3, 5 or 15. See How to find x mod 15 without using any Arithmetic Operations?

In fact we can check divisibility by 5 in any base 24k like 16, 256, 4096...

Using that property we have the following solution

unsigned mod5(unsigned x) {
    unsigned mod = 0;
    while (x) {
        mod += x & 0x0F;
        x >>= 4;
    }
    while (mod >= 15)
    {
        if (mod == 15) return 0;
        mod = (mod >> 4) + (mod & 0x0F);
    }
    return mod;   
}

Or it can be further optimized like this using a bit lookup table in the last step

unsigned isDivisibleBy5(unsigned x) {
    x = (x >> 16) + (x & 0xffff);
    x = (x >> 8)  + (x & 0x00ff);
    x = (x >> 4)  + (x & 0x000f);
    return (0x1084210842108421ULL >> x) & 1;
}
5
0

Add all the bytes and check (by table look-up) if the sum is divisible by 5.

2
  • 1
    Actually that works, because 256 % 5 = 1, and therefore the "multiplier" for each digit is 1 (ie, just add them). If it hadn't been 1, the algorithm with a digital sum still works, but you'd have to scale every digit by some amount.
    – harold
    Jun 14, 2013 at 20:27
  • @harold was thinking bits. Would be really happy to +1 this if Egor edits it (-1 locked).
    – zw324
    Jun 14, 2013 at 23:35
0

Keep subtracting by multiples of 5 like 50, 500,100, etc. Start with big numbers. If the result goes in negative then subtract with a smaller number number until you reach 0. Otherwise the number is not divisible.

1
  • (A bit more organised this is one division algorithm.)
    – greybeard
    Mar 5 at 8:49
0
bool trythis(int number){
  Int start = number;
  Do{
    start = start - 5;
  } while (start > 5)

  If (start == 5 || start == 0) {
    Return true;
  } else return false;
}
1
  • While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value. Mar 26, 2017 at 11:25
-3

Typecast or convert to a string, then see if the final character is a 5 or 0.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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