[C++/Python] Project Euler #57 - Square Root Convergents

This problem may appear to be a math problem, but it’s actually just a simple calculation problem.

It’s rated as a 5% difficulty problem on the Project Euler site.

Pell's equation

The content of the problem is that when calculating the square root of 2, it can be expressed as a continued fraction. For more about continued fractions, refer to Pell’s equation.

We can express the square root of 2 in such a way using a continued fraction.

\[ \sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cdots}}} = [1; \overline{2}] \]

However, that aspect isn’t the main point of this problem. When expanding the continued fraction and expressing it as a fraction, both the numerator and denominator are integers. The problem is to find how many times the number of digits in the numerator exceeds the number of digits in the denominator.

---

Although you can convert the continued fraction into a regular fraction, the numbers get quite large. You could use a double-precision float to approximate the values, but doing so would give you an incorrect answer due to how sensitive this problem is. Because of that, you are forced to use BigInt.

Using BigInt is actually more convenient in languages like Python, which provide BigInt support by default, than in C++.

I used a custom-built BigInt struct that I implemented myself.

//------------------------------------------------
//    Project Euler #57 - Square Root Convergents
//        - by Aubrey Choi
//        - created at 2015-09-24
//------------------------------------------------
#include <stdio.h>
#include <time.h>

struct BigInt
{
    BigInt() { len = 0; }
    BigInt(int m)
    {
        len = 0;
        while(m)
        {
            v[len++] = m%10;
            m /= 10;
        }
    }
    void mul2add(BigInt &a)
    {
        int c = 0;
        for(int i = 0; i < len; i++)
        {
            c += v[i]*2 + ((i < a.len)?a.v[i]:0);
            v[i] = c%10;
            c /= 10;
        }
        while(c)
        {
            v[len++] = c%10;
            c /= 10;
        }
    }
    int len;
    char v[1024];
};

void solve1()
{
    BigInt d = 2, n = 3, d1 = 1, n1 = 1;
    int count = 0;
    for( int i = 2 ; i <= 1000 ; i++ )
    {
        BigInt t;
        t = d; d.mul2add(d1); d1 = t;
        t = n; n.mul2add(n1); n1 = t;
        if( n.len > d.len ) count++;
    }
    printf("Ans = %d\n", count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}

 

I don’t think my implementation is particularly efficient compared to Python, but it ran about 2–3 times faster in C/C++. You can also find a BigInt library online and apply it to C/C++ if you prefer.

The algorithm itself isn’t very difficult.

 

Here is Python version.

#------------------------------------------------------------
#    Project Euler #57 - Square Root Convergents
#    Author: Aubrey Choi
#    Date:    2015.09.24.
#------------------------------------------------------------
d, n, d1, n1 = 2, 3, 1, 1
count = 0
for i in range(2, 1001):
    d, d1 = 2*d+d1, d
    n, n1 = 2*n+n1, n
    if len(str(n)) > len(str(d)): count += 1
print(f"Ans = {count}")