Project Euler/64: Difference between revisions

From charlesreid1
Line 22: Line 22:
\dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} }
\dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} }
</math>
</math>
===Magic Method for Square Roots===
In the process of implementing this, I needed to compute square roots to arbitrary precision - something that BigDecimal does NOT do!
I found this (magical) arbitrary precision BigDecimal square root algorithm that is extremely handy:
<pre>
    /** Find the square root of a BigDecimal to precision SCALE. */
    public static BigDecimal sqrtBig(BigDecimal A, final int SCALE) {
        BigDecimal x0 = new BigDecimal("0");
        BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
        while (!x0.equals(x1)) {
            x0 = x1;
            x1 = A.divide(x0, SCALE, RoundingMode.HALF_UP);
            x1 = x1.add(x0);
            x1 = x1.divide(BigDecimal.valueOf(2), SCALE, RoundingMode.HALF_UP);
        }
        return x1;
    }
</pre>


==Code==
==Code==

Revision as of 10:41, 8 January 2018

Problem Statement

More investigation of continued fractions and the continued fraction representation of square roots.

Link: https://projecteuler.net/problem=64

Blog post: Computing square roots using continued fractions: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/063/Problem063.java

Solution Technique

The blog post linked above contains some of the code used to solve this problem, but it basically boils down to implementing the recurrence relation formula that we already saw in Project Euler/57, with various initial conditions.

Continued fractions are implemented as a class. Key functionality includes:

  • Check if integer is perfect square
  • Solve the Pell equation
  • Find the convergents P, Q of a continued fraction
  • Find the (shorter than 10-long) continued fraction representation of an integer (uses normal float type)
  • Find the (really long) continued fraction representation of an integer (uses arbitrary precision BigDecimal type)

$ \dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} } $

Code

Link: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064

ContinuedFractionBig.java defines the ContinuedFractionBig class: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/ContinuedFractionBig.java

Problem064.java uses the ContinuedFractionBig class to solve the problem: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java

Flags



Euler.jpg
Project Euler
project euler notes

Project Euler

Grid 0: Problems 1-99

Problem 1  · Problem 2  · Problem 3  · Problem 4  · Problem 5  · Problem 6  · Problem 7  · Problem 8  · Problem 9  · Problem 10

Problem 11  · Problem 12  · Problem 13  · Problem 14  · Problem 15  · Problem 16  · Problem 17  · Problem 18  · Problem 19  · Problem 20

Problem 27  · Problem 28  · Problem 29  · Problem 30

Problem 31  · Problem 32  · Problem 33  · Problem 40

Problem 41  · Problem 42  · Problem 43  · Problem 44  · Problem 45  · Problem 46  · Problem 47  · Problem 48  · Problem 49  · Problem 50

Problem 51  · Problem 52  · Problem 53  · Problem 54  · Problem 55  · Problem 56  · Problem 57  · Problem 58  · Problem 59  · Problem 60

Problem 61  · Problem 62  · Problem 63  · Problem 64  · Problem 65  · Problem 66  · Problem 67  · Problem 68  · Problem 69  · Problem 70

Grid 1: Problems 100-199

...

Problem 110  · Problem 111  · Problem 112  · Problem 113  · Problem 114  · Problem 115  · Problem 116  · Problem 117  · Problem 118  · Problem 119

Problem 150  · Problem 151  · Problem 152  · Problem 153  · Problem 154  · Problem 155  · Problem 156  · Problem 157  · Problem 158  · Problem 159

...

Problem 170  · Problem 171  · Problem 172  · Problem 173  · Problem 174  · Problem 175  · Problem 176  · Problem 177  · Problem 178  · Problem 179

...


Problem 190  · Problem 191  · Problem 192  · Problem 193  · Problem 194  · Problem 195  · Problem 196  · Problem 197  · Problem 198  · Problem 199


Grid 2: Problems 200-299

Problem 227  · Problem 254


Grid 3: Problems 300-399


Problem 301  · Problem 310

Problem 312  · Problem 319

Problem 323  · Problem 328

Problem 334  · Problem 337

Problem 345  · Problem 346

Problem 355  · Problem 356

Problem 364  · Problem 367

Problem 373  · Problem 378

Problem 382  · Problem 389

Problem 391

Grid 4: Problems 400-499

Problem 400


Grid 5: Problems 500-599

Problem 500  · Problem 501  · Problem 502


Grid 9: Problems 900-999

Problem 932


* = in progress

Flags  · Template:ProjectEulerFlag  · e


Retrieved from "https://charlesreid1.com/w/index.php?title=Project_Euler/64&oldid=22932"