# How hard is it to do arithmetic?

People in computing are often observed saying that a computation takes $\operatorname{O}(n^3\log n)$ steps or that it's NP-hard or that it's not computable, or that it's primitive recursive, etc. I took a course that included some of the stuff about the boundary between what's computable and what's not, along the lines of Hartley Rogers' book, but I know next to nothing about computational complexity involving things well within the boundaries of what is computable (a topic neglected by Rogers' book). But I'm curious about this question about arithmetic.

An example: Say I'm confronted with the problem of finding the prime factorization of $667$. Unless it's prime itself, it's divisible by a prime number no bigger than its own square root, and the largest such is $23$. After ruling out, by various means, divisibility by all primes less than $23$, I consider that one. Now $3$ and $7$ are complementary relative to $10$, so if I add $23$ to $667$ I reduce the problem to whether a two-digit number is divisible by $23$. $667+23=690$, so that two-digit number is $69$, and that's obviously divisible by $23$. Therefore $667=23\times\text{something}$. Since $69=23\times3$, we've got $690=23\times30$, and this is $23$ less than that, so $667=23\times29$, and $29$ is prime, so we're done. BUT one checks the result by doing the multiplication by other methods, and so I notice that halfway between $23$ and $29$ is $26$, so $23\times29=(26+3)(26-3)$. Factoring a difference of two squares is something everybody learned in 7th grade (except those who didn't....) and so it's $26^2-3^2$. I know that $26^2 = 676$, and $3^2 = 9$, and guess what $676 - 9$ is? So it works. And of course I can also do it via the distributive law, the way they taught you in third grade.

The question is: If one figures out in each instance what the most efficient thing to do is, among all the arithmetic shortcuts and techniques that might cross one's mind in doing this, would the ten or fifteen or so seconds that it takes you to do all of the above suddenly expand into more time than it would take if you just plodded through it by applying prescribed algorithms that you learned in childhood? Often within seconds after I do something like this, I think of two or three other shortcuts that would have been quicker. But if I stopped to evaluate all the possibilities, it would take me more time than just doing things like what I described above and not thinking about what alternatives might not have occurred to me. So the question is whether this informal observation can be made precise and proved.

Warning: One of the comments raises in my mind the question of whether this will be widely misunderstood. I am NOT asking whether using shortcuts that come to mind on the fly is quicker than using the algorithms you've been taught at your mother's knee. I already know that it is. Otherwise I couldn't have written what I did above. What I'm asking is this: Would it take more time to figure out which way is quickest than to use what comes to mind?

Another clarification: I said "ten or fifteen or so seconds". I suspect that doing all that I described above explicitly probably took me less than ten seconds, but actually eliminating the primes less than 23 before that probably took me more than twice that long.

• Because mathematicians are tricky people, problems of this type that they set tend to yield to tricks. And we have a deep familiarity with small numbers. But I doubt that there is anything better than the prescribed algorithms for generic products off medium-sized primes, say bigger than $300$. – André Nicolas Feb 9 '12 at 1:08
• Until P=NP is solved, there won't be a good answer to this in general. If you're just talking about arithmetic shortcuts and the like, not about the actual complexity class, then I can testify that trying to find shortcuts saves enough time when it works to more than make up for the times when it doesn't. – Lopsy Feb 9 '12 at 1:10
• @Lopsy : I am of course well aware that your last statement is true. But now you've got me wondering whether everyone will completely misunderstand my question and think that it's about whether shortcuts save time. – Michael Hardy Feb 9 '12 at 2:59
• "what comes to mind" is hard to formalize. Nevertheless, I think the answer is yes. If you want deterministically turn a non-deterministic turning machine (i.e, one that tries "all the arithmetic shortcuts and techniques that might cross one's mind in doing this") into a deterministic one, by "figuring out which way is quickest", then you will have to explore all the paths (e.g. primes $< 23$) and this exploration will not be in polynomial time. – user2468 Feb 9 '12 at 3:21
• Do you really mean to ask about finding the quickest method? Or just about the trade-off between the time it takes to find quicker methods versus the resulting savings in execution time? The former looks unsolvable to me. – Andreas Blass Feb 19 '18 at 15:27

Would it take more time to figure out which way is quickest than to use what comes to mind?

You cannot solve your problem and not figure out which way is the quickest, since the quickest for each instance is given by your output. In your instance the quickest is to divide by 23.

• This answer is interesting and probably correct, and it raises the possibility that I should refine the question in order to avoid such a silly answer. It also makes it appear that that might not be so easy. – Michael Hardy Feb 9 '12 at 19:23

Factorization and arithmetic are two wildly different subjects.

The complexity of arithmetic is reasonably well understood. You might think that arithmetic (say addition, subtraction, multiplication, division, and raising to a power) is trivial. But multiplying large numbers is non-trivial. The algorithm used in practice to multiply really large numbers (Schönhage-Strassen) was only invented in 1971, and recently (2007) an even better algorithm was suggested by Fürer, though his algorithm isn't faster in practice even for huge numbers.

It gets even worse for factorization. There are various "tricks" used to factor numbers, and they use non-obvious algebraic number theory. The two most wildly-used algorithms today are Lenstra's elliptic curve factorization and the number field sieve (the number fields in question are $\mathbb{Q}$ adjoined with the root of some high-degree polynomial).

Wikipedia has a nice summary of best known results. There are also books on the subject, check Wikipedia's page on computational number theory, or (for a different selection of topics), Algebraic Complexity Theory.

• This answer is not completely on topic. When I added the "arithmetic" tag, I had in mind that factoring numbers is part of what I meant by "arithmetic". However: see the "Warning" I posted in a later edit to my question. – Michael Hardy Feb 9 '12 at 3:06