What is the convenient base for the bignum library and the primacy testing algorithm?
I have to program the Nightingale-Strassen primitiveness test presented in the original article on RSA.
Also, I will need to write a small bignum library, so when looking for a convenient representation for bignum, I came across this specification :
struct {
int sign;
int size;
int *tab;
} bignum;
I will also be writing a multiplication routine using Karatsuba's method.
So on my question:
Which database would be convenient for storing integer data in a bignum structure?
Note. I am not allowed to use third party or inline implementations for bignum such as GMP.
Thanks.
a source to share
The base you are using must be of cardinality 2. Since it looks like you will be tracking the sign separately, you can use unsigned ints to store the numbers themselves. You will need the ability to multiply 2 parts / digits / units of these numbers at a time, so the size should be no more than half the word size available to you. that is, on x86, the unsigned int is 32 bits, so you want your digits to be no more than 16 bits. You can also use "long long" for intermediate results of unsigned int products. Then you are looking at 2 ^ 32 for your base. One last thing to consider is that you might want to add the amounts of products that will overflow if you don't use fewer bits.
If performance isn't a major issue, I would just use base 256 and call it a day. You can use typedefs and certain constants so that you can easily change these parameters later.
a source to share
Power 2.
For a simple implementation, perhaps half the word size on your computer so you can multiply two digits without overflow. So 65536 or 4294967296. Or perhaps half the size of the largest integer type for the same reason, but possibly better performance than all.
But I have never implemented such a library: if you use the most famous algorithms, then you will not do long multiplication in the school style. Karatsuba multiplication (and any other clever tricks you use) could benefit from being executed on an integer size that's more than double the size of the digits, I really don't know how performance works. If so, then you are better off using 256 and 32 bit arithmetic or 65536 and 64 bit arithmetic.
In any case, if your representation is binary, you can pick and choose more powerful bases with two main parameters that are convenient for each operation. For example, you can treat the data as a 2 ^ 16 base to multiply, but a 2 ^ 32 base to add. It's like you're being careful about endianism. I would probably start with a base of 2 ^ 16 (since that makes me start at the end, and 2 ^ 8 doesn't) and see how I find myself - as each operation is optimized, the optimization is to determine the best base.
Using a size that is not a multiple of bytes is a possibility, but then you should use the same base for everything, because there are unused bits in the store in certain locations according to the base.
a source to share
You will perform the following operation:
ab + cd ...
Either choose 1/4 the largest word size, or 1/2 the largest word size less than a bit or two. That would be 2 ^ 16 or 2 ^ 30 for 64-bit systems and 2 ^ 8 or 2 ^ 14 for 32-bit systems. Use the largest size the compiler supports, not the hardware.
If you choose 2 ^ 31 on a 64-bit system, that means you can add 4 products without overflow. If you choose 2 ^ 30, you can add 16 products without overflow. The more you can add without overflow, the larger intermediate blocks you can use.
If you choose 1/4 the word size, you will still have your own type to make it easier to save the results. You can also ignore overflow. This will basically make the writing code faster and less error prone, and also slightly more memory efficient. I would recommend this if you are not comfortable with the many bit manipulations along with your math.
Choosing a larger base will make the larger O-numbers look better. In practice, while it would probably be faster to have a larger base, it won't be the 4x speed you might have hoped for.
a source to share
Integers in a tab array must be unsigned. They should be the largest possible size (base) that you can multiply and still represent the product. For example, if your compiler / processor supports 64-bit unsigned for a long time, you can use uint32_t for an array of "digits". If your compiler / processor can only natively produce 32-bit products, you should use uint16_t.
When you sum two arrays, you will need to deal with overflow; in assembly it is easy. In C, you can choose one bit (31 or 15) to make overflow detection easier.
Also consider endianess, and the effect it and the algorithm will have on cache behavior.
a source to share