Search code examples
algorithmassemblyx86multiplication

Problem in multiplying two 64-bit numbers


I want to multiply two 64-bit unsigned numbers together and store the result in a 128-bit variable. I did it in the way given in the link https://www.plantation-productions.com/Webster/www.artofasm.com/Windows/HTML/AdvancedArithmetica2.html#1007619 And Michael Burr has mentioned it, in response to Kawarazu's question (How can I multiply two 64-bit numbers using x86 assembly language?). This is my code:

program exercise;
static  

      qw1:qword:=  956_3547_6850_2300_5452;//$84B8_8BF3_1E4E_3B0C 
      qw2:qword:=  956_3547_6850_2300_5452;//$84B8_8BF3_1E4E_3B0C
  //qw1:qword:=  18_446_744_073_709_551_615;//$FFFF_FFFF_FFFF_FFFF
  //qw2:qword:=  18_446_744_073_709_551_615;//$FFFF_FFFF_FFFF_FFFF

    prd:lword :=0;
  
#include("Stdlib.hhf");

begin exercise;
mov((type dword qw1[0]),eax);
mul((type dword qw2[0]),eax);
mov(eax,(type dword prd[0]));
mov(edx,ecx);

mov((type dword qw1[4]),eax);
mul((type dword qw2[0]),eax);
add(ecx,eax);
mov(eax,ebx);
adc(0,edx);
mov(edx,ecx);

mov((type dword qw1[0]),eax);
mul((type dword qw2[4]),eax);
add(ebx,eax);
mov(eax,(type dword prd[4]));
adc(ecx,edx);
mov(edx,ecx);

mov((type dword qw1[4]),eax);
mul((type dword qw2[4]),eax);
add(ecx,eax);
mov(eax,(type dword prd[8]));
adc(0,edx);
mov(edx,(type dword prd[12]));
stdout.put(prd, "     ",(type uns128 prd));

end exercise;

After running the program,This code answers accurately For the product of two smaller upper numbers
(in this case, the exact answer is : 44CED55C313E2724C1798E86D8EE8890) But for the lower two larger numbers, the answer is far from the exact value
(in this case, the exact answer is: FFFFFFFFFFFFFFFE0000000000000001 but But the program gets the value FFFFFFFEFFFFFFFE0000000000000001 that there is a difference in the 13th byte).
But when I change the last adc(0,edx); to adc(1,edx);, the problem is solved.

  1. My question is, where does this number 1 come from?
  2. What is my mistake?
  3. How can I modify this program?

This issue has created a serious challenge for me and I am grateful to my friends who will guide me in this matter.


Solution

  • You skipped commenting your source code.

    The addition of the second "middle sub-product" generates a carry you don't account for.
    Generally, either addition may generate a carry: just process them.


    The addition of the second "middle sub-product" doesn't generate a carry for two larger numbers (Hashem alizadeh )

    Well, it should:
    FFFF FFFF×FFFF FFFF = FFFF FFFE 0000 0001

           hi×hi               lo×lo  
    FFFF FFFE 0000 0001 FFFF FFFE 0000 0001   lower half never needs to be touched
    no carry→ FFFF FFFE 0000 0001             1st add of middle sub-product, say, hi×lo
    _____________________________
    FFFF FFFE FFFF FFFF FFFF FFFF
       carry→ FFFF FFFE 0000 0001             2nd add of middle sub-product, say, lo×hi
    _____________________________
    FFFF FFFF FFFF FFFE 0000 0000