5

I am building a library class that provides functionality for mathematical operations on BigDecimals (and a few on BigIntegers). Now, BigIntegers are quite easy to master and pleasant to use. BigDecimals can be tricky, but in the end, it finally pays off.

I want my class to provide results accurate up to a specified level of accuracy (like, number of places after the decimal point). This is where Math fails me because it supports operations on double. Now double supports 15-16 significant digits (not 15-16 places after decimal.) Hence, I've decided to upgrade to Bigdecimal.

But now, the problem is where can I find algorithms that support arbitrary precision calculations? Moreover, I would like to make my BigMath(so I call it) analogous to its sibling in the java.lang package. Then it struck me that if I opt for algorithms used by scientific calculators, then I might achieve the required level of accuracy.

So here are my (related) questions:

  1. Can I achieve the required level of accuracy using calculator algorithms?
  2. If yes, then where can I find the required algorithms?
  3. Are there any caveats lurking in my approach?

UPDATE: Right now, I have just added support for the sqrt(BigDecimal) method. It makes use of the Newtonian method (and a special trick to generate a good estimate).

So, here's the entire BigMath class:

package in.blogspot.life_on_the_heap.bigmath;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;

/**
 * @author ambigram_maker
 */
public class BigMath {

    public static void main(String[] args) {
        BigDecimal number = new BigDecimal("91.91");
        BigDecimal sqrt = sqrt(number);
        System.out.println("number = " + number);
        System.out.println("sqrt(number) = " + sqrt);
        System.out.println("number = " +
                                   sqrt.multiply(sqrt, getContext(sqrt, DEFAULT_PREC))
                                           .stripTrailingZeros());
    }

    public static final BigDecimal TWO = BigDecimal.valueOf(2L);

    /*
     * The default number of places after the decimal. This is also the
     * *minimum* precision provided by this class.
     */
    private static final int DEFAULT_PREC = 20;
    /*
     * Maintains the "precision" or the number of digits after the decimal.
     */
    private static int precision = DEFAULT_PREC;

    public static void setPrecision(int precision_) {
        if (precision_ < DEFAULT_PREC) {
            precision = DEFAULT_PREC;
        } else {
            precision = precision_;
        }
    }

    public static int getPrecision() {
        return precision;
    }

    public static BigDecimal sqrt(BigDecimal decimal) {
        return sqrt(decimal, precision);
    }

    public static BigDecimal sqrt(BigDecimal decimal, int P_A_D) {
        // quick exit checks:
        if (decimal.compareTo(BigDecimal.ZERO) < 0) {
            return BigDecimal.valueOf(Double.NaN);
        }
        BigDecimal
                answer,     // The storage for the guesses.
                original,   // The result of squaring the guesses
                epsillon;   // The tolerance of this method.
        MathContext context = getContext(decimal, P_A_D);
        {
        /*
         * Obtain a good estimate of the square-root for the initial guess.
         * This is done by obtaining the "top" half of the bits of the decimal.
         */
            BigInteger integer = decimal.toBigInteger();
            answer = new BigDecimal
                             (integer.shiftRight(integer.bitLength() >>> 1));
        }
        original = answer.multiply(answer);
        epsillon = getEpsillon(P_A_D);
        while (original.subtract(decimal).abs().compareTo(epsillon) > 0) {
            answer = answer.subtract(original.subtract(decimal)
                                             .divide(TWO.multiply(answer),
                                                            context));
            original = answer.multiply(answer);
        }
        return answer.round(context);
    }

    public static BigDecimal getEpsillon(int precision) {
        return new BigDecimal("1E-" + precision);
    }

    private static MathContext getContext(BigDecimal decimal, int precision) {
        int beforePoint = (decimal.toString()).indexOf('.');
        if (beforePoint == -1) beforePoint = decimal.toString().length();
        return new MathContext(beforePoint + precision);
    }
}

The output is the desired one:

number = 91.91
sqrt(number) = 9.586970324351692703533
number = 91.91

Because I am quite happy with the result, I am determined to move ahead. Hence, I seek advice.

14
  • 2
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Sep 30 '14 at 12:56
  • 1
    The code itself might not be all that useful, but if you haven't found any algorithms then tell us what search terms you've been using. If you have found algorithms then tell us which ones you have found and why they're not appropriate for your needs. – James Snell Sep 30 '14 at 13:15
  • 5
    @ambigram_maker: You don't need to post your code, but you ould explain which possibilities you already explored and why they didn't work out for you. Also keep in mind that we are not a redirection service. – Bart van Ingen Schenau Sep 30 '14 at 13:16
  • 2
    If it is possible to calculate pi to the 1000th digit, you can write a more precise square root algorithm. The issue is not whether you can but whether or not you really want to. Why reinvent the wheel? – Neil Sep 30 '14 at 13:30
  • 1
    @ambigram_maker You should follow this article explaining how to do digit-by-digit calculation of a square root. You run the algorithm for a certain number of significant digits, add zeroes to the rest (assuming you haven't hit decimal point). I haven't tried to do this with BigDecimal, but I'd guess you could probably get away with converting BigDecimal to String and dealing with it one digit at a time, reconstructing the new String that you will use to make a the new BigDecimal number to return. – Neil Sep 30 '14 at 13:44
6

As people are hinting in the comments, if you want to do this for the fun of doing it, that's one thing, but if you want a library of scientific functions to use, you should use one that's already been written by experts. There's a list at http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries

The open-source libraries listed there are also a place to look for (if not find!) readable code.

Algorithms like this are part of numerical analysis; see Wikipedia for that, too. The famous "Numerical Recipes" books give both code and discussion for many kinds of calculations.

If you're talking about physical electronic calculators (as opposed to programs that are also called "calculators"), there are three reasons why I doubt you could use calculator code as a prototype for your arbitrary precision math library.

  • I don't know of any calculator company that has released the software and hardware designs of its calculators.

  • I've never heard of an electronic calculator with arbitrary precision arithmetic. A typical scientific calculator has a fixed precision. There will be no clue within the code how to extend a given function to a given larger precision (whereas the writers of, e.g., GNU MPFR will have solved these problems). For instance, what precision intermediate results will it need? How many more times will you need to go through the loops? Is the algorithm one that will work reasonably fast, or will it slow down too much, as you add precision?

  • A given calculator may have very advanced math hardware (to do Taylor series for instance) or very primitive hardware (can't even multiply two-digit numbers). The code will probably be hand-written machine code without more-readable source code. You'd need to understand and emulate both the functions of the hardware and code in your software. An interesting hobby but maybe not the one you were thinking of.

4
  • This answer truly addresses my problem, so +1! And BTW I want to do this for fun (I'm just a teen). I wanted to know about this approach for scientific calculators are really fast and accurate. You say that the calculators have fixed precision, and the code is not easily available. So I guess I'll have to stay satisfied with the libraries mentioned. I'll wait for another opinion before accepting your answer – Hungry Blue Dev Oct 2 '14 at 2:18
  • Also, could you please mention a few more resources (books included) that provide algorithms for arbitrary precision arithmetic? – Hungry Blue Dev Oct 2 '14 at 2:26
  • @ambigram_maker -- No, because the idea of stack overflow is that you come here after you've tried your best and got stuck. Which of the references at the bottom of the Wikipedia article I linked to, did you look into? Did you type "arbitrary precision arithmetic" into Google? – FutureNerd Oct 5 '14 at 3:54
  • 1
    1: All. 2: Yes. However, I did hear that CORDIC are digit-by-digit algorithms and are used in calculators. But since they are not favored in system with support for multiplication, I dropped the idea. – Hungry Blue Dev Oct 5 '14 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.