# How to avoid costly square root operations in A* algorithm?

As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $$f = g + h$$, where $$g$$ is the cost of getting to this vertex from the start vertex, and $$h$$ is an estimation on remaining cost to get from this vertex to the destination vertex. In my specific A* path finding algorithm, my estimation function has a square root operation. It isn't the standard $$h = \sqrt{a^2 + b^2}$$; for simplicity, let's say it's $$h = \sqrt{d}$$ where $$d$$ is some easily computable value. My problem is that my algorithm can take quite some time on some instances. Should I have a look at replacing my estimation function for a faster one, say without any square root operations?

I've looked around and some people simply ignore the square root (so $$H = d$$) which makes A* run faster but then it may overestimate, resulting in non-optimal solutions. I'd like to keep optimality, so next I was thinking about the priority function $$F = f^2$$ so as to accommodate for this overdominating $$H = d$$ (note that $$F$$ overestimates as well, but since the priority queue order for $$f$$ is the same as for $$F$$ optimality is preserved). However, since $$f^2 = g^2 + 2gh + h^2 = g^2 + 2gh + H$$, I would still need to compute $$h = \sqrt{d}$$. My first question is: could I use priority function $$F_2 = g^2 + 2g + H$$ instead? It's missing the $$h$$ from priority function $$F$$, could this create a problem, like $$g$$ being too dominant and the A* algorithm regressing too much to a Dijkstra algorithm?

Another idea I had was to construct an array during precomputation with the square root values of $$d$$ up to some upper bound on $$d$$, say $$D$$. I have such a bound, of about 500 say, so I could construct an array of values $$1^2$$, $$2^2$$, $$3^2$$, ..., $$24^2= 576$$. Then, when I need to compute a square root of $$d$$, for example $$d=200$$, a binary search in my array could give me highest value $$\leq 200$$, being $$196$$ at index 13, implying $$h = 14$$ with possibly some decimal notation which I don't care too much about. My second question is: would this method, of time complexity $$\log(\sqrt{D})$$, be faster than the standard (Java) square root?

Finally, more generally speaking, my third question is: how would one generally avoid such costly square root computations in A* algorithms?

• Did you check en.wikipedia.org/wiki/Methods_of_computing_square_roots? Mar 7 at 17:44
• @Nathaniel I have, I should have added in my post that I suppose that any method mentioned on wikipedia is probably as good as the standard (Java) method used. My question more relates to optimisation regarding square roots in context of an A* algorithm, instead of the more general optimisation for square root computation. Mar 7 at 17:50
• Have you benchmarked and measured your code to see what fraction of the time spent in your code is spent on computing the square root? You ask whether an alternative with an array would be faster; the best way is to try it, use that same measurement methodology, and see whether it is indeed faster.
– D.W.
Mar 7 at 20:59
• If your implementation of $A^*$ is as I expect, then the most expensive part is heap operations, so square root costs you nothing. Apr 7 at 4:11
• Square root is about as expensive as a division, which is to say, it's not trivial but it's not as bad as most people think. It's also worth nothing that many CPUs have single-cycle approximate reciprocal square root instructions these days (e.g. RSQRTSS on Intel/AMD, FRSQRTE on ARM), so x * rsqrt(x) is even faster than sqrt(x). Aug 5 at 2:20

If you can use square root with limited precision, then you may try this approach:

1. use g^2 + 2gh + H formula, so you have exact value of H
2. compute leading zeroes in H so you can represent H=x*2^n
3. shift H so only 10 bits remain: H2 = H >> (n-10)
4. compute sqrtH2 = sqrt_table[H2]
5. now h = sqrtH2 * 32 * 2^(n/2)
• Wait, if I have to use the sqrt_table anyways in your proposed solution, wouldn't it be better to directly use my proposed solution regarding the square root array? Mar 9 at 10:37
• The square root being a hard-wired function, chances are high that any software emulation will be slower.
– user16034
Apr 7 at 16:01
• @YvesDaoust it's correct only for an exact calculation of sqrt, while I propose to use a rough estimation Apr 8 at 17:33
• @Bulat: I commented on that elsewhere.
– user16034
Apr 10 at 12:25

Here’s a suggestion to verify that the square root is a problem: Measure how fast your code is. Replace sqrt(d) with sqrt(sqrt(d*d)). How much slower does your code get?