flat assembler
Message board for the users of flat assembler.

 Index > High Level Languages > Big Int Division and Modulus
Author
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: 3977
Location: vpcmipstrm
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: 20212
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: 20212
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: 3977
Location: vpcmipstrm
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: 3977
Location: vpcmipstrm
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.
(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. There's no make [that's worth a crap] for Windows, so have fun installing that by hand.
30 Sep 2010, 03:10
bitRAKE

Joined: 21 Jul 2003
Posts: 3977
Location: vpcmipstrm
bitRAKE 30 Sep 2010, 06:33
Instructions:

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

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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

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