MAT32 - 32-Bit math for the Basic Stamp 2

(BACK TO THE BS2 MATH MAIN PAGE)

These routines add, subtract, multiply and divide 32-bit binary numbers. The number of bits is absolutely not fixed, and can be changed simply changing the value of a constant, going from 24 bits to 40 bits (even more if you don't need multplication and division)

Please note that these routines are quite slow, while division is VERY slow (something like 4 seconds!).

The source code is quite commented, so i'll leave it without further discussions.

The DISPLAY subroutine displays the contents of the accumulator in hexadecimal. Constants are also read from memory in hexadecimal format.

If you want to download this program, I suggest you to save it using your Browser's "Save as.." function, and then selecting "Text file (*.TXT)" as format. This will automatically strip the source code of the embedded HTML tags.

If you download/use/change this program, please drop me a note to the asdress f.bonomi@agora.stm.it



' ***********

' *  MAT32  *

' ***********	

'        Long integer math routines 

'          for the Basic Stamp 2

'        Copyright  F. Bonomi 1996-1998

'               version 0.7



' Non-commercial use of this software is welcome!

' Please signal bugs & changes to: f.bonomi@agora.stm.it



' BCD addition, subtraction and multiplication with

' arbitrary precision for the Basic Stamp II



' Copyright Francesco Bonomi 1996-1998, non-commercial use permitted

' Please send comments, corrections and bugs to f.bonomi@agora.stm.it



' 

' These routines give a rudimentary set for integer

' math with more than 16 bits. Please note that, although

' called mat32, they can be used for a large range of bit-length,

' from 24 to 40! (even more if you remove the divide routines, 

' and)



' NOTE: 

' The DIVIDE routine is terrible! (see below)



' OTHER NOTE:

' I have not taken in account overflows, but I have

' tried to mark where and how to detect them.



' Ideas for chamge:



' An interesting change might be changing MULTIPLY

' so that it uses EEPROM instead ot the mul() variable

' to temporarily store one of the multiplication

' operators, as long as you don't mind writing

' to EEPROM (they say you can do it only a million times!)



' Another idea might be, if you only multiply by

' constant numbers, would be to change MULTIPLY

' so that it multiplies by constant numbers

' keeping them in EEPROM and READing a digit at

' a time. So, you could avoid declaring the mul() array.



' Also, you could try to find a way to re-use the buffer's

' RAM space by declaring other variables on top of it.



' Another way to spare memory could be, if this is the case,

' to use special versions of MULTIPLY and DIVIDE that only

' multply and divide by 16-bit numbers. (again, you would

' avoid declaring the mul() array.



digits con 4          ' How many 8-bits digits?

digits1 con digits-1  ' Same number minus 1, used in for-next loops



acc var byte (digits)    ' The accumulator

opr var byte (digits)    ' The operator buffer

mul var byte (digits)    ' The multiplying buffer



' In these variables, low index means low significance:

' acc(0) holds the least significant digit,

' acc(digits1) the most significant digit, etc.



tmp var word           ' A word variable, used in intermediate

                       ' calculations to generate carry/borrow

                       ' Also used as a pointer to constants

                       ' passed to load_acc and load_opr



carry var nib          ' Carry/borrow



dig1 var nib           ' Variables used to cycle through the digits

dig2 var nib



dig3 var carry         ' Another variable, only used by MUL.

                       ' As MUL does not use the carry, 

                       ' dig3 can be declared on top of carry





' constants to play with

num1 data $12,$34,$56,$78 ' this represent the hex number $12345678

num2 data $00,$04,$32,$10 ' this represent the hex number $00043210



x var word



' Let's do some operations!



' load $12345678 in the accumulator

tmp=num1

gosub load_acc



' load $00043210 in the operator

tmp=num2

gosub load_opr



' subtract $0043210 for $1234568

gosub subtract



' display the result ($12302468)

gosub display



' Now:

' the accumulator has $12302468

' the operator still has $00043210

' let's divide $12302468 by $0043210



gosub divide

' and display the result ($455)

gosub display



' now let's multiply our result times $00043210

' (note that DIVIDE cleared the operator, so we 

' have to reload it)



tmp=num2

gosub load_opr

gosub multiply

gosub display



' Of course, the result is 122CDF50, not the 

' original value of $12302468, because we had some

' round-off during the integer division.



' and now, for something completely different...

pause 1000

debug cls



' Let's clear the accumulator

gosub clear_acc



' store a number in the operator

tmp=num2

gosub load_opr



' do the sum a thousand times!

for x=1 to 1000

 gosub add

 gosub display

next



end



' That's all!



' SUBROUTINES FOLLOW

' Subroutine ADD: Addition

ADD ' Add the operator to the accumulator ' clear carry carry = 0 for dig1= 0 to digits1 ' each digit will be replaced by: tmp=carry+acc(dig1) ' the carry plus the accumulator digit tmp=tmp+opr(dig1) ' plus the operator digit ' the accumulator gets the lower digit acc(dig1)=tmp.lowbyte ' the higher digit becomes the carry for next digit carry=tmp.highbyte next ' here, you might check for overflow: if after ' adding the most significant digit we have a ' carry, this is an overflow! return

' Subroutine SUBTRACT: Subtraction

SUBTRACT ' Subtract the operator from the accumulator ' clear borrow carry = 0 for dig1=0 to digits1 ' each digit will be replaced by: tmp=acc(dig1)-carry ' the accumulator digit minus the borrow tmp=tmp-opr(dig1) ' minus the operator digit carry=0 ' did we have a borrow? if tmp.highbyte=0 then SUB_no_borrow ' no, jump forward ' yes, remember the borrow carry=1 SUB_no_borrow ' the accumulator gets the lower digit acc(dig1)=tmp.lowbyte next ' here too, carry>0 means overflow return

' Subroutine MULTIPLY: Multiplication

MULTIPLY ' The accumulator is multiplied times the operator ' The multiply buffer is temporarily used ' probably an optimized version could be made using ** and */, ' but like this it's easier to have a flexible number ' of digits! ' copy the accumulator in the multiply buffer, ' and clear the accumulator for dig1=0 to digits1 mul(dig1)=acc(dig1) acc(dig1)=0 next ' each digit of opr must be multiplied ' with each digit of mul, the result must be added in acc for dig1 = 0 to digits1 for dig2 = 0 to digits1 tmp=opr(dig1)*mul(dig2) ' at which digit must it be written to in acc? dig3=dig1+dig2 ' if dig3>digits1 and tmp>0 then it's an overflow! if dig3 > digits1 then MUL_skip_add ' otherwise we can do the addition ' instead of adding tmp in acc(dig3), we will do the opposite, ' as tmp is a word and will correctly handle carries MUL_ripple_carry tmp=tmp+acc(dig3) acc(dig3)=tmp.lowbyte ' the low part of tmp goes in acc, tmp=tmp >> 8 ' the high part of tmp stays there to become ' a carry for the higher-order digit dig3=dig3+1 if tmp>0 and dig3<=digits1 then MUL_ripple_carry ' here, if tmp>0 it's an other overflow! MUL_skip_add next next return

' Subroutine CLEAR_ACC: Clear the accumulator

CLEAR_ACC ' Clear the accumulator for dig1 =0 to digits1 acc(dig1)=0 next return

' Subroutine CLEAR_OPR: Clear the operator

CLEAR_OPR ' Clear the operator for dig1 =0 to digits1 opr(dig1)=0 next return

' Subroutine LOAD_ACC: Load the accumulator

LOAD_ACC ' Load the accumulator with the number stored ' in EEPROM and pointed at by tmp ' the number must be stored high-byte first, ' one byte at time, and with trailing zeroes, ' like in the following example (supposing digits=4): ' ' number data $00, $12, $34, $56 ' tmp=number ' gosub load_acc ' gosub display ' 00123456 for dig1 =0 to digits1 read tmp+digits1-dig1, acc(dig1) next return

' Subroutine LOAD_OPR: Load the operator

LOAD_OPR ' Load the operator with a number stored in EEPROM for dig1 =0 to digits1 read tmp+digits1-dig1, opr(dig1) next return

' Subroutine DISPLAY: Display the accumulator

DISPLAY ' Display the accumulator value in hex through DEBUG for dig1 = digits1 to 0 debug hex2 acc(dig1) next debug cr return ' THE FOLLOWING DECLARATIONS AND SUBROUTINES PERTAIN TO DIVISION ONLY. ' I feel so un-satisfied with them that I have kept them apart, where ' it is easier to cut them away. ' During division we will need to access some of our variables one ' bit at a time, so I declare them again as array of bits max_bits con digits*8-1 ' how many bits in the array? (0 to this value) opr_bit var opr.lowbit acc_bit var acc.lowbit mul_bit var mul.lowbit ' we will need a few pointers in the bit-array, which ' cannot be declared as nib. Let us re-use tmp, a 16-bits ' variable not used during division bp1 var byte' tmp.lowbyte bp2 var byte' tmp.highbyte shift_count var byte acc_larger var bit ' true if acc is larger than opr

' Subroutine DIVIDE: Divide the accumulator by the operator

DIVIDE ' the only thing good that can be said of this routine ' is that it divides. It's a memory eater, terribly slow, ' dumb and un-elegant. BTW, as in effects it's a ' simplified form of floating-point division, it ' would be easy to change the last part of the routine ' to return any number of fractionary hex digits ' (something like $1A.80 would mean 26.5) ' during division, we will have: ' acc dividend ' opr divisor ' mul result ' While the other operations leave opr unchanged, ' DIVIDE leaves it empty ' first let us see if dividend or divisor are equal to 0 ' if dividend is equal to 0, the correct result is 0 ' if divisor is equal to 0, we have a divide-by-zero error, ' in both cases we will return a 0 result ' use bp1 and bp2 as flags fo see if one of the operands is zero bp1=0 bp2=0 for dig1=0 to digits1 if acc(dig1)=0 then DIVIDE_acc_is_still_zero bp1=1 DIVIDE_acc_is_still_zero if opr(dig1)=0 then DIVIDE_opr_is_still_zero bp2=1 DIVIDE_opr_is_still_zero next ' in case one of the operands is zero, jumpo into ' CLEAR_ACC so that we return with a 0 result if bp1=0 or bp2=0 then CLEAR_ACC for dig1=0 to digits1 mul(dig1)=0 next ' We will perform a sort of floating-point binary division: ' let us shift dividend and divisor up until their most ' significant bit is 1, and let's keep count ' of how much we shift one relative to the other ' shift_count can have a negative or a positive value. ' to handle this in an unsinged byte we will take 128 as ' a relative 0, so that 127 will mean -1 and 129 will mean +1 shift_count=128 ' Shift the operator up! DIVIDE_shift_opr_loop ' if the the highest bit of the operator ' is 1, then we have finished, if opr_bit(max_bits)=1 then DIVIDE_shift_opr_done ' otherwise, shift it up a bit for bp1=max_bits to 1 opr_bit(bp1)=opr_bit(bp1-1) next opr_bit(0)=0 ' counting how many times we shift it shift_count=shift_count+1 ' loop until we have shifted! goto DIVIDE_shift_opr_loop DIVIDE_shift_opr_done ' Ok, the operator is shifted, now let's ' deal similarly with the accumulator if acc_bit(max_bits)=1 then DIVIDE_shift_acc_done for bp1=max_bits to 1 acc_bit(bp1)=acc_bit(bp1-1) next acc_bit(0)=0 shift_count=shift_count-1 goto DIVIDE_shift_opr_done DIVIDE_shift_acc_done ' shift_count was initialized at 128, and then it ' was incremented each time we shifted the ' operator, and decremented each time we shifted the ' accumulator. We could say that it gives the ' difference in "length" of the two numbers, plus 128. ' In floating-point terminology, shift_count ' contains the exponent of the result, added to 128 ' Simplified example with 8-bit numbers: ' opr was 00000110 (binary) tmp was 128 ' shift it 00001100 tmp goes to 129 ' again 00011000 tmp goes to 130 ' again 00110000 tmp goes to 131 ' again 01100000 tmp goes to 132 ' once more 11000000 tmp goes to 133 ' now the accumulator ' acc was 000101111 tmp was 133 ' shift it 001011110 tmp goes to 132 ' again 010111100 tmp goes to 131 ' 131 is 128 + exponent of result, ' exponent of result is 3 ' We now know that the result is "about" 2^3 ' (more exactly, it is of the form n*2^3, ' where 1opr(dig1) then DIVIDE_acc_compare_done dig1=dig1-1 goto DIVIDE_acc_compare_loop DIVIDE_acc_is_smaller acc_larger=0 DIVIDE_acc_compare_done ' 2) if acc is larger or equal, then: if acc_larger=0 then DIVIDE_acc_is_not_larger ' 3) subtract opr from acc gosub subtract ' 4) write a '1' in mul's correspondig bit mul_bit(bp1)=1 DIVIDE_acc_is_not_larger ' 5) else ' 6) write a '0' in mul's corresponding bit '(it's already 0) ' 7) shift opr down (right) a bit for bp2= 0 to max_bits-1 opr_bit(bp2)=opr_bit(bp2+1) next opr_bit(max_bits)=0 next ' The division is done. We have a (sort of) floating point ' result, where mul() has the mantissa and shift_count is ' the exponent+128 ' For the moment, we will convert the result to integer ' but this part is easily modified to keep fractionary results ' the topmost bit of mul should have been the ' (shift_count-128)th bit of the result. ' Let us copy the result in acc, aligning it properly. for dig1=0 to digits1 acc(dig1)=0 next ' if shift_count is negative, then the result is ' completely fractionary, a binary number like 0.000101.. ' In integer math, this means a result of 0, and we can quit if shift_count<128 then DIVIDE_done for bp1= max_bits to 0 bp2=bp1+max_bits-shift_count+128 ' the bp1-th bit in acc most come from the bp2-th bit in mul ' unless bp2 is out of range if bp2>max_bits then DIVIDE_out acc_bit(bp1)=mul_bit(bp2) DIVIDE_out next DIVIDE_done return