undefined | Better HN

0 pointsanyfoo11y ago0 comments

First of all there is no Nobel in math/CS.

I know. An algorithm this efficient would still be worth that much. :)

But more importantly, when we talk about the running time of algorithms, we talk about the time in relation to how many bits it takes to describe the number. So linear in the size of the number is exponential in the number of bits, and that is not very interesting.

No, the regular expression described here works on numbers in unary representation. Linear to the size of the unary representation is linear to the number itself.

0 comments

2 comments · 1 top-level

sold11y ago· 1 in thread

Unary representation is useless when speaking about complexity in number theory.

If you take a number N given in unary, convert it to binary and do trial division up to the square root, it will take O(N log N) time for conversion to binary and O(sqrt(N) * log(N)^2) for trial division (depending on your computational model, it could be O(N) and O(sqrt(N)) - I am counting bit complexity). In total, it's O(N log N). The runtime is dominated by reading the input! The complexity of trial division and the brilliant AKS algorithm is the same from this viewpoint.

Even if you had an algorithm that did not have to convert to binary and could tell in time linear to unary represenation whether a number is prime, it would be interesting trivia but nothing worthy a Nobel prize. In practice numbers are given in binary (or some other base>1 number system). To use your algorithm, you would have to convert to unary, which already means trial division would be faster.

anyfooOP11y ago

Ah, I see, thanks for the explanation.

j / k navigate · click thread line to collapse