Anyone could tell me the multiplication algorithm without using mul and imul instructions? Thanks :)
Posted on 2006-11-01 17:26:49 by ammfj
You could use FPU instructions.  :lol:


fld    number
fmul pi
fstp number


For more info, you could visit this Raymond's FPU Tutorial: hxxp://www.ray.masmcode.com/fpu.html
Posted on 2006-11-01 20:28:08 by modchip
it's easy in base 2, shift and add.
Posted on 2006-11-01 20:39:59 by jack
Even though this thread has a serious taste of homework, I let you in on the oldest of the many possible ways on how to multiply without actually using mul or imul or fmulp or similar.

Let's assume you have to multiply 13 by 7. If you add 13 to itself 7 times then you actually found a workaround. In assembly:


xor eax, eax
mov ecx, 7
@me:
add eax, 13
loop @me

Posted on 2006-11-01 21:28:38 by JimmyClif
Unsigned multiplication can easily be done using a series of shifts to the left or right and subtractions or additions. Some well known combinations are SHL and ADD or SHL and SUB. The first method is when you predict a number on power of 2 which is less than your target number and the latter is used when you predict a number which is greater than your target.

Multiplication by numbers which are powers of two, for example 8, can easily be done with shifts to the left of the number. All you have to do is to find n in this formula: 2^n = 8. In general, to find the result of the multiplication of an unsigned integral value by a factor which is the result of 2 on power of a number, you could use the below formula (Assuming that your number is n and the factor is x):

n*x = n SHL y
2^y = x

For example, if you are intending to multiply 12 by 8, you could use only a simple shift due to the fact that 8 is a power of two. So putting the numbers in the above formula you will have:

12*8 = 12 SHL y
2^y = 8 => y = 3
12*8 = 12 SHL 3 = 96

The hard part is when the factor you want to multiply your number with is not a power of two. In this case the easiest way is to do the followings:

1) Find a power of two which is the closest to but yet less than your factor.
2) Find how many shifts to the left are required to get to the factor that we found in the first step.
3) Subtract the factor that you found from the main factor.
4) If the result of the previous statement is zero, then all you have to do is to shift the number to the left by the number of factors and then add the original number to the result. If the result is not equal to zero then you have to shift the number to the left just like you did if the result was zero and then add the result to the original result shifted to the left by the number of the result of the subtraction.

The best way to describe this is by an example. Let?s say that we are going to multiply 7 by 12; follow through the steps below:

1) Find a power of two which is less than 12 which is 3 (2^3=8).
2) Subtract 8 from 12 which is the main factor to get 4.
3) Shift the number to the left by the factor that we found in the first step (3). We will have 7 SHL 3 which is equal to 7*2^3 = 56.
4) Now you should multiply the original number (7) by the number that we found at the 2nd step which is 4 (7*4=28). Note that multiplication by 4 can be done using 2 shifts to the left due to the fact that 2^2=4.
5) Calculate the sum of the result found at the 4th step and the 3rd which is 56+28 = 84. Therefore, 7*12 is equal to 84.


Another example; lets say we want to multiply 6 by 7:

1) Find a power of two which is less than 7. This gives us 2 (2^2=4).
2) Subtract 4 from the main factor which is 7 to get 3.
3) Shift the number to the left by the factor that we found at the first step (2). We now will have 6 SHL 2 which is equal to 6*2^2 = 6*4=24.
4) Multiply the original number by the factor that we found at the 2nd step of the code which is 3. In this case we will get 6*3 = 18.
5) Add the result of the 3rd and the 4th steps to get 24+18 = 42. We got it! 6*7 = 42.

Note that there are times that the factor used at the fourth step of the above algorithm is not a power of two which can not be calculated with another shift. In this case you can use a series of shifts to the left and additions to find this factor. For example, in the above algorithm at the 4th step, to be able to multiply 6 by 3, you could shift 6 to the left 1 time (2^1=2 which is less than 3) and add the result to the original number. This would give us (6 SHL 1) + 6 = 12+6 = 18.

Solely using addition in order to perform multiplication would be more time-consuming than using series of shifts and additions but the drawback of the shifts and additions is that you are going to have to find a formula for each factor because the formula which works for one factor would not work for the other which is in contrast to the addition approach.

Hope I could help. Good luck.
Posted on 2006-11-02 03:07:27 by XCHG
Thanks to all  :).  All of your solutions have been of great importance to me. Even with the 5 star joke 8)... Bye!
Posted on 2006-11-02 04:20:58 by ammfj
Another hit-and-run  :shock:
Posted on 2006-11-02 04:47:06 by Ultrano
hit and run :D The world is in constant movement :) Even the most insignificant problems have a solution. Assembly language doesn't have to be a mind breaker!
Posted on 2006-11-02 05:25:07 by ammfj
The "Bye!" ending reminded me of the growing number of people who ask 1 question, get the answer, and never come back :) .

A cpu-based simple algorithm for mul, that uses brute-force is:


// Result = Param1 * Param2
Result=0;
while(Param2){
  if(Param2 & 1) Result+=Param1;
  // now shift
  Param1<<=1;
  Param2>>=1;
}
return Result;


So, consider Param1 = 1001b (9)  and Param2 = 101b (5)
first pass in "while"
// param1=1001b
// param2=101b
// result = 0;
Result+=1001b;  // the "if" condition is true

second pass in "while":
// param1 = 10010b
// param2 = 10b
// result = 1001b
10b & 1 <-  this returns false, so we don't add anything to Result

third pass in "while":
// param1 = 100100b
// param2 = 1
// result = 1001b
Result+=100100b

So, finally, Result = 101101b = 45 (decimal) = 9*5

:)

A simple speed-up would be to have Param2<Param1, as obvious :)
Posted on 2006-11-02 08:25:20 by Ultrano
Resuming... There are "a few" possible ways to make multiplication in a faster way?! Yes there are :D
Thanks Ultrano!
Posted on 2006-11-02 10:14:39 by ammfj
If you need to multiply quickly, you should use logarithms. But I believe that's beyond the scope of a homework.
Posted on 2006-11-02 12:26:13 by ti_mo_n
If you'r looking for fast multiplication of *BIG* numbers, maybe you would like take a look at that. At least It would give a idea.
Attachments:
Posted on 2006-11-02 16:09:35 by Dite
I remember back in the 486 days... it could actually be faster doing a "loop add" instead of mul :)
Posted on 2006-11-03 02:12:55 by f0dder

UselessDwordTimesDwordToDword:
push ebp
push ebx
mov ebx, ;;arg1
mov ebp, ;;arg2
xor eax,eax
test ebx,ebx
jz END
test ebp,ebp
jz END
mov cl,32
LOOP1:
dec cl
shl ebx,1
jnc LOOP1
mov edx,ebp
shl edx,cl
add eax,edx
test ebx,ebx
jnz LOOP
END:
pop ebx
pop ebp
ret 8


Shift and Shift and Add
Posted on 2006-11-03 21:26:25 by r22
Hello! Ok, this recent version help us to understand the use of test instruction for multiplying. Another interesting solution.  :D
Posted on 2006-11-04 05:54:29 by ammfj
xchg,

that would be how I would do multiplication for big number.  ;)
Posted on 2006-11-04 19:56:35 by roticv