Wait, I'm also confused. I thought completely rewriting the implementation of an algorithm would not violate copyright. It may run afoul of other laws, but not copyright. Am I mistaken?
I don't mean simply renaming variables or changing a couple of lines.
"Derivative work" doesn't mean "a work made with knowledge of another work". WP explains, "In copyright law, a derivative work is an expressive creation that includes major copyrightable elements of an original, previously created first work (the underlying work)." Canonical examples include translations into another language, dramatizations of novels, or phonorecords of sheet music.
Algorithms, being purely functional, are not copyrightable in any country that I know of. So a new implementation that uses the same algorithm as the original, but without copying any of its non-functional aspects, is not a derivative work of the original and does not infringe its copyright.
Cleanroom reimplementation is a defense against allegations of copying, because under, for example, US copyright law, access plus substantial similarity is sufficient to show copying. The "He's So Fine" lawsuit is one of the most extreme examples of this doctrine. Cleanroom reimplementations are a defense against copying by eliminating the access element. But copying the functional aspects of a program does not meet the "substantial similarity" bar.
I don't mean simply renaming variables or changing a couple of lines.