Channels ▼

Jonathan Erickson

Dr. Dobb's Bloggers

A Trillion Triangles and a Few Multicore Processors

October 02, 2009

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video