Good idea. Usually this trick is not useful for integer division, because the dividend is usually used for storing the result (dividend and quotient sharing the same location). But here we have a separate memory for output, so it works! Using the trick, 3 words / 3 cycles / 1 register are saved. I just had to correct the bit you set, it should have been c0.1. ;----------------------------------------------------------------------------- ; Input: ; a1:a0 - 10 bit dividend ; b1:b0 - 15 bit divisor in 7Q8 format (b1 is integer, b0 is ; fractional) ; Output: ; c1:c0 - 15 bit quotient in 7Q8 format ; ; Size: 27 words ; Time: 2+3+3+15*(2+3+7+5)-1+2=264 instruction cycles ; ;----------------------------------------------------------------------------- div_uint10_fxp7q8_fxp7q8 ;left align the dividend ; (shift accumulator left 1 bit to get the first result bit weight ; equal to 128) clrc rlf a0, f rlf a1, f ;carry is cleared here ;initialize registers clrf c0 ;clear result - it will be used clrf c1 ;to shift zeroes to dividend bsf c0, 1 ;15 iterations div_loop rlf a0, f ;and shift out next bit of dividend rlf a1, f ;to remainder movf b0, w ;load w with lower divisor byte skpnc ;if remainder positive - subtract, goto div_add ;if negative - add ;subract subwf a0, f movf b1, w skpc incfsz b1, w subwf a1, f goto div_next div_add ;add addwf a0, f movf b1, w skpnc incfsz b1, w addwf a1, f div_next ;here carry has a new result bit rlf c0, f ;shift in next result bit rlf c1, f skpc goto div_loop return ;----------------------------------------------------------------------------- This routine uses a non-restoring algorithm. The nice thing about it is that it doesn't require a comparison. Each iteration does either addition or subtraction, but never both. Therefore, it is almost two times faster comparing to the restoring algorithm. First, divisor is subtracted from dividend (lets call it the remainder). Depending on inputs/outputs types the divisor should be aligned relative to the remainder, so that the first result bit has an appropriate weight (128 in our case), but let's not go into that, this is exactly how it is always done in a division. If the remainder becomes negative after subtraction, the next result bit should be zero. This is the value of carry after subtraction, which is convenient. Next iteration we shift the remainder left and add the divisor to it. This is equivalent to the restoring method, where divisor is added to remainder to restore it, then remainder shifted left, and divisor subtracted again. In both methods we add a divisor in fact. The result of two iterations is: 1) Non-restoring: remainder = remainder - divisor + divisor/2 = remainder - divisor/2 2) Restoring: remainder = remainder - divisor + divisor - divisor/2 = remainder - divisor/2 And carry flag is always set correct for addition and subtraction (subtraction is performed as addition internally, I guess). Don't you now love the way carry works in PICs! The routine works, I checked :) Thanks, Nikolai ---- Original Message ---- From: Scott Dattalo Sent: Wednesday, March 14, 2001 7:33:01 To: PICLIST@MITVMA.MIT.EDU Subj: [PIC]: math calibration algorithm ? > On Tue, 13 Mar 2001, Nikolai Golovchenko wrote: >> Just thought that once we have only 15 bits in divisor, the routine >> can be optimized quite a bit: > And there's another trick to optimize it further. But before going there, > I have a question. Why do you want to add the divisor (b) to the dividend > (a) when the msb of the dividend is set? In other words, when you shift the > dividend left and the carry get set, then yes, you unconditionally want to > perform the subtraction. However, if the carry doesn't get set then you need to > perform a comparison to see if dividend is less than the divisor. This > comparison can be a subtraction, but if it turns out that the dividend is not > greater than the subtraction has to be restored. Or am I'm missing something? > Let's assume that I don't undertand the algorithm and that what's below is > correct. Here's a cute trick to save a few cycles (I learned this one from Andy > Warren): >> >> ;----------------------------------------------------------------------------- >> ; Input: >> ; a1:a0 - 10 bit dividend (a0 - lower byte) >> ; b1:b0 - 15 bit divisor in 7Q8 format (b1 is integer, b0 is >> ; fractional) >> ; Output: >> ; c1:c0 - 15 bit quotient in 7Q8 format >> ; >> ; Temporary: >> ; count - counter >> ; >> ;----------------------------------------------------------------------------- >> div_uint10_fxp7q8_fxp7q8 >> >> ;left align the dividend >> ; (shift accumulator left 1 bit to get the first result bit weight >> ; equal to 128) >> clrc >> rlf a0, f >> rlf a1, f ;carry is cleared here >> ;initialize registers > Don't need a count register: ;>> movlw 15 ;15 iterations ;>> movwf count >> clrf c0 ;clear result - it will be used >> clrf c1 ;to shift zeroes to dividend > bsf c1,2 ; use c0:c1 as the counter after 15 shifts, this > ; bit will go to the carry. >> div_loop > move the c0:c1<<1 down below ;>> rlf c0, f ;shift in next result bit ;>> rlf c1, f >> rlf a0, f ;and shift out next bit of dividend >> rlf a1, f ;to remainder >> >> movf b0, w ;load w with lower divisor byte >> skpnc ;if remainder positive - subtract, >> goto div_add ;if negative - add >> ;subract >> subwf a0, f >> movf b1, w >> skpc >> incfsz b1, w >> subwf a1, f >> goto div_next >> div_add >> ;add >> addwf a0, f >> movf b1, w >> skpnc >> incfsz b1, w >> addwf a1, f >> div_next >> ;here carry has a new result bit > rlf c0, f ;shift in next result bit > rlf c1, f > Don't need this counter anymore: >> decfsz count, f >> goto div_loop > skpc ;did the "count" bit pop out? > goto div_loop > return > don't need this any more: >> ;shift in last result bit >> rlf c0, f >> rlf c1, f >> return >> ;----------------------------------------------------------------------------- > Scott > -- > http://www.piclist.com hint: The list server can filter out subtopics > (like ads or off topics) for you. See http://www.piclist.com/#topics -- http://www.piclist.com hint: The list server can filter out subtopics (like ads or off topics) for you. See http://www.piclist.com/#topics