ASM Community

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

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)

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.

Thanks for answer guys.......

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

{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?

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

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

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