In other languages it is possible to do math on extremely large numbers. How can this be done in asm? From what I have read so far, math is done using the registers. This limits to only 32bit numbers on 32bit processors. How would one go about doing math on larger numbers?

One way that I can see would be to covert a decimal number to binary then do binary math on the numbers then convert back to decimal. This method would seem slow due to all the conversions, and digit by digit math on such large numbers. Is there a better more proficient way of dealing with large numbers in asm?

Thanks
~laz
Posted on 2007-09-15 10:32:54 by lazman

In other languages it is possible to do math on extremely large numbers. How can this be done in asm? From what I have read so far, math is done using the registers. This limits to only 32bit numbers on 32bit processors. How would one go about doing math on larger numbers?

Oh really ? The other languages use "Infinite Improbability Drive" to calculate large number.
Posted on 2007-09-15 10:55:58 by Dite
heh, ok
Posted on 2007-09-15 11:04:25 by lazman
It is a pain most of the time actually.... Here a simple example of adding two 128-bit unsigned integers but this is of the simplier arithmetic operations possible

mov ebx, addr c
mov esi, addr a
mov edi, addr b

mov eax,
add eax,
mov , eax

mov eax,
adc eax,
mov , eax

mov eax,
adc eax,
mov , eax

mov eax,
adc eax,
mov , eax


For multiplication and division is hard to understand and the code is a lot larger (check AMD Optimization Manual).

Before starting with these "advanced" topics is better to learn the basics first, read The Art of Assembly Language or related stuff. Just an advice but you do as you want :P

Actually valid for signed integer as well. Seems that I should learn the basics too :P
Posted on 2007-09-15 11:33:54 by LocoDelAssembly
That is because higher-level languages make use of the underlying architecture in such a way that it makes things transparent to the programmer... which is what the programmer really wants with a high-level language.

What happens if you have a one gallon bucket and you need to carry two gallons of water? You carry one gallon at a time... or get a bigger bucket ;)

Using the 32-bit General Purpose Registers, your standard compiler doesn't do anything different than what you would have to do if you were using a piece of paper and pencil... you'd keep track of carry/borrow operations and apply them while performing multiple iterations over a large number.
Posted on 2007-09-15 11:34:41 by SpooK
I would consider math operations to be basic. At least add, subtract, multiply, and divide. What I am attempting to accomplish is a proc or macro that will handle these basic math operations on signed/unsigned integer/float numbers from two memory locations no matter what the size of the numbers are. I understand there are some limitations. However, if I am able to accomplish this task then there will be no need to revisit this issue in the future. It will be as simple as passing the address of two numbers and getting an address to the result. The size of the numbers will not matter.

At this point, I am certain this can be done. I just do not fully understand the process of how to achieve it. I understand offsets, pointers, and basic concepts of this type. What would you consider basic?

Thanks for the reply!
~laz
Posted on 2007-09-15 12:25:48 by lazman
I remember doing 128 bit signed and unsigned divisions on a 16-bit processor under DOS. You can do a hell lot better using a 32-bit processor!
Posted on 2007-09-15 14:45:16 by XCHG
Do you remember the process you took to do this? Do you have some code that I can look at?

On a side note. I have been looking at GNU http://gmplib.org/ I am not sure how to implement this using asm. It does appear to be what I am wanting to accomplish, I think.

The main goal here is to have an easy interface that deals with basic math. That way I can focus on bigger task without being bogged down with math. I'm looking to create something so that I can do.

All_add addr1, addr2, result_addr
All_sub addr1, addr2, result_addr
All_mul addr1, addr2, result_addr
All_div  addr1, addr2, result_addr

Where addr1 and addr2 are pointers to the numbers that I want to do math on, then of course the result of the math operation is put into the result_addr. The code will be able to determine what kind of math should be done on the numbers by what is at that location. If it is an integer then it will do math for integers. If it is a signed number then it will do math for a signed number.

This will require some overhead that does not have to be there for a lot of calculations. However, the ease of use will be such that it will allow for easy code reading and writing.

Perhaps this task it too great for someone of my ability in programming with asm. But nonetheless it has already proven to be a great learning experience.

Has something like this already been done in asm? (still searching)
Am I trying to simplify math calculations interface too much?
How to work with numbers that are bigger than the register size? (this one has already been shown to some extent)
Is it possible to determine what kind of math calculations should be used? (I think it can, not exactly sure how yet)

These are some of the questions I have, and the order in which I am trying to answer them.

I hope all this makes sense.
~laz
Posted on 2007-09-15 15:19:58 by lazman
How to work with numbers that are bigger than the register size?

First of all I recommend to take a look at the file in the attachment. It's a fpu tutorial. With fpu you can calculate floating point numbers within rage 10^37 - 10^-37 (not precisely but take a look)

However, If you need really big integers, you can add them just like with pen and paper.
Let's add one

eax = low part of first number
edx = high parf of first number

ecx = low part of second number
ebx = high part of second number

;first add low parts
add eax, ecx
jnc @F ;if it's not carry goto @@
inc edx ; eax + ecx is bigger than 32bits, so we have a carry
@@:
;and the high parts
add edx,ebx
jc @error ; the sum of numbers are too big (bigger than 64bit)

If you have a pen and a papper, you will do same thing (probably)
Attachments:
Posted on 2007-09-15 15:46:03 by Dite
jc @error ; the sum of numbers are too big (bigger than 64bit)


How can this be avoided?

If you write the result to to a memory location then you only ever add two 32 bit numbers at a time. Correct?
Of course the memory location would have to be big enough to hold the result. What I am trying to say is that you only need to use two of the registers at a time.

I suppose figuring out how many bits the two number are is the part I am having trouble with. The only way I can think of is to null terminate the number like a c style string. Then it would be easy to see how big the numbers are and grab just 32 bits of them at a time to add. Then if the carry flag is set then add one to the next 32 bit set until all the numbers are gone through.

How is this problem of knowing how big a number at a location is usually solved? If it is a number bigger than a qword then there is no data type for a number that big. So, how do you figure out how many bits it is?

Thank you for uploading the FPU information. I will be reading though it.
~laz
Posted on 2007-09-15 16:17:12 by lazman
You may also want to have a look at the following if you intend to get into really BIG numbers:

http://www.ray.masmcode.com/BCDtut.html

The downloadable file also contains an example to extract the square root of any number with a precision of up to 9999 decimal places.

Raymond
Posted on 2007-09-15 22:10:46 by Raymond
I would consider math operations to be basic. At least add, subtract, multiply, and divide.

Some program I had made quite some time back.

Directly use strings (character array) to do the math operations.

The algorithm for doing the operationx is _exactly_ the way we would do it using pen-and-paper !!!  :lol:

P.S.
Please ignore that I had got a bit carried away with the UI elements  :P :lol: (center align text, flashing icon, etc)

Regards,
Shantanu
Attachments:
Posted on 2007-09-15 22:38:50 by shantanu_gadgil
Do you have the code for the math operations?

Also, it seems the program can not handle single numbers when dividing.
Posted on 2007-09-15 22:47:50 by lazman
Thanks Raymond for such a information. I just had to try out your root program. Unfortunately it just crashes. It does not matter what number I put in. It errors out every time.
Posted on 2007-09-15 23:00:11 by lazman
This is an example of doing 32-bit and 64-bit operations using 16-bit registers. It simply multiplies a 32-bit value in DX:AX by another 32-bit value in CX:BX and then returns the 64-bit QWORD result in DX:CX:BX:AX:


; ------------------------------
DWORDMUL PROC
  COMMENT *
    Description : Multiplies the DWORD value located at DX:AX by another DWORD
                  located at CX:BX and stores the result in DX:CX:BX:AX as a QWORD.
                  See note(s).

    Calling Convention : Register.

    Parameter(s) :
      WORD AX (Register) = The Low Order Word of the first DWORD value.
      WORD DX (Register) = The High Order word of the first DWORD value.
      WORD BX (Register) = The Low Order Word of the second DWORD value.
      WORD CX (Register) = The High Order Word of the second DWORD value.

    Stack Usage: 14 Bytes.

    Note : 1) When the procedure is through, DX:CX will hold the High Order DWORD
              and BX:AX will hold the Low Order DWORD of the result.

    Example : Multiply the DWORD number 0xFFFFFFFF by another DWORD with the same value.

    .CODE
      MOV    AX , 0FFFFh ; AX = 0xFFFF
      MOV    DX , AX    ; DX:AX = 0xFFFFFFFF
      MOV    BX , AX    ; BX = 0xFFFF
      MOV    CX , AX    ; CX:BX = 0xFFFFFFFF
      CALL    DWORDMUL    ; Multiply them now
      ; DX:CX:BX:AX = 0xFFFFFFFE00000001
  *
  PUSH    BP                              ; Push the base pointer onto the stack
  MOV    BP , SP                        ; Move the stack pointer to the base pointer
  SUB    SP , 000Ch                      ; Allocate 12 Bytes of space in the stack
  MOV    WORD PTR , AX          ; Store the AX register in BP-0Ch
  MOV    WORD PTR , DX          ; Store the DX register in BP-0Ah
  MOV    WORD PTR , 0000h      ; Zero out the content of the Result#4
  MOV    WORD PTR , 0000h      ; Zero out the content of the Result#3
  MUL    BX                              ; Multiply AX by BX
  MOV    WORD PTR , AX          ; BP-08h now holds the Result#1
  MOV    WORD PTR , DX          ; BP-06h now holds the Result#2
  MOV    AX , WORD PTR           ; AX is now equal to the original DX
  MUL    BX                              ; Multiplt AX by BX
  ADD    WORD PTR , AX          ; Result#2 = Result#2 + AX
  ADC    WORD PTR , DX          ; Result#3 = Result#3 + DX + Carry Flag
  MOV    AX , WORD PTR           ; AX is now equal to the original AX
  MUL    CX                              ; Multiply AX by AX
  ADD    WORD PTR , AX          ; Result#2 = Result#2 + AX
  ADC    WORD PTR , DX          ; Result#3 = Result#3 + DX + Carry Flag
  ADC    WORD PTR , 0000h      ; Result#4 = Result#4 + Carry Flag
  MOV    AX , WORD PTR           ; AX is now equal to the original DX
  MUL    CX                              ; Multiply AX by CX
  ADD    WORD PTR , AX          ; Result#3 = Result#3 + AX
  ADC    WORD PTR , DX          ; Result#4 = Result#4 + DX + Carry Flag
  MOV    AX , WORD PTR           ; AX = Result#1
  MOV    BX , WORD PTR           ; BX = Result#2
  MOV    CX , WORD PTR           ; CX = Result#3
  MOV    DX , WORD PTR           ; DX = Result#4
  ADD    SP , 000Ch                      ; Jump over the temporary results
  POP    BP                              ; Restore the base pointer
  RET                                    ; Return to the calling procedure
DWORDMUL ENDP
; ------------------------------


I have commented the code rather thoroughly but still if you think you need some help in understanding it, holler back!
Posted on 2007-09-16 05:29:44 by XCHG
A while ago I wrote my own Giant Number Math Lib, based on 'pen and paper methods'.
Apart from it working perfectly, two things went wrong.
First, nobody was ever interested.
Second, and more importantly, I never justified using it myself.

Shame, Shame, Shame.
Posted on 2007-09-16 08:09:26 by Homer

Thanks Raymond for such a information. I just had to try out your root program. Unfortunately it just crashes. It does not matter what number I put in. It errors out every time.

The program is designed to run under Windows and runs OK on my system with either Win98 or WinXP. Are you using an OS other than Windows? Does your system report the kind of error?

Raymond
Posted on 2007-09-16 09:50:10 by Raymond

Also, it seems the program can not handle single numbers when dividing.

For what values does it NOT work ?

The division is "integer division".

Regards,
Shantanu
Posted on 2007-09-16 11:24:41 by shantanu_gadgil
Do you want to write & understand the code yourself, or do you just want "bignum code that works"? If you just want something that works, look at GMP again, it should be relatively fast and relatively easy to use...
Posted on 2007-09-16 11:56:40 by f0dder


Also, it seems the program can not handle single numbers when dividing.

For what values does it NOT work ?

The division is "integer division".

Regards,
Shantanu


I tried it. Simply adding 1 + 2 threw errors.
Posted on 2007-09-16 12:32:23 by SpooK