DEV Community

Cover image for Schönhage–Strassen algorithm in 256 chars or less (hopefully)
Kostas Kalafatis
Kostas Kalafatis

Posted on

2

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

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!

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay