 # Exact sqrt in Julia?

I want to check if an expression evaluates to Integer result. I know this is never the best solution, but I ran out of ideas and not able to come up with an algorithm to solve the problem in a reasonable time. The only way I have now is bruteforce. I used `setprecision` with `big` without getting the correct results, then I tried `SymPy`. The latter calculated the result correctly but is too slow to solve the full-size problem. Any ideas, thank you.

``````function sLength(w,v,y)
x = w * y // (v + w)
s = sqrt(x^2 + w^2) + sqrt((y-x)^2 + v^2)
s == trunc(s)
end
``````

`isinteger(2.5)` `isinteger(2.0)` but you can run into precisions issues.

reminds me of a project euler problem

Not exactly, but yes, it is part of a bigger problem that I have mathematically reduced to this formula but can’t go further. I always find it fun to tackle a hard problem and reduce it to a simple solution.

`isinteger` is nice but the problem with precision remains.

Does https://en.wikipedia.org/wiki/Integer_square_root help at all?

Julia already has a `isqrt()`, but the problem here is the sum of the two roots is to be integer, not each one individually.

1 Like

`(x^2 + w^2)` this should be a fraction and `(y-x)^2 + v^2` should be a fraction.

I think you can check the `numerator(fraction1)` and `denominator(fraction2)` and work ou if the whole should be frac

5 Likes

Yes, it works. Thank you.

What are the signs of the numbers ? If `v` and `w` are of the same sign, then `s == sqrt(y^2 + (v+w)^2)`. The problem is then whether `y` and `v+w` are members of a pythagorean triple. (Assuming `y` and `v+w` are integers)

If `v` and `w` are of opposite signs, and `v + w != 0`, then
`s == sqrt(y^2 + (v+w)^2) * abs((v-w)/(v+w))`

2 Likes

Yes, all numbers are positive and I reached the same conclusion as you did. Only a small problem remains; how can I generate the triples incrementally? That’s, normally loops finish the last index first, I want all indices to grow together, one after another in an alternating way. Probably I want a priority queue or something?

Well, I did it like this:

``````for k = 1:M
for j = 1:k
for i = 1:j
use indices (i,j,k)
...
end
end
end
``````

If your goal is to generate all triples that satisfy the condition, then the fastest way would be to first search for y and z where `sqrt(y^2 + z^2)` is integer, and then generate all `(v,w)` that satisfy `v + w == z`.

Something like

``````for y = 1:M
for z = 1:y
if y^2 + z^2 is a square
for v = 1:z-1
w = z - v
output(y, v, w)
end
end
end
end
``````
4 Likes

Then, as Per says, you have to partition one of the triples as `v + w`

2 Likes