Author Topic: 256-bit integer division on x86_64  (Read 8598 times)

Offline Ux

  • Jr. Member
  • *
  • Posts: 12
256-bit integer division on x86_64
« on: May 12, 2012, 06:40:22 PM »
Hi folks,

Is there any way to use the Intel64 integer division instructions
to perform a larger division of 128, 256, or more bits?
I can imagine how a larger multiplication might work but
how to do division based on smaller units somehow escapes me.
BTW I'm not opposed to using multiplication to perform said
division but I'd like to hold off on that until using division
instructions is ruled out.
Help?

Thanks.

Offline TightCoderEx

  • Full Member
  • **
  • Posts: 103
Re: 256-bit integer division on x86_64
« Reply #1 on: May 12, 2012, 07:40:21 PM »
Essentially, multiplication and division are nothing more than successive addition and subtraction respectively. Take for example and keep in mind this would not work as simplistically in code

    3107224 / 4021 = 772 with 3012 left over

     31072
   -   4021 can be done 7 times

       292524
   -     4021 can be done another 7 times

         11054
        -   4021 can be done twice

and 3021 will be the remainder

So you can see by successively shifting the divisor, you are only limited by the amount of memory.

This also works on an 8 bit computer, but with 64 bits you may be able to design an algo that more effective than exclusively using memory.
« Last Edit: May 12, 2012, 07:42:23 PM by TightCoderEx »

Offline codeFoil

  • Jr. Member
  • *
  • Posts: 13
Re: 256-bit integer division on x86_64
« Reply #2 on: May 12, 2012, 09:09:12 PM »
You may find this helpful : http://homepage.mac.com/randyhyde/webster.cs.ucr.edu/www.artofasm.com/Windows/HTML/AdvancedArithmetica2.html

Division is covered toward the bottom of the page.

The example code is in R. Hyde's HLA, but the concept is easy to translate.

Offline Mathi

  • Jr. Member
  • *
  • Posts: 82
  • Country: in
    • Win32NASM
Re: 256-bit integer division on x86_64
« Reply #3 on: May 20, 2012, 05:31:43 AM »
If you guys are talking about Multi precision arithmetic,
I tried this sometime back. It works for decimal numbers.

I have attached the zip file with the macros, procedures and the example program.(bignum.asm)

It uses Nagoa+.inc .

Quote
Essentially, multiplication and division are nothing more than successive addition and subtraction respectively.

Yes , thats what this does.

Thanks,
Mathi.