Hacker News Reader

A colleague of mine had invented a technique for factoring composite numbers, that he thought would be quite fast.

I thought a little about it and saw that it would degenerate into sat solving.

I checked taocp and indeed my colleague's idea was in there. Also a faster algorithm was presented in the relevant section. I lended the book to him and we saved around a month of work.

View on HN

This is exactly what TAOCP can be best at - if you know enough about the problem domain to be dangerous, or even to build a solution, you will know enough to read the relevant portion of TAOCP, where it is very likely you will find value.

There is quite a lot of money waiting for you if you ever figure out how to factor composites quickly. (Any old bum can factor primes quickly.)

We had a very specific use case, where the input was a known composite, and some properties of the factors were known.

Also, while no fast algorithms are known (and may never be depending on if p=np) some are faster than others depending on the properties of your inputs, and choosing the right one can mean saving a lot of time and effort.

Reply on news.ycombinator.com