How to check if given number is divisible of 15 in fastest way?

How to check if given number is divisible of 15 in fastest way?

Division in processor takes much time, so I want to ask how to check in fastest way if number is divisible of some other number, in my case I need to check if number is divisible by 15.

Also I've been looking through web and found fun ways to check if number is divisible of some number, but I'm looking for fast option.

NOTE: as division takes much time I'm looking for answer without / and %.

Answer by ST3 for How to check if given number is divisible of 15 in fastest way?

Multiplication takes less time then division, so you can try this:

inline bool divisible15(unsigned int x)  {      //286331153 = (2^32 - 1) / 15      //4008636143 = (2^32) - 286331153      return x * 4008636143u <= 286331153u;  }  

This way works because 2^32-1 (max 32-bit value) is divisible of 15, however if you take, for example 7, it would look like working, but wouldn't work in all cases.

EDIT: See this, it proves that this solution (on some compilers) is faster then module.

Answer by Max for How to check if given number is divisible of 15 in fastest way?

Obligatory answer for other learners who might come looking for an answer.

if (number % n == 0)

In most cases, you can always do this, trusting the smart modern compilers.

This doesn't mean you get discouraged from learning fun ways though. Check out these links.

Fast divisibility tests (by 2,3,4,5,.., 16)?

Bit Twiddling Hacks

Answer by aaronman for How to check if given number is divisible of 15 in fastest way?

Just use i % 15 == 0

---

1. Since the compiler can easily see that 15 will never change it can feel free to make any optimization it wants on the mod operation. It is a compiler writers job to make this kind of optimization if they haven't thought of a better way to do it you won't.

2. For example it is very easy to check if a number is divisible by 2 because you just check the first bit. Compiler writers know this and you could write the code yourself to check the first bit but especially a mature compiler will have people thinking about and working on these things for years. This type of optimization is a very simple one to make as it only requires changing an instruction or 2, optimizations like better register allocation are much harder to achieve

3. One more thing to consider is that your compiler was written for the system that it is on, you code on the other hand is the same everywhere, if you write some strange code that may be just as fast on one system (probably still not faster) but on another system which has a special hardware optimization your code may lose by an order of magnitude. Since you wrote some esoteric code to check for the divisibility the compiler is unlikely to realize it can optimize to a single hardware op, writing the obvious thing to do makes life better for you and easier for the compiler.

4. Since you haven't actually checked that the speed matters writing code the strange way will make the code very difficult to read for the next person and more error prone ( premature optimization is the root of all evil)

5. It still works whether the input is 16, 32, or 64 bits since it doesn't rely on an bit manipulation.

6. Even if the compiler writer hasn't implemented it, it is clearly possible for someone to implement it (even yourself)

Answer by Mats Petersson for How to check if given number is divisible of 15 in fastest way?

On a reasonably modern process, dividing by 15 shouldn't be that terrible. The AMD optimisation guide defines it based on the quotient (the value that is being divided), and it takes 8 + bit position of the most significant bit of the quotient. So if your numbers have the 63rd bit set, you end up with 71 cycles - which is quite a long instruction, of course. But for a 32-bit number with a few zeros in the top bits, we're talking 30-40 cycles. If the number fits in a 16-bit value, we the maximum is 23 cycles.

To get the remainder is one more clockcycle on top of that.

If you are doing this ALL the time, of course, you may find that this time is quite long, but I'm not sure there is a trivial way to avoid it.

Like others have said, compiler may be able to replace it with something better. But 15 does not, to my knowledge have an obvious fast solution (if you have 16 instead of 15, then we can use the trick of x & 15).

If it's a limited range, you could build a table [vector for example, which will store 1 bit per entry], but you'll quite soon run into the problem that the non-cached memory access takes just as long as a divide operation...

There are some interesting ways to figure out if a number divides by 3, 5 and so on by summing the digits, but unfortunately, those only work based on decimal digits, which involves a long sequence of divides.

Answer by ugoren for How to check if given number is divisible of 15 in fastest way?

Here's another approach, which is probably slower than others, but uses only addition, bitwise-and and shift:

int divisible15(unsigned int x) {          if (x==0) return 1;          x = (x & 0x0f0f0f0f) + ((x&0xf0f0f0f0)>>4);          x = (x & 0x00ff00ff) + ((x&0xff00ff00)>>8);          x = (x & 0x0000ffff) + ((x&0xffff0000)>>16);          x = (x & 0x0f) + ((x&0xf0)>>4);          return x==15;  }  

The idea is that divisibility by 15, in base 16, is like divisibility by 9 in base 10 - the sum of digits must be divisible by 15.
So the code sums up all hex digits (similarly to the way you count bits), and the sum must equal 15 (except for 0).

Answer by Roddy for How to check if given number is divisible of 15 in fastest way?

Well, it's very easy to do in your head if you have the hex representation. Just sum all the digits, until you have a single digit. If the answer is '0xf', it's divisible by 15.

Example 0x3a98 : 3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf, so that's divisible by 15.

This works for all factors on X-1, where X is the base used to represent the number. (For smaller factors, the final digit must be divisible by the factor).

Don't expect this to be fast in code, though.

Answer by Atul Dureja for How to check if given number is divisible of 15 in fastest way?

You can use ternary statements and the modulus operator for this. It can be done in following manner:

((num % 15) == 0) ? "DIVISIBLE" : "NOT DIVISIBLE";  

This will tell you if a number is divisible by 15 or not. The % operator divides num by 15 and returns the remainder. If the remainder is 0, the number is evenly divisible. As simple as that!

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72