Finding the last two digits before the decimal point for the number (4+sqrt(11))^n

Question

I am doing a problem in which I have to find the last two digits before the decimal point for the number
[4 + sqrt(11)]ⁿ.

For example, when n = 4, [4 + sqrt(11)]⁴ = 2865.78190... the answer is 65. Where n can vary from 2 <= n <= 10⁹.

My solution - I have tried to build a square root function which calculate the sqrt of 11 which a precision equal to value of n input by the user.

I have used BigDecimal in Java to avoid overflow problems.

public class MathGenius {

    public static void main(String[] args) {

        Scanner reader = new Scanner(System.in);
        long a = 0;
        try {
            a = reader.nextInt();
        } catch (Exception e) {
            System.out.println("Please enter a integer value");
            System.exit(0);
        }

        // Setting precision for square root 0f 11. str contain string like 0.00001
        StringBuffer str = new StringBuffer("0.");
        for (long i = 1; i <= a; i++)
            str.append('0');
        str.append('1');

        // Calculating square root of 11 having precision equal to number enter
        // by the user.
        BigDecimal num = new BigDecimal("11"), precision = new BigDecimal(
                str.toString()), guess = num.divide(new BigDecimal("2")), change = num
                .divide(new BigDecimal("4"));
        BigDecimal TWO = new BigDecimal("2.0");
        BigDecimal MinusOne = new BigDecimal("-1"), temp = guess
                .multiply(guess);
        while ((((temp).subtract(num)).compareTo(precision) > 0)
                || num.subtract(temp).compareTo(precision) > 0) {

            guess = guess.add(((temp).compareTo(num) > 0) ? change
                    .multiply(MinusOne) : change);

            change = change.divide(TWO);
            temp = guess.multiply(guess);
        }

        // Calculating the (4+sqrt(11))^n
        BigDecimal deci = BigDecimal.ONE;
        BigDecimal num1 = guess.add(new BigDecimal("4.0"));
        for (int i = 1; i <= a; i++)
             deci = deci.multiply(num1);

        // Calculating two digits before the decimal point
        StringBuffer str1 = new StringBuffer(deci.toPlainString());
        int index = 0;
        while (str1.charAt(index) != '.')
            index++;
        // Printing output

        System.out.print(str1.charAt(index - 2));
        System.out.println(str1.charAt(index - 1));
    }
}

This solution works up to n = 200, but then it begins to slow down. It stops working for n = 1000.

What is a good method to deal with problem?

2 -- 53
3 -- 91
4    65
5    67
6    13
7    71
8    05
9    87
10   73
11   51
12   45
13   07
14   33
15   31
16   85
17   27
18   93
19   11
20   25
21   47
22   53
23   91
24   65
25   67

Answer 1

At n=22 the results seem to repeat from the position of n=2. So keep those 20 values in an array in the same order as in your list e.g. nums[20].

Then when the user provides an n:

return nums[(n-2)%20]

There is now a proof of this pattern repeating here.

Alternatively, if you insist on computing at length; since you calculating the power by looping multiplication (and not BigDecimal pow(n)) you could trim the number you are working with at the front to the last 2 digits and the fractional part.

Answer 2

Here is a much simpler solution for you...

Use the rational representation of 4+sqrt(11):

BigInteger hundred     = new BigInteger("100");
BigInteger numerator   = new BigInteger("5017987099799880733320738241");
BigInteger denominator = new BigInteger("685833597263928519195691392");
BigInteger result = numerator.pow(n).divide(denominator.pow(n)).mod(hundred);

UPDATE:

As you've mentioned in the comments below, this procedure is prone to precision-loss, and will eventually yield an incorrect result. I found this question to be rather interesting on the mathematical aspect, and so I published a question on MO (https://mathoverflow.net/q/158420/27456).

You can read the answer at https://mathoverflow.net/a/158422/27456.