Project Euler/64: Difference between revisions
From charlesreid1
(→Code) |
|||
| Line 10: | Line 10: | ||
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. | 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 | |||
* Find the continued fraction representation of an integer | |||
* Find the convergents P, Q of a continued fraction | |||
<math> | |||
\dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} } | |||
</math> | |||
==Code== | ==Code== | ||
Revision as of 10:37, 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
- Find the continued fraction representation of an integer
- Find the convergents P, Q of a continued fraction
$ \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
