flat assembler
Message board for the users of flat assembler.

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

Author
Thread Post new topic Reply to topic
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
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:
Image

THX, for your response, code and help;)
Post 20 Dec 2013, 02:01
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17478
Location: In your JS exploiting you and your system
revolution
What do you need help with? Or is this intended as finished code for others to use?
Post 20 Dec 2013, 02:05
View user's profile Send private message Visit poster's website Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
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
Post 20 Dec 2013, 14:12
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
bipocich,

That simply is a long division algorithm (binary version) on your flowchart. What part you have trouble to implement?
Post 20 Dec 2013, 15:59
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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?
Post 21 Dec 2013, 00:46
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17478
Location: In your JS exploiting you and your system
revolution
Hehe:
Code:
stdcall SlowDivide,0,0 ;what is the result?    
Post 21 Dec 2013, 00:51
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
Quote:
stdcall SlowDivide,0,0 ;what is the result?

I don't know yet - my computer is still working on that one...
Post 21 Dec 2013, 00:55
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17478
Location: In your JS exploiting you and your system
revolution
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.
Post 21 Dec 2013, 01:05
View user's profile Send private message Visit poster's website Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
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
Post 21 Dec 2013, 02:25
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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    
Post 21 Dec 2013, 02:46
View user's profile Send private message Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
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.
Post 23 Dec 2013, 15:25
View user's profile Send private message Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
revolution wrote:
Hehe:
Code:
stdcall SlowDivide,0,0 ;what is the result?    

I don't know Wink
revolution, you can try Very Happy
Post 23 Dec 2013, 15:26
View user's profile Send private message Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
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
Post 23 Dec 2013, 15:31
View user's profile Send private message Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
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>
Post 23 Dec 2013, 15:44
View user's profile Send private message Reply with quote
HaHaAnonymous



Joined: 02 Dec 2012
Posts: 1180
Location: Unknown
HaHaAnonymous
[ Post removed by author. ]


Last edited by HaHaAnonymous on 28 Feb 2015, 18:55; edited 1 time in total
Post 23 Dec 2013, 15:57
View user's profile Send private message Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
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: 245 Time(s)

Post 23 Dec 2013, 21:05
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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     
Post 28 Dec 2013, 04:35
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
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    
Post 28 Dec 2013, 16:54
View user's profile Send private message Reply with quote
bipocich



Joined: 17 Nov 2013
Posts: 18
bipocich
tthsqe wrote:
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     



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 ;

    
Post 09 Jan 2014, 01:53
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.