A Trillion Triangles and a Few Multicore Processors
Solving an old mathematic problem seems a lot like picking at a scab. But then I'm not a mathematician. Still, it's hard not to be impressed when mathematicians solve a problem that's stumped other mathematicians for hundreds of years.
The latest example is the Congruent Number Problem, first posed by the Persian mathematician al-Karaji (c.953 - c.1029). The problem involves determining which whole numbers can be the area of a right-angled triangle whose sides are whole numbers or fractions. The area of such a triangle is called a "congruent number." For example, the 3-4-5 right triangle that students see in geometry has area 1/2 x 3 x 4=6, so 6 is a congruent number. The smallest congruent number is 5, which is the area of the right triangle with sides 3/2, 20/3, and 41/6. The first few congruent numbers are 5, 6, 7, 13, 14, 15, 20, and 21.
Actually, the international team of mathematicians didn't really solve the problem -- they only resolved it for the first 1 trillion cases. As it turns out, the biggest challenge was that these numbers were so large that they couldn't fit in the computer's main memory (right, it's a hardware problem), so the researchers resorted to accessing hard drives (what do you think *that* did to network performance?).
To ensure accuracy, the mathematicians split into two teams. Team "1" -- Bill Hart (Warwick University) and Gonzalo Tornaria (Universidad de la Republica) -- used "Selmer," a DUNK Teraserve R2850 with four 2.4 Ghz AMD quad-core CPUs, 128-GB RAM, a 1.5-TB hard drive, and an NVIDIA nForce Pro 3600 chipset. Team "2" -- Mark Watkins (University of Sydney), David Harvey (NYU), and Robert Bradshaw (University of Washington) -- used "Sage," a Sun Fire X4450 Server built around 4x6-core 2.66-GHz Intel Xeon CPUs, 128-GB RAM, and 2.7 TB hard drive. As for the software, the teams based their calculations on the freely available C library FLINT (short for "Fast Library for Number Theory").
"The difficult part was developing a fast general library of computer code for doing these kinds of calculations," says Bill Hart. "Once we had that, it didn't take long to write the specialized program needed for this particular computation." (For a detailed description of how they approached the problem, see Congruent Number Theta Coefficients to 10^12.)
Many congruent numbers were known prior to the new calculation. For example, every number in the sequence 5, 13, 21, 29, 37, ..., is a congruent number. But other similar looking sequences, like 3, 11, 19, 27, 35, ...., are more mysterious and each number has to be checked individually. The calculation found 3,148,379,694 of these congruent numbers up to a trillion. I'm impressed.