Bigint (Bigbit) Library

Bigint (bigbit) library

There are several, including GMP, but for speed, the best is likely TTmath. TTmath's design decision to use templated fixed lengths at compiletime lets it be quite fast.

C++ Largest Numerical Storage

Check these:

• C++ Big Integer Library
• GMP
• TTMath

Using extremely large integer holding 3001 digits

Use an arbitrary-precision arithmetic library like GMP or Boost.Multiprecision.

How to store extremely large numbers?

If you already have a boost dependency (which many people these days do), you can use the boost multi-precision library. In fact, it already has an example of a factorial program that can support output up to 128 bits, though extending it further is pretty trivial.

BigInt isPrime test, more elegant solution?

Here is my primality checker for BigInts:

private static Boolean isSpsp(BigInteger n, BigInteger a)
{
    BigInteger two = BigInteger.valueOf(2);
    BigInteger n1 = n.subtract(BigInteger.ONE);
    BigInteger d = n1;
    int s = 0;

    while (d.mod(two).equals(BigInteger.ZERO))
    {
        d = d.divide(two);
        s += 1;
    }

    BigInteger t = a.modPow(d, n);

    if (t.equals(BigInteger.ONE) || t.equals(n1))
    {
        return true;
    }

    while (--s > 0)
    {
        t = t.multiply(t).mod(n);
        if (t.equals(n1))
        {
            return true;
        }
    }

    return false;
}

public static Boolean isPrime(BigInteger n)
{
    Random r = new Random();
    BigInteger two = BigInteger.valueOf(2);
    BigInteger n3 = n.subtract(BigInteger.valueOf(3));
    BigInteger a;
    int k = 25;

    if (n.compareTo(two) < 0)
    {
        return false;
    }

    if (n.mod(two).equals(BigInteger.ZERO))
    {
        return n.equals(two);
    }

    while (k > 0)
    {
        a = new BigInteger(n.bitLength(), r).add(two);
        while (a.compareTo(n) >= 0)
        {
            a = new BigInteger(n.bitLength(), r).add(two);
        }

        if (! isSpsp(n, a))
        {
            return false;
        }

        k -= 1;
    }

    return true;
}

You can read more about it at my Programming with Prime Numbers essay.

---

Related Topics