Dividing two numbers (sign module).

Index > DOS > Dividing two numbers (sign module).

Author

Thread

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 20 Dec 2013, 02:01

Hello!
I have two sign module numbers.

Code:

segment dane
number1 db '     $'
number2 db '     $'
number3 db '     $'

This is a code to get a numbers (number one - example, number two is the same):

Code:

macro get_hex
{
local check1, letter_s, letter_b, digit, good
 check1:
        mov ah,07
        int 21h

        cmp al,'0'
        jb check1
        cmp al,'9' 
        jbe digit 
        cmp al,'A' 
        jb check1
        cmp al,'F' 
        jbe letter_b 
        cmp al,'a' 
        jb check1
        cmp al,'f' 
        ja check1
letter_s:        
        push ax 
        mov dl,al       ;view
        mov ah,2 
        int 21h 
        pop ax        
        sub al,87 
        jmp good
letter_b:          
        push ax 
        mov dl,al       ;view
        mov ah,2 
        int 21h 
        pop ax        
        sub al,55 
        jmp good
digit:           
        push ax 
        mov dl,al       ;view
        mov ah,2 
        int 21h 
        pop ax        
        sub al,30h ; 48 
good:
        mov ah,0


}

Code:

get_sign1:


mov cx,5
mov si,0

check_number:

get_hex
shl al,4
mov byte [number1+si],al
get_hex
;add al, byte [number1+si]
add byte [number1+si],al




inc si
dec cx
cmp cx,0
jz next1
jmp check_number


next1:

call main1

This is example algorithm:

THX, for your response, code and help;)

20 Dec 2013, 02:01

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20453
Location: In your JS exploiting you and your system

revolution 20 Dec 2013, 02:05

What do you need help with? Or is this intended as finished code for others to use?

20 Dec 2013, 02:05

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 20 Dec 2013, 14:12

revolution THX for your very quick response Wink

In wrote the code for this part of the job (dividing two numbers - sign module).

No, this is a education project on my University.
I wrote code in following algorithm

Code:

result = 0;
while ( nb1 > nb2)
{ nb1 = nb1 - nb2;
result ++;
}

but this algorithm it isn't optimal and I need change it.
But I don't know how I can implement it... Crying or Very sad

20 Dec 2013, 14:12

baldr

Joined: 19 Mar 2008
Posts: 1651

baldr 20 Dec 2013, 15:59

bipocich,

That simply is a long division algorithm (binary version) on your flowchart. What part you have trouble to implement?

20 Dec 2013, 15:59

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 21 Dec 2013, 00:46

biopocich, the c function:

Code:

unsigned int SlowDivide(unsigned int nb1, unsigned int nb2)
{
  unsigned int result = 0; 
  while ( nb1 > nb2) 
  { nb1 = nb1 - nb2; 
    result ++; 
  } 
  return result
}

can be compiled as

Code:

SlowDivide: 
          or  rax,-1
    @@:  add  rax,1
         sub  rcx,rdx
         jnc  @b
         ret

call the function as

Code:

     stdcall  SlowDivide,7,2
                        ; quotient now in rax  (3)

To speed things up, who not use the idiv instruction?

21 Dec 2013, 00:46

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20453
Location: In your JS exploiting you and your system

revolution 21 Dec 2013, 00:51

Hehe:

Code:

stdcall SlowDivide,0,0 ;what is the result?

21 Dec 2013, 00:51

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 21 Dec 2013, 00:55

Quote:

stdcall SlowDivide,0,0 ;what is the result?

I don't know yet - my computer is still working on that one...

21 Dec 2013, 00:55

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20453
Location: In your JS exploiting you and your system

revolution 21 Dec 2013, 01:05

tthsqe wrote:

Quote:
stdcall SlowDivide,0,0 ;what is the result?

I don't know yet - my computer is still working on that one...

Come back to us when it is finished. Make sure you stay watching it while waiting, you wouldn't want to miss the answer. I think the computer will do it faster if you hold your breath.

21 Dec 2013, 01:05

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 21 Dec 2013, 02:25

baldr wrote:

bipocich,

That simply is a long division algorithm (binary version) on your flowchart. What part you have trouble to implement?

baldr, THX for your response Wink

Yes. All part division I have a problem (implement this algorithm http://i.stack.imgur.com/sqRmX.png).

Look the following links, I have other projects with like topic:
http://board.flatassembler.net/topic.php?t=15958
http://board.flatassembler.net/topic.php?t=16089

21 Dec 2013, 02:25

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 21 Dec 2013, 02:46

biopocich, in your png, the statements "Count = N" and "Shift Left A,Q" don't make sense to me. What is N? Does "Shift Left A,Q" mean "A<<=1; Q<<=1;"?

Edit: Here are some unsigned algorithms. If you want to support signed division, you are going to have to specify where the remainder may lie. Also, you might have to change BITS and some of the cmov's if the processor mode is not so generous.

Code:

; both of these algorithms have operational complexity proportional to BITS
use64
BITS = 64    ; number of bits in our unsigned integers
UnsignedSqrt: ; rax = floor of sqrt of rcx
        xor  eax,eax
        mov  r8,rcx
        mov  ecx,BITS/2-1
        lea  rdx,[rax+1]
        shl  rdx,cl
@@:     mov  r10,r8
        lea  r9,[rdx+2*rax]
        shl  r9,cl
        lea  r11,[rax+rdx]
        sub  r10,r9
     cmovns  rax,r11
     cmovns  r8,r10
        shr  rdx,1
        sub  ecx,1
        jns  @b
        ret

UnsignedDivide: ; rax & rdx = quotient & remainder from rcx / rdx
        mov  r9,rdx
        xor  eax,eax
        xor  edx,edx
        mov  r8d,BITS
@@:     shl  rcx,1
        adc  rdx,rdx
        mov  r10,rdx
        sub  r10,r9
     cmovnc  rdx,r10
        cmc
        adc  rax,rax
        sub  r8d,1
        jnz  @b
        ret

Usage:
    stdcall  UnsignedSqrt,10
      ; rax = 3
    stdcall  UnsignedDivide,71,13
      ; rax = 5
      ; rdx = 6

21 Dec 2013, 02:46

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 23 Dec 2013, 15:25

tthsqe, THX for you response, code and comments Wink

1. I know that it is c function.
I wanted show more clear algorithm.
C code is more clear than Assembler code.
I think you agree with me??:>

2. WoW, is very simle and short codeXD

3. Why stdcall than call?

Good to know.
However, it seems to me that I can not use it in my task.

23 Dec 2013, 15:25

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 23 Dec 2013, 15:26

revolution wrote:

Hehe:

Code:

stdcall SlowDivide,0,0 ;what is the result?

I don't know Wink

revolution, you can try Very Happy

23 Dec 2013, 15:26

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 23 Dec 2013, 15:31

tthsqe wrote:

Quote:
stdcall SlowDivide,0,0 ;what is the result?

I don't know yet - my computer is still working on that one...

tthsqe, you have VERY SLOW computer, you should change it (Commodore 64 is too old for this application)XD Wink

23 Dec 2013, 15:31

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 23 Dec 2013, 15:44

revolution wrote:

tthsqe wrote:

Quote:
stdcall SlowDivide,0,0 ;what is the result?

I don't know yet - my computer is still working on that one...
Come back to us when it is finished. Make sure you stay watching it while waiting, you wouldn't want to miss the answer. I think the computer will do it faster if you hold your breath.

revolution <y>
WoW, tthsqe, computer is calculating result 3 daysXD

Quote:

I think the computer will do it faster if you hold your breath.

<y>

23 Dec 2013, 15:44

HaHaAnonymous

Joined: 02 Dec 2012
Posts: 1178
Location: Unknown

HaHaAnonymous 23 Dec 2013, 15:57

[ Post removed by author. ]

Last edited by HaHaAnonymous on 28 Feb 2015, 18:55; edited 1 time in total

23 Dec 2013, 15:57

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 23 Dec 2013, 21:05

Hello tthsqe,
THX for your response, very hard code and questions Very Happy

Quote:

biopocich, in your png, the statements "Count = N" and "Shift Left A,Q" don't make sense to me. What is N? Does "Shift Left A,Q" mean "A<<=1; Q<<=1;"?

tthsqe, it is not my png. I post example algorithm from the Internet. I don't know Sad

I did not analyze it deeply.

My algorithm scheme is in attachment Wink

2. Okay tthsqe, THX. Hmm, I understand a bit.
Processor in my task is 8086.

tthsqe, Thank you very much for your code.
But I understand it a bit.
Look at this url, please:
http://www.m.rydel.po.opole.pl/index.php?option=com_remository&Itemid=75&func=startdown&id=9
This is a list of commands that I know of and know how use them.

For example I don't know what's do "@@:" or "eax,eax".
My level of knowledge of Assembler is very low.

Beautifully Thank you for your help.
If you can, please describe what is happening in this code.

Description:	Algorithm scheme	Download
Filename:	Schemat.pdf
Filesize:	21.17 KB
Downloaded:	2148 Time(s)

23 Dec 2013, 21:05

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 28 Dec 2013, 04:35

bipocich, sorry I have been away for a while. I will try to address your questions and write some code and describe what each instruction does so that you can learn more easily. I'll also keep down to 8086 so BITS = 16 then.

Code:

Unsigneddivide:
   ; in this function we hope - without using idiv - to accomplish:
   ; ax = quotient from arg1 / arg2
   ; dx = remainder from arg1 / arg2
       push  si di bx          ; these registers are supposed to be saved by function
        mov  si,word[sp+2*4]   ; fetch the first argument (numerator) into si
        mov  di,word[sp+2*5]   ; fetch the second srgument (denominator) into di
        xor  ax,ax             ; set ax (eventual quotient) to 0
        xor  dx,dx             ; set dx (eventual remainder) to 0
        mov  cx,16             ; cx will be our loop counter
.1:     add  si,si             ; shifts si to the left one bit, and shift msb into carry flag
        adc  dx,dx             ; shifts dx to the left one bit, and shift carry flag into lsb of dx
        mov  bx,dx             ;
        sub  bx,di             ; bx = dx - di
         jc  .2                ; do not execute the next instruction if dx < di
        mov  dx,bx             ;
.2:     cmc                    ; complement the carry flag
        adc  ax,ax             ; and shift the new carry flag into ax
       loop  .1                ; loop to .1 a total of BITS times
        pop  bx di si          ; restore the nonvolatile registers
        ret                    ; or ret 4 if you are supposed to clean the stack - not sure about convention


; at a higher level this might looks something like:
;
;UnsignedDivide(si,di):
;   ax = dx = 0;
;   repeat 16 times
;       do a 32 bit multiprecision left shift on si:dx
;       if  dx >= di
;       then
;           dx = dx - di
;           left shift 1 into lsb of ax
;       else
;           left shift 0 into lsb of ax
;       end if
;   end repeat
;   return ax:dx

28 Dec 2013, 04:35

tthsqe

Joined: 20 May 2009
Posts: 767

tthsqe 28 Dec 2013, 16:54

bipocich, the algorithm I just posted is the usual grade-school algorithm. The one you posted in your schemat is also correct and I am in the process of proving it. Once I figure out how it works, i'll let you know.
Edit:
let QR(n,d,k) denote the quotient and remainder from n/d given that n < d<<(k+1). QR(n,d,k) returns a list {q,r}, and lists are added pointwise {a,b}+{c,d}={a+c,b+d}.
Here is code for QR:

Code:

QR(n, d, k):
  if n >= d<<(k+1)
    error
  else if k < 0
    return {0, n}  
  else if n < d<<k 
    return QR(n, d, k-1)
  else           
    return {1<<k, 0} + QR(n - d<<k, d, k-1)
  end if

Here is code for idiv:

Code:

idiv(n, d):
  k = 0
  while (d<<k) < (n>>1)
    k++
  end while
  return QR(n, d, k)

The correctness of QR and idiv should be clear, and the equivalence of the two to your flow chart should also be clear. In your flow chart, the remainder is in dividend and the quotient is in result when the function returns. The only difference is that your flow chart computes the maximal k, while my idiv computes the optimal k. Neither of them will overflow a register, though. Now, to compile to 8086:

Code:

idiv:
       push  di bx
        mov  ax,word[sp+2*3]   ; arg1
        mov  di,word[sp+2*4]   ; arg2
        shr  ax,1
        xor  cx,cx
        jmp  .2
.1:     add  di,di
        add  cx,1
.2:     cmp  di,ax
         jb  .1
        xor  ax,ax
        mov  dx,word[sp+2*3]   ; arg1
.3:     mov  bx,dx
        sub  bx,di
         jc  .4
        mov  dx,bx
.4:     cmc  
        adc  ax,ax
        shr  di,1
        sub  cx,1
        jns  .3
        pop  bx di
        ret

28 Dec 2013, 16:54

bipocich

Joined: 17 Nov 2013
Posts: 18

bipocich 09 Jan 2014, 01:53

tthsqe wrote:

Code:

Unsigneddivide:
   ; in this function we hope - without using idiv - to accomplish:
   ; ax = quotient from arg1 / arg2
   ; dx = remainder from arg1 / arg2
       push  si di bx          ; these registers are supposed to be saved by function
        mov  si,word[sp+2*4]   ; fetch the first argument (numerator) into si
        mov  di,word[sp+2*5]   ; fetch the second srgument (denominator) into di
        xor  ax,ax             ; set ax (eventual quotient) to 0
        xor  dx,dx             ; set dx (eventual remainder) to 0
        mov  cx,16             ; cx will be our loop counter
.1:     add  si,si             ; shifts si to the left one bit, and shift msb into carry flag
        adc  dx,dx             ; shifts dx to the left one bit, and shift carry flag into lsb of dx
        mov  bx,dx             ;
        sub  bx,di             ; bx = dx - di
         jc  .2                ; do not execute the next instruction if dx < di
        mov  dx,bx             ;
.2:     cmc                    ; complement the carry flag
        adc  ax,ax             ; and shift the new carry flag into ax
       loop  .1                ; loop to .1 a total of BITS times
        pop  bx di si          ; restore the nonvolatile registers
        ret                    ; or ret 4 if you are supposed to clean the stack - not sure about convention


; at a higher level this might looks something like:
;
;UnsignedDivide(si,di):
;   ax = dx = 0;
;   repeat 16 times
;       do a 32 bit multiprecision left shift on si:dx
;       if  dx >= di
;       then
;           dx = dx - di
;           left shift 1 into lsb of ax
;       else
;           left shift 0 into lsb of ax
;       end if
;   end repeat
;   return ax:dx

tthsqe, Thank you for your time.
But how can I move result dividing to number3?

Code:

divide:
        push si di bx 
        mov si, word[number1+2*4] 
        mov di, word[number2+2*5] 
        xor ax, ax 
        xor dx, dx 
        mov cx, 16
one_arg:
        add si, si 
        adc dx, dx 
        mov bx, dx
        sub bx, di 
        jc two_arg 
        mov dx,bx
two_arg:
        cmc 
        adc ax,ax 
        loop one_arg 

;At this place?
; But how??:>
;        mov [number3],ah
;        mov [number3+3],al

        pop bx di si ;

09 Jan 2014, 01:53

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum