Anyone could tell me the multiplication algorithm without using mul and imul instructions? Thanks :)

You could use FPU instructions. :lol:

For more info, you could visit this Raymond's FPU Tutorial:

fld number

fmul pi

fstp number

For more info, you could visit this Raymond's FPU Tutorial:

**hxxp://www.ray.masmcode.com/fpu.html**it's easy in base 2, shift and add.

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:

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

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.

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.

Thanks to all :). All of your solutions have been of great importance to me. Even with the 5 star joke 8)... Bye!

Another hit-and-run :shock:

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!

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:

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 :)

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 :)

Resuming... There are "a few" possible ways to make multiplication in a faster way?! Yes there are :D

Thanks Ultrano!

Thanks Ultrano!

If you need to multiply quickly, you should use logarithms. But I believe that's beyond the scope of a homework.

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.

I remember back in the 486 days... it could actually be faster doing a "loop add" instead of mul :)

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

Hello! Ok, this recent version help us to understand the use of test instruction for multiplying. Another interesting solution. :D

xchg,

that would be how I would do multiplication for big number. ;)

that would be how I would do multiplication for big number. ;)