Knuth's Art of Computer Programming, V 4B, has gone into print

Re:Knuth's Art of Computer Programming, V 4B, has gone into ... by linschn on Tuesday October 04, 2022 @01:00PM (#33083240)

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.

[ Parent | on HN ]

Re:Knuth's Art of Computer Programming, V 4B, has gone into ... by bombcar on Tuesday October 04, 2022 @01:57PM (#33084172)

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.

[ Parent | on HN ]

Re:Knuth's Art of Computer Programming, V 4B, has gone into ... by lupire on Tuesday October 04, 2022 @04:06PM (#33085971)

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.)

[ Parent | on HN ]

Re:Knuth's Art of Computer Programming, V 4B, has gone into ... by linschn on Tuesday October 04, 2022 @05:48PM (#33087501)

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.

[ Parent | on HN ]