Kids learn their times tables in school. Memorize them. Good luck with three-digit numbers. That\u2019s where algorithms kick in. You stack the digits. Multiply row by row. For thousands of years, we thought that was the best we could do. It\u2019s slow. Brutally slow for big data. Then in 1960 a 23-year-old changed everything. The mystery of multiplication speed remains wide open.<\/p>\n
Multiplication isn’t just homework. It runs the internet. Encryption, AI, audio processing. All of it leans on multiplication. Heavy multiplication. When you multiply huge numbers millions of times per second, every step counts. A slight efficiency gain saves billions.<\/p>\n
Look at the grade school method. Two digits mean four single-digit multiplications. Three digits? Nine. It scales quadratically. Double the length, quadruple the work. Double it again, work increases by sixteen times. Computer scientists ignore seconds. Hardware speeds up anyway. They count steps. We call it Big O notation. Grade school is O(n^2). Quadratic. If your number grows by 1,000, the work explodes by a million.<\/p>\n
\nThe workload scales with the square of number of digits.<\/p>\n<\/blockquote>\n
Since antiquity, math wizards assumed this quadratic limit was a law of nature. Andrey Kolmogorov, a Soviet legend, bet his reputation on it in a 1960 lecture. He told the students at Moscow State University: \u201cIt takes O(n^2).\u201d It\u2019s a formal conjecture. A challenge. Wait for someone to prove it or break it.<\/p>\n
It took a week. Anatoly Karatsuba sat in the audience. He was 23. He came back with proof Kolmogorov was wrong. The professor was stunned. Kolmogorov actually wrote the paper himself for a prestigious journal but put Karatsuba\u2019s name on it. The kid didn\u2019t know until the reprints arrived in the mail.<\/p>\n
The Trick<\/h3>\n
Karatsuba realized something simple but profound. Multiplications are expensive. Additions are cheap. Why not trade them?<\/p>\n
Take 12 x 34.
\nSplit it up.
\n12 is 10 + 2.
\n34 is 30 + 4.<\/p>\nTraditionally, you do four multiplies:
\n1×3
\n1×4
\n2×3
\n2×4<\/p>\nKaratsuba found a way to do it with three.
\nCalculate the first part: 1×3 = 3.
\nCalculate the last part: 2×4 = 8.<\/p>\nNow the middle. Normally you\u2019d do (1×4) + (2×3). Two multiplies. Instead, add the first numbers: 1+2=3. Add the last numbers: 3+4=7. Multiply those sums: 3×7=21. Subtract the parts you already know. 21 – 3 – 8 = 10.
\nBoom. You got the middle term with one extra multiplication.<\/p>\nIs this worth it?
\nNot for small numbers. The overhead of splitting and adding costs you.
\nBut for 1,234 x 5,678? Split it in half. Recurse. Split those halves. Do it again. The savings compound.
\nThe algorithm drops to roughly O(n^1.585).
\nThousand-digit numbers used to require a million single-digit mults. Now it takes fewer than 57,00 steps. Massive.<\/p>\nThis isn\u2019t just theory. It\u2019s in Python.
\nPython uses standard school math for small inputs. Smooth enough.
\nOnce you hit roughly 63 decimal digits (depending on the machine\u2019s base), Python flips a switch. Karatsuba takes over. You don\u2019t see it happening. But it\u2019s there. Handling your cryptography.<\/p>\nGalactic Algorithms<\/h3>\n
The race continued for decades. Can we go faster?
\n2019 brought the latest shock. David Harvey and Joris van Der Hoeven published an algorithm that beats Karatsuba by a mile.
\nO(n log n).<\/p>\nRead that again.
\nLogarithms grow incredibly slowly.
\nn log n is barely bigger than n.
\nBasically, multiplying two massive numbers now takes about the same time as reading them.<\/p>\nIt\u2019s staggering. The theoretical ceiling seems to have been touched.
\nOr maybe not.
\nHere is the catch.
\nIt doesn\u2019t work for numbers we care about.<\/p>\nHarvey and Van Der Hoeven\u2019s algorithm only becomes faster than Karatsuba when the numbers get really<\/em> big. Not “credit card number” big. Galactic big.
\nIn computer science we have a term for this: galactic algorithm.
\nBeautiful theory. Zero practical use. The numbers required are larger than most digital transactions in human history combined.<\/p>\nWe are stuck in the middle.
\nUsing 1960s tricks for most of our daily computing.
\nWearing 21st century suits on top of 20th century math.<\/p>\nDo we ever actually use O(n log n) in the real world?
\nMaybe when we process data sets the size of galaxies.
\nUntil then we wait.
\nFor the next trick.
\nOr better hardware to hide our laziness.<\/p>\nThe answer might still be quadratic.
\nIt might be linear.
\nWe don’t know yet.<\/p>\n","protected":false},"excerpt":{"rendered":"Kids learn their times tables in school. Memorize them. Good luck with three-digit numbers. That\u2019s where algorithms kick in. You stack the digits. Multiply row by row. For thousands of years, we thought that was the best we could do. It\u2019s slow. Brutally slow for big data. Then in 1960 a 23-year-old changed everything. The […]<\/p>\n","protected":false},"author":1,"featured_media":7909,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"tdm_status":"","tdm_grid_status":""},"categories":[1],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/en\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}