flat assembler
Message board for the users of flat assembler.

Index > High Level Languages > Big Int Division and Modulus

Author
Thread Post new topic Reply to topic
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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.
Post 11 Sep 2010, 04:33
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3045
Location: vpcmipstrm
bitRAKE
Sure it's possible, but it's slow.

Kind of cool method by Garthower:
http://board.flatassembler.net/topic.php?p=64895#64895
Post 11 Sep 2010, 06:40
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17669
Location: In your JS exploiting you and your system
revolution
Read about Barrett's method. Or even Montgomery's if you are really keen.
Post 11 Sep 2010, 07:29
View user's profile Send private message Visit poster's website Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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.
Post 11 Sep 2010, 09:53
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17669
Location: In your JS exploiting you and your system
revolution
The RSA macros use Barrett's Method
Post 11 Sep 2010, 10:11
View user's profile Send private message Visit poster's website Reply with quote
Kain



Joined: 26 Oct 2003
Posts: 108
Kain
is bigint the same as a qword?
Post 30 Sep 2010, 01:44
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3045
Location: vpcmipstrm
bitRAKE
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
Post 30 Sep 2010, 01:45
View user's profile Send private message Visit poster's website Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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.
Post 30 Sep 2010, 02:02
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3045
Location: vpcmipstrm
bitRAKE
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.)
Post 30 Sep 2010, 02:51
View user's profile Send private message Visit poster's website Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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
Post 30 Sep 2010, 03:10
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3045
Location: vpcmipstrm
bitRAKE
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.
Post 30 Sep 2010, 06:33
View user's profile Send private message Visit poster's website Reply with quote
Kain



Joined: 26 Oct 2003
Posts: 108
Kain
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
Post 01 Oct 2010, 01:04
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.