Help with adding Big Numbers

[peter_asm]

OKay, I'm using BNCALC to generate the numbers.

http://sourceforge.net/projects/bncalc/

[dedndave]

the result is 257 bits in width
so, you have to write your code to handle at least that many bits
when dealing with large values in 32-bit code, it is best to use whole DWORD's
to accomodate the result with DWORD's, we need at least 9 DWORD's of width (288 bits)

next, to define the large values in the .DATA section, we reverse the order from what may seem natural   :P

Code Select Expand

; p     =   EABC39EB D635C26C 6977419B 5101A1FE 4B4E6804 344C5DCF E5E6A8C8 778FE3E9
; q     =   AA469F19 BA22C209 8A130F9B E52C747B A64ECDB1 799E5564 39531014 24126A6F

; p + q = 1 9502D905 90588475 F38A5137 362E1679 F19D35B5 ADEAB334 1F39B8DC 9BA24E58

p_prime dd 778FE3E9h,0E5E6A8C8h,344C5DCFh,4B4E6804h,5101A1FEh,6977419Bh,0D635C26Ch,0EABC39EBh,0
q_prime dd 24126A6Fh,39531014h,799E5564h,0A64ECDB1h,0E52C747Bh,8A130F9Bh,0BA22C209h,0AA469F19h,0
notice that i have added a 0 DWORD at the high-order end of each value, making them 288 bits, each

now, all we need is some code to display and add

give me a few minutes, and i will post a test program.....

[dedndave]

here - try this.....

[peter_asm]

:)

; p + q = 1 9502D905 90588475 F38A5137 362E1679 F19D35B5 ADEAB334 1F39B8DC 9BA24E58
; p + q = 1 9502D905 90588475 F38A5137 362E1679 F19D35B5 799EB334 1F39B8DC 9BA24E58

I see a typo there with edx but nice one, looks good.
Got confused with the byte order.

Thanks for taking time to help me, well appreciated.
We just have multiplication and division/modulus left...

j/k :)

[dedndave]

good catch - corrected the typo

division will be fun   
how large is the divisor ?

[peter_asm]

I found a couple of things to work with but it's late where i am probably won't do anything with it until tomorrow.
For multiply, i have

Code Select Expand


uint64_t multiply(uint64_t a, uint64_t b) {
  uint64_t c = 0;
 
  while (a > 0) {
    if (a & 1)
      c += b;
   
    a >>= 1;
    b <<= 1;
  } 
  return c;
}

This isn't too bad, could use rcr/rcl/add/adc there..with big numbers of course.
Not sure about division but I'm guessing something similar with sub/sbb will do it.

Did see this for 128-bit numbers

Code Select Expand

public static void DivMod (Int128 dividend, Int128 divisor, out Int128 quotient, out Int128 remainder)
{
    quotient = dividend;
    remainder = 0;
    for (int i = 0; i < 128; i++)
    {
        // Left shift Remainder:Quotient by 1
        remainder <<= 1;
        if (quotient < 0)
            remainder._lo |= 1;
        quotient <<= 1;

        if (remainder >= divisor)
        {
            remainder -= divisor;
            quotient++;
        }
    }
}

It doesn't have to be fast at all and in fact im just trying to grasp basics of how it's done at machine code level.
Picking simple algos... so no montgomery multiplication.

[dedndave]

well, i will give you a couple hints

if you multiply a 45-bit value by a 29-bit value, the result may be as large as (45+29) bits wide

for integer division, the modulus width may be as wide as the divisor, no wider

for integer division of values with large divisors, google "long division algorithm"
if the divisor is 32 bits or less, you can use "multiple-precision division"

there are other ways to go - like multiple-precision FPU code, but that's probably not what you're looking for

[dedndave]

couple more hints for long division
write the add and subtract routines first
then write shift-left and shift-right routines
you can make the division routine with a couple loops and calls   :P

[peter_asm]

Sounds like a good plan!
I'll get back tomorrow with my progress :)