### Author Topic: Math question: How can I divide by 3?  (Read 891 times)

#### mineiro

• Member
• Posts: 365
##### Math question: How can I divide by 3?
« on: August 15, 2017, 01:30:06 AM »
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.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

#### jj2007

• Member
• Posts: 8081
• Assembler is fun ;-)
##### Re: Math question: How can I divide by 3?
« Reply #1 on: August 15, 2017, 01:46:12 AM »
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

• Member
• Posts: 674
##### Re: Math question: How can I divide by 3?
« Reply #2 on: August 15, 2017, 02:45:53 AM »
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

• Member
• Posts: 1086
• Let's Make ASM Great Again!
##### Re: Math question: How can I divide by 3?
« Reply #3 on: August 15, 2017, 03:07:54 AM »
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

• Member
• Posts: 365
##### Re: Math question: How can I divide by 3?
« Reply #4 on: August 15, 2017, 04:02:37 AM »
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.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

#### rrr314159

• Member
• Posts: 1381
##### Re: Math question: How can I divide by 3?
« Reply #5 on: August 15, 2017, 01:51:51 PM »
@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.
I am NaN

#### Mikl__

• Member
• Posts: 591
##### Re: Math question: How can I divide by 3?
« Reply #6 on: August 15, 2017, 04:13:25 PM »
Y/3=?    1/3=21845/216   Y/3=(Y*21845)/216

#### mineiro

• Member
• Posts: 365
##### Re: Math question: How can I divide by 3?
« Reply #7 on: August 15, 2017, 09:41:49 PM »
Thank you for the answers and tips.
The 2 complement stayed in limbo for years, it was worthless when it was invented.
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.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

#### Mikl__

• Member
• Posts: 591
##### Re: Math question: How can I divide by 3?
« Reply #8 on: August 16, 2017, 01:31:55 AM »
Olá, mineiro!
Leia aqui sobre a divisão
« Last Edit: August 16, 2017, 02:38:26 PM by Mikl__ »

#### mineiro

• Member
• Posts: 365
##### Re: Math question: How can I divide by 3?
« Reply #9 on: August 16, 2017, 06:42:27 AM »
привет сэр Mikl__
Спасибо за ссылки, я читаю их сейчас.
братские объятия.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

#### tenkey

• Regular Member
• Posts: 10
##### Re: Math question: How can I divide by 3?
« Reply #10 on: August 20, 2017, 09:19:38 AM »
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__

• Member
• Posts: 591
##### Re: Math question: How can I divide by 3?
« Reply #11 on: August 20, 2017, 10:50:31 AM »
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 2N is equivalent to shifting this number by N digits to the left. If the sign of the result is positive, then add 2N 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 27. 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
27>125>26 24>11>23 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]
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
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:
« Last Edit: August 21, 2017, 02:46:06 AM by Mikl__ »