Breaking news in the algorithmic/arithmetic world!

Integer multiplication in time O(n · log n). [1]

It means you can multiply two n-bits integer using roughly n log n operations. It's a *very* important problem because a lot of mathematical software rely on efficient integer multiplication.

It breaks the last best known algorithm [2] (Schönhage–Strassen), that was in O(n · log n · log log n)

[1] https://hal.archives-ouvertes.fr/hal-02070778/document

[2] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

I have this stuck in my head: https://www.youtube.com/watch?v=M699TqhO06k

Ooh, a cool puzzle game by @increpare@twitter.com https://games.increpare.com/Gestalt_OS/

The Incredible Proof Machine: "LabView wrestled through the Curry-Howard isomorphism"

@olligobber Another proof by induction: If you don't believe this, you're drafted.

Proof by induction: https://www.smbc-comics.com/comic/proof

@enumerator 404

@enumerator 4, 5 and 6

What a treat! Over the weekend I received an unexpected email from a fan, containing proofs of the Riemann hypothesis, Fermat's last theorem, the Beal conjecture *and* the abc conjecture! Furthermore, they're all proved by the one proof! #blessed

Thanks @christianp for sorting out my signup issues.

- Pronoun
- Any

- Location
- Australia

Mathematician and design enthusiast. Computing, music, science, video games and art.

Joined Oct 2018