# Difference between revisions of "Project Euler/64"

### From charlesreid1

m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
|||

Line 7: | Line 7: | ||

==Also See== | ==Also See== | ||

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

Problem 57 (also deals with continued fractions): [[Project Euler/57]] | Problem 57 (also deals with continued fractions): [[Project Euler/57]] | ||

Line 29: | Line 29: | ||

==Code== | ==Code== | ||

− | Link: https://charlesreid1.com | + | Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/064 |

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

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

===Problem 64 Algorithm=== | ===Problem 64 Algorithm=== |

## Latest revision as of 03:49, 9 October 2019

## Contents

## Problem Statement

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

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

## Also See

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

Problem 57 (also deals with continued fractions): Project Euler/57

## 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 Problem 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)

## Code

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

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

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

### Problem 64 Algorithm

Skipping the details of the continued fraction representation, here is the essential algorithm for Problem 64. Note that the `continuedFractionSqrtBig()`

method is using an arbitrary precision decimal library to compute many, many terms of the continued fraction representation.

public class Problem064 { public static void main(String[] args) { int oddConv = 0; for(int j=2; j<=10000; j++) { List<Integer> cf; try { cf = ContinuedFractionBig.continuedFractionSqrtBig(j); if(cf.size()%2==0) { oddConv++; //System.out.println(j+" : "+cf); } } catch(IllegalArgumentException e) { continue; } } System.out.println(oddConv); } }

### 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:

/** 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; }

## Flags

Project Euler
Problem 1
Problem 11
Problem 51
Problem 100
Problem 500
- = in progress
· Template:ProjectEulerFlag · e |