Author Topic: Math question: How can I divide by 3?  (Read 364 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: 7541
  • Assembler is fun ;-)
    • MasmBasic
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: 671
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: 697
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: 537
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.
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.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

Mikl__

  • Member
  • ****
  • Posts: 537
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: 537
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
   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:
« Last Edit: August 21, 2017, 02:46:06 AM by Mikl__ »