Multiplication of large unsigned integers

[dsouza123]

With the hope of eventually having available assembly code dealing with basic math operations
on large integers easily available.

Code to do the multiplication of two unsigned integers.

It uses the method taught in elementary school
but uses dwords as units instead of decimal digits.

It works correctly but needs work to be used as drop in code
as a procedure with arbitrary sized integers.

The dword array sizes used for the input numbers are 16, but
the routine will work with larger/smaller numbers and ones that aren't the same.
The carry holder and result are each 32 dwords, the number of dwords
for both carry holder and result must >= the total of the number of dwords
from both input numbers, works fine with it ==.

The routine takes in two large unsigned integers (as dword arrays) and the count of dwords in each.
The result is a large unsigned integer, of which the number of dwords needed
is the total of the dword counts from both inputs.
It also uses a carry holding dword array/large unsigned integer the same length
as the result.

It has a two algorithmic optimizations:

If the dword unit that will multiply the other whole integer is zero it is skipped.

For example

   2 3 4 5
* 6 7 0 2
=====
when the 0 is picked to multiply the dword array 2 3 4 5,
its multiplication with addition to the total is skipped
but the indexes into the number 6 7 0 2 and the result/carry holder
are done correctly.

It uses a carry holder array instead of doing continued carry propagation
in adding the current unit by unit multiply to the result.


It displays the two input numbers and the result all as hex integers in a MessageBox.

Optimizations, rework for use as a proc, adaption to signed integers are all welcome.

[attachment deleted by admin]

[EduardoS]

I thought in a little diferent way to perform this kind of multiplication (basically just changed the order of multiplications), i found problems to write it with just 8 registers... So here is my ideia on "pseudo-64bits-assembly", with some bugs... Too tired to port it to "real-32bits-assembly" and test it:

Code Select Expand


bigmul proc result:QWORD, num1:QWORD, num2:QWORD, size:QWORD
    mov rsi, num1
    mov rdi, num2
    mov rbx, result
    mov rcx, size
    shl rcx, 3; from qwords to bytes
    xor r8, r8
    xor r9, r9
    xor r10, r10
    xor r11, r11
    xor r12, r12

@@:

    mov rax, [rsi+r8]
    mov rdx, [rdi+r9]
    mul rdx
    add r10, rax
    adc r11, rdx
    adc r12, 0
    add r8, 8
    sub r9, 8
    jnc @B

    mov [rbx], r10
    add rbx, 8
    mov r10, r11
    mov r11, r12
    xor r12, r12
   
    mov r9, r8
    xor r8, r8
    cmp r9, rcx
    jb @B

    sub r9, 8
    jz exit

    add rsi, 8
    add rdi, 8

@@:
    mov rax, [rsi+r8]
    mov rdx, [rdi+r9]
    mul rdx
    add r10, rax
    adc r11, rdx
    adc r12, 0
    add r8, 8
    sub r9, 8
    jnc @B

    mov [rbx], r10
    add rbx, 8
    mov r10, r11
    mov r11, r12
    xor r12, r12
    add rsi, 8
    add rdi, 8
   
    mov r9, r8
    xor r8, r8
    sub r9, 8
    jnc @B
    mov [rbx], r10
    mov rax, r12 ;carry, if any

ret
   
bigmul endp