**PETZOLD BOOK BLOG**

Recent Entries | ||

< Previous | Browse the Archives | Next > |

Subscribe to the RSS Feed |

December 12, 2007

Roscoe, N.Y.

I *do* have work to do today. I have an article for *MSDN Magazine* due on Saturday, and I have a book to finish by the end of this month. But this morning when Deirdre emailed me an article about
Alexis Lemaire calculating 13th roots of 200-digit numbers in his head I got a little, well, distracted.

Here's the deal: Two days ago Alexis Lemaire was given a "random" 200-digit number and in 70.2 second he calculated the 13th root of the number, or 2,407,899,893,032,210.

I put "random" in quotation marks because obviously the particular 200-digit number wasn't *entirely* random. It was a 200-digit number that has an *integral* 13th root.

So I started thinking: **Exactly how many 200-digit numbers have integral 13th roots?** Maybe it's not so many. Maybe this is less a calculational job than a memorization job. For example, suppose you wanted to calculate 13th roots of 20-digit numbers. There are only 6 of them: 29 (to the 13th power equals 10,260,628,712,958,602,189) through 34 (to the 13th power equals 81,138,303,245,565,435,904). But I had no feel for how that fact could be extrapolated to 200-digit numbers.

**
Solution 1. Write a Program!
**

Yeah, except that when you want to mess around with 200-digit numbers, you're beyond the realm of common integer arithmetic. You need arbitrary-precision integers, and I was actually on my way to writing a tiny arbitrary-precision integer class in C# that derived from *List<int>* to store the digits. I had the + override finished and when plotting out my strategy for * I figured I should look around for somebody else's arbitrary-precision integer library. After all, I *do* have work to do today.

After a little bit of search, and contemplating downloading the GNU multi-precision (GMP) library, I stumbled upon
this .NET Matters article by Stephen Toub where he recommends using the J# *BigInteger* class. I didn't even have to download anything new!

This
ThirteenthRoots.cs program requires a reference to vjslib.dll (which is probably on your machine if you have Visual Studio installed) and it has an *include* statement for the *java.math* namespace.

The program uses the *pow* method to calculate the 200-digit number Alexis Lemaire was given, which I won't repeat here. The program also attempts to find all 200-digit numbers that have integral 13th roots. I don't know if this part of the program is working right or not; I suspect the brute-force method I implemented might require several years or even centuries of processing time.

However, while attempting to refine the range of numbers the program tests, I realized I didn't need to write a program at all. Duh!

**
Solution 2. Do the Math!
**

The math to determine how many integers have 13th powers with 200 digits is actually quite easy and can be done with the Windows Calculator. We're looking for all integer values X that satisfy the following relationship:

10^{199} ≤ X^{13} < 10^{200}

or:

10^{199/13} ≤ X < 10^{200/13}

The calculation on the left gives you an X value of 2,030,917,620,904,735 with an infinite decimal so the lowest integer is 2,030,917,620,904,736. Similarly, 10 to the 200/13 power is 2,424,462,017,082,328 with an infinite decimal that can be ignored. There are therefore 393,544,396,177,593 numbers that have 13th powers with 200 digits. That results prompts me to be much more impressed with Alexis Lemaire's feat, and it confirms that the Yahoo article was actually accurate when it referred to "a possible 393 trillion answers."

**
Solution 3. Look it up in Wikipedia!
**

While preparing this blog entry, I wondered if there might be a term akin to "square root" and "cube root" that is better than "13th root," and I came upon this Wikipedia entry on "13th Root" that contains precisely the information that I calculated and some other little nuggets as well.

The moral for the day is: **Code is cool but Wikipedia is speedier.**

Recent Entries | ||

< Previous | Browse the Archives | Next > |

Subscribe to the RSS Feed |

(c) Copyright Charles Petzold

www.charlespetzold.com

Comments:There are very efficient algorithms for exponentiation and it's possible that he's using something like the square and multiply algorithm in reverse, and I'm sure you could do that very quickly with a lot of practice at it which the wikipedia entry says he does a lot of.

I'd say the moral of the story is if you spend your time practicing the calculation of 13th roots then you need something else to be working on. More impressive would be calculations of that magnitude with little practice at all.

— Richard Threlkeld, Wed, 12 Dec 2007 18:22:51 -0500 (EST)

Charles, your "moral for the day" reminds me of Spike Milligan's little poem, "String", which goes like this:

String is a very important thing

Rope is thicker, but string is quicker

Almost as succinct is his treatise on "Rain":

There are holes in the sky where rain comes in

The holes are very small, that's why rain is thin

Oh, and nice work on the 13th roots, too :D Now let's both get back to doing what we should be doing!

— Philip the Duck, Thu, 13 Dec 2007 09:23:15 -0500 (EST)

I was actually thinking of another little poem:

"Reflections on Ice Breaking" by Ogden Nash

Candy

Is dandy

But liquor

Is quicker.

— Charles

Last time I checked, J#'s BigInteger class has a bug: Try

BigInteger bI = new BigInteger("117137");

boolean b = bI.isProbablePrime(2);

J++ 6.0 works great, but J++ won't work under Vista.

Real Java is an option, but you still need to re-invent the user interface every time.

VBA/Excel is great for some research, you can program with zero I/O overhead, but VBA can't handle real-sized numbers.

Alas, MS software can handle only trivial-sized numbers when MS has a big budget for scientific research. If Bill had only graduated from college, maybe it would be different....

— Bill Ellis, Thu, 13 Dec 2007 22:32:42 -0500 (EST)

I will prefer the 1st option since 3rd option suffer from several problems (http://www.spinellis.gr/blog/20071110/)

— Chris Mylonas, Fri, 14 Dec 2007 03:23:34 -0500 (EST)