Morgan - Numerical Methods (523161), страница 11
Текст из файла (страница 11)
Since the datatype is a quadword, the initial division must be by 24. Storing the multiplicand in theproduct variable and concatenating this variable with the internal registers allows useight words, enough for the largest possible product of two quadwords. As themultiplicand is shifted right and out, the lower bytes of the product are shifted in. Thisway, we can use one less register (or memory location).cmul2: Algorithm1.Move the multiplicand into the lowest four words of the product and loadthe shift counter (numbits) with 64.
Clear registers AX, BX, CX, and DXto hold the upper words of the product.2.Check bit 0 of the multiplicand.51NUMERICAL METHODSIf it's one, go to step 3.Shift the product and multiplicand right one bit.Decrement the counter.If it's not zero, return to the beginning of step 2.If it's zero, we're done.3.Add the multiplier to the product.Shift the product and the multiplicand right one bit.Decrement the counter.If it's not zero, return to step 2.If it's zero, we're done.cmul2: Listing; ******;; A faster shift and add. Multiply one quadword by another,; passed on the stack, pointers returned to the results.; Composed of shift and add instructions.cmul2 proc uses bx cx dx si di, multiplicand:qword, multiplier:qword,product:wordnumbits:bytelocalpushfcldax, axsubdi, word ptr productmov;write the multiplicandleasi, word ptr multiplicand;to the productmovcx, 4swmovrepdi, 8;point to base of productsubleasi, word ptr multiplier;number of bitsbyte ptr numbits, 40hmovsubax, axmovbx, axcx, axmovmovdx, axtest_for_zero:testword ptr [di], 1;test the multiplicand for a;one in the LSBadd multiplier;makes the jump if thejne52INTEGERS;LSB is a onejmpadd multiplieraddshort shiftax, word ptr [si]adcadcadcbx, word ptr [si][2]cx, word ptr [si][4]dx, word ptr [si][6]shrdx, 1rcrrcrrcrrcrrcrrcrrcrdecjzjmpcx, 1bx, 1ax, 1word ptr [di][6], 1word ptr [d1][4], 1word ptr [di][2], 1word ptr [di][O], 1byte ptr numbitsexitshort test_for_zeromovword ptr [di][8], axmovmovmovpopfretendpword ptr [dil [10], bxword ptr [di][12], cxword ptr [di][14], dx;add the multlplier to;subproductshift:;shift it into the lower;bytes of the productexit:cmul;move the upper byte of;the productFor an example of a routine written for the Z80 and employing this technique,see the SAMPLES.
module on the accompanying disk.Skipping Ones and ZerosAnyone who has ever struggled with time-critical code on a bit-oriented machinehas probably tried to find a way to lump the groups of ones and zeros in multipliersand multiplicands into one add or shift. A number of methods involve skipping overseries of ones and zeros; we’ll look at two such procedures. Their efficiency dependson the hardware involved: On machines that provide a sticky bit, such as the 80C196,53NUMERICAL METHODSthese routines can provide the most improvement. Unfortunately, the processors thatprovide that bit also normally have a hardware multiply.The first technique we’ll look at is the Booth algorithm which finds its wayaround ones and zeros by restating the multiplier.2 Suppose we want to multiply1234H by 0fff0H. Studying the multiplier, we find that 0fff0H is equal to 10000H-10H. A long series of rotates and additions can thus be replaced by one subtractionand one addition-that is, subtract 10H x 1234H from the product, then add 10000Hx 1234H to the product.
The drawback is that the time it takes to execute thisoperation depends on the data. If the worst-case condition arises-a multiplier withalternating ones and zeros-the procedure can take longer than a standard shift andadd.The trick here is to scan the multiplier looking for changes from ones to zerosand zeros to ones.
The way this is done depends on the programmer and the MPUselected. The following table presents the possible combinations of bits examinedand the actions taken.Bit 00011Carry0101Action*No actionAdd the current state of the multiplicandSubtract the current state of the multiplicandNo action* This chart assumes that the multiplicand has been rotated along with the multiplieras it is being scanned.Remember that as the multiplier is scanned from position 0 through position n,the multiplicand must also be shifted (multiplied) through these positions.In its simplest form, the Booth algorithm may be implemented similarly to theshift and add above except that bit 0 of the multiplier is checked along with the carryto determine the appropriate action.
As you can see from the table, if you’re in themiddle of a stream of zeros or ones, you do nothing but shift the multiplier andmultiplicand. Depending on the size of the operands involved and the instruction set,it may be faster simply to increment a counter for a multibit shift when the timecomes.The coding for this algorithm is heavily dependent on the device (instruction54INTEGERSset), but one possible scheme is as follows.booth: Algorithm1.Allocate space for the multiplicand and 32 shifts. Clear the carry andthe registers used to form the product.2.Jump to step 6 if the carry bit is set.3.Test the 0 th bit.
If it's not set, jump to step 5.4.Subtract mltpcnd from the registers used to form the product.5.Shift mltpcnd left one position.Check multiplier to see if it's zero. If so, go to step 8.Shift multiplier right one position, shifting the LSB into the carry,and jump to step 2.6.Test the 0th bit. If it's set, jump to step 5.7.Add mltpcnd to the product registers and jump to step 5.8.Write the product registers to product and go home.booth: Listing; *****; booth; unsigned multiplication algorithm; 16 X 16 multiplybooth proc uses bx cx dx, multiplicand:dword, multiplier:dword, product:wordmltpcnd:qwordlocalpushfcldax, axsubsi, word ptr multiplicandlealeadi, word ptr mltpcndcx, 2movswmovrepstosw;clear upper wordsstoswbx, axmovcx, axmovmovdx, axclccheck_carry:55NUMERICAL METHODSjctestjzsub_multiplicand:subsbbsbbsbbshift_multiplicand:shlrclrclrclorjnzorjnzjwshift multiplier:shrrcrjmpexit:movmovmovmovmovpopfretcarry-set:testjnzadd multiplicand:addadcadcadcjmpbooth endpcarry_setword ptr multiplier, 1shift_multiplicandax,bx,cx,dx,wordwordwordwordptrptrptrptrmltpcndmltpcnd[2]mltpcnd[4]mltpcnd[61word ptr mltpcnd, 1word ptr mltpcnd[2], 1word ptr mltpcnd[4], 1word ptr mltpcnd[6], 1word ptr multiplier[2], 0shift multiplierword ptr multiplier, 0shift multipliershort exitword ptr multiplier[2], 1word ptr multiplier, 1short check carrydi, wordword ptrword ptrword ptrword ptr;test bit 0;early-out mechanism;shift multiplierptr product[di], ax[dil[2], bx[di][4], cx[di][6], dxword ptr multiplier, 1shift-multiplicand;test bit 0ax, word ptr mltpcndbx, word ptr mltpcnd[2]cx, word ptr mltpcnd[4]dx, word ptr mltpcnd[6]short shift_multiplicandA corollary to the Booth algorithm is bit pair encoding.
The multiplier isscanned, as in the Booth algorithm, but this time three bits are considered at once (see56INTEGERSthe following chart). This method is attractive because it guarantees that half as manypartial products will be required as with the shift and add to produce the result.Bit n+lBit n000Bit n-l001Add the current state of the multiplicand010Add the current state of the multiplicand011010Add twice the current state of the multiplicandSubtract twice the current state of themultiplicand101Subtract the current state of the multiplicand110Subtract the current state of the multiplicand111No actionAction*No action* This chart assumes that the multiplicand has been shifted along with the multiplierscanning.The multiplier is examined two bits at a time relative to the high-order bit of thenext lower pair (bit n-l in the table).
First, the multiplier is understood to have aphantom zero to the right of bits 0 and 1; These bits are analyzed accordingly.Second, a phantom zero can be assumed to the left of the multiplier for the purposeof filling out the table. For example, the number 21H would be viewed as:02512402302202l 2001 0The basic approach to implementing this routine is similar to the Boothalgorithm.bit_pair: Algorithm1.Allocate space to hold the multiplicand plus 32 bits for shifting. Clearthe carry and the registers to be used to form the product.2.If the carry bit is set, jump to step 8.3.Test the 0 th bit.
If it's clear, jump to step 5.57NUMERICAL METHODS4.Test bit 1.If it's set, subtract mltpcnd from the product registers and continuewith step 7.Otherwise, add mltpcnd to the product registers and go to step 7.5.Test bit 1.If it's set, jump to step 6.Otherwise, continue from step 7.6.7.Subtract twice mltpcnd from the product registers.Shift mltpcnd left two positions.Check multiplier to see if it's zero. If so, continue at step 13.Shift multiplier two positions to the right and into the carry.Jump to step 2.8.Test the 0 th bit.If it's set, jump to step 11.Otherwise, go to step 12.9.Add the current value of mltpcnd to the product registers.10.Add the current value of mltpcnd to the product registers and continuewith step 7.11.Test bit 1.If it's set, jump to step 7.Otherwise, add twice mltpcnd to the product registers and continue fromstep 7.12. Test bit 1.If it's set, subtract mltpcnd from the product registers and continuewith step 7.Otherwise, add mltpcnd to the product registers and go to step 7.13.Write the product registers to product and go home.bit_pair: Listing; ******; bit pair encoding;;;bit_pair proc uses bx cx dx, multiplicand:dword, multiplier:dword, product:word58INTEGERSlocalmltpcnd:qwordpushfcldsubax, axleasi, word ptr multiplicandleadi, word ptr mltpcndmovcx, 2movswrepstoswstoswmovbx, axmovcx, axmovdx, axclccheck carry:carry setjctestword ptr multiplier, 1shiftorsubjztestword ptr multiplier, 2jnzsub multiplicandadd multiplicandjmpshiftorsub:testword ptr multiplier, 2shift multiplicandjzsubx2_multiplicand:subax, word ptr mltpcndbx, word ptr mltpcnd[2]sbbsbbcx, word ptr mltpcnd[4]sbbdx, word ptr mltpcnd[6]sub multiplicand:subax, word ptr mltpcndsbbbx, word ptr mltpcnd[2]sbbcx, word ptr mltpcnd[4]sbbdx, word ptr mltpcnd[6]shift multiplicand:shlword ptr mltpcnd, 1rclword ptr mltpcnd[2], 1rclword ptr mltpcnd[4], 1rclword ptr mltpcnd[6], 1shlword ptr mltpcnd, 1rclword ptr mltpcnd[2], 1rclword ptr mltpcnd[4], 1rclword ptr mltpcnd[6], 1orword ptr multlplier[2], 0;clear upper words;test bit n-l;test bit 0;test bit 1;test bit 1;cheap in-line multiply;early out if multiplier is zero59NUMERICAL METHODSjnzorjnzjmpshift multiplier:shrrcrshrrcrjmpexit:movmovmovmovmovpopfretcarry_set:testjnzjmpaddx2_multiplicand:addadcadcadcadd-multiplicand:addadcadcadcjmpaddorsubx2:testjnzjmpaddorsubx1:testjnzjmp60shift_multiplierword ptr multiplier, 0shift multipliershort exitwordwordwordwordshortptr multiplier[2], 1ptr multiplier, 1ptr multiplier[2], 1ptr multiplier, 1check_carrydi, wordword ptrword ptrword ptrword ptrptr product[di], ax[di] [2], bx[di][4], cx[di][6], dx; shift multiplier right twice;write product out beforeleavingword ptr multiplier, 1addorsubx2short addorsubx1ax,bx,cx,dx,wordwordwordwordptrptrptrptrmltpcndmltpcnd[2]mltpcnd[4]mltpcnd[6];cheap in-line multiplierax, word ptr mltpcndbx, word ptr mltpcnd[2]cx, word ptr mltpcnd[4]dx, word ptr mltpcnd[6]short shift_multiplicandword ptr multiplier, 2shift-multiplicandshort addx2_multiplicand;test bit 1word ptr multiplier, 2sub_multiplicandshort add_multiplicand;test bit 1INTEGERSbit_pairendpHardware Multiplication: Single and MultiprecisionIf the processor you’re using has a hardware multiply, you’re in luck.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
