flat assembler
Message board for the users of flat assembler.
Index
> DOS > Dividing two numbers (sign module). 
Author 

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


20 Dec 2013, 02:05 

bipocich
revolution THX for your very quick response
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... 

20 Dec 2013, 14:12 

baldr
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
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 } Code: SlowDivide: or rax,1 @@: add rax,1 sub rcx,rdx jnc @b ret 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
Hehe:
Code: stdcall SlowDivide,0,0 ;what is the result? 

21 Dec 2013, 00:51 

tthsqe
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
tthsqe wrote:


21 Dec 2013, 01:05 

bipocich
baldr wrote: bipocich, baldr, THX for your response 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
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/21 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
tthsqe, THX for you response, code and comments
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
revolution wrote: Hehe: I don't know revolution, you can try 

23 Dec 2013, 15:26 

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

23 Dec 2013, 15:31 

bipocich
revolution wrote:
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
[ 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
Hello tthsqe,
THX for your response, very hard code and questions 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 I did not analyze it deeply. My algorithm scheme is in attachment 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.


23 Dec 2013, 21:05 

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 

28 Dec 2013, 04:35 

tthsqe
bipocich, the algorithm I just posted is the usual gradeschool 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, k1) else return {1<<k, 0} + QR(n  d<<k, d, k1) 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
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. 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:

Copyright © 19992020, Tomasz Grysztar.
Powered by rwasa.