Schönhage–Strassen algorithm in 256 chars or less (hopefully)

#devchallenge #cschallenge #computerscience #beginners

This is a submission for DEV Computer Science Challenge v24.06.12: One Byte Explainer.

Explainer

You have two huge LEGO towers and want to combine them. First, break each tower into chunks. Then, rearrange the pieces to snap easier (FFT). Snap the pieces, unscramble them (inverse FFT), and finally put all the small chunks together into a single tower.

Additional Context

Well, it took me about 128 hours to understand the math behind the Schönhage–Strassen algorithm, and then another 128 hours to come up with a beginner-friendly explanation. Dear reader, heed my warning: don't try this at home, unless you have a spare 256 hours and a love for mathematical adventures!

edit: Also, my eyes played a trick on me! Instead of 265 characters, I read 256. Maybe I need an eye algorithm upgrade next!