Multiplying integers
The classical algorithm, that everyone knows from elementary school, for multiplying two n-digit integers runs in \(O(n^2)\)-time. Recently, there was a preprint posted on HAL (link) in which the authors provide an algorithm which runs in \(O(n\log(n))\)-time. A nice article about this discovery may be found at the QuantaMagazine: link. Further, it was also recently proven in another preprint … Continue reading "Multiplying integers"