Integer multiplication using divide-and-conquer method

Since elementary school, I have been taught a method to multiplicate two numbers: get a sub-product by multiplying each digit of one number with the other number. However, today I read chapter 5.5 – Integer Multiplication of the book Algorithm Design, and it first occurred to me that the process can be completed in less than O(n * n) time!

The method uses a divide-and-conquer spirit. Say two numbers x and y are n-digit base-k numbers. We now split two numbers by half:

x = x1 * k ^ (n/2) + x2

y = y1 * k ^ (n/2) + y2

Multiplying two numbers we get:

x * y = x1y1 * k ^ n + (x2y1 + x1y2) * k ^ (n/2) + x2y2

In which the numbers we need to get are x1y1, x1y2, x2y1 and x2y2

Right now the recurrence function is T(n) = 4 * T(n/2) + O(n) which would be O(n * n). This is no different from the old way, so we need to reduce the recursion call down to 3 instead of 4. Notice x2y1 + x1y2 = (x1 + x2) * (y1 + y2) – x1y1 – x2y2, and we can get (x1 + x2) * (y1 + y2) in T(n/2) time. Therefore, if we “circle around”, magically the recurrence function turns into T(n) = 3 * T(n/2) + O(n) = O(n ^ 1.59)!

The more I learn, the more I realize that a lot of stuff they taught us in school aren’t the best way to go, but I would say it’s much more difficult for kids to do recursions like computers than calculating sub-products.

14 thoughts on “Integer multiplication using divide-and-conquer method”

  1. Hana Tam: 網民是伴侶 Marie Claire (HK) Edition 網絡時代,瓦解不可能,為女性開闢更多生活模式的選項。在這個三八婦女節,《嘉兒》邀來中港台多位因網絡而開展第二人生的女性分享她的新生活;也探討網絡如何推進女性攀上國際大舞台。 Hana Tam@香

  2. JUVEDERM由透明質酸Hyaluronic Acid(一種天然多醣體)製造而成,並具有幼滑及高凝聚力的配方。透明質酸(HA)是皮膚組織的主要成份之一,能自然存在於人體肌膚內 JUVEDERM所用的透明質酸非由動物身體提取,可鎖住水份保濕皮膚,從而增加皮膚密度並改善質感 Juvederm 玻尿酸 加強優化面部輪廓,可被身體完全吸引,能自然地修飾面部輪廓 功效可長達24個月以上 JUVEDERM的特點: 效果立即可見 非永久性 非手術性 安全有效 效果自然 JUVEDERM獲歐盟(CE)及美國及藥物管理局(FDA)認證 首先及唯一獲得FDA認證在首次療程後能維持長達一年2-4功效 新世代專員Hylacross科技為產品帶來獨特的物理特質,包括凝聚力、支撐力及柔順度 這是一套由全球著名醫學美容醫生Dr. Maurício de Maio,以JUVÉDERM®系列透明質酸產品為基礎而研發的面部優化療程,藉著簡單程序便達致面部優化效果,不需進行手術,減低風險。

  3. Cardiff will sell Chile World Cup midfielder Gary Medel to Inter Milan for £10million.  Medel, 26, played 34 times last season but the club accepted it was unrealistic to keep him following relegation. Gary Medel set for Inter Milan in £10m move as Cardiff accept Championship reality 

  4. You are so cool! I do not suppose I’ve truly read through something like this before.So nice to find somebody with original thoughts on this subject matter.Seriously.. thanks for starting this up. This web site is something that is required on the web, someone with a bit of originality!

  5. Jordan 12 Gym Red 2018
    nike factory outlet
    nike factory outlet
    Nike Outlet
    air jordan 33
    cheap jerseys from china
    nfl jerseys
    air jordan 11 concord
    Jordan 12 Gym Red
    Jordan 12 Gym Red
    Yeezy Shoes
    Yeezy Shoes
    Yeezy Sneakers
    Yeezy Boost
    Yeezy Boost
    Yeezy Boost 350 V2 Blue Tint
    Yeezy 500 Utility Black
    Yeezy 500 Utility Black
    Nike Air VaporMax
    Salomon Speedcross 4
    Off White Jordan
    Vapor Max
    Nike React Element 87
    Nike Element 87
    Nike Vapormax Plus
    Nike Outlet Online–
    Nike Outlet Store Online Shopping
    Nike Outlet Store
    Cheap Nike NBA Jerseys
    Air Max 97
    Air Max 2017
    Jordan Shoes
    Jordan 11 Concord
    Cheap Yeezy Boost
    Wholesale Cheap NBA Jerseys
    Birkenstock UK
    NBA Jerseys
    Balenciaga UK
    Nike Air Max 270
    Adidas Yeezys
    Adidas Yeezy Shoes

Leave a Reply