{"page":"\u003clink rel=\"stylesheet\" href=\"https://lessonplanet.com/assets/packs/css/resources-c03aa079.css\" /\u003e\n\u003clink rel=\"stylesheet\" href=\"https://lessonplanet.com/assets/packs/css/lp_boclips_stylesheets-517835be.css\" media=\"all\" /\u003e\n\u003cdiv data-title='But what is a convolution?' data-url='/boclips/videos/639f27b19e646b190d593398' data-video-url='/boclips/videos/639f27b19e646b190d593398' id='bo_player_modal'\u003e\n\u003cdiv class='boclips-resource-page modal-dialog panel-container'\u003e\n\u003cdiv class='react-notifications-root'\u003e\u003c/div\u003e\n\u003cdiv class='rp-header'\u003e\n\u003cdiv class='rp-type'\u003e\n\u003ci aria-hidden='true' class='fai fa-regular fa-circle-play'\u003e\u003c/i\u003e\nVideo\n\u003c/div\u003e\n\u003ch1 class='rp-title' id='video-title'\u003e\nBut what is a convolution?\n\u003c/h1\u003e\n\u003cdiv class='rp-actions'\u003e\n\u003cdiv class='mr-1'\u003e\n\u003ca class=\"btn btn-success\" data-posthog-event=\"Signup: LP Signup Activity\" data-posthog-location=\"body_link_boclips\" data-remote=\"true\" href=\"/subscription/new\"\u003e\u003cspan\u003e\u003cspan\u003eGet Free Access\u003c/span\u003e\u003cspan class=\"\"\u003e for 10 Days\u003c/span\u003e\u003cspan\u003e!\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv class='rp-body'\u003e\n\u003cdiv class='rp-info'\u003e\n\u003cdiv aria-label='Hide resource details' class='rp-hide-info' role='button' tabindex='0'\u003e\u0026times;\u003c/div\u003e\n\u003ci aria-label='Expand resource details' class='rp-expand-info fai fa-solid fa-up-right-and-down-left-from-center' role='button' tabindex='0'\u003e\u003c/i\u003e\n\u003ci aria-label='Compress resource details' class='rp-compress-info fai fa-solid fa-down-left-and-up-right-to-center' role='button' tabindex='0'\u003e\u003c/i\u003e\n\u003cdiv class='rp-rating'\u003e\n\u003cspan class='resource-pool'\u003e\n\u003cspan class='pool-label'\u003ePublisher:\u003c/span\u003e\n\u003cspan class='pool-name'\u003e\n\u003cspan class='text'\u003e\u003ca data-publisher-id=\"30354888\" href=\"/search?publisher_ids%5B%5D=30354888\u0026amp;search_tab_id=1\"\u003e3Blue1Brown\u003c/a\u003e\u003c/span\u003e\n\u003c/span\u003e\n\u003c/span\u003e\n\u003c/div\u003e\n\u003cdiv class='rp-description'\u003e\n\u003cspan class='short-description'\u003eA small correction for the integer multiplication algorithm mentioned at the end. A “straightforward” application of FFT results in a runtime of O(N * log(n) log(log(n)) ). That log(log(n)) term is tiny, but it is only recently in 2019,...\u003c/span\u003e\n\u003cspan class='full-description hide'\u003eA small correction for the integer multiplication algorithm mentioned at the end. A “straightforward” application of FFT results in a runtime of O(N * log(n) log(log(n)) ). That log(log(n)) term is tiny, but it is only recently in 2019, Harvey and van der Hoeven found an algorithm that removed that log(log(n)) term.\u003cbr/\u003e\u003cbr/\u003eAnother small correction at 17:00. I describe O(N^2) as meaning \"the number of operations needed scales with N^2\". However, this is technically what Theta(N^2) would mean. O(N^2) would mean that the number of operations needed is at most constant times N^2, in particular, it includes algorithms whose runtimes don't actually have any N^2 term, but which are bounded by it. The distinction doesn't matter in this case, since there is an explicit N^2 term.\u003cbr/\u003eTimestamps\u003cbr/\u003e0:00 - Where do convolutions show up?\u003cbr/\u003e2:07 - Add two random variables\u003cbr/\u003e6:28 - A simple example\u003cbr/\u003e7:25 - Moving averages\u003cbr/\u003e8:32 - Image processing\u003cbr/\u003e13:42 - Measuring runtime\u003cbr/\u003e14:40 - Polynomial multiplication\u003cbr/\u003e18:10 - Speeding up with FFTs\u003cbr/\u003e21:22 - Concluding thoughts\u003c/span\u003e\n\u003c/div\u003e\n\u003cdiv class='action-container flex justify-between'\u003e\n\u003cbutton aria-expanded='false' aria-label='Read more description' class='rp-full-description' type='button'\u003e\n\u003ci class='fai fa-solid fa-align-left'\u003e\u003c/i\u003e\n\u003cspan id='read_more'\u003eRead More\u003c/span\u003e\n\u003c/button\u003e\n\u003cdiv class='rp-report'\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='resource-details-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='resource-details-heading'\u003eResource Details\u003c/h2\u003e\n\u003cdiv class='rp-resource-details clearfix'\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eCurator Rating\u003c/dt\u003e\n\u003cdd\u003e\u003cspan class=\"star-rating\" aria-label=\"5.0 out of 5 stars\" role=\"img\"\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003c/span\u003e\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt class=\"educator-rating-title\"\u003eEducator Rating\u003c/dt\u003e\u003cdd\u003e\u003cdiv class=\"educator-rating-details\" data-path=\"/educator_ratings/rrp_data?resourceable_id=130791\u0026amp;resourceable_type=Boclips%3A%3AVideoMetadata\"\u003e\u003cspan class=\"not-yet-rated\"\u003eNot yet Rated\u003c/span\u003e\u003c/div\u003e\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eMedia Length\u003c/dt\u003e\n\u003cdd\u003e22:34\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eGrade\u003c/dt\u003e\u003cdd title=\"Grade\"\u003e12th - Higher Ed\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eSubjects\u003c/dt\u003e\u003cdd\u003e\u003cspan\u003e\u003ca href=\"/search?grade_ids%5B%5D=258\u0026amp;grade_ids%5B%5D=259\u0026amp;search_tab_id=1\u0026amp;subject_ids%5B%5D=365220\"\u003eMath\u003c/a\u003e\u003c/span\u003e\u003c/dd\u003e\u003cdd class=\"text-muted\"\u003e\u003ci class=\"fa-solid fa-lock mr5\"\u003e\u003c/i\u003e1 more...\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eMedia Type\u003c/dt\u003e\u003cdd\u003e\u003cspan\u003e\u003ca href=\"/search?grade_ids%5B%5D=258\u0026amp;grade_ids%5B%5D=259\u0026amp;search_tab_id=2\u0026amp;type_ids%5B%5D=4543647\"\u003eInstructional Videos\u003c/a\u003e\u003c/span\u003e\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eSource:\u003c/dt\u003e\n\u003cdiv class='preview-source' data-animation='true' data-boundary='.rp-info' data-container='.rp-resource-details' data-html='false' data-title='3Blue1Brown is a channel about visualizing math, with content ranging from calculus to linear algebra, topology, neural networks and even how bitcoin works.' data-trigger='hover focus'\u003e\n\u003cspan\u003e3Blue1Brown\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-circle-info channel-tooltip-icon' id='channel-tooltip'\u003e\u003c/i\u003e\n\u003c/div\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eDate\u003c/dt\u003e\n\u003cdd\u003e2022\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003ci aria-hidden='true' class='fai fa-solid fa-language'\u003e\u003c/i\u003e\n\u003cdt\u003eLanguage\u003c/dt\u003e\u003cdd\u003eEnglish\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eAudiences\u003c/dt\u003e\u003cdd\u003e\u003cspan\u003e\u003ca href=\"/search?audience_ids%5B%5D=371079\u0026amp;grade_ids%5B%5D=258\u0026amp;grade_ids%5B%5D=259\u0026amp;search_tab_id=1\"\u003eFor Teacher Use\u003c/a\u003e\u003c/span\u003e\u003c/dd\u003e\u003cdd class=\"text-muted\"\u003e\u003ci class=\"fa-solid fa-lock mr5\"\u003e\u003c/i\u003e2 more...\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eUsage Permissions\u003c/dt\u003e\u003cdd\u003eFine Print: Educational Use\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='additional-materials-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='additional-materials-heading'\u003eAdditional Materials\u003c/h2\u003e\n\u003cdiv class='additional-material'\u003e\n\u003ci aria-hidden='true' class='fai fa-solid fa-lock'\u003e\u003c/i\u003e\n\u003ca class=\"text-muted\" title=\"Video Transcript\" data-html=\"true\" data-placement=\"bottom\" data-trigger=\"click\" data-content=\"\u003cdiv class=\u0026quot;text-center py-2\u0026quot;\u003e\u003ca class=\u0026quot;bold\u0026quot; href=\u0026quot;/auth/users/sign_in\u0026quot;\u003eSign in\u003c/a\u003e or \u003ca class=\u0026quot;bold text-danger\u0026quot; data-posthog-event=\u0026quot;Signup: LP Signup Activity\u0026quot; data-posthog-location=\u0026quot;body_link_boclips\u0026quot; data-remote=\u0026quot;true\u0026quot; href=\u0026quot;/subscription/new\u0026quot;\u003eJoin Now\u003c/a\u003e\u003c/div\u003e\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" href=\"/subscription/new\"\u003eVideo Transcript\u003c/a\u003e\n\u003c/div\u003e\n\u003cdiv class='additional-material'\u003e\n\u003ci aria-hidden='true' class='fai fa-solid fa-lock'\u003e\u003c/i\u003e\n\u003ca class=\"text-muted\" title=\"Video Preview\" data-html=\"true\" data-placement=\"bottom\" data-trigger=\"click\" data-content=\"\u003cdiv class=\u0026quot;text-center py-2\u0026quot;\u003e\u003ca class=\u0026quot;bold\u0026quot; href=\u0026quot;/auth/users/sign_in\u0026quot;\u003eSign in\u003c/a\u003e or \u003ca class=\u0026quot;bold text-danger\u0026quot; data-posthog-event=\u0026quot;Signup: LP Signup Activity\u0026quot; data-posthog-location=\u0026quot;body_link_boclips\u0026quot; data-remote=\u0026quot;true\u0026quot; href=\u0026quot;/subscription/new\u0026quot;\u003eJoin Now\u003c/a\u003e\u003c/div\u003e\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" href=\"/subscription/new\"\u003eVideo Preview\u003c/a\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='concepts-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='concepts-heading'\u003eConcepts\u003c/h2\u003e\n\u003cdiv class='clearfix'\u003e\n\u003cdiv class='details-list concepts' data-identifier='Boclips::VideoDecorator639f27b19e646b190d593398' data-type='concepts'\u003eproducts, data, arrays\u003c/div\u003e\n\u003cdiv class='concepts-toggle-buttons' data-identifier='Boclips::VideoDecorator639f27b19e646b190d593398'\u003e\n\u003cbutton aria-expanded='false' class='more btn-link' type='button'\u003e\n\u003cspan\u003eShow More\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-down ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003cbutton aria-expanded='true' class='less btn-link' style='display: none;' type='button'\u003e\n\u003cspan\u003eShow Less\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-up ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='additional-tags-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='additional-tags-heading'\u003eAdditional Tags\u003c/h2\u003e\n\u003cdiv class='clearfix'\u003e\n\u003cdiv class='details-list keyterms' data-identifier='Boclips::VideoDecorator639f27b19e646b190d593398' data-type='keyterms'\u003emathematics, three blue one brown, 3 blue 1 brown, 3b1b, 3brown1blue, 3 brown 1 blue, three brown one blue, red dye, sneaky backdoor, elementary school, pairwise products, fft algorithm, 1st place, blue dye, moving average, fast algorithm, convolve function, single pixel, image processing, offset values, smaller list, negative values, distinct pairs, algorithm, blue, average, function, product, system, pixel, picture, pair, bottom, table\u003c/div\u003e\n\u003cdiv class='keyterms-toggle-buttons' data-identifier='Boclips::VideoDecorator639f27b19e646b190d593398'\u003e\n\u003cbutton aria-expanded='false' class='more btn-link' type='button'\u003e\n\u003cspan\u003eShow More\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-down ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003cbutton aria-expanded='true' class='less btn-link' style='display: none;' type='button'\u003e\n\u003cspan\u003eShow Less\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-up ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='classroom-considerations-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='classroom-considerations-heading'\u003eClassroom Considerations\u003c/h2\u003e\n\u003cdiv class='classroom-considerations'\u003e\u003cdiv class='fai fa-solid fa-bell'\u003e\u003c/div\u003eBest For: Explaining a topic\u003c/div\u003e\u003cdiv class='classroom-considerations'\u003e\u003cdiv class='fai fa-solid fa-bell'\u003e\u003c/div\u003eVideo is ad-free\u003c/div\u003e \n\u003c/div\u003e\n\u003cdiv aria-labelledby='educator-ratings-heading' class='rp-info-section'\u003e\n\u003ch2 class='title sr-only' id='educator-ratings-heading'\u003eEducator Ratings\u003c/h2\u003e\n\u003cdiv id=\"educator-ratings-root\"\u003e\u003c/div\u003e\u003cdiv id=\"all-educator-ratings-root\"\u003e\u003c/div\u003e\u003cdiv id=\"educator-rating-form-root\"\u003e\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv class='rp-resource'\u003e\n\u003cdiv aria-label='Show resource details' class='rp-show-info' role='button' tabindex='0'\u003e\n\u003ci class='fai fa-solid fa-align-left'\u003e\u003c/i\u003e\nShow resource details\n\u003c/div\u003e\n\u003cdiv aria-label='Video player' class='player' id='player-wrapper' role='region'\u003e\n\u003cdiv class='relative container mx-auto' id='lp-boclips-visitor-thumbnail'\u003e\n\u003ca class=\"block\" data-html=\"true\" data-placement=\"bottom\" data-trigger=\"click\" data-content=\"\u003cdiv class=\u0026quot;text-center py-2\u0026quot;\u003e\u003ca class=\u0026quot;bold\u0026quot; href=\u0026quot;/auth/users/sign_in\u0026quot;\u003eSign in\u003c/a\u003e or \u003ca class=\u0026quot;bold text-danger\u0026quot; data-posthog-event=\u0026quot;Signup: LP Signup Activity\u0026quot; data-posthog-location=\u0026quot;body_link_boclips\u0026quot; data-remote=\u0026quot;true\u0026quot; href=\u0026quot;/subscription/new\u0026quot;\u003eJoin Now\u003c/a\u003e\u003c/div\u003e\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" aria-label=\"Play video: But what is a convolution?\" href=\"/subscription/new\"\u003e\u003cimg class=\"resource-img img-thumbnail img-responsive z-10 lp-boclips-thumbnail w-full h-full lozad\" alt=\"But what is a convolution?\" title=\"But what is a convolution?\" onError=\"handleImageNotLoadedError(this)\" data-default-image=\"https://static.lp.lexp.cloud/images/attachment_defaults/resource/large/missing.png\" data-src=\"https://cdnapisec.kaltura.com/p/1776261/thumbnail/entry_id/1_5xgxn6hc/width/250\" width=\"315\" height=\"220\" src=\"data:image/png;base64,R0lGODlhAQABAAD/ACwAAAAAAQABAAACADs\" /\u003e\n\u003cspan aria-hidden='true' class='flex justify-center items-center bg-white rounded-full w-16 h-16 absolute top-1/2 left-1/2 -mt-8 -ml-8 cursor-pointer z-0 border-2 border-primary drop-shadow-md lp-boclips-thumbnail-playBtn'\u003e\n\u003ci class='fa-solid fa-play text-primary text-3xl ml-1 drop-shadow-xl'\u003e\u003c/i\u003e\n\u003c/span\u003e\n\u003c/a\u003e\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n"}