How Karatsubas algorithm gave us new ways to multiply @Nemean

Nemean To advance the field of computer science, mathematician Kolmogorov tried to optimise the multiplication algorithm we learn in elementary school. After failing to do so, he conjectured that no faster algorithms exist. This gave rise to Karatsuba's fast multiplication algorithm, an algorithm named after Anatoly Karatsuba that is faster than the elementary school algorithm. This video gives an introduction to theoretical computer science and Kolmogorov's conjecture, explains the algorithm, proves that it has a runtime faster than quadratic, and goes over the history of multiplication algorithms that came afterwards.

0:00 Theoretical Computer Science
5:25 Kolmogorov
7:34 Karatsuba
15:12 The Post-FFT Era

updated 3 years ago

How Karatsubas algorithm gave us new ways to multiply

Nemean 2021-08-22 | To advance the field of computer science, mathematician Kolmogorov tried to optimise the multiplication algorithm we learn in elementary school. After failing to do so, he conjectured that no faster algorithms exist. This gave rise to Karatsuba's fast multiplication algorithm, an algorithm named after Anatoly Karatsuba that is faster than the elementary school algorithm. This video gives an introduction to theoretical computer science and Kolmogorov's conjecture, explains the algorithm, proves that it has a runtime faster than quadratic, and goes over the history of multiplication algorithms that came afterwards.

0:00 Theoretical Computer Science
5:25 Kolmogorov
7:34 Karatsuba
15:12 The Post-FFT Era

Researchers Use Group Theory to Speed Up Algorithms — Introduction to Groups

Nemean 2022-08-06 | This is the most information-dense introduction to group theory you'll see on this website. If you're a computer scientist like me and have always wondered what group theory is useful for and why it even exists and furthermore don't want to bother spending hours learning the basics, this is the video for you. We cover everything from the basic history of group theory, over how and why subgroups partition groups, to the classification of all groups of prime order.

Babai's talk can be found at: http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4

0:00 Intro
1:42 Abstract Algebra
4:28 Group Theory
8:01 Z Q Zn Dn
14:29 Proofs
18:58 Subgroups & Cosets
25:31 The Theorem
29:11 Classification of Groups of Prime Order

#SoME2

Karatsubas Multiplication Trick Summarised in 1 Minute

Nemean 2021-08-12 | #VeritasiumContest

When soviet mathematician Kolmogorov set out to prove that there exists no faster multiplication method than the standard one we learn in elementary school, a young student by the name of Karatsuba, also trying to find a proof, managed to find a trick that beats the standard method. This video explains the high-level idea and the insight of Karatsuba's multiplication algorithm.

E-Mail address: Nemean_YT@protonmail.com

Fast Inverse Square Root — A Quake III Algorithm

Nemean 2020-11-28 | In this video we will take an in depth look at the fast inverse square root and see where the mysterious number 0x5f3759df comes from. This algorithm became famous after id Software open sourced the engine for Quake III. On the way we will also learn about floating point numbers and newton's method.

0:00 Introduction
1:23 Why Care?
3:21 The Code
4:18 IEEE 754
9:38 Bits and Numbers
12:09 1st Step: Evil Bit Hack
14:46 2nd Step: WTF
17:34 3rd Step: Newton
19:46 Summary

Picture of John Carmack is licensed under CC BY 2.0 from author Drew "Prognar" Campbell.
Source: http://flic.kr/p/6YxWYp