Sign in to follow this  
Lode

multiplication in "large" number class

Recommended Posts

Lode    1003
Hi, I've got a class representing a 128-bit fixed point number in C++ (called fixed128). The precision of this number allows me to have nanometer precision over a range of 4187211692790 lightyears :) There are 32 bits representing the part behind the point, the other bits are the part before the point, and one bit is the sign. I use two's complement to represent negative numbers (that turned out to be the easiest to implement). The bits of the number are stored in an array: unsigned int data[4]; and I assume unsigned int to be 32 bit. This made it easy to do addition and subtraction. A conversion to and from double (as long as in the range) is also working nicely. I also got a not too efficient left and right bit shift working. I'd however also like to have the ability to multiply this number with a double (multiplying with other things is fine too but not really needed for my purpose, I only need fixed128 * double). It's got these 4 unsigned ints, and each of them can have an influence on each other while the multiplication is done, and the fact that they're in two's complement when negative (while the other factor is a double where sign is represented in a totally different way) also doesn't seem to make it any easier. I don't know where to get started, how can I do this? P.S. This is a small class, that fits in my code without giving me external dependencies. I don't plan to use an already existing library. I know these will be much more efficient than any self-made implementation, but if my implementation is at least somewhat efficient I'm already happy. It's not that critical (it's only to generate some solar system coordinates in a galaxy), but I don't want to sit with a "stupid" inefficient implementation.

Share this post


Link to post
Share on other sites
Extrarius    1412
The basic way to multiply numbers in parts is to multiply each part with each other part and then put it in the appropriate position. The only difficult part is tracking overflow - if your compiler supports a 64 bit int type, that greatly, greatly simplifies things.

You have two numbers 'ABC.D' and 'HIJ.K'

0.K * 0.D is going to be a smaller fraction than your number can store, and so is not calculated

0.K * C.0 belongs in the fraction part, so store that there.

0.K * B0.0 belongs in the "ones" slot, so put that there.

[...]

J.0 * 0.D belongs in the fraction part, so add that to the previously calculated fraction part and carry any excess to the "ones" slot.

And so on. Obviously, if you're multiplying 32 bit numbers, the result can be up to 64 bits, which is why it's easier to use a larger data type for the intermediate steps. If you don't have access to a 64-bit integer type, the next best thing is to multiply 16 bits at a time and use 32-bit accumulators. This just means you'll need more steps and bit masking and shifting and a bit more work to make sure everything ends up contributing to the correct part of the result.

Share this post


Link to post
Share on other sites
iMalc    2466
I have a big-int class on my home page, and a fixed-int class which could take the big-int class as it's underlying data type, so essentially with a single typedef I can create a fixed128 that works exactly the same as you describe (and laid out in memory just the same, using two's-complement).
That said, my advice would be to simply create a constructor that takes a double and converts that to a fixed128.
From there all you need to do is a fixed128 multiply, which is taken care of already by the two classes I just mentioned.

Share this post


Link to post
Share on other sites
Lode    1003
Quote:
Original post by iMalc
I have a big-int class on my home page, and a fixed-int class which could take the big-int class as it's underlying data type, so essentially with a single typedef I can create a fixed128 that works exactly the same as you describe (and laid out in memory just the same, using two's-complement).
That said, my advice would be to simply create a constructor that takes a double and converts that to a fixed128.
From there all you need to do is a fixed128 multiply, which is taken care of already by the two classes I just mentioned.


Hey, I see that you do the multiplication by going over each bit and shifting. I implemented it like that to implement multiplication of fixed128 with an unsigned long (with shifting 32 times) but didn't post it because I thought that it was a very inefficient method that isn't worth it, because the multiplication of the unsigned ints directly on the CPU isn't used.

Since you're using it it must be an ok way to do it? Do you think this is a good method?

Nice classes on your page btw :)

Share this post


Link to post
Share on other sites
Rockoon1    104
Quote:
Original post by Extrarius

0.K * 0.D is going to be a smaller fraction than your number can store, and so is not calculated



Not true.

These are 0.32 fixed point..

..multiplication yields a 0.64 fixed point value


The lower 32-bits of this value can be thrown away, but not the upper 32.

Share this post


Link to post
Share on other sites
Extrarius    1412
Quote:
Original post by Rockoon1
[...]The lower 32-bits of this value can be thrown away, but not the upper 32.
You are, of course, correct. Oh well, I got the basic idea right despite having never actually implemented the algorithm =-)

Share this post


Link to post
Share on other sites
iMalc    2466
Quote:
Original post by Lode
Quote:
Original post by iMalc
I have a big-int class on my home page, and a fixed-int class which could take the big-int class as it's underlying data type, so essentially with a single typedef I can create a fixed128 that works exactly the same as you describe (and laid out in memory just the same, using two's-complement).
That said, my advice would be to simply create a constructor that takes a double and converts that to a fixed128.
From there all you need to do is a fixed128 multiply, which is taken care of already by the two classes I just mentioned.


Hey, I see that you do the multiplication by going over each bit and shifting. I implemented it like that to implement multiplication of fixed128 with an unsigned long (with shifting 32 times) but didn't post it because I thought that it was a very inefficient method that isn't worth it, because the multiplication of the unsigned ints directly on the CPU isn't used.

Since you're using it it must be an ok way to do it? Do you think this is a good method?

Nice classes on your page btw :)
Thanks.
Although most of that class is pretty well optimised (ignore the horrible prime number testing), multiplication is one of the areas I had thought I could improve. I did try writing it in such a way as to utilise built-in integer multiplication, but I deleted it for some reason. I certainly remember that the code for it was longer. Anyway, since I can't remember why I deleted it, and I don't think I had even profiled it, I might code it up again. I wouldn't be surprised if using built-in multiplication was actually faster though.

Share this post


Link to post
Share on other sites
Rockoon1    104
Quote:
Original post by _cdcel
Just curious, how would you convert a custom-sized number into text?


Repeated division and modulus by 10 is the most straightforward way.

Share this post


Link to post
Share on other sites
Extrarius    1412
Quote:
Original post by Lode
[...]Hey, I see that you do the multiplication by going over each bit and shifting. I implemented it like that to implement multiplication of fixed128 with an unsigned long (with shifting 32 times) but didn't post it because I thought that it was a very inefficient method that isn't worth it, because the multiplication of the unsigned ints directly on the CPU isn't used.

Since you're using it it must be an ok way to do it? Do you think this is a good method?

Nice classes on your page btw :)
I just remebered that I had an arbitrary size large integer implementation somewhere from a long time ago, so I looked it up and found the multiplication:
TLargeInt &operator *=(const TLargeInt &p_Other)
{
TLargeInt PlaceTracker(p_Other);
TLargeInt PlaceValue(*this);

(*this) = TLargeInt(0);
while(!PlaceTracker.IsZero())
{
if(!PlaceTracker.IsEven())
{
(*this) += PlaceValue;
}
PlaceTracker >>= 1;
PlaceValue <<= 1;
}
return (*this);
}



You could use the same procedure with slight modifications (such as testing the lowest bit instead of for even), with an extra step at the end to move the decimal back into the right spot.

This class had very limited use for a very specific purpose (establishing a shared key using a Diffie-Hellman key exchange) so it might not be the best implementation, but it was definitely fast enough for the purpose. If you want to implement modulus or exponentiation, the naive methods are too slow for large numbers, but simple shifting tricks speed them up tremendously.

Quote:
Original post by Rockoon1
Quote:
Original post by _cdcel
Just curious, how would you convert a custom-sized number into text?


Repeated division and modulus by 10 is the most straightforward way.
Since large-int division and modulus are generally slow (relative to both other operations on large int and relative to native operations on a regular int), it's better to divide by a larger number, such as 1000000000, and then put that into a native integer and extract individual digits from there to get 9 digits per large div/mod instead of just 1 =-)

Share this post


Link to post
Share on other sites
Extrarius    1412
Quote:
Original post by Lode
The result:

Source file
Header file

Thanks for the help :)
One thing I notice that could simplify some of your code would be to make it a template that allows you to specify the number of ints on each side of the decimal. Then, for the multiply, you could use the basic algorithm I posted but for fixed<3,1> you cast it to fixed<4,1> before the algorithm, use the standard operators for that size, then cast it back afterwards.

Share this post


Link to post
Share on other sites
iMalc    2466
Quote:
Original post by _cdcel
use:

(double)(0x100000000)

instead of:

4294967296.0

?

(Think it would be easier to determine the purpose of the number this way)

That assumes you have a compiler that supports 64bit integer literals.
I.e. don't try that with VS6.
However I agree that it you shouldn't have to type in the maximum value in decimal. I use:
(double(~0U) + 1.0)
But the preferred way would be to make use of std::numeric_limits.

Share this post


Link to post
Share on other sites
Lode    1003
Quote:
Original post by nmi
I think the most easy and fastest implementation for you problem would be using Karatsube multiplication:
http://en.wikipedia.org/wiki/Karatsuba_algorithm

This way multiplication of 128 bit numbers is based on multiplication of 32 bit numbers. Since the size of big integers is known the multiplication algorithm can be unrolled.


It looks like a good algorithm for even larger numbers, but mine aren't large enough yet:

Quote:
Implementations differ greatly on what the crossover point is when Karatsuba becomes faster than the classical algorithm, but generally numbers over 2^320 are faster with Karatsuba. [1][2] Toom-Cook multiplication is a faster generalization of Karatsuba's, and is further surpassed by the Schönhage-Strassen algorithm.


Mine are only up to 2^128 :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this