# Proof for the divide-by-three rule and other rules of thumb
**URL:** https://boards.straightdope.com/t/proof-for-the-divide-by-three-rule-and-other-rules-of-thumb/193866
**Category:** Factual Questions
**Created:** [August 8, 2003, 5:51pm UTC](https://boards.straightdope.com/t/proof-for-the-divide-by-three-rule-and-other-rules-of-thumb/193866 "2003-08-08T17:51:20Z")
**Posts on this page:** 3
**Page:** 2
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [August 9, 2003, 11:40pm UTC](https://boards.straightdope.com/t/proof-for-the-divide-by-three-rule-and-other-rules-of-thumb/193866/21 "2003-08-09T23:40:51Z")
> [@](#):
>
> \*Originally posted by ftg \*
> **Plavacek** , I cannot conceive of any situation involving computer math where _any_ of the rules involving looking at all digits would be faster than a division. Division is _hardwired_ in at the word level. The time to do even the divisibility by 3 rule would be ridiculously long in comparison to a division. You’d have to have a _loop_! \*
Well, first of all, on many chip architectures an integer division of a 32-bit number takes 32 cycles, while most other integer instructions take only 1. Also, you can unroll the loop quite easily, since you know exactly how large the number can be.
And you can analyze modulo arithmetic on any base, to find a convenient relationship. So, for example, the number 17.
1 = 1 mod 17, and 1 = -16 mod 17
2 = 2 mod 17, and 2 = -15 mod 17
4 = 4 mod 17, and 4 = -13 mod 17
8 = 8 mod 17, and 8 = -9 mod 17
16 = 16 mod 17, and 16 = -1 mod 17
So, with any integer n represented by two integers i & j where n = i \* 16 + j, and 0 \<= j \< 16, then if n = 0 mod 17, then i \* 16 + j = 0 mod 17, so i \* -1 + j = 0 mod 17, so if i - j is evenly divisible by 17, then n is evenly divisible by 17.
So, I choose 16 to be the base, which is even more convenient because base-16 (hexadecimal) is a convenient format to show numbers in. If you’re unfamiliar with base 16, every digit is multiplied by a power of 16 for every step left of the ones digit, and the letters a through 4 represent the numbers 10 through 15. for example, the number 482154 would be represented as 75b6a in hexadecimal, usually denoted as 0x75b6a, to make it clear that everything to the right of the “0x” is a hexadecimal number.
So, in hexidecimal, 7 + b + a = 1C, and 5 + 6 = B. And 1C - B = 11, which is 17 in base-16, so 482154 is evenly divisible by 17. That took 3 adds and 1 subtract, each of which only take one cycle to compute, compared to a divide operation that could take up to a cycle per bit.
Continuing the example, in the MIPS instruction set, with the original number in register r1, the code to check the divisibility of a number by 17 would look like this:
```auto
andi r2, r1, 0x0f0f
srl r3, r1, 16
andi r3, r3, 0x0f0f
addu r2, r2, r3
srl r3, r2, 8
addu r4, r2, r3
srl r2, r1, 4
andi r2, r2, 0x0f0f
srl r3, r1, 20
andi r3, r3, 0x0f0f
addu r2, r2, r3
srl r3, r2, 8
addu r2, r2, r3
subu r2, r2, r4
srl r3, r2, 7
andi r3, r3, 0x0001
subu r2, r2, r3
srl r3, r2, 4
xor r2, r2, r3
andi r2, r2, 0x000f
```
…while to do the equivalent using divide would be:
```auto
addi r2, r0, 0x0011
divu r1, r2
mfhi r2
```
While the first code takes 20 instructions to set r2 to 0 if r1 is evenly divisible by 17, it would take exactly 20 cycles to perform. The second code, while only 3 instructions to do the same thing, would take 34 cycles. So, a 40% speedup going from the division to the modular-math technique.
The discrepency on 64-bit architectures is even larger, since the divide would take twice as long, but the modular-math technique would only take a few more instructions.
---
### Author:  [@ChordedZither](https://boards.straightdope.com/u/ChordedZither)
#### Post date: [August 10, 2003, 1:08am UTC](https://boards.straightdope.com/t/proof-for-the-divide-by-three-rule-and-other-rules-of-thumb/193866/22 "2003-08-10T01:08:28Z")
In considering whether these rules would ever be useful on a computer, it’s worth noting that there are a couple of common situations where the appropriate arithmetic operations are often not “hard-wired”.
One, which has already been mentioned, is dealing with very large integers. For example, the kinds of factorization that is at the heart of cryptography could benefit from quick tests for divisibility by the smaller primes. The suitability of these particular rules is limited in this case by the fact that the underlying representation is binary, not decimal, as **ftg** and others have noted.
Another situation not yet mentioned is the use of fixed-point calculations, which often do employ an underlying decimal representation. Now, the most common applications of fixed-point would be monetary and divisibility/modulo calculations would, I think, be pretty uncommon in those applications. But in those rare circumstances when you did need it, these rules could come in handy.
---
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [August 10, 2003, 7:42pm UTC](https://boards.straightdope.com/t/proof-for-the-divide-by-three-rule-and-other-rules-of-thumb/193866/23 "2003-08-10T19:42:25Z")
> [@](#):
>
> \*Originally posted by Punoqllads \*
> and the letters a through 4 represent the numbers 10 through 15.
That should be, “…and the letters a through f represent the numbers 10 through 15.” Sorry for making the post even more confusing than it already was.
[Previous page](https://boards.straightdope.com/t/proof-for-the-divide-by-three-rule-and-other-rules-of-thumb/193866.md?page=1)