Timeline for What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2018 at 18:44 | comment | added | DanaJ | There are also some fast pre-tests that can very quickly reject large percentages of arbitrary inputs. Bloom filters (fastest) or some modular methods as shown in Cohen and elsewhere (Cook has a blog about it also, though he doesn't discuss bloom filters). This is a big speedup for the many algorithms that do millions of tests on native size (e.g. 64-bit) inputs. I like your description of the partial precision method, which I think GMP uses. | |
| Feb 26, 2018 at 23:05 | history | answered | gnasher729 | CC BY-SA 3.0 |