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
Posted on 2002-12-05 03:50:59 by processingspeed
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)
Posted on 2002-12-05 07:31:22 by JimmyClif

___________________________

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..
Suppose A, B, C, and D are 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.
Posted on 2002-12-05 15:44:21 by tenkey
Thanks for answer guys.......

the can I have the implemention of your algorithm in assembly... because I need it desperately........
regards
Posted on 2002-12-05 23:16:44 by processingspeed
:) 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
Posted on 2002-12-06 00:18:21 by bitRAKE
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
Posted on 2002-12-06 22:32:25 by processingspeed

{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.
{1}Yes, carry is in high word of result.

{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?
Posted on 2002-12-07 00:29:34 by bitRAKE
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
Posted on 2002-12-07 09:47:29 by processingspeed

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 ;)
Posted on 2002-12-07 10:23:16 by Tola
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
Posted on 2002-12-08 22:44:12 by processingspeed
it's not my code but roy's (-> in case there are any questions, don't ask me :grin: ).
Posted on 2002-12-09 06:37:58 by Tola