multiplication in "large" number class
Author
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.
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.
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.
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.
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.
Author
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 :)
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.
Quote:Original post by Rockoon1You are, of course, correct. Oh well, I got the basic idea right despite having never actually implemented the algorithm =-)
[...]The lower 32-bits of this value can be thrown away, but not the upper 32.
Quote:Original post by LodeThanks.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 :)
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.
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.
Quote:Original post by LodeI 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:
[...]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 :)
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);}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 Rockoon1Since 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 =-)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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement