# VxWire
###### tags: `VxRail`
## 10 minutes for some coding skill
### How to check if an integer is divisible by 3/ 5/ 15?
#### Intro.
For this purpose, you might be think: That's too easy, Use modulus to resolve, see the pseudo code
```
if $nr modulus 15 is 0
print $nr is divided by 15
else if $nr modulus 3 is 0
print $nr is divided by 3
else if $nr modulus 5 is 0
print $nr is divided by 5
```
But just as we know, the modulus calculation costs a lot of computing power (But in the recent CPU/ GPU, the HW has special desgin for these computing), so how to reduce it by math. meth?
We can see [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/)
:::info
The intuition is as follows. To divide by four, you might choose to multiply by 0.25 instead. Take 5 * 0.25, you get 1.25. The integer part (1) gives you the quotient, and the decimal part (0.25) is indicative of the remainder: multiply 0.25 by 4 and you get 1
:::
upon sentences showing in this document
So following this, we can set modulus by 3 to show with 0.$\overline{33}$, modulus by 5 to show with 0.2.
Now we can be in conclusions with that:
1. All division can be seperated from 0 to 1
2. the remainder will be
$(dividend * \dfrac{1}{Divisor} - int(dividend* \dfrac{1}{Divisor}) )*Divisor$
Let dividend is call y, and divisor is call x, so following these rules, we can think $y*\dfrac{1}{x} - int(y*\dfrac{1}{x})$ is the number y on the number x system
:::info
e.g. Thinking about in hex system, 34(0x22) is divide by "hex", we can think that a number 34 is walking on "hex-ring" system( if larger than 0xf becomes a carry number), so the 34 in "hex-ring" system will be 2 carrys and 2 steps in the ring.
And the remainder is the steps in the ring.
:::
```graphviz
digraph RingHex {
// layout=circo;
node [shape=record, style="filled" fillcolor="#F0E442" color="#E69F00" penwidth=8, fontsize="20"];
fontsize="40"
label="Figure 1. 34 in hex ring"
"0x0"[fillcolor=""]
layout="neato"
subgraph cluster_hex00{
"0x0"->"0"[style=invis]
"0"->"16"[style=invis]
"16"->"32"[style=invis]
};
subgraph cluster_hex01{
"0x1"->"1"[style=invis]
"1"->"17"[style=invis]
"17"->"33"[style=invis]
};
subgraph cluster_hex02{
"0x2"->"2"[style=invis]
"2"->"18"[style=invis]
"18"->"34"[style=invis]
};
subgraph cluster_hex03{
"0x3"->"3"[style=invis]
"3"->"19"[style=invis]
"19"->"35"[style=invis]
};
subgraph cluster_hex04{
"0x4"->"4"[style=invis]
"4"->"20"[style=invis]
"20"->"36"[style=invis]
};
subgraph cluster_hex05{
"0x5"->"5"[style=invis]
"5"->"21"[style=invis]
"21"->"37"[style=invis]
};
subgraph cluster_hex06{
"0x6"->"6"[style=invis]
"6"->"22"[style=invis]
"22"->"38"[style=invis]
};
subgraph cluster_hex07{
"0x7"->"7"[style=invis]
"7"->"23"[style=invis]
"23"->"39"[style=invis]
};
subgraph cluster_hex08{
"0x8"->"8"[style=invis]
"8"->"24"[style=invis]
"24"->"40"[style=invis]
};
subgraph cluster_hex09{
"0x9"->"9"[style=invis]
"9"->"25"[style=invis]
"25"->"41"[style=invis]
};
subgraph cluster_hex0A{
"0xA"->"10"[style=invis]
"10"->"26"[style=invis]
"26"->"42"[style=invis]
};
subgraph cluster_hex0B{
"0xB"->"11"[style=invis]
"11"->"27"[style=invis]
"27"->"43"[style=invis]
};
subgraph cluster_hex0C{
"0xC"->"12"[style=invis]
"12"->"28"[style=invis]
"28"->"44"[style=invis]
};
subgraph cluster_hex0D{
"0xD"->"13"[style=invis]
"13"->"29"[style=invis]
"29"->"45"[style=invis]
};
subgraph cluster_hex0E{
"0xE"->"14"[style=invis]
"14"->"30"[style=invis]
"30"->"46"[style=invis]
};
subgraph cluster_hex0E{
"0xF"->"15"[style=invis]
"15"->"31"[style=invis]
"31"->"47"[style=invis]
};
"35"[style=invis]
"36"[style=invis]
"37"[style=invis]
"38"[style=invis]
"39"[style=invis]
"40"[style=invis]
"41"[style=invis]
"42"[style=invis]
"43"[style=invis]
"44"[style=invis]
"45"[style=invis]
"46"[style=invis]
"47"[style=invis]
// rankdir=LR;
// "0x1E"->"0x10" [style=invis]
subgraph cycle{
// graph [layout=circo]
// layout=circo
"0x0"->"0x1"->"0x2"->"0x3"
"0x3"->"0x4"->"0x5"->"0x6"
"0x6"->"0x7"->"0x8"->"0x9"
"0x9"->"0xA"->"0xB"->"0xC"
"0xC"->"0xD"->"0xE"->"0xF"
"0xF"->"0x0"
}
}
```
By the figure 1, we can extern 0xF to 0xFFFFFFFFFFFFFFFF for 64 bits machine, and we cae write a new code for this topic:
```c
static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;
static inline bool is_divisible(uint32_t n, uint64_t M) {
return n * M <= M - 1;
}
div3 = is_divisible(i, M3);
div5 = is_divisible(i, M5);
```
#### How to work
On the following, we use 16 bits for the MAX. data and using divide by 3 to explain
```
0xFFFF 0xAAAA 0x5555 0x0000
|---------|---------|---------|
````
In the this system, more than 16 bits (overflow) will be truncate automatically. So in this numerical system, if the number falls between 0x0000 ~ 0x5555, that's means the number can be divided by 3(in the c code, present by =="<= M - 1"==), 0x5556 ~ 0xAAAA is the remainder 1, 0xAAAB ~ 0xFFFF is the remainder 2.
And ==+1== make sure the calculation number will be within the range
```
e.g.
2/3 -> this means: 2 * (0x5555 + 1) = 0xAAAC, so the remainder is 2
4/3 -> this means: 4 * (0x5555 + 1) = 0x5558, so the remainder is 1
```
:::info
Why ==+1== is needed as an adjustment?
without +1, what happen in "2/3"?
2 * (0x5555) = 0xAAAA, this number would is on the boundary number, so that this is way to distinguish the answer is 1 or 2.
:::
That's do some tests in the linux system. Using the number is from 0 to MAX_INT >>2 (C MAX_INT) for the checking, compiler option using -Os
This is use modulus to cal.
This is use the =="is_divisible"== method to cal.
You can see that, this method is better performance.
:::warning
* fizz means the how many numbers can be divide by 3 exclude divide by 15
* Buzz means the how many numbers can be divide by 5 exclude divide by 15
* FizzBuzz means the how many numbers can be divide by 15
You can see the Fizz/ Buzz problem
:::
#### Question?
That has another question, why is function "is_divisible(uint32_t n, uint64_t M)" input paramter using "uint32_t" not using "uint64_t" ?
let we use n = 0x7FFFFFFFFFFFFFFF , n = 0x8000000000000000 for testing.....
* by use M3 -> 0x7FFFFFFFFFFFFFFF the number is in section two (0xAA...AA ~ 0x55...55) and remainder is also 1
* by use M3 -> 0x8000000000000000 the number is in section one (0x55...55 ~ 0x00...00) but remainder is 2
that's wrong answer........
The reason is =="+1"==
as the same we use 16bit system for example.
|nr | hex after mul M3| over num(compare with 0x5555)|
|-|-|-|
|1 | 0x5556 | 1 |
|2 | 0xAAAC | 2 |
|3 | 0x0002 | 2 |
|4 | 0x5558 | 3 |
|5 | 0xAAAE | 4 |
|6 | 0x0004 | 4 |
Using another format is more easy to understand
|nr|hex|over||nr|hex|over|
|-|-|-|-|-|-|-|
|1 | 0x5556 | 1 ||4 | 0x5558 | 3 |
|2 | 0xAAAC | 2 ||5 | 0xAAAE | 4 |
|3 | 0x0002 | 2 ||6 | 0x0004 | 4 |
by this rule, we can know which nubmer will make to over the next range.
so, we can calcular the max number: 0x5555/2 + 0x5555 = 0x7FFF
that's the answer why using uint32_t, (half the 64 bit) to make sure all uint32 can be calculated.
Sign in with Wallet
Connect another wallet