Fast Bignum Square Computation

Fast bignum square computation

If I understand your algorithm correctly, it seems O(n^2) where n is the number of digits.

Have you looked at Karatsuba Algorithm?
It speeds up multiplication using the divide and conquer approach. It may be worth taking a look at.

Is there a good way to optimize the multiplication of two BigNums?

If you use a different base, say 2^16 instead of 10, the multiplication will be much faster.

But getting to print in decimal will be longer.

Calculating the square of BigInteger

That depends on how large your numbers are. As the Wikipedia page tells you:

In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2²¹⁵ to 2²¹⁷ (10,000 to 40,000 decimal digits).

System.Numerics.BigInteger uses the Karatsuba algorithm or standard schoolbook multiplication, depending on the size of the numbers. Karatsuba has a time complexity of O(n ^log₂ 3). But if your numbers are smaller than above quoted figures, then you likely won't see much speedup from implementing Schönhage–Strassen.

As for Pow() this itself squares the number at least once during its calculations (and it does that by simply doing num * num – so I think this won't be more efficient, either.

Prove or disprove: it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers [duplicate]

If x and y are two n bit numbers, then x+y is an n+1 bit number. ((x+y)^2 - x^2 - y^2)/2 is xy.

So multiplication of two n bit numbers is at most as expensive as 1 addition, three squarings, two subtractions, and a divide by 2.

Since addition, subtraction and division by 2 are Theta(n), this shows that squaring can't be asymptotically faster.

Trying to understand simple big number calculations

addition and substractions are pretty straightforward

You need to inspect signs and magnitudes of operands and if needed convert the operation to/from +/-. Typical C++ implementation of mine for this is like this:

//---------------------------------------------------------------------------
arbnum arbnum::operator + (const arbnum &x)
    {
    arbnum c;
    // you can skip this if you do not have NaN or Inf support
    // this just handles cases like adding inf or NaN or zero
    if (  isnan() ) return *this;
    if (x.isnan() ) { c.nan(); return c; }
    if (  iszero()) { c=x; return c; }
    if (x.iszero()) return *this;
    if (  isinf() ) { if (x.isinf()) { if (sig==x.sig) return *this;
                    c.nan(); return c; } return *this; }
    if (x.isinf()) { c.inf(); return c; }
    // this compares the sign bits if both signs are the same it is addition
    if (sig*x.sig>0) { c.add(x,this[0]); c.sig=sig; }
    // if not
    else{
        // compare absolute values (magnitudes)
        if (c.geq(this[0],x)) // |this| >= |x| ... return (this-x)
                {
                c.sub(this[0],x); 
                c.sig=sig;    // use sign of the abs greater operand
                }
        else    {             // else return (x-this)
                c.sub(x,this[0]);
                c.sig=x.sig;
                } 
        }
    return c;
    }
//---------------------------------------------------------------------------
arbnum arbnum::operator - (const arbnum &x)
    {
    arbnum c;
    if (  isnan() ) return *this;
    if (x.isnan() ) { c.nan(); return c; }
    if (  iszero()) { c=x; c.sig=-x.sig; return c; }
    if (x.iszero()) return *this;
    if (  isinf() ) { if (x.isinf()) { if (sig!=x.sig) return *this;
                    c.nan(); return c; } return *this; }
    if (x.isinf()) { c.inf(); c.sig=-x.sig;  return c; }
    if (x.sig*sig<0) { c.add(x,this[0]); c.sig=sig; }
    else{
        if (c.geq(this[0],x))
                {
                c.sub(this[0],x);
                c.sig=sig;
                }
        else    {
                c.sub(x,this[0]);
                c.sig=-x.sig;
                }
        }
    return c;
    }
//---------------------------------------------------------------------------

where:

• geq is unsigned comparison greater or equal
• add is unsigned +
• sub is unsigned -

division is a bit more complicated

see:

• bignum divisions

• approximational bignum divider

  For divisions you need to have already implemented things like +,-,*,<<,>> and for some more advanced approaches you need even things like: absolute comparison (you need them for +/- anyway) , sqr, number of used bits usually separate for fractional and integer part.

  The most important is the multiplication see Fast bignum square computation because it is core for most division algorithms.

performance

for some hints see BigInteger numbers implementation and performance

text conversion

If your number is in ASCII or in BASE=10^n digits then this is easy but If you use BASE=2^n instead for performance reasons then you need to have fast functions capable of converting between dec and hex strings so you can actually load and print some numbers to/from your class. see:

• How do I convert a very long binary number to decimal?
• How to convert a gi-normous integer (in string format) to hex format?

What is a convenient base for a bignum library & primality testing algorithm?

The base you use should be a power of 2. Since it looks like you're going to keep track of sign separately, you can use unsigned ints for storing the numbers themselves. You're going to need the ability to multiply 2 pieces/digits/units of these numbers at a time, so the size must be no more than half the word size you've got available. i.e. on x86 an unsigned int is 32 bits, so you'd want your digits to be not more than 16 bits. You may also use "long long" for the intermediate results of products of unsigned ints. Then you're looking at 2^32 for your base. One last thing to consider is that you may want to add sums of products, which will overflow unless you use fewer bits.

If performance is not a major concern, I'd just use base 256 and call it a day. You may want to use typedefs and defined constants so you can later change these parameters easily.

---

Related Topics