Timeline for How to avoid costly square root operations in A* algorithm?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 2 at 12:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 3, 2023 at 11:12 | answer | added | gnasher729 | timeline score: 1 | |
| Dec 3, 2023 at 11:10 | comment | added | gnasher729 | I would bet it is not the square root making things slow. | |
| Dec 3, 2023 at 1:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 5, 2023 at 2:20 | comment | added | Pseudonym♦ | 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, 2023 at 0:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 7, 2023 at 16:03 | comment | added | user16034 | I agree with @Dmitry: before embarking to this change, make sure that the square root contributes a significant share of the running time, by profiling. Anyway, a crude approximation of the square root (like halving the floating-point exponent) could be sufficient to implement the A* heuristic. | |
| Apr 7, 2023 at 4:11 | comment | added | Dmitry | 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, 2023 at 0:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 9, 2023 at 10:34 | comment | added | J. Schmidt | @D.W. I'll do that, seems like a sure way to know for sure indeed. | |
| Mar 7, 2023 at 23:43 | answer | added | Bulat | timeline score: -1 | |
| Mar 7, 2023 at 20:59 | comment | added | D.W.♦ | 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. | |
| Mar 7, 2023 at 18:22 | comment | added | user555045 | But what is your heuristic? You've told us what it isn't.. Just ignoring the square root is indeed plainly wrong, actually Euclidean distance is usually not great anyway (on grids with 8-direction movement, it unnecessarily underestimates distance, diagonal distance is better) | |
| Mar 7, 2023 at 17:50 | comment | added | J. Schmidt | @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, 2023 at 17:44 | comment | added | Nathaniel | Did you check en.wikipedia.org/wiki/Methods_of_computing_square_roots? | |
| Mar 7, 2023 at 14:58 | history | edited | J. Schmidt | CC BY-SA 4.0 |
use D as notation for upper bound on d
|
| Mar 7, 2023 at 13:57 | history | edited | J. Schmidt | CC BY-SA 4.0 |
"it doesn't matter" was too ambiguous
|
| Mar 7, 2023 at 13:49 | history | asked | J. Schmidt | CC BY-SA 4.0 |