PurpleMind
PurpleMind
  • 11
  • 449 135
The Genius Way Computers Multiply Big Numbers
This video was sponsored by Brilliant.
To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/PurpleMind/ . You’ll also get 20% off an annual premium subscription.
In this video we dive into the history of algorithmic advancements in performing large multiplications, which gave rise to a young mathematics superstar, shaped some of the most popular programming languages, inspired new algorithmic techniques now used to train artificial intelligence, and even directly contributes to the security of your data when you write emails or browse the web (like you’re doing right now :D ).
It all started with a challenge by Andrey Kolmogorov in 1960 to find a faster way to multiply and an ingenious algebraic reformulation of the multiplication process by Anatoly Karatsuba, leading to what we now know as Karatsuba's Algorithm.
I’m super excited to continue making videos on Theoretical Computer Science in the future, and if there are any topics you’d like to see covered on the channel, please don’t hesitate to leave a comment below!
Thanks so much to Brilliant for sponsoring this video and to all of you for watching!
Feel free to join my Discord server: discord.gg/smuxnzZ5Zf.
For those of you who are interested, I’ve posted a commented version of my Python code I displayed in the video in the #recent-videos-discussion channel.
I am on Patreon: www.patreon.com/PurpleMindCS/membership. If you would like to support the channel, this is the best way to do it!
Business Inquiries: purplemindcs@gmail.com
Math animations are made using Manim, by 3Blue1Brown.
Character animation done by Huzaifa Animate.
มุมมอง: 280 293

วีดีโอ

How This Robot Creates Alien Text
มุมมอง 10Kหลายเดือนก่อน
This video was sponsored by Brilliant. To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/PurpleMind/ . You’ll also get 20% off an annual premium subscription. Here we explore the fascinating world of creating fake handwriting, which is a form of art called asemic script writing without meaning. We go in-depth on how to make use of intuitive, fundamental struc...
Can You Solve This Geometric Puzzle?
มุมมอง 18K3 หลายเดือนก่อน
This is episode 3 in a series called "Brainstorm." The topics for these videos are puzzle-style problems, broken into two parts each, a couple months apart. In the first part, I introduce the problem, and you (the viewers) try to solve the problem yourself, or at least come up with some initial approaches or first steps. I encourage you all to submit your (possibly partial) solutions to me thro...
How to Make "Trick Dice" That Are Actually Fair
มุมมอง 61K3 หลายเดือนก่อน
This video was sponsored by Brilliant! Check out brilliant.org/PurpleMind/ for a 30-day free trial and a 20% discount on an annual premium subscription. This is episode "2B" in a series called "Brainstorm." The topics for these videos are puzzle-style problems, broken into two parts each, a couple months apart. In the first part, I introduce the problem, and you (the viewers) try to solve the p...
My Viewers Are Math Geniuses
มุมมอง 51K4 หลายเดือนก่อน
This is episode "1B" in a series called "Brainstorm." The topics for these videos are puzzle-style problems, broken into two parts each, a couple months apart. In the first part, I introduce the problem, and you (the viewers) try to solve the problem yourself, or at least come up with some initial approaches or first steps. In the second part, I follow up with animated discussions of the soluti...
Dice Don't Normally Look Like This...
มุมมอง 18K5 หลายเดือนก่อน
This is episode 2 in a series I'm calling "Brainstorm." The topics for these videos are puzzle-style problems, broken into two parts each, a couple months apart. In the first part, I introduce the problem, and you (the viewers) try to solve the problem yourself, or at least come up with some initial approaches or first steps. I encourage you all to submit your (possibly partial) solutions to me...
I dare you to try to solve this math puzzle.
มุมมอง 4.2K6 หลายเดือนก่อน
This is the first of (hopefully many) videos in a new series idea I had that I think has some good potential: The topics for these videos will be mostly puzzle-style problems, broken into two parts each, a couple months apart. In the first part, I introduce the problem, and you (the viewers) try to solve the problem yourself, or at least come up with some initial approaches or first steps. I en...
How Quantum Computers Can Solve The World's Most Useless Problem (Part 3B/3)
มุมมอง 1.7K7 หลายเดือนก่อน
This is part 3B of a 3-part series on intro-level quantum computation. It is the final and most-advanced video in the series, and we go into some fairly complicated math! Part 1: th-cam.com/video/8kqXnLzYYqQ/w-d-xo.html Part 2: th-cam.com/video/H3uQsOcvUTw/w-d-xo.html Part 3A: th-cam.com/video/jg6HJXVek1w/w-d-xo.html In this video, we flesh out a proof for the correctness of "MysteryTogglesDete...
How Quantum Computers Can Solve The World's Most Useless Problem (Part 3A/3)
มุมมอง 2K9 หลายเดือนก่อน
This is part 3A of a 3-video series on intro-level quantum computation. I had originally planned for this to be the last video but I decided to split it up into two parts. Part 1: th-cam.com/video/8kqXnLzYYqQ/w-d-xo.html Part 2: th-cam.com/video/H3uQsOcvUTw/w-d-xo.html Part 3B: th-cam.com/video/nOlnc1uwmwE/w-d-xo.html In this video, we formalize quantum programming with concepts from linear alg...
How Quantum Computers Can Solve The World's Most Useless Problem (Part 2/3)
มุมมอง 2.6K11 หลายเดือนก่อน
This is part 2 of a 3-video series on intro-level quantum computation. Part 1: th-cam.com/video/8kqXnLzYYqQ/w-d-xo.html Part 3A: th-cam.com/video/jg6HJXVek1w/w-d-xo.html Part 3B: th-cam.com/video/nOlnc1uwmwE/w-d-xo.html In this video, we familiarize ourselves with quantum programming, and begin to use its similarity in analysis to randomized algorithms to reason about some simple quantum progra...
How Quantum Computers Can Solve The World's Most Useless Problem (Part 1/3)
มุมมอง 3Kปีที่แล้ว
This is part 1 of a 3-video series on intro-level quantum computation. Part 2: th-cam.com/video/H3uQsOcvUTw/w-d-xo.html Part 3A: th-cam.com/video/jg6HJXVek1w/w-d-xo.html Part 3B: th-cam.com/video/nOlnc1uwmwE/w-d-xo.html In this video, we introduce a problem called "MysteryToggles," which provably requires a certain amount of work to solve classically, whereas the quantum version is solvable in ...

ความคิดเห็น

  • @RetroHobbyMag
    @RetroHobbyMag 23 ชั่วโมงที่ผ่านมา

    You over-egged the explanation a little - you underestimate your audience somewhat.

  • @soulsand4287
    @soulsand4287 วันที่ผ่านมา

    2:00 you can't hide pi or e from me...

  • @ochko7599
    @ochko7599 วันที่ผ่านมา

    Would've much more appreciated if it were reels but thanks tho.

  • @azuremonday
    @azuremonday 2 วันที่ผ่านมา

    Its called vedic mathematics invented by Adi Shankaracharya. I(not only me every sishu mandir student in india) learned this technique in class 2. 1000years ago this method invented. Its called Adhar multiplication.

  • @Tdg_fun
    @Tdg_fun 2 วันที่ผ่านมา

    2:18 is (pi + e)

  • @megasupy1997
    @megasupy1997 2 วันที่ผ่านมา

    That final solution was absolutely insane.

  • @moritzvaneimern299
    @moritzvaneimern299 2 วันที่ผ่านมา

    Imagine adding pi to e

  • @jeromehauss8228
    @jeromehauss8228 3 วันที่ผ่านมา

    Very nice. In an old Pour la science magazine (french version of Scientific American) there was an interesting algorithm for base 10 but shifted to -5..4 where addition propagates carry only one step right or left in parallel You can obtain base 20 digits -9..9 (or is it base 19 -9..8 ?) in a sequential way. Curious if it can be extended to multiplication. At the end there is the expense of converting to unshifted base 10 that ruins a bit the gain in carry propagation for obtaining sequential base 10 digits, which is required to compare two numbers. For addition of n numbers you "just" traverse n parallel pipelines (through renormalization to shifted base 10) and _begin_ to get shifted digits for arbitrary long integers after only n steps. Could be used in shifted base 3 -1..1 ?

  • @coulie27
    @coulie27 3 วันที่ผ่านมา

    12:25 I have found this number (log2 3) = 1.585 related to Sierpinski triangles (and other fractals of that Hausdorff dimension) and the Collatz Conjecture. Here it is again! 🙌 Super neat

  • @pokemonjourneysfan5925
    @pokemonjourneysfan5925 3 วันที่ผ่านมา

    2:56-2:59, Ahh. This might just be me, but I think you're glossing over some things. O(n) doesn't have to be perfectly linear. Example if the runtime of an algorithm was n+floor((log n)/(log 2)) it would still be O(n), because the base 2 log grows slower than n. And in Big O, we only care about the dominating part.

  • @paperiswhite2
    @paperiswhite2 3 วันที่ผ่านมา

    I got no idea why youtube recommending me this, but it got me into math for probably a week now

  • @Jonasz314
    @Jonasz314 4 วันที่ผ่านมา

    Karatsuba algorithm also exists in C++ through boost library. C++ does not have native support for big ints, as long as you're dealing with 64-bit quantities or less, multitplication is done by hardware, so there's no point in trying to optimize. The boost bigint library is a little clunky to use, and word to the wise - use the decimal version rather than the binary version, it's actually faster (the reason being that you never have to worry about overflow during the intra-limbs multiplication at leaf level, which saves a ton of cycles). in C++, Karatsuba is slower than straight-up multiplication with anything less that ~1000 bits of data, so that's typically where the branching stops (Boost cuts off Karatsuba at 40 limbs, each limb is a 32-bit quantity).

  • @beaconofwierd1883
    @beaconofwierd1883 4 วันที่ผ่านมา

    Shouldn’t the Python native implementation be better than Karatsuba since it switches to regular ”hardware accelerated” multiplication for the sub problems aswell? Or does it not do this? Feels like you should save a lot of time if it did, since you’re cutting n in half, meaning you go back to ”0 time complexity” very quickly.

  • @TskJafri
    @TskJafri 4 วันที่ผ่านมา

    I just opened TH-cam for a nice video to watch during lunch. Thank you! Instant subscribe. Kudos, and looking forward to more.

    • @PurpleMindCS
      @PurpleMindCS 4 วันที่ผ่านมา

      Glad you enjoy the content :)

  • @mohammedyuan
    @mohammedyuan 5 วันที่ผ่านมา

    2:00 the little reference here to pi (3.14159) and e (2.71828) is funny lol

  • @rocketman5004
    @rocketman5004 5 วันที่ผ่านมา

    make 3 arrays. one for each number you want to multiply and one for the result. the result array has the lenghth of both numbers combined. now make 9 arrays, the lenghth of number a. array 1 is a, array 2 is array 1+a, array 3 is array 2+a, array 4 is array 3+a, and so on. now go along the result array, shifting it by one number everytime you multiply it with the next number from array b and just add the corresponding array 1-9. that way you just have to do 9+n additions of large numbers. additions should be easier than multiplications anyway.

  • @cgarzs
    @cgarzs 5 วันที่ผ่านมา

    Extremely fascinating. I hope one day galactic scale calculations are commonplace. Though, with this species at least, I highly doubt it 😂

  • @marca9955
    @marca9955 5 วันที่ผ่านมา

    Ingenious. Ingenious is the adjective.

  • @moorix6204
    @moorix6204 5 วันที่ผ่านมา

    Very Interesting Video! However, can you make a video where you explain how computers can calculate numbers like 2^25000? This is the max value my phone calculator can display. This number is so insanely large that you cant even wrap your head around! If you would take every single Atom in our universe and gave it each its own new universe with the same amount of atoms. Then give every atom from the new universe another universe and repeat this step around 850 times, you start to get close to 2^25000.

    • @matiasgarciacasas558
      @matiasgarciacasas558 5 วันที่ผ่านมา

      That is a really large number. But if you think about it, it's only got a few thousand digits, which is nothing for a computer with multiple gigabytes of RAM. A person could conceivably calculate that number by hand, it would take months or years, but it's pretty straight forward. A computer can do billions of operations in one second, it could calculate that in an instant. The fact that it's a power of 2 makes it extra easy, because in binary that's just a one followed by 25000 zeros.

  • @Zyugo
    @Zyugo 6 วันที่ผ่านมา

    Let's get this to 10K likes

  • @matthewwoods6972
    @matthewwoods6972 6 วันที่ผ่านมา

    It can be a fraction. 117/200. So n^1&117/200

    • @A_literal_cube
      @A_literal_cube 5 วันที่ผ่านมา

      log2(3) is an irrational number.

    • @matthewwoods6972
      @matthewwoods6972 5 วันที่ผ่านมา

      @A_literal_cube fair but you said .585 in my defense.

    • @A_literal_cube
      @A_literal_cube 5 วันที่ผ่านมา

      @@matthewwoods6972 Sorry, I didn't create this video, and he said "approximately 1.585" not exactly.

  • @supersmashbghemming6445
    @supersmashbghemming6445 6 วันที่ผ่านมา

    Great video! I think a cool idea for a similar video would be the brilliant deterministic k-select algorithm/median of medians! You'd do a great job explaining that I think

    • @PurpleMindCS
      @PurpleMindCS 6 วันที่ผ่านมา

      I was actually already considering making a video on that... how funny!

  • @souhardyamali7343
    @souhardyamali7343 6 วันที่ผ่านมา

    .

  • @BryndanMeyerholtTheRealDeal
    @BryndanMeyerholtTheRealDeal 6 วันที่ผ่านมา

    Wouldn't be more efficient if the numbers are in scientific notation, then adding the exponents while multiplying the mantissas, normalizing the number as needed?

    • @OneOfTheDips
      @OneOfTheDips 4 วันที่ผ่านมา

      That was my first thought tbh, I have no idea if it is practical in use

  • @bigblackbadger1
    @bigblackbadger1 6 วันที่ผ่านมา

    I didn't understand anything. I like it when people try to explain complicated things in a way that can be understood but this video just doesn't do a great job.

  • @Conqueror933
    @Conqueror933 6 วันที่ผ่านมา

    Is this 3Blue1Brown on his second account?

  • @nosharing-sf2mk
    @nosharing-sf2mk 6 วันที่ผ่านมา

    Why are programmers mega Nerds💀

  • @firasnizam
    @firasnizam 7 วันที่ผ่านมา

    nice video, thanks

    • @PurpleMindCS
      @PurpleMindCS 6 วันที่ผ่านมา

      Glad you enjoyed!

  • @Dicecaster38
    @Dicecaster38 7 วันที่ผ่านมา

    I thought this was CScript for a second.

  • @TmOnlineMapper
    @TmOnlineMapper 7 วันที่ผ่านมา

    As a little note as to why the naive approach is actually fast for smaller numbers. When we go back to the long multiplication, the idea is that you shift the top number and multiply it by the digit of the lower number you're currently doing. In binary all the digits you have are 0 and 1. Multiplying by 0 gives zero, so you have nothing to add. Multiplying by 1 just gives the same number. So essentially you just shift the top number over one by one and if the corresponding digit in the bottom number is a 1, you just add it to the total. And as a further optimization, you can just ignore the tailing digits of your sum as you go along, further reducing the work you need to do. It's still O(n^2), but very efficient, since the individual operations are extremely fast on CPUs.

  • @halvapidrid-b9h
    @halvapidrid-b9h 7 วันที่ผ่านมา

    FAST FURIES TRANSFORMATION!!!

  • @bucketslash11
    @bucketslash11 7 วันที่ผ่านมา

    big numbers you say: BB10,000^Graham's Number^TREE(3)

  • @sasson10
    @sasson10 7 วันที่ผ่านมา

    How tf did I only realize at 18:35 that I _wasn't_ watching a 3Blue1Brown video 💀

    • @PurpleMindCS
      @PurpleMindCS 7 วันที่ผ่านมา

      I'll take that as a compliment :)

  • @GetSomeFuker
    @GetSomeFuker 7 วันที่ผ่านมา

    1:59 PI and E reference π = 3.14159 e = 2.71828

  • @purple-sky-ro
    @purple-sky-ro 7 วันที่ผ่านมา

    Great video! I love the style of explaining. You should have much more subscribers :)

    • @PurpleMindCS
      @PurpleMindCS 7 วันที่ผ่านมา

      Thanks so much!

  • @PeterMoore-q5k
    @PeterMoore-q5k 7 วันที่ผ่านมา

    Just curious - did you compare performance to the CPUs own register multiplication instructions? (Realizing on a 64-bit CPU this would only work for up to 32-bit numbers). Assuming the CPU is better, could you not use these same algorithms but in base 2^32? In other words a 2048 bit number would have 64 "digits" for purposes of the algorithm, and you'd use CPU register multiplication to do the intermediate multiplication steps for the "digits". Maybe python might not be the right language to try something like that.

    • @PurpleMindCS
      @PurpleMindCS 7 วันที่ผ่านมา

      What you are suggesting is very close to how Python actually implements Karatsuba's algorithm for its built-in multiplication!

    • @PeterMoore-q5k
      @PeterMoore-q5k 7 วันที่ผ่านมา

      ​@@PurpleMindCS Aha! Very cool. Thanks much.

  • @brandyballoon
    @brandyballoon 7 วันที่ผ่านมา

    Nothing motivates people more than being told it can't be done.

  • @Andrew90046zero
    @Andrew90046zero 7 วันที่ผ่านมา

    I liked the video, but I was hoping you would be connecting the discussion to how multiplication is done in hardware, not software. From what I know, there is a lot of bit shifting involved.

  • @slouch186
    @slouch186 8 วันที่ผ่านมา

    im kinda surprised it's not some weird bit manipulation hack

  • @ScruffyMC
    @ScruffyMC 8 วันที่ผ่านมา

    I guess the switching that python does is also the method I'd go by for on-paper multiplication without machine help. Still it's interesting that optimizations in mathematics directly impact informatics even if the hardware is still the same. With bottlenecks in logic being "easier" removed than bottlenecks in physical limits for the machines that implement them, there is a certain point at which software updates bring better performance than switching out the hardware. Think smarter not harder i suppose

  • @snglvl
    @snglvl 8 วันที่ผ่านมา

    Anatoly Flex has been in existence for a long time.😂

  • @fiboot-oaken
    @fiboot-oaken 8 วันที่ผ่านมา

    This is a nice video, excpect the 'every 2min bait reminding to see the result in python'

  • @minebuilder1805
    @minebuilder1805 8 วันที่ผ่านมา

    One question though, how big is the multiplyer c in the runtime when not converting to the O format?

    • @PurpleMindCS
      @PurpleMindCS 8 วันที่ผ่านมา

      Well, it depends on how you're counting operations :)

    • @minebuilder1805
      @minebuilder1805 8 วันที่ผ่านมา

      @PurpleMindCS I'd count the multiplications in the algorythm as whole operations, addition and substraction as halve of an operation as they are way easier, I'd count the 2 additions to add those 3 calculations together too but not the multiplication to shift the numbers back. The example you have given in the video would have 6 operations then, 3 multiplications and 6 additions/substractions equal to 3 operations.

  • @nicemathproblems
    @nicemathproblems 8 วันที่ผ่านมา

    Awesome video! Well done 🥰

    • @PurpleMindCS
      @PurpleMindCS 8 วันที่ผ่านมา

      Thank you! Very much appreciated <3

  • @PlayTestGameTest4ever
    @PlayTestGameTest4ever 8 วันที่ผ่านมา

    Why not just compare each digit with the And logic gate? This way the result is the multiplication, all base 2. Numbers are represented in binary anyway

    • @PurpleMindCS
      @PurpleMindCS 8 วันที่ผ่านมา

      If you look at the code from 14:24, I believe I have implemented what you're suggesting here? Or am I missing something?

    • @PlayTestGameTest4ever
      @PlayTestGameTest4ever 8 วันที่ผ่านมา

      ​@@PurpleMindCS it was near my suggestion, but now i noticed im half the answer and i have the same problem as normal multiplication. Anyway, thanks, i loved it :3

  • @steelrazor4782
    @steelrazor4782 8 วันที่ผ่านมา

    19:28 holy voicecrack

  • @Gandi800
    @Gandi800 8 วันที่ผ่านมา

    This is some true 2Blue1Brown quality. Great job and I hope your subscriber count takes off!

    • @PurpleMindCS
      @PurpleMindCS 8 วันที่ผ่านมา

      Thank you so much!

  • @hs-fp4vp
    @hs-fp4vp 8 วันที่ผ่านมา

    when are you gonna create a code that lets me beat the odds at blackjack in Vegas?