Math question: How can I divide by 3?

[mineiro]

How can I divide by 3?

After much reflection and introspection I came to the conclusion that I only know but do not understand certain numerical divisions.
If I put a parallel between multiplication and division I have to:
- to multiply a number by 10 (1010b) I can perform the sum between multiplying the number by 8 and by 2

Ex: 3 * 10 == (3 * 2) + (3 * 8 ) = 6 + 24 = 30

But what about division? Why not the same step?
Ex: 30/10 != (30/2) +- (30/8) == ?????????
I understand that it is necessary to factor the number 10 to (2 * 5) to achieve the desired result.
ex; 30/10 == ((30/2) / 5) == 3
What is my fault? Something related to product of sums and sum of products?

The above question led me to think about how to divide by 3 just in binary.

In binary:
30/3 ==

11110b |_ 11b
-11         1
_______
00110b |_ 11b
              10
_______
00110b |_ 11b
-    11     101
_______
0000   |_ 11b
00000   1010

The question I ask is how to divide by 3 or 5 based only on the division by 2?
In better words, if I only know how to divide by 2, how do I divide a number (a block) by 3 or 5?
Critics are welcome, I do not take them personally.

[jj2007]

There is a dedicated thread here, including a nice tool written by qWord. It is not exactly what you want, but before starting a new discussion, reading that thread won't do any harm ;-)

[RuiLoureiro]

How can I divide by 3?

After much reflection and introspection I came to the conclusion that I only know but do not understand certain numerical divisions.
If I put a parallel between multiplication and division I have to:
- to multiply a number by 10 (1010b) I can perform the sum between multiplying the number by 8 and by 2

Ex: 3 * 10 == (3 * 2) + (3 * 8 ) = 6 + 24 = 30

But what about division? Why not the same step?
Ex: 30/10 != (30/2) +- (30/8) == ?????????
I understand that it is necessary to factor the number 10 to (2 * 5) to achieve the desired result.
ex; 30/10 == ((30/2) / 5) == 3
What is my fault? Something related to product of sums and sum of products?

Because 30/2 + 30/8 =120 /8 + 30 /8 = 150 / 8

To divide X by n you may do: X=a+b and then X/n= a/n + b/n

[aw27]

How can I divide by 3?

According to qWord's nice calculator, it would be:
mov eax,X
mov edx,0AAAAAAABh
mul edx
shr edx,01h
; edx = quotient

PS: Microsoft workers have thought about that as well
https://blogs.msdn.microsoft.com/devdev/2005/12/12/integer-division-by-constants/

[mineiro]

thank you sirs by the answers, but sorry, I continue not understanding. I know this sounds easy but to me is so much complex.

The point about magical numbers if I really take the point is that it uses some form of complement, 2 complement or 1 complement I suppose, and inside computer we have 32,64, ... bits.
So, I continue not understand how that number 8 on multiplication turned into number 5 on division while number 2 remains the same on both  division/multiplication by 10.

Well, let me reformulate the question:
If I have a pencil (object) and I like to divide that pencil into 3 same parts by only dividing by 2 (half). How can I do that? I reformulate this question because on pencil we cannot use 2 or 1 complement.

Is this impossible because 3 or 5 is a prime number?
Again, thank you sir by patience.

[rrr314159]

@mineiro,

It's impossible to get to 1/3 by dividing in halves. When people ask me if I'm Irish, I have a standard joke: "I'm one third Irish". The joke is, you can't be. You can only be (any number) / (power of 2) Irish! And the same is true for the pencil.

OTOH you can use "magic numbers" to divide by 3. It works if you don't need to be too precise. But if you do, don't bother, just use div. Borderline case gives the wrong answer so you'll need an extra "if" statement. Or, maybe two of them (don't remember exactly). If I'd had a couple more registers I could have (just barely) gotten it slightly faster, but I didn't. Bottom line: not worth the hassle.

BTW, I'm something like 5/16 Irish .. and only about 1/3 of people get the joke.

[Mikl__]

Y/3=?    1/3=21845/2¹⁶   Y/3=(Y*21845)/2¹⁶

[mineiro]

Thank you for the answers and tips.
The 2 complement stayed in limbo for years, it was worthless when it was invented.
I was doing the third reading when I thought about this question and after 2 months without finding a solution I decided to ask them.
In computing we have the unit (bit) and the pseudo whole (registers). And that is how I rephrased the question, for in a pencil we do not have the unity, only the whole. I understand about the limitation of magic numbers (whole).

jj2007, RuiLoureiro, aw27, rrr314159, Mikl___
I thank you very much for your answers, you deserve all my respect.

[Mikl__]

Olá, mineiro!
Leia aqui sobre a divisão

• Optimizing subroutines in assembly language (An optimization guide for x86 platforms) de Agner Fog. Cabeça "Integer division by a constant (all processors)" páginas 148-149
• Division by Invariant Integers Using Multiplication (1994) de Torbjörn Granlund, Peter L. Montgomery
• Hacker's Delight de Henry S. Warren. Cabeça 10 "INTEGER DIVISION BY CONSTANTS"

[mineiro]

привет сэр Mikl__
Спасибо за ссылки, я читаю их сейчас.
братские объятия.

[tenkey]

In binary:
30/3 ==

11110b |_ 11b
-11         1           3 shl 3 = 3 x 8  = 24, 30/3 = 24/3 + 6/3 = 8 + 6/3
_______
00110b |_ 11b
              10         3 shl 2 = 3 x 4 = 12, can't subtract 12 from 6
_______
00110b |_ 11b
-    11     101        3 shl 1 = 3 x 2 = 6, 30/3 = 8 + 6/3 = 8 + 2
_______
0000   |_ 11b       3 shl 0 = 3 x 1 = 3, can't subtract 3 from 0
00000   1010        8 + 2 = 10

[Mikl__]

hi, tenky!
There is the simplest in ALU... The divisor is subtracted from the dividend multiplied by the power of two. The product of a number by 2^N is equivalent to shifting this number by N digits to the left. If the sign of the result is positive, then add 2^N to the quotient. If the result is negative, then the quotient is not incremented. When the result sign changes to negative, subtraction is replaced by addition.
This is repeated with decreasing degrees of deuce until a degree equal to zero is reached. The remainder is the last positive result. For example we divide 125 by 11. The divisor is  byte (11 <255), so start with 2⁷. At the beginning of the calculation, the quotient is always 0

Action	|	comments
------------------	+	-------------------------------------------------
125-11*27=-1283	|
-1283+11*26=-579	|
-579+11*25=-227	|
-227+11*24=-51	|
-51+11*23=37	|	The result is positive, so we add 23 to a quotient, the quotient is 0 + 8 = 8
37-11*22=-7	|
-7+11*21=15	|	The result is positive, so we add 21 to a quotient, the quotient is 8 + 2 = 10
15-11*20=4	|	The result is positive, so we add 20 with the quotient, the quotient is 10 + 1 = 11, the remainder is 4

Slightly accelerate the process of division
2⁷>125>2⁶ 2⁴>11>2³ 7-3=4

Action	|	comments
125-11*24=-51	|
-51+11*23=37	|	0+8=8
37-11*22=-7	|
-7+11*21=15	|	8+2=10
15-11*20=4	|	the quotient is 10 + 1 = 11, the remainder is 4

Code Select Expand

   mov edx,dividend
   bsr ecx,edx
   mov ebx,divisor
   bsr eax,ebx ; So as not to do unnecessary operations, 
   sub ecx,eax ; we determine the digits of the dividend
   mov ebp,1 ; and the divisor
   shl ebp,cl
   shl ebx,cl
   xor eax,eax; in EAX place for quotient, in EDX - remainder
   or esi,-1
@@: mov edi,ebx
   add edi,esi
   xor edi,esi; neg edi
   add edx,edi; if esi=-1 then edx:=edx-ebx else edx:=edx+ebx
   sbb esi,esi; if CF=1 then esi:=-1 else esi:=0
   mov edi,esi
   and edi,ebp; if esi=-1 then edi:=ebp else edi:=0
   add eax,edi; if esi=-1 then eax:= eax + ebp
   test edx,edx
   jz exit
   shr ebx,1
   shr ebp,1
   jnz @b
exit: