Warren Weckesser: CLN Example

Computing With Large Integers Using the CLN C++ Library

CLN is a C++ library that allows you to do arithmetic with arbitrarily large integers.

As an example, I have written a program, ammprobcln.cpp, that searches for solutions to the equation

n³ + n² + n + 1 = x²
To run the program on a computer in the lab, first save the file to your home directory. Then start up a terminal, and enter the command

$ g++ ammprobcln.cpp -o ammprobcln -lcln

This will compile the C++ program, and create the command ammprobcln. This command takes two arguments that give the range of integers to test. For example, to test the integers from 1 to 10000, enter

$ ./ammprobcln 1 10000

This will produce the output

1 4 2
7 400 20

The first number in each line of output is the value of n, and the third number is x.

You don't have to be an expert C++ programmer to use this library. Take a look at the C++ program. The main loop of the computation is at the bottom, beginning with the line that says while ( n <= nlast ). (Note that n³ + n² + n + 1 = (n²+1)(n+1).) The code before this point consists of C++ header information, variable declarations, and some code that gets the numbers from the command line. You can use this C++ file as a template for your own programs.

To learn about the CLN functions that are available, check out the CLN documentation. In particular, for integers, you will find an assortment of interesting functions (including gcd, lcm, and more) in Section 4.9, and the sqrtp function that I used in my example is documented in Section 4.7.

But what about...?

Experienced programmers, or users of software such as Maple or Mathematica, might ask about alternatives to CLN.

Why not just use the C/C++ integers?
An unsigned long integer is represented with 32 bits. The largest number that can be represented is 2³² - 1. If n = 2048 = 2¹¹, then n³ = 2³³, so the computations required for this problem could only be done for n < 2048.
Maple can handle arbitrarily large integers. Why not use Maple?
You can use Maple, or Mathematica, or some other computer algebra system (CAS). However, you will generally find that using C++ is much faster. If you are familiar with a CAS, you could use it to perform your experiments and initial tests. But when you are ready to do some serious computation, you can translate your problem to C++/CLN.
For example, here is a Maple script that performs the search for solutions to the above problem for n up to 10⁷: ammprobmaple.txt. On my computer, with Maple 10, this program takes 130 seconds. The CLN program takes 12.8 seconds.
I feel the need for speed. Is there anything faster?
If you are willing to leave the convenience of C++ and use C, you can use the GNU MP library (GMP). For example, here is a C program that uses GMP to solve this problem: ammprobgmp.c. Compared to CLN, programming with GMP is awkward. However, the compiled program runs faster. This program required just 5.3 seconds to search up to n = 10⁷, less than half the time required by the CLN version.
Timing summary for a search up to n = 10⁷:

Maple 130. sec

CLN (C++) 12.8 sec

GMP (C) 5.3 sec

Footnotes:

Depending on how CLN was configured, it might be using GMP as its library for handling large integers. So you can think of CLN as a nice C++ wrapper around GMP. (CLN also includes many more higher-level mathematical functions.)
GMP includes its own C++ interace to the GMP C library. However, I found that it is slower than using CLN. Also, not all of the C functions have C++ wrappers, so you will probably have to access the C data structures and functions at some point in your code.

(Notes by Warren Weckesser, June 2006)

Maple	130. sec
CLN (C++)	12.8 sec
GMP (C)	5.3 sec