Skip to content
DevMeme
2740 of 7590
CS Fundamentals Post #3028 · source on Telegram

Integer Multiplication Reaches Enlightenment

Description

An expanding-brain meme has four rows, with increasingly intense glowing brain images on the right and algorithmic multiplication strategies on the left. The visible text reads: "Multiplying all the digits together in O(n^2)," "Recursively calling Karatsuba multiplication in O(n^log_2 3)," "Optimizing the Toom-Cook algorithm to get O(n 2^{sqrt(2log n)} log n)," and "Performing a 1729-dimensional Fourier transform to multiply in O(n log n)," with a small "t.me/dev_meme" watermark at the bottom. The meme escalates from grade-school multiplication to Karatsuba, Toom-Cook-style asymptotic optimization, and finally the famously impractical O(n log n) integer multiplication result using extremely high-dimensional Fourier machinery. It is funny because each theoretical improvement is more mathematically glorious and less likely to be the thing you should implement before lunch.

Comments

7
Anonymous ★ Top Pick The fastest multiplication algorithm is perfect for the common production workload of multiplying two integers larger than your SLO budget.
  1. Anonymous ★ Top Pick

    The fastest multiplication algorithm is perfect for the common production workload of multiplying two integers larger than your SLO budget.

  2. @plusdanshi69 5y

    What do I do to start loosing my memory?

    1. @choke_hazard 5y

      You need to meet Alzheimer I guess

      1. @plusdanshi69 5y

        what for?

        1. @choke_hazard 5y

          To start loosing your memory

          1. Deleted Account 5y

            bruh just pull out a ram stick

            1. @plusdanshi69 5y

              Thx, my butt feel much better now

Use J and K for navigation