Exact sqrt in Julia?

General Usage
,
1

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
2

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

3

reminds me of a project euler problem

4

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.

5

isinteger is nice but the problem with precision remains.

6

Does Integer square root - Wikipedia help at all?

7

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
8

(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
9

Yes, it works. Thank you.

10

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
11

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?

12

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
13

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
14

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

2 Likes