Integer Math Error
pjv
Posts: 1,903
Hi All;
For those who work with integer math, I just ran accross what I think is an error in one of the integer multiply routines on the SX List.
Typically mutiplication is performed by successive shifting of the multiplier, then if the shifted-out bit is a one,·adding the multiplicand to an accumulator. This works for precisions using any number of bytes, I believe the errant code was for a 24 bit example.
As the multiplicand is added to the muli-byte accumulator, the carry represents overflows from the current accumulator byte being summed, and must cascade as a "plus one" into the next higher accumulator byte. (This can be handled directly·by the processor·if the carryx extension is enabled,·then the programmer need not bother).
In the errant example, this adding of "one" is handled by loading·an incremented value of the multiplicand if the carry was set (MOV w,++MultiplicandByte), or the regular value of the mutiplicand if carry was not set (MOV w,MultiplicandByte), and adding this carry-adjusted value to the accumulator. All good so far.
The problem comes in when the value in the loaded multiplicand byte is $FF, then loading the incremented multiplicand byte would be $00, and the ripple-through of the carry is lost, causing an error in the result.
To prevent this, the ripple-though carry must instead be handled·by·successively ADDING a·one to each of the higher accumulator bytes when a carry-out occurs, so that the carries can properly cascade through each byte of the accumulator.
Cheers,
Peter (pjv)
Post Edited (pjv) : 4/16/2005 10:57:28 PM GMT
For those who work with integer math, I just ran accross what I think is an error in one of the integer multiply routines on the SX List.
Typically mutiplication is performed by successive shifting of the multiplier, then if the shifted-out bit is a one,·adding the multiplicand to an accumulator. This works for precisions using any number of bytes, I believe the errant code was for a 24 bit example.
As the multiplicand is added to the muli-byte accumulator, the carry represents overflows from the current accumulator byte being summed, and must cascade as a "plus one" into the next higher accumulator byte. (This can be handled directly·by the processor·if the carryx extension is enabled,·then the programmer need not bother).
In the errant example, this adding of "one" is handled by loading·an incremented value of the multiplicand if the carry was set (MOV w,++MultiplicandByte), or the regular value of the mutiplicand if carry was not set (MOV w,MultiplicandByte), and adding this carry-adjusted value to the accumulator. All good so far.
The problem comes in when the value in the loaded multiplicand byte is $FF, then loading the incremented multiplicand byte would be $00, and the ripple-through of the carry is lost, causing an error in the result.
To prevent this, the ripple-though carry must instead be handled·by·successively ADDING a·one to each of the higher accumulator bytes when a carry-out occurs, so that the carries can properly cascade through each byte of the accumulator.
Cheers,
Peter (pjv)
Post Edited (pjv) : 4/16/2005 10:57:28 PM GMT
Comments
I have run into errors on the SX list in some of the mutliply divide routines.
I will have to check my notes when I get home. I had to do a 'repair' of one
of the samples of code to get my multiply/divide correct.
I was going to check it out on the SX list page to see if any of the code
would 'jog' my memory, but...··· ...apparently I was accessing pages too
quickly...·· ...so no go.
-Dan
·
If ever you have any problem with the code you find on the site, do please use the little form at the bottom to post a comment, even if it is just "this didn't work for me" but hopefully people will post the corrections.
If you guys remember what page you where looking at, please let me know.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
---
James Newton, Host of SXList.com
james@sxlist.com 1-619-652-0593 fax:1-208-279-8767
SX FAQ / Code / Tutorials / Documentation:
http://www.sxlist.com Pick faster!
I hope someone who tags onto your thread can use them.
Leinster
IF mul1616_test=1 ; 16 bit x 16 bit multiplication ; entry: multiplicand in $09,08, multiplier at $0b,$0a ; exit : 32 bit product at $0d,$0c,$b,$a ; cycles ;mul1616 mov count,#17 ; 2 set number of times to shift clr upper_prdt ; 1 clear upper product clr upper_prdt+1 ; 1 higher byte of the 16 bit upeper product clc ; 1 clear carry ; the following are executed [noparse][[/noparse]count] times m1616loop rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add decsz count ; 1/2 loop [noparse][[/noparse]count] times to get proper product jmp m1616loop ; 3 jmp to rotate the next half of product ret ; 3 done... ; fast 16 bit x 16 bit multiplication ; entry: multiplicand in $09,08, multiplier at $0b,$0a ; exit : 32 bit product at $0d,$0c,$b,$a IF mul1616_test=1 mul1616 clr upper_prdt ; 1 clear upper product clr upper_prdt+1 ; 1 higher byte of the 16 bit upeper product clc ; 1 clear carry rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add1 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add1 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add2 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add2 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add3 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add3 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add4 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add4 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add5 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add5 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add6 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add6 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add7 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add7 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add8 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add8 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add9 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add9 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add10 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add10 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add11 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add11 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add12 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add12 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add13 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add13 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add14 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add14 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add15 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add15 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add16 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add16 rr upper_prdt+1 ; 1 rotate right the whole product rr upper_prdt ; 1 lower byte of the 16 bit upper product rr mr16+1 ; 1 high byte of the multiplier rr mr16 ; 1 check lsb sc ; 1 skip addition if no carry jmp no_add17 ; 3 no addition since lsb=0 clc ; 1 clear carry add upper_prdt,md16 ; 1 add multiplicand to upper product add upper_prdt+1,md16+1 ; 1 add the next 16 bit of multiplicand addb upper_prdt+1, c ; *********************CORRECTION FOR NO CARRYX no_add17 ret ; 3 done...