Divide by 3 in Binary (Verilog)

The other day I was wondering how to divide by 3 in Verilog, by using only operations like sum, diff, bit shifting, or logical operations. I'll show here the trick I came up with.

Dividing by 3 is the same as multiplying by 1/3.

And 1/3 is the limit of this sum when N goes to infinity:

(This sum is actually called the geometric series with first term 1/4 and ratio 1/4).

Go play with it on Desmos, and you'll see how it goes from 0,25 to 1/3 as N grows.

Here we can see that with N=30, we reach a nice approximation already. What is nice about that sum is that each term is the inverse of a power of 2. For example, when N=5, we get:

Now, in binary, dividing by 4 is the same as shifting 2 bits to the right, dividing by 16 is shifting 4 bits to the right...

So, dividing by 3 is now like adding several time the same number, each time shifted by 2 bits on the right!

Now let see an example, 239/3 would give 79.67, that is 80 if we round up properly (as 0.67 is over 0.50), and how it works in binary:

I leave here the Verilog functions code to compute the div3() and mod3() of a byte.

And here you can see the same calculus for all values between 0 and 255.

Before writing the Verilog function I did a first attempt to validate the algorithm in RPN and wrote an RPL program (Reverse Polish Language), on my HP48sx. And it worked great!

Here is the program:

<<
R->B 256 *
DUP DUP DUP DUP
4 /
SWAP 16 /
3 ROLL 64 /
4 ROLL 256 /
5 ROLL 1024 /
+ + + +
128 / DUP
# 1b AND
SWAP
2 /
+
B->R
>>

Have Comments?

Leave them here on Twitter ;), Like and Retweet.