How a Russian student invented a faster multiplication method

[@soyanchd5439]

Props to Kolmogorov, he could have sent the paper in his own name without giving credit to an unknown student and take all the merit. The academic world is sometimes ruthless

[@MiGujack3]

@@marcnye9221 Corporate is eroding that, now quicker than ever.

[@beltramejp]

@@marcnye9221 while in engineering... :/

[@qTnD42hR]

@@marcnye9221 great that you've got that impression, but the reality is that more and more university professors are favouring producing quantity over quality of papers so they can earn "prestige", and the students are used as free labour to support that.

[@mrkitty777]

Sure B Gates gave credits to computer scientist, sure, B Gates is well known for it. In reality however Gates stole almost everything and forced many people over the edge to afterlife. Dr Gary Kildall his Wikipedia can enlighten you how B Gates haircut fooled him when B Gates stole his 10 year of work developing an operating system and the BIOS all computers once had.

[@no1ofinterst]

Incorrect. I can name atleast one Ruth in the academic field (Ruth Aaronson Bari)

[@yurr7408]

Kolmogorov is one of the coolest men I've heard of. Admitting defeat and then anonymously supporting the kid. wild

[@bluesteel7874]

Really curious people wants their ideas to be scrutinized. They seek knowledge.

[@godfather7339]

Soviets and their communism. nowadays you will get "researchers" sponsored by pharma/oil/any companies.

[@NemisCassander]

I know of Kolmogorov mainly from my work in statistical analysis. There he is, basically, a god.

[@healmyvision5941]

Unthinkable nowadays Nowadays he would have canceled him and his career for the „crime“ of being right

[@scottcourtney8878]

Indeed. To not only admit, but actually welcome, verifiable new information that unseats old hypotheses is the hallmark of good science. I have no doubt that Kolmogorov carefully analyzed Karatsuba's proofs before fully accepting them (as any wise researcher would), but once he had confirmed their validity, he had the intellectual courage and integrity to embrace them. A scientist is not diminished when their hypotheses are disproved, because that is how we evolve the body of human knowledge, but some will diminish themselves by refusing to accept this with grace.

[@alexray4969]

I think the fact we don't teach fast fourier transform in elementary school says a lot about society.

[@jakewalklate6226]

We should replace the early education curriculum with theoretical computer science and graph theory

[@letsburn00]

Read the comment section on any WW2 obscure event which has an insignificant effect on the war. "Why didnt I learn about this in school? Clearly it's a conspiracy against America!" I know youre joking, but that attitude is so common.

[@jakewalklate6226]

@@letsburn00 well there will be no history at all once I’m done with it, mathematics only

[@letsburn00]

@@jakewalklate6226 Spoken like a true mathematician. "Clearly Stalin invaded at the point due to numerical superiority over Finland. What about mathematical history? I'm still never entirely sure why we use 360 degrees apart from ease of use and something about Babylonians.

[@paulmichaelfreedman8334]

@@letsburn00 the use of 60 and 360 is because 60 is divisible by a lot of numbers. 1,2,3,4,5,6,10,12,15,20 and 30. Easy for calculator-less times.

[@kitsurubami]

For anyone curious at 13:38 N^1.6 is used as an approximation. It's really N ^ log base 2 of 3. If you want to enter it into a calculator use the change of base formula. Log(3) / Log(2)

[@mskiptr]

Well, every O(n^log2(3)) algorithm is also an O(n^1.6) algorithm, so the video is fully correct in approximating that number while not labeling the whole thing as approximated. Though I personally do like to state bounds like that exactly. Θ notation is a good way to do that (it just means both O and Ω).

[@willsterjohnson]

taking log2 of 3 to be 1.58 (it's not, it's much closer to 1.6, I've added about 30% difference here) this difference doesn't break 10% until N=194, in base 10 that's; 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 it doesn't break 5% until N=13, or one trillion in base 10, so the discrepancy grows at a painfully slow logarithmic curve; 1,000,000,000,000 For all human use cases, N^log2(3) = N^1.6

[@tytywuu]

I love how you bring nearly-unreachable knowledge to the community through interesting and easy-to-understand videos. I would never know this bit of theoretical CS otherwise. Keep up the good work!!!

[@ApteraEV2024]

& I also £♡✌️€ , how I'm studying Russian language, ,& this Shows me RUSSIAN letters, names, historical events & People! Spasibo. Спасибо. (Thank You).

[@MattWyndham]

This is what I studied in my 200-level, 300-level, and 400-level computer science algorithms class. Good explanation!

[@BotCheese]

The legend is back

[@bartekltg]

Between Karatsuba and FFT there is a Toom-Cook algorithm, from 1963-66. As FFT, it treats both numbers as polynomials, evaluate the values naivly in some points (for small numbers! Like 0,+-1, -2,+inf), multiply them and then interpolate it back to polynomial form. "2 way" toom-cook recreates Karatsuba. The original "3 way" and "for way" have the complexity O(N^1.465) and O(N^1.404). The GMP library (a hefty library for big numbers) uses naive, Karatsuba, "3","4","6.5" and "8.5-way" toom-cook, and fft, using each algorithm for numbers of different lengths.

[@yash1152]

uhm waht? :sweat_smile:

[@haiguyzimnew]

I loved fast inverse square root and finally you've released some more videos! Makes my day. Take however long you want, they're worth it.

[@nicholashall3479]

Content like this is why I still pay my internet bill. Thoughtfully presented, beautifully explained, and utterly fascinating even to a cynical math-o-phobe like me. Eighteen minutes well spent. I look forward to future content as a new subscriber. Bravo!

[@polarisinglol]

Wonderful video :) I am writing an Algorithms exam next week and wanted to take a break from learning but ended up learning about the algorithm more than in my lecture and in a more exciting and relaxing way. Thank you for this masterpiece and wonderful editing!

[@tomerwolberg37]

17:20 note that also loglogN is practically constant like the k^log*(n) since loglog(N) where N is the numbers of atoms in the observable universe is around 8. If N is the number of atoms in the observable universe then loglogN is actually smaller than 4^log*(N).

[@daldi5211]

What base do you use for the log?

[@tomerwolberg37]

@@daldi5211 2

[@trueriver1950]

@@daldi5211 in practice in IT we would use base 2 as we can approximate it by counting bits from the ones bit (which we count as zero) up to the largest bit with a value of 1. However there is a theorem that states that to change a log from one base to another we can multiply by a constant that depends only on the two bases. And we know from earlier that we can ignore constant multipliers. So you can apply this rule in any base you like and it still works.

[@zip753]

it's not a theorem, it's just a simple property deduced from the definition of the logarithm :)

[@ViguLiviu]

Fuck, I actually checked it for log(log(10^82)) and it truly does round to 8. Granted I did it in my mind, but it does check out.

[@roberthigbee3260]

Kolmogorov also advanced the study of fluid flow turbulence so much that they named a constant after him and still refer to his work to this day!

[@ristekostadinov2820]

Kolmogorov have done a lot for statistics and random processes

[@Ricocossa1]

It's amazing how a simple problem like multiplication can devolve into such complex mathematical discoveries. Who would have thought that multiplying optimally is insanely more difficult than adding.

[@SnakeTwix]

Would you really not expect multiplication, which is basically an extension of addition, to be harder to optimize, than its more basic "counterpart"?

[@Ricocossa1]

@@SnakeTwix Yes, but not that much harder.

[@michaelbauers8800]

I set out, one afternoon, to write a large number library, just for my own edification. When I got to division, I realized I didn't actually know how to program a computer to divide, other than using built in divide. Sometimes simple things are not as simple as they seem :)

[@AntoineViallonDevelloper]

@@michaelbauers8800 just use Euclid's algorithm for integers.

[@CTimmerman]

@@AntoineViallonDevelloper Euclid's algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers) but it uses division itself, so isn't useful to Michael.

[@rebmcr]

Even if the lower bound is Ω(N × log N), there is still mathematical progress to be made (or disproven) in finding an algorithm which is that efficient with smaller and smaller inputs.

[@icollectstories5702]

Look-up table!😜

[@auriga05]

@@icollectstories5702 O(1) multiplication?

[@diamondcreeper0982]

@@icollectstories5702 it's fast but not memory efficient.

[@Ruhrpottpatriot]

@@diamondcreeper0982 You always have the trade-off between speed and memory and as it currently goes, memory is cheap.

[@diamondcreeper0982]

@@Ruhrpottpatriot although memory is cheap it's not available in everything. for example if we wanted to use this method we would run out of memory in an Arduino quickly, but i do agree that if we have the memory to spare then this would be the fastest solution.

[@gligoradrian784]

I have just discovered this channel and the animations and the gradients are so beautiful, the content, so mesmerising, that I instantly subscribed. Thank you.

[@simonmultiverse6349]

14:47 That was honest of Kolmogorov. I have met a few people in my career who would pretend to have done work which was actually done by someone else. They would then take the credit for the other person's work.

[@CrudeBuster]

yeah you know, people learned the lesson after all the Leibniz/Newton kerfuffle over calculus

[@kyoai]

9:30 and 16:00 I think it would've been better if you used actual numbers and showed a practical example of the calculation instead of empty digit boxes/partially filled circle shapes, it would be easier to keep track on and follow what you're talking about. Since the video started with practical examples for the easier algorithms I also was expecting practical examples for the more complicated algorithms. Having to follow where you put which blank box or which abstract circle is filled by how much and trying to find out why you gave the circles these fill values while at the same time also trying to listen to what you are saying is rather irritating.

[@tophan5146]

I had the same thoughts

[@louispalko691]

I'm glad someone else pointed this out. I got lost and felt that if I just had a real example to go off of it'd be much easier to follow

[@Alb-Patriot]

Click on his channel. The second video does exactly that

[@AngelicHunk]

@@DrDeuteron If you're _not_ bothered by getting lost, I'd say that's a sign of complacency.

[@louispalko691]

@@DrDeuteron just admit you don't know wtf is going on and move on lol

[@mickharrigan1814]

I really enjoyed this, good to see more coming from this channel. Excitedly looking forward for more!

[@sm5172]

I'm super excited to watch this later when I'm done with work. Thank you for the amazing content!

[@Corncycle]

what an incredible video, you have a real talent for getting at the core of these ideas and showcasing the clear arguments which easily get muddled by technicalities

[@fabyr_]

Omg he published again!!!! The god returned yeeeesss Your content is so high quality, can't emphasize this enough.

[@Nemean]

How do you know? You commented 2 minutes after the video got published, there's no way you have watched it all yet. Maybe my video sucks.

[@notbob9865]

@@Nemean it slapped bro

[@fabyr_]

​@@Nemean I just knew from the previous one (Quake Inverse Sqrt Algorithm), and damn this video was really great. It had some really unexplainable feel at the end (all the multiplication-algorithms and their runtime). It was super informative and very interesting in fact. 👍👍👍👍👍👍👍👍👍👍👍👍👍

[@Nemean]

@@notbob9865 Thanks :)

[@sevm7792]

@@Nemean 10x playback speed

[@mikkolukas]

Fun fact: When computers are multiplying whole numbers, the compiler will often optimize the code, so it doubles (or halves) the number one or more times (which is a single operation in the computer, known as bit shifting) and then add or subtract a konstant to achieve the result. So a code of x * 9 (which is (x * 8) + 1) would be compiled as an equivalent to (x

[@hoane6777]

very interesting, do all compilers do this? is there a way to force this specific method if i notice the compiler isnt doing it? Also, i think you meant to write (x * (8+1)) or even more descriptive, (x * (2^3+1))

[@EpicBikingAdventures]

(x * 8) + x

[@timewave02012]

@@hoane6777 In general, no, you can't force a compiler to do something not specified by the language. You have to write the code the way you want it, and that's almost always a bad idea for maintainability. Also, if you're working with numbers big enough for calculation speed to matter, the compiler won't know to optimize anything, because the calculations will span multiple variables of the largest builtin type (e.g. 64 bits). If you're working on cryptographic code, you need to worry about how the calculations are performed for more than just speed. If a calculation takes a different number of steps depending on the value of a key, for example, that weakness can be used by attackers to retrieve the value of the key.

[@DasHemdchen]

I was astonished to learn that my C64 didn‘t have a Mult opcode, and to multiply any number by for example ten, it had to multiply by eight (shift three times) and then add the input value two times. What a hassle!

[@coopergates9680]

@@DasHemdchen After the shift left 3 bits, it didn't shift the original left 1 bit to get a double to add to the eight to arrive at ten? Weird... or shift left 1 for double, then shift that result 2 to get 8x. If you've come across the binary exponentiation algorithm (square and multiply), you could use successive bit shifting and addition to arrive at multiplication for arbitrary numbers. As a bonus, if you want the answer mod some n, you can just subtract n after each single bit shift left that yields n or greater, instead of programming division.

[@baka_geddy]

The Quality and The Content is top notch! Thanks for sharing!

[@Jaime.02]

This video is truly amazing, it mixes the beauty of computer science and math

[@jonathanross6260]

Hahaha I loved your inverse FFT notation. Well played, well played.

[@Filaxsan]

Amazingly beautiful review and info! Thanks for making this! All the best

[@pattabor5268]

I'm so happy that you've made another video, this makes my hyped to learn again. It's great motivation!

[@owobooperlv7673]

Glad I had my notifications on, Welcome back! Thanks for yet another informative video that is surprisingly easy to understand :DD

[@mjthebest7294]

This is FIRE! What a spectacular journey. This is how it should be taught. Can't wait for more videos from you!

[@kimdammers3838]

Not for everyone. I found the presentation confusing.

[@frankman2]

Imagine teaching this to 9 year olds.

[@teslababbage]

Absolutely fascinating, please keep them coming.

[@akirachisaka9997]

I have to say, I can't even remember how many times I have learned Big O notation already, but it's the first time in my life I heard about Linear speedup theorem. Like, it suddenly explained everything. I suddenly understand why the linear magnitude does not matter.

[@DavidTriphon]

This whole video is incredibly interesting and explains lots of things very well, but I am laughing so hard at 17:00 . The deadpan delivery of that line “log star of the number of atoms in the universe... is five.”

[@sproga_265]

Glad to have you back! Some of the highest quality content on the platform

[@philrod1]

That was a joy to watch. Thank you!

[@adrijachakraborty2316]

My goodness the explanation and visuals are amazing! Glad I came across this channel.

[@icollectstories5702]

Thanks for explaining this. I vaguely remember running into this algorithm, but discarded it because it recursed without really reducing complexity. After watching your explanation, I realized that if I restrict the recursion depth, I might get something usable.

[@rik0904]

i kind of understood this. thank you for this video. I often come back to your first video when i need inspiration how to change way of thinking when i search for answer.

[@keidza2029]

I'm not into computer science or even math, yet still here to watch video until finished.

[@beltramejp]

Since your fast SQRT video I was waiting until your next lauch. This video gave me a thousand goosebumps, incredible! Good job

[@ZK-im6er]

Thank you for educating us with this beautiful video of yours. The way you put them together is just perfect, thank you again.

[@Kubonka_]

The cadence and tone of your voice is very pleasant to listen to. It reminds me of the JCS channel. Thank you very much for teaching me with such detailed and illustrative information.

[@SianaGearz]

I have seen fast multiplication on Commodore 64 (6502 processor without a built-in multiplier) based on a similar idea. a*b = ( (a+b)/2 )^2 - ( (a-b)/2 )^2. For all possible values of a+b and a-b, the square of a half is precalculated in a table; so for 8-bit numbers, 512 precalculated table entries are needed. This is easily a few times faster than trivial multiplication.

[@j.fischer5035]

Wow. Interesting.

[@AminemBD]

Really glad you're back! Can't wait to see more of your content.

[@knightofvirtue613]

I looked at this video on a random whim and I'm glad i did! Very well explained video on a topic that can be difficult to follow. As others have mentioned, practical examples may have worked better than the colored blocks used, as this would allow the audience to follow along in an easier fashion. Thanks!

[@Grecks75]

This is such an excellent lecture and presentation, you make a great professor! I'm saying this as a computer scientist. It was educating and entertaining at the same time. Kolmogorov was a genius, albeit not infallible. We are standing on the shoulders of giants. Thanks for educating us! I learned new stuff from this video.

[@YellowBunny]

I really like that the best multiplication algorithm uses the Ramanujan-Hardy number.

[@insideoutsideupsidedown2218]

My guess is there would be a square root symbol in it somewhere…

[@estepario7415]

Hi YellowBunny!

[@YellowBunny]

Hi Estepario

[@Xxnightwalk1]

I really love your videos so far, clear and somewhat concise Really instructive, thanks. I hope you make more

[@financialcafe]

This story about Kolmogorov and Karatsuba should be made into a film so that more people know it

[@simongross3122]

Excellent discussion, thank you. Also what a mensch Kolmogorov is. Good to see, and thanks for telling us about it.

[@HWMREWesker]

Just a heads up - there's a terminology mistake at 1:00 . "Addition" should be translated as "Сложение" in Russian, while "Дополнение" in English would be "Complement" term from Set Theory.

[@loganswinamer4003]

i've never seen a youtube account with 3 videos that makes such high quality videos. seriously well done man

[@andrewkraevskii]

1:01 In Russian it is better to use the word "сложение" instead of "дополнение" to denote addition.

[@andrewkraevskii]

"дополнение" in Russian means complement (set theory)

[@Nemean]

Oh Jesus... thanks for the input though

[@AffidavidDonda]

​@@Nemean​*Oh Lenin...

[@muchhustle4982]

@@AffidavidDonda ?? As if Lenin is at all praiseworthy?? I’m sure his black charcoal of a heart is still providing fuel for the fires of “oh hell” tho…. It’s for the despicable evil, deliberately propagated like deadly contagions still infecting the minds the of the vulnerable, mentally weak, and those victims with “compromised intellectual immunity” who had their natural defenses of logic, reason, and objective observation castrated by atrophy, shriveled and withered like undesirable testicles on the proverbial farm hog, resulting from the constrictive rubber bands of indoctrination posing as education by Marxist operatives posing as teachers, all susceptible and succumbing to the mental viruses created and propagated by Marx, Lenin, and the rest of the monsters of yesterday and today, that cause lapses in my Agnosticism to pray that there is a heaven for some and a well deserved hell for others.

[@azratosh]

@@muchhustle4982 Thanks for that copypasta my dude! Haven't seen that one before

[@mastergmatquant]

Just loved the video man! awesome it was.

[@pawebielinski4903]

I love this subject, mainly because it is both quite recent and revolutionary, in a way, as well as rather easily understood by a teenager. Every now and again I talk about it to my students, and it is usually well received.

[@neilshen759]

Nice video! Really liked the smooth animation

[@taureon_]

i thought this account exists just to post one vid and nothing else, nice to see a new upload!

[@deepjoshi356]

Thanks for making computational mathematics accessible. The last summary is pure gold.

[@johnywhy4679]

14:13 You say "It's ONLY application is cryptography" as if that's a weakness or flaw. The fact that it can offer real optimization on modern hardware for a certain subset of applications is awesome and amazing and valuable. Also, even if it had NO practical applications, it's still awesome because it disproved a prevailing theory. Even if it didn't do that, it demonstrated a new kind of algorithm. It did THREE amazing things. And you say, "I dunnno" :D

[@stankoo1413]

Even if this video doesn't blow up it is still amazing content, thanks!

[@scottcourtney8878]

Fascinating algorithm and historical context. Thanks for sharing this and for explaining it so lucidly. For those who aren't old enough to remember the old days of computing, one of the reasons multiplication was of such interest is that early CPUs did not have a multiply instruction in hardware. They relied on repeated addition, so if you wanted 58 * 37 it was computed as 58 + 58 + 58 ..... (37 times total), or vice-versa. I'm not sure if the first computers even had the hardware smarts to swap the numbers so they added the larger number a smaller number of times. Repeated addition is often even slower than the O(N**2) elementary school algorithm, so computer scientists were eager for anything that could improve upon that. Also for the non-computer folks, Nemean makes the comment that subtraction is essentially the same problem as addition. You know from grade school that subtracting N is the same as adding -N, of course, but it might occur to you that -N is defined as -1 * N, which seems to imply a hidden multiplication step. Fortunately, since computers work in binary, we avoid that by using the "twos complement". In binary, this means flip every bit of the original number, which gives you the "ones complement", then add one. Adding the twos complement of N to another number, say M, is the same as computing M - N. Here's an example using 8-bit integers, a common size for early CPUs, to compute 100 - 35. 100 is 64 + 32 + 4, or 01100100 binary. 35 is 32 + 3, or 00100011 binary. Take the ones complement of 00100011 to get 11011100, then add one for the twos complement of 11011101. Adding 01100100 to 11011101 gives (1)01000001. The parentheses are around the carry bit, which in this situation we ignore (see note below). 01000001 is 64 + 1, or 65 decimal, the answer we expect. Even in very early computers, the operations to invert every bit (ones complement) and to add one (increment) were single hardware instructions, so the twos complement took at most two steps (and some CPUs had a single instruction to combine them). So subtraction, even on an early CPU with no subtract instruction, was not significantly more difficult than addition. The use of twos complement binary arithmetic does imply a need to keep track of that leftmost bit and being aware of whether it is being used as a sign (1 for negative, 0 for positive) or simply as another binary digit. Programmers can define "signed integers" which cut the value's range in half but allow negative numbers, or "unsigned integers" which allow the full range but cannot be less than zero. For instance, a 16-bit unsigned integer can be 0 to 65535, inclusive, while a 16-bit signed integer can instead be -32768 to +32767, inclusive. The CPU hardware, generally, handles the raw bits the same, but the programming language and compiler help the programmer avoid misinterpreting the data. I hope this side-trip into computer history and binary math is useful to readers who aren't computer specialists.

[@_schnelli4800]

Great comment

[@raman249]

Very helpful 👍🙂

[@eatstudio9244]

wait, didn't booths multiplication algorithm exist back then? I'm surprised they used repeated addition

[@dtvjho]

To give an example, the Mostek / Rockwell 6502 (of Apple II fame) had add and subtract but no multiply or divide instructions, but the Motorola 68000 (Macintosh) had them. These chips hit the market only 4 years apart.

[@Dr_Wrong]

So subtracting, is adding a negative number: 8 - 2 = 8 + (-2) And to add a negative number you subtract its absolute value? 8 + (-2) = 8 - |-2| ... ... *= 8 - 2 = 8 + (-2) = 8 - |-2| = 8 - 2 =* ... forever..

[@cowlegacy]

This was super interesting thanks for uploading, I will be watching you form now on

[@pianowhizz]

I believe Karatsuba's algorithm is used in quantum computing as the current fastest/most efficient method of multiplication.

[@BELLAOUAR_Mahmoud]

we learn more in this video ...thnx 4 posting .

[@SrIgort]

Really cool seeing that discoveries in mathematics are still being done to this day :)

[@schweinmachtbree1013]

discoveries in math are being done every day - mathematics is so much more than just arithmetic!

[@noahwinslow3252]

Thank you for a fantastically well put together video.

[@KnakuanaRka]

I feel like when you were talking about big O, there were some big aspects you missed. In particular, one of the big reasons big O is important is that it better measures how an algorithm scales to extremely large inputs. While the big O might not be able to tell you an exact runtime, it can tell you how that runtime changes when you change the input. For example, for an O(n) algorithm, doubling the size of the input make it take twice as long as before, while an O(n^2) algorithm will take 4 times as long, and an O(log n) algorithm will only take a constant amount of time more. The ways that different algorithms scale tends to be more important than any constant factors when n is extremely large. For example, the runtime of an O(n) algorithm might be like 10n, while an O(n^2) algorithm might be n^2/10; with small n, the O(n) algorithm is slower due to the high overhead (for n=4, the first algorithm is 40 while the second is 1.6), but as n increases, the difference in powers rapidly overcomes the constant factors (for n=10,000, it’s 100,000 versus 10,000,000, so the first is a hundred times faster). That’s why we talk about big O in algorithms; when the input is big enough that runtime is a concern, that’s what gives you a real idea of the runtime.

[@awogbob]

Wow this makes waaaay more sense

[@RobBCactive]

An O(log n) algorithm isn't constant, but would be proportional to natural logarithm, O (n log n) is more feasible as just processing the input is O(n).

[@KnakuanaRka]

@@RobBCactive I wasn’t saying log n was constant time; I was saying for a log n algorithm, doubling the input length would increase the time by a constant amount, since log 2n = log n + log 2.

[@RobBCactive]

@@KnakuanaRka No you specifically said, "and an O(log n) algorithm will only take a constant amount of time more", read your post adding log 2 or log 3 to log n for factors of N is NOT a constant

[@KnakuanaRka]

@@RobBCactive Well, if log n is the runtime for input of length N, adding log 2 for the runtime of 2N is effectively a constant amount more (since it doesn’t depend on N); what’s the problem?

[@bradley1995]

Awesome video so far. 48 seconds in and started with a verse, had some code in there... Kool stuff!

[@Adityarm.08]

Amazing work, thank you!! This certainly was a brilliant idea.

[@adolfohenriquez6715]

I loved this video! Inmediatly suscribed!

[@NZAnimeManga]

Excellent video!!

[@totheknee]

18:00 - For smaller numbers... Lololllol 🤣 I love your delivery. Pure gold.

[@Fowly-Fr]

That was fascinating, thank you

[@ollyoctavian]

Really great explanations! And I really appreciate the overview of recent developments

[@controlflow89]

Epic video, товарищ! :)

[@Nemean]

spatsiba or whatever

[@ardentdrops]

He was so impressed with this young kid's genius that he did all the work for him as a gift.

[@spiikesan]

This algorithm is used in Java's implementation of BigDecimals (or BigIntegers ?) for very big numbers.

[@joachimprz]

BigInt yes

[@abhishekrnath6560]

Also python and possibly javascript

[@thinotmandresy]

Awesome video! I just found this channel now thanks to the algorithm. I'm subscribing right away!

[@sergeytaranov2015]

Great video! And as a Russian-speaking person I want to notice that mathematical operation "addition" is called "сложение" not "дополнение". The term's you used meaning is "a minor member of a sentence, usually expressed as a noun". Best Regards!

[@RFC-3514]

дополнение means "addition" in the sense of supplement or expansion (i.e., it would be used in sentences like "the addition of a new terminal to the airport", or "with added vitamins").

[@Wecoc1]

I'm just discovering this channel now. Nice stuff!

[@TymexComputing]

In the time when Kolmogorov was at the age of Karatsuba (when they met) there was no Fast Fourier Transform, but on the other hand Parseval theorem was already stated in the 18th century - kids read the books and study them ! :)

[@samuelgunter]

I'm glad I clicked on this video, the thumbnail made it look like it was going to be a dumb math method that still works but overcomplicates things/does the exact same thing the normal method does but displayed slightly differently but clickbaited as "a new faster way to do math" but it turned out to actually be more efficient (as the length of the numbers increases)

[@simonmultiverse6349]

If you do the FFT in _modular_ arithmetic (which uses only integers) you get multiplication with no rounding error because you don't need to worry about floating-point arithmetic. The algorithm is the same.

[@astrodreamer9168]

I think Bunimovs optimization of Montgomerys algorithm is another beautiful algorithm to compute products using modular arithmetic in finite sets.

[@JonathanMandrake]

We learned the Karatsuba Method last week in Numerics, so this was an interesting new take on the way we learned it

[@marianarlt]

I love the super subtle humor here, hahaha. The explanatory visuals are also great even though I feel it still quickly becomes a lot to digest for us lower peasants. YT needs more of this. Thank you.

[@mitchevans4597]

Thank you for showing me how the computer works using algorithms.

[@sounak5853]

Can we all agree that this person should make more videos? Explaining complex computer science and mathematics concepts in simpler terms is something we all need in our lives.

[@MrSlowThought]

"I claim", kudos for knowing what's right and saying what's obvious, and moving all of us along the path of learning.

[@NigelTolley]

That was brilliant. And actually taught me new maths too.

[@secularph8424]

Legend , Pls do more of these type.

[@algorithminc.8850]

Thank you ... great explanation ... interesting history ...

[@mr2octavio]

Another fantastic video my friend

[@SurfinScientist]

That was a fun video! (said by a Theoretical Computer Scientist / Mathematician)

[@sargentscythe]

Another fantastic video!

[@anthonykeller5120]

Hmmm…reminds me of another algorithm dealing with linear programming (LP). LP is theoretically a N^x steps where x is the number variables. There is a Russian algorithm that has O(N) steps, but the slope of T (time) is so steep it might as well be a quadratic equation. I wrote a paper on this 40 years ago for one of CS Master’s classes after reading about it in a programming journal. The math was so obscure (or maybe the Russian was so obscure) that I had to go back to the original paper to get the algorithm correct. It was a fun project, as I was really interested in linear programming at the time. Seems I fell in love with CAD, though.

[@toskium]

I really enjoyed your video, I can only encourage you to publish more content like this.

[@rhythmepaper]

I smashed subscribe button. No doubt. What a quality algorithm explanation.

[@aidanhackett8530]

Dude dropped two of the best CS videos on KZbin and then dipped

[@ashhadnaqavi]

very interesting and informative video

[@morgus9215]

hey wait a minute, this is the same guy on quake fast sqrt. glad you're back with some bangers