It is currently Fri Apr 10, 2020 3:07 am

 All times are UTC

 Page 2 of 2 [ 21 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Posted: Fri Feb 03, 2006 8:10 pm

Joined: Mon Jan 16, 2006 3:04 pm
Posts: 7
ok, i misunderstood your scheme then
i thought that word A was that highest 0000 and that it shouldn't be included when dividing, but rather combine that FFFD as the highest word and then put the middle word from 48 bit as the low word in that 32 register which would then be FFFD 0002

thanks again for it, you're the man lee, now i can finally give that assignment

Top

 Post subject: Posted: Sat Feb 04, 2006 12:32 pm

Joined: Mon Dec 27, 2004 11:40 pm
Posts: 318
The first divide you do in this sort of routine should always be small enough to never overflow a 16 bit result. The easiest way to ensure that is to make the first divide into \$0000xxxx where xxxx is the highest 16 bits of your number.

Ok last bit of huge ASCII art on this, this is to divide a 48 bit number by 10 leaving a 48 bit result and a 0 to 9 remainder (which is the next digit).

Code:
|       64 bit very long word       |
|                 |
V                 V
| 32 bit longword | 32 bit longword |
|        |        |        |
V        V        V        V
| word A | word B | word C | word D |   word A always \$0000
|        |        |
V        |        |
|  \$0000 | word B |   |        |
divide by         |     10 |   |        |
-------------------   |        |
| remain |result h|   |        |
swap words                     |        |
|result h| remain |   |        |
|        |        |        |
|        V        V        |
|    | remain | word C |   |
divide by    |             |     10 |   |
|    -------------------   |
|    | remain | result |   |
swap words   |                          |
|    |result m| remain |   |
|        |        |        |
|        |        V        V
|        |    | remain | word D |
divide by    |        |             |     10 |
|        |    -------------------
|        |    | remain |result l|
swap words   |        |
|        |    |result l| remain | -> remainder is digit
|        |        |
V        V        V
|result h|result m|result l|
|        |        |
V        V        V
| word A | word B | word C | word D |   for next divide

Lee.

Last edited by lee on Sun Feb 05, 2006 4:37 pm, edited 4 times in total.

Top

 Post subject: Posted: Sun Feb 05, 2006 4:39 pm

Joined: Mon Dec 27, 2004 11:40 pm
Posts: 318
There were more corrections to do than that but, as I was having a very hard time connecting, I gave up.

All fixed now, I think.

Lee.

Top

 Post subject: Posted: Thu Feb 09, 2006 3:01 am

Joined: Thu Feb 09, 2006 2:57 am
Posts: 1
I only registered to thank you all. I had the same assignment as Velorien.
And this thread helped me a lot.

And I guess you're going to have lots of Croats around here in the near future.

Thanks again!

Dino

Top

 Post subject: Posted: Sat Mar 19, 2011 10:31 pm

Joined: Mon Jul 26, 2010 11:43 pm
Posts: 198
Location: Aurora, IL
Code:
*------------------------------------
* Decimal conversion and 64-bit division example
*  clive@tbcnet.com  cturvey@gmail.com
*------------------------------------

org     \$400

* Program starts here

start

move.l  #12345,d0
lea     buffer,a0
bsr     dec16
bsr     puts

move.l  #1234567890,d0
lea     buffer,a0
bsr     dec32
bsr     puts

move.l  #\$FFFFFFFF,d0 ; d1:d0 = 64-bit
move.l  #\$FFFFFFFF,d1
lea     buffer,a0
bsr     dec64
bsr     puts

MOVE.L  #9,D0
TRAP    #15     ; halt simulator

*------------------------------------
* Convert 16-bit binary to decimal

; D0=binary number (0-65,535), Assume High Order Zero, Real Limit (0-655,359)
; A0=string output address

dec16   movem.l d0-d1/a0,-(a7)  ; Save D0,D1,A0
move.w  #0,-(a7)        ; Push NUL End-Of-Stack marker
loop1   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
move.l  d0,d1           ; Copy to split quotient and remainder
swap    d1              ; Get remainder in D1:LOW
add.w   #\$30,d1         ; Add ASCII '0' to 0-9 digit
move.w  d1,-(a7)        ; Push Digit, number built backward
and.l   #\$FFFF,d0       ; D0:HIGH = 0
bne     loop1           ; until D0 = 0

; Now unstack reverse decimal built on stack

loop2   move.w  (a7)+,d1        ; unstack next digit
move.b  d1,(a0)+        ; copy into output string buffer
bne     loop2           ; Until NUL unstacked

movem.l (a7)+,d0-d1/a0  ; Restore D0,D1,A0
rts

*------------------------------------
* Convert 32-bit binary to decimal

; D0=binary number (0-4,294,967,295)
; A0=string output address

dec32   cmp.l   #655360,d0      ; Use 16-bit routine if in range
bcs     dec16           ; unsigned less than 655,360

; At least 6 significant digits

movem.l d0-d3/a0,-(a7)  ; Save D0,D1,D2,D3,A0

move.w  #0,-(a7)        ; Push NUL End-Of-Stack marker

move.l  d0,d2           ; Save original D0 for remainder computation

; Improve 68K efficiency by using 16-bit divides, beware
;  the student that blindly copies this code. It was written
;  by someone who knows what they are doing.

lsr.l   #1,d0           ; / 2
move.w  #50000,d1       ;   50000
divu    d1,d0           ; / 100000, ie (50000 * 2)
and.l   #\$FFFF,d0       ; Mask quotient
mulu    d0,d1           ; D1 = D0 * 50000
sub.l   d1,d2           ; back out quotient twice for remainder
sub.l   d1,d2           ; D2 -= D0 * 100000

; The preceeding sequence effectively performs a divide
;  beyond the scope of a single 16-bit hardware divide.

; D0 = D0 / 100000, D2 = D0 % 100000

move.l   #5-2,d3        ; D3 = 5 Least significant digits

loop3   divu    #10,d2          ; D2:LOW = D2/10, D2:HIGH = D2%10
move.l  d2,d1           ; Copy to split quotient and remainder
swap    d1              ; Get remainder in D1:LOW
add.w   #\$30,d1         ; Add ASCII '0' to 0-9 digit
move.w  d1,-(a7)        ; Push Digit, number built backward
and.l   #\$FFFF,d2       ; D2:HIGH = 0
dbra    d3,loop3        ; until 5 digits
add.w   #\$30,d2         ; Add ASCII '0' to 0-9 digit
move.w  d2,-(a7)        ; Push Digit, number built backward

; Most significant 1-5 digits

loop4   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
move.l  d0,d1           ; Copy to split quotient and remainder
swap    d1              ; Get remainder in D1:LOW
add.w   #\$30,d1         ; Add ASCII '0' to 0-9 digit
move.w  d1,-(a7)        ; Push Digit, number built backward
and.l   #\$FFFF,d0       ; D0:HIGH = 0
bne     loop4           ; until D0 = 0

loop5   move.w  (a7)+,d1        ; unstack next digit
move.b  d1,(a0)+        ; copy into output string buffer
bne     loop5           ; Until NUL unstacked

movem.l (a7)+,d0-d3/a0  ; Restore D0,D1,D2,D3,A0
rts

*------------------------------------
* Convert 64-bit binary to decimal

; D1:D0=binary number (0-18,446,744,073,709,551,615)
; A0=string output address

dec64   or.l    d1,d1           ; Use 32-bit routine if in range
beq     dec32           ; unsigned less than 4,294,967,296

movem.l d0-d5/a0,-(a7)  ; Save

move.l  d1,d2           ; Map to registers used by the 64-bit divides
move.l  d0,d1           ; D2:D1 - 64-bit number

move.l  #10000,d3       ; Divisor constant for 16-bit 4-digit multiples

move.w  #0,-(a7)        ; Push NUL End-Of-Stack marker
loop6
bsr     div6416         ; D2:D1 = D2:D1 / 10000, D0 = D2:D1 % 10000
move.l  d1,d4           ; 64-bit quotient test
or.l    d2,d4
beq     loop8           ; quotient zero, final digits

move.w  #4-2,d4         ; 4 digits (final /10 not required)
loop7   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
move.l  d0,d5           ; Copy to split quotient and remainder
swap    d5              ; Get remainder in D5:LOW
add.w   #\$30,d5         ; Add ASCII '0' to 0-9 digit
move.w  d5,-(a7)        ; Push Digit, number built backward
and.l   #\$FFFF,d0       ; D0:HIGH = 0
dbra    d4, loop7
add.w   #\$30,d0         ; Add ASCII '0' to 0-9 digit
move.w  d0,-(a7)        ; Push Digit, number built backward
or.l    d2,d2           ; High order empty?
bne     loop6           ; Still 64-bit wide
bsr     div3216         ; Otherwise 32-bit, D1 = D1 / 10000, D0 = D1 % 10000
move.w  #4-2,d4         ; 4 digits
or.l    d1,d1           ; 32-bit quotient test
bne     loop7           ; Non-zero quotient, another group

; Most significant 1-4 digits

loop8   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
move.l  d0,d5           ; Copy to split quotient and remainder
swap    d5              ; Get remainder in D5:LOW
add.w   #\$30,d5         ; Add ASCII '0' to 0-9 digit
move.w  d5,-(a7)        ; Push Digit, number built backward
and.l   #\$FFFF,d0       ; D0:HIGH = 0
bne     loop8           ; While any digits remain

loop9   move.w  (a7)+,d1        ; unstack next digit
move.b  d1,(a0)+        ; copy into output string buffer
bne     loop9           ; Until NUL unstacked

movem.l (a7)+,d0-d5/a0  ; Restore
rts

*------------------------------------
; Divide 64-bit by 16-bit
;
; D1[32] = D1[32] / D3[16]
; D0[16] = D1[32] % D3[16]
; D3 Preserved
;
; Algorithm
;
; A B / X = C D, and A B % X = d (each digit is 16-bit word)
;
; The remainder cascades down the chain of divides
;
; Where C = A / X, c = A % X
;       D = ((c << 16) + B) / X, d = ((c << 16) + B) % X
;
; The final remainder is that for the entire division chain

div3216 move.l  d4,-(a7)        ; Save D4
move.w  d1,d4           ; D1 = A:B, D4:LOW = B
clr.w   d1              ; D1:LOW = 0
swap    d1              ; D1:LOW = A, D1:HIGH = 0
divu.w  d3,d1           ; D1:LOW = 0:A/X (C), D1:HIGH = 0:A%X (c)
move.l  d1,d0           ; D0:LOW = C, D0:HIGH = c
swap    d1              ; D1:LOW = c, D1:HIGH = C
move.w  d4,d0           ; D0:LOW = B (D0:HIGH = c)
divu.w  d3,d0           ; D0:LOW = c:B/X (D), D0:HIGH = c:B%X (d)
move.w  d0,d1           ; D1:LOW = D (D1:HIGH = C) - Final C:D
clr.w   d0              ; D0:LOW = 0
swap    d0              ; D0:LOW = c:B%X (d), D0:HIGH = 0 - Remainder 0:d
move.l  (a7)+,d4        ; Restore D4
rts

*------------------------------------
; Divide 64-bit by 16-bit
;
; D2:D1[64] = D2:D1[64] / D3[16]
; D0[16]    = D2:D1[64] % D3[16]
; D3 Preserved
;
; Algorithm
;
; A B C D / X = E F G H, and A B C D % X = h (each digit is 16-bit word)
;
; The remainder cascades down the chain of divides
;
; Where E = A / X, e = A % X
;       F = ((e << 16) + B) / X, f = ((e << 16) + B) % X
;       G = ((f << 16) + C) / X, g = ((f << 16) + C) % X
;       H = ((g << 16) + D) / X, h = ((g << 16) + D) % X
;
; The final remainder is that for the entire division chain
;
; The observation is that (((V % X) << 16) + W) / X will always fit in 16-bits
;  and the cascades can be extended to 128-bits, or whatever extent required.
; On the 68020 you could evolve the divides to 32-bit longs.
;
; The 16-bit divisor works well for decimals, specifically 10 (1 digit) or 10000 (4 digits)
;  The remainder from a 10000 divide, permits 4 digits to be printed with intrinsic DIVU's

div6416 move.l  d4,-(a7)        ; Save D4
move.w  d2,d4           ; D2 = A:B, D4:LOW = B
clr.w   d2              ; D2:LOW = 0
swap    d2              ; D2:LOW = A, D2:HIGH = 0
divu.w  d3,d2           ; D2:LOW = 0:A/X (E), D2:HIGH = 0:A%X (e)
move.l  d2,d0           ; D0:HIGH = e, D0:HIGH = E
swap    d2              ; D2:HIGH = E - Save
move.w  d4,d0           ; D0:LOW = B (D0:HIGH = e)
divu.w  d3,d0           ; D0:LOW = e:B/X (F), D0:HIGH = e:B%X (f)
move.w  d0,d2           ; D2:LOW = F (D2:HIGH = E) - Final E:F
swap    d0              ; D0:HIGH = F, D0:LOW = f
move.w  d1,d4           ; D1 = C:D, D4:LOW  = D
move.w  d0,d1           ; D1:LOW = f (D1:HIGH = C)
swap    d1              ; D1:HIGH = f, D1:LOW = C
divu.w  d3,d1           ; D1:LOW = f:C/X (G), D1:HIGH = f:C%X (g)
move.l  d1,d0           ; D0:HIGH = g, D0:LOW = G
swap    d1              ; D1:HIGH = G - Save
move.w  d4,d0           ; D0:LOW = D, D0:HIGH g
divu.w  d3,d0           ; D0:LOW = g:D/X (H), D0:HIGH = g:D%X (h)
move.w  d0,d1           ; D1:LOW = H (D1:HIGH = G) - Final G:H
clr.w   d0              ; D0:LOW = 0
swap    d0              ; D0:LOW = g:D%X (h), D0:HIGH = 0 - Remainder 0:h
move.l  (a7)+,d4        ; Restore D4
rts

*------------------------------------
* Subroutine to display NUL terminated string

outstr  movem.l d0/a0-a1,-(a7)
move    #14,d0          ; task number into D0
move    a0,a1
trap    #15             ; display string
movem.l (a7)+,d0/a0-a1
rts

*------------------------------------

puts    movem.l d0/a0-a1,-(a7)
move    #14,d0          ; task number into D0
move    a0,a1
trap    #15             ; display string
lea     crlf,a1
trap    #15
movem.l (a7)+,d0/a0-a1
rts

crlf    dc.b    13,10,0,0

*------------------------------------

buffer  ds.b    30

end start

Top

 Post subject: 68000 multiple-precision divisionPosted: Wed Jan 15, 2014 4:37 am

Joined: Tue Nov 15, 2005 7:58 am
Posts: 129
Location: Oregon, USA
Lee (or anybody) -- can you point me to any methods to divide by arbitrary numbers bigger than a word and that make good use of 68000 hardware? Ones possibly that don't require trial divisors?
I'm familiar with one-bit-per-iteration methods, but I'm hoping for something more efficient, but not as complex as say FFTs, elliptic curves, or other exotica.

Thanks much.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 21 posts ] Go to page Previous  1, 2

 All times are UTC

#### Who is online

Users browsing this forum: No registered users and 4 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ EASy68K Forum    FAQ    Latest Features    EASy68K Questions    68000 Programming Questions    Wish List    Wishes Granted    Undocumented Features    Documented Features    General Discussion    EASy68K Projects