---
# System prepended metadata

title: VxWire
tags: [VxRail]

---

# 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.
![](https://i.imgur.com/axCPzlA.png)

This is use the =="is_divisible"== method to cal.
![](https://i.imgur.com/kw7W4C9.png)

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.