Big Int Division and Modulus

Index > High Level Languages > Big Int Division and Modulus

Author

Thread

Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA

Tyler 11 Sep 2010, 04:33

I've got a method to divide my bigint by an int. But since the bigint is stored as an array of unsigned ints, I see no way to div a bigint by a bigint. Is it even possible to do that? My Pre-Cal teacher seems to think not, I don't know. Something about violating fundamental rules of fractions...

Basically, I'm just starting at the most sig. unsigned int, and dividing it by the divisor, then storing the result of that in that unsigned int, and the remainder in the high end of a 64b int, then moving the next sig. uint into the low word, doing the div ... etc.

Here's my code for div'ing my an int:

Code:

     BigInt BigInt::div(BigInt dividend, int divisor)
    {
              unsigned int i = dividend.len;
              long long r = 0;

                // Check for div by 0
               //if(rhs == 0)
                      // Throw exception

              // Check signs
              if(dividend.sign != (divisor < 0))
                       dividend.sign = !dividend.sign;

         // Make rhs positive
                if(divisor < 0)
                  divisor = -1 * divisor;
             do{
                    i--;

                    // Get remainder and store in high word
                     r <<= sizeof(unsigned int) * 8;

                   // Get new low word
                 r += dividend.data[i];

                  // Do and store division
                    dividend.data[i] = r / divisor;

                 // Get remainder
                    r -= (r / divisor) * divisor;
               }while(i != 0);

            // Check for empty last block
               if(dividend.data[dividend.len - 1] == 0)
                    dividend.resize(dividend.len - 1);

              return dividend;
    }

P.S. The sign of the bigint is kept in a separate bool for simplicity.

11 Sep 2010, 04:33

bitRAKE

Joined: 21 Jul 2003
Posts: 4224
Location: vpcmpistri

bitRAKE 11 Sep 2010, 06:40

Sure it's possible, but it's slow.

Kind of cool method by Garthower:
http://board.flatassembler.net/topic.php?p=64895#64895

11 Sep 2010, 06:40

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20621
Location: In your JS exploiting you and your system

revolution 11 Sep 2010, 07:29

Read about Barrett's method. Or even Montgomery's if you are really keen.

11 Sep 2010, 07:29

Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA

Tyler 11 Sep 2010, 09:53

Thanks bitRAKE, I'm not sure what he's doing, but it looks like repeated subtraction. I didn't even think of repeated subtraction...

revolution, do you know of an algorithmic explanation of Barrett's? I've been reading a white paper about it, but the math is over my head.

11 Sep 2010, 09:53

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20621
Location: In your JS exploiting you and your system

revolution 11 Sep 2010, 10:11

The RSA macros use Barrett's Method

11 Sep 2010, 10:11

Kain

Joined: 26 Oct 2003
Posts: 108

Kain 30 Sep 2010, 01:44

is bigint the same as a qword?

30 Sep 2010, 01:44

bitRAKE

Joined: 21 Jul 2003
Posts: 4224
Location: vpcmpistri

bitRAKE 30 Sep 2010, 01:45

No, he's using an array of int for bigint.

Here is a very nice overview - I could even understand it:
www.treskal.com/kalle/exjobb/original-report.pdf

Last edited by bitRAKE on 30 Sep 2010, 02:47; edited 1 time in total

30 Sep 2010, 01:45

Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA

Tyler 30 Sep 2010, 02:02

I just used this guy's bigint class. He's also got a variable sized bigint class, that's pretty cool, but not so practical for my needs. It's really easy to use, and saved me about a month's worth of coding.

I've used the bigint template on his site for ints as big as 65536 bits. It allows more though... The best part is that you only get the crappy effects of such a huge int when you actually use some of it. In other words, even when it can hold a huge number, but actually holds a relatively small number, you get the performance of a relatively small number.

EDIT: I assume you run Windows. In which case the above would be easier than using gmp, but if you run a *nix, you should use gmp. It uses sub routines hand coded in asm by armies of people like revolution.

30 Sep 2010, 02:02

bitRAKE

Joined: 21 Jul 2003
Posts: 4224
Location: vpcmpistri

bitRAKE 30 Sep 2010, 02:51

After revolution's suggestion, I read the above paper.

GMP can easily be used through windows because another army took it and made it Windows friendly. Wink

(Quite active project, BTW.)

30 Sep 2010, 02:51

Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA

Tyler 30 Sep 2010, 03:10

Source tarball != Window's friendly

If it's for Windows, it has to have an msi or exe, or I won't touch it. Wink

There's no make [that's worth a crap] for Windows, so have fun installing that by hand. Razz

30 Sep 2010, 03:10

bitRAKE

Joined: 21 Jul 2003
Posts: 4224
Location: vpcmpistri

bitRAKE 30 Sep 2010, 06:33

Instructions:

http://www.exploringbinary.com/how-to-install-and-run-gmp-on-windows-using-mpir/

or try: mpir-2.1.3\build.vc10\readme.txt
seems trivial

The YASM source files can be used in FASM with little changes, and have been adjusted to the Windows ABI.

30 Sep 2010, 06:33

Kain

Joined: 26 Oct 2003
Posts: 108

Kain 01 Oct 2010, 01:04

bitRAKE wrote:

No, he's using an array of int for bigint.

Here is a very nice overview - I could even understand it:
www.treskal.com/kalle/exjobb/original-report.pdf

thanks, very good resource.

_________________
:sevag.k

01 Oct 2010, 01:04

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum