Bloomiboy Babble -- Technical,'s all here...

Here's where I do a brain dump of everything I feel like throwing out's part technical, part personal, part crap, and hopefully you get to learn something...sometime.

Saturday, September 02, 2006

Euler or Euler-Mascheroni's Constant and its large precision calculation

This post has been inspired by one of the assignments I had for an Algorithms course while in graduate school. The task was to find 4 integer values a, b, c and d such that:

a/b < γ < c/d

There were 3 tests to be satisfied for the above condition:
1.) a/b < c/d
2.) a/b is the proper lower bound, i.e. a/b < γ
3.) c/d is the proper upper bound, i.e. c/d > γ

The ultimate test was to get the lowest possible difference (c/d - a/b)
Note that the same question can be applied to any mathematical constant such as e (Euler's number, natural logarithm base) and pi (approx. 22/7).

Some background on γ from my final project document:

The calculation of Euler's constant (γ) has not attracted the same public intrigue as pi or even e but it has inspired the dedication of a few. While we presently know millions of decimal places of it's other contemporaries, only several thousand places of pi are known till now. Initially started by D.E. Knuth, it was soon followed by Sweeney, Brent & McMillan, and some recent methods have taken the limit to a few hundred thousand digits of accuracy.

This project, though not directly involved in the calculation of the accuracy of γ to any limit, does involve the calculation to a certain limit governed only by time. It seeks to find out the bounds within which γ lies. The accuracy of these bounds, as suggested, will be limited by the amount of computer time that is allowed for the program.
Most of the details are in the project document (in PostScript format; you will need GhostScript/GhostView to view it) and I will mention just my relevant experiences in the current post. The document also provides a very clear background, derivations and explanations of all the formulae used and the method chosen. The final program was written in C on the Solaris platform using the GNU Multi Precision library (GMP). GMP defines its own float, double and integer variables such that the values and precision are limited only by the amount of hard-disk space available on your machine. So theoretically, you can represent a float/double value of infinite length using this library. Given a chance I encourage you to use this extremely lucid library for any other needs that require maintenance of large precision values. Note: Be careful not to blame this library for any bugs in your program.

The maximum precision of your calculations is limited by the minimum precision among all the parameters in your equation.

e.g., if you are calculating d = a * b * c, and a's precision = 10 digits, b's precision = 15 digits and c's precision = 7 digits, then the overall precision of d will be 7 digits. These kind of gotchas make the above problem very interesting.

One rule to make the program tougher would be to disallow the use of float/double GMP variables in your program. --- In the process of finding the solution, there was the need to find the natural logarithm of a number; and based on the above logic, we inadvertently also solved the problem of finding the logarithm value of a number to a large precision value.

The document makes really interesting reading with regards to why one method was chosen above the other. In the end, the C program (of course, the results are specific to the machine used then) could calculate a precision of 14,200 bits (or roughly 4275 digits of accuracy) and I'm happy to mention that this was the best precision calculation in a minute amongst all folks in the course. --

Lots of details in the linked document below, including the source code for the program (in PostScript format; you will need GhostScript/GhostView to view it). Most machine and course specific information has been removed from it.

Standard Disclaimer: If you plan to use the information in this document for your personal or professional work, I will not have any copyright issues but feel free to acknowledge this article. Also, I bear no responsibility to the accuracy or correctness of this document that may cause issues for your specific usage. Please be aware of plagiarism notices of research work.

PostScript document (631KB, 59 pages)


Post a Comment

<< Home