Helper Me Speed Up Diophantine Solution?

Questions / Help
1

Hi Folks.

Came across this question on Codewars, and I wasn’t even able to submit with a “this took longer than 12sec to run” for their submission test suite.

In mathematics, a Diophantine equation is a polynomial equation, usually with two or more unknowns, such that only the integer solutions are sought or studied.

In this kata we want to find all integers x, y ( x >= 0, y >= 0 ) solutions of a diophantine equation of the form:

x^2 - 4 * y^2 = n

(where the unknowns are x and y , and n is a given positive number) in decreasing order of the positive xi.

If there is no solution return [] or "[]" or "" . (See “RUN SAMPLE TESTS” for examples of returns).

Here is my current solution using some horribly written recursion D:. It is MUCH more performant than my first few renditions, but still no where near fast enough to submit to codewars apparently. Can anyone help me understand why this is still slow?


defmodule Dioph do

    @eq "x2 - 4 * y2 = n"
    @eq_terms_of_x "x = sqrt(n + (4 * y^2))"  
    @eq_terms_of_y " y = sqrt((-1 * (n - x^2))/4)"  

    def solve(n) do
       k = round(n/2 + 1)
       equation(n, k, []) |> Enum.reverse
    end

    def equation(_, 0, acc), do: acc
    def equation(n, val, acc) do
        x = val
        right_side = (-1 * (n - :math.pow(x, 2))/4)
        y = if right_side < 0.00, do: -1.00, else: :math.sqrt(right_side)
        if is_valid_result?({x, y}), do: equation(n, val-1, [{round(x), round(y)}| acc]), else: equation(n, val-1, acc)
    end

    def is_valid_result?({x, y}) do
        round(x) == x && x != -1 && round(y) == y && y != -1
    end

end
2

The problem with a “count down by one” solution like this is that the solution is very sparse relative to the input number - for instance, with n=200_000_000:

iex(6)> Dioph.solve(200000000)
[
  {100000001, 50000000},
  {25000002, 12499999},
  {12500004, 6249998},
  {6250008, 3124996},
  {5000010, 2499995},
  {3125016, 1562492},
  {2500020, 1249990},
  {1562532, 781234},
  {1250040, 624980},
  {1000050, 499975},
  {781314, 390593},
  {625080, 312460},
  {500100, 249950},
  {312660, 156170},
  {250200, 124900},
  {200250, 99875},
  {156570, 77965},
  {125400, 62300},
  {100500, 49750},
  {63300, 30850},
  {51000, 24500},
  {41250, 19375},
  {32850, 14825},
  {27000, 11500},
  {22500, 8750},
  {16500, 4250},
  {15000, 2500},
  {14250, 875}
]

That’s a LONG way to count to get a handful of matches.

Brute-force is not going to perform well on this solution, but there’s a mathematical insight that can help skip past most of those 200 million choices:

x^2 - 4 * y^2 = (x - 2 * y) * (x + 2 * y)

so both x - 2 * y and x + 2 * y have to be factors of n.

2 Likes