Hi all guys.....

___________________________

suppose A, B, C, and D are 32-bit number and we form two numbers N1 and N2 as under ---

N1 = Aw + B

N2 = Cw + D

where w is the base of the number system.

now, a = A*C, b = B*D and c = (A+C) * (B+D) - a - b

hence when

P = N1*N2

= a (w^2) + c (w) + b

Hence, inorder to multiply N1 and N2 we only required 3 multiplications, 2 additions and 2 subtraction.

Thus, saving 1 multiplication.. This method of multiplying is called KaratSuba- Ofman Multiplication Method.

_____________________________________________________

But can somebody tell me how to achieve this multiplication through ASM because I am not getting how to get the output..

Regards

___________________________

suppose A, B, C, and D are 32-bit number and we form two numbers N1 and N2 as under ---

N1 = Aw + B

N2 = Cw + D

where w is the base of the number system.

now, a = A*C, b = B*D and c = (A+C) * (B+D) - a - b

hence when

P = N1*N2

= a (w^2) + c (w) + b

Hence, inorder to multiply N1 and N2 we only required 3 multiplications, 2 additions and 2 subtraction.

Thus, saving 1 multiplication.. This method of multiplying is called KaratSuba- Ofman Multiplication Method.

_____________________________________________________

But can somebody tell me how to achieve this multiplication through ASM because I am not getting how to get the output..

Regards

Look for Eoin's Floating Point tut on the board...

(Looks to me you only need a couple multiplications... I like Fp because there's no need to save any temporary results into vars)

(Looks to me you only need a couple multiplications... I like Fp because there's no need to save any temporary results into vars)

___________________________

suppose A, B, C, and D are 32-bit number and we form two numbers N1 and N2 as under ---

N1 = Aw + B

N2 = Cw + D

where w is the base of the number system.

now, a = A*C, b = B*D and c = (A+C) * (B+D) - a - b

hence when

P = N1*N2

= a (w^2) + c (w) + b

Hence, inorder to multiply N1 and N2 we only required 3 multiplications, 2 additions and 2 subtraction.

Thus, saving 1 multiplication.. This method of multiplying is called KaratSuba- Ofman Multiplication Method.

________________________________________________

But can somebody tell me how to achieve this multiplication through ASM because I am not getting how to get the output..

**digits in base w**, where numbers N1 = AB and N2 = CD.

Arithmetically,

N1 = A * w + B

N2 = C * w + D

a = A * C and b = B * D are double digit numbers (the first digit may be 0).

c should be (A + B) * (C + D) - a - b, because c = A*D + B*C (the multiply cross),

Since adding two digits yields a maximum carry of 1,

(A + B) = RS and (C + D) = TU, where R and T are 0 or 1.

RS * TU = (R*w + S) * (T*w + U) = (R*T)*w^2 + (R*U + S*T)*w + S*U.

So the first partial product is 000 or 100; the second partial product is 00, R0, T0, or their sum; the third partial product is the product of S and U; thus only one multiplication is needed to calculate c.

The rest is just multiprecision addition and subtraction. (Use ADC and SBB, and avoid adding guaranteed 0 digits). And, of course, translating to ASM. Treat each 32-bit DWORD value as a single digit.

Thanks for answer guys.......

the can I have the implemention of your algorithm in assembly... because I need it desperately........

regards

the can I have the implemention of your algorithm in assembly... because I need it desperately........

regards

:) Here is the 16-bit version - you extend to 32-bit:

```
_DATA SEGMENT
```

; w = 10000h

;

;N1 = A*w + B

___B dw 0FFFFh

___A dw 0FFFEh

;N2 = A*w + B

___D dw 0FFFDh

___C dw 0FFFCh

___P dq 0

_DATA ENDS

movzx eax, WORD PTR ___A

movzx ebx, WORD PTR ___B

movzx ecx, WORD PTR ___C

movzx edx, WORD PTR ___D

; a = A * C

mov esi, eax

imul esi, ecx

; b = B * D

mov edi, ebx

imul edi, edx

; c = (A+B)*(C+D) - a - b

add eax, ebx

add ecx, edx

mul ecx

sub eax, esi

sbb edx, 0

sub eax, edi

sbb edx, 0

;result: P = a (w^2) + c (w) + b

mov DWORD PTR ___P + 4, esi

mov DWORD PTR ___P, edi

add DWORD PTR ___P + 2, eax

adc WORD PTR ___P + 6, dx

;----------Test it!-----------

mov eax, DWORD PTR ___B

mul DWORD PTR ___D

cmp DWORD PTR ___P, eax

jne ERROR

cmp DWORD PTR ___P+4, edx

jne ERROR

BitRake I have tested your code my making changes but it didn't work i.e I mean to say it result is erroneous...

can you test your code yourself for the input of ---

A = FFFFh

B = FFFFh

C = FFFFh

D = FFFFh

The answer should be FFFF FFFE 0 1 but it's not there...

Can tell me you have taken care of carry produced after the addition of A+B and C+D in your code....

Moreover due to imul H.O bits get lost which I don't want to..

suggest any other method.

regards

can you test your code yourself for the input of ---

A = FFFFh

B = FFFFh

C = FFFFh

D = FFFFh

The answer should be FFFF FFFE 0 1 but it's not there...

Can tell me you have taken care of carry produced after the addition of A+B and C+D in your code....

Moreover due to imul H.O bits get lost which I don't want to..

suggest any other method.

regards

{1}Can tell me you have taken care of carry produced after the addition of A+B and C+D in your code....

{2}Moreover due to imul H.O bits get lost which I don't want to..

suggest any other method.

{2}True, this is an error. Sorry, for the quick hack - you'll have to move the registers around and use MUL. Maybe, when I have some spare time I'll work on the 32-bit version.

What do you need this algo for?

Actually bitrake

right now I am working on arithmetic manipulation of larger number... there is lot of source code on the net but no one has implement all these thing in assembly..

I want to check the speed of arithmetic operation when I completely write the arithmetic function with respect to the sources available on the net in high level language..

That's it..

Can anyone help me out regarding my above question...

cya

right now I am working on arithmetic manipulation of larger number... there is lot of source code on the net but no one has implement all these thing in assembly..

I want to check the speed of arithmetic operation when I completely write the arithmetic function with respect to the sources available on the net in high level language..

That's it..

Can anyone help me out regarding my above question...

cya

Actually bitrake

right now I am working on arithmetic manipulation of larger number... there is lot of source code on the net but no one has implement all these thing in assembly..

well, i wrote a bignum library in asm (not open source, though), roy started to write one as well (you can download the source here).

if you can't find what you're looking for, i guess you'll have to write it yourself ;)

Thanks tola..

for the source code but.. the way in which you have implemented your code is completely different from mine.

But I am going through your code may be it will help out... Also I want my library to perform fast calculations...

Anyway Thanks alot all you guys.....

regards

for the source code but.. the way in which you have implemented your code is completely different from mine.

But I am going through your code may be it will help out... Also I want my library to perform fast calculations...

Anyway Thanks alot all you guys.....

regards

it's not my code but roy's (-> in case there are any questions, don't ask me :grin: ).