Channels ▼

Mark Nelson

Dr. Dobb's Bloggers

Big Numbers

September 28, 2009

Nothing is more fun than mathematics, right? It must then follow that Robert Bradshaw, William B. Hart, David Harvey, Gonzalo Tornaria, and Mark Watkins had more fun last year than anyone else on the planet. This is the team that found all the congruent numbers up to a trillion, a remarkable achievement in the annals of mathematics.

 What makes this feat notable to Dobbs readers is that the software that generated the sequence had to multiply numbers so large they wouldn't fit in 128GB of RAM. According to the team's report, the polynomials used in these calculations ended up requiring .5TB of memory, significantly more than was available on their host machines.

What is a congruent number ?

An integer n is considered congruent if it is the area of a right triangle whose sides are all of rational length. (Rational, but not necessarily integral.) The simplest example of this is the congruent number 6, the area of a triangle with sides of lengths 3, 4, and 5.

It is relatively easy to find congruent numbers by generating Pythagorean triples, but pumping them out in order is not so simple. If you just start generating triples, odds are you will find 6 as your first congruent number, but it might be a bit longer before you generate the numbers that show you that 5 is also congruent.

Using something called Tunnel's criterion, the team listed above was able to decide whether every number below 1012 was congruent or not. This feat is all the more remarkable when you consider that in 1980, congruent status was not even known for all the integers under 1000.

While the details of the algorithm wander into some areas that might be hard to follow for those without serious credentials, the overall description of the implementation is still fascinating.  Anyone who has ever used a bignum will have a deep appreciation for how this was done - and of course the program had to deal with multiprocessing issues as well.

Any ideas on what other mathematical challenges are ready to fall to modern hardware attacks?

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