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 http://www.jordan12gymred.us.com/
    nike factory outlet http://www.nikefactoryoutletstoreonline.com/
    nike factory outlet http://www.nikefactoryoutletstoreonline.us/
    Nike Outlet http://www.nikestores.us.com/
    air jordan 33 http://www.jordan33.us/
    cheap jerseys from china http://www.cheapjerseysfromchina.us/
    nfl jerseys http://www.customnfljerseys.us/
    air jordan 11 concord http://www.jordan11concord.us.com/
    Jordan 12 Gym Red http://www.jordan12gymred.us/
    Jordan 12 Gym Red http://www.redjordan12.us/
    Yeezys http://www.yeezy.com.co/
    Yeezy Shoes http://www.yeezys.us.com/
    Yeezy Shoes http://www.yeezysupply.us.com/
    Yeezy Sneakers http://www.yeezy-shoes.us.com/
    Yeezy Boost http://www.yeezy-boost350.com/
    Yeezy Boost http://www.yeezyboost350.us.com/
    Yeezy Boost 350 V2 Blue Tint http://www.yeezybluetint.com/
    Yeezy 500 Utility Black http://www.yeezy500utilityblack.com/
    Yeezy 500 Utility Black http://www.yeezy500utilityblack.us/
    Nike Air VaporMax http://www.vapor-max.org.uk/
    Salomon http://www.salomon-shoes.org.uk/
    Salomon http://www.salomons.me.uk/
    Salomon Speedcross 4 http://www.salomonspeedcross4.org.uk/
    Off White Jordan http://www.offwhitejordan1.com/
    Vapor Max http://www.nikevapormax.org.uk/
    Nike React Element 87 http://www.nikereactelement87.us.com/
    Nike Element 87 http://www.nikereactelement87.us/
    Nike Vapormax Plus http://www.nikeplus.us/
    Nike Outlet Online http://www.nike–outlet.us/
    Nike Outlet Store Online Shopping http://www.nikeoutletstoreonlineshopping.us/
    Nike Outlet Store http://www.nikeoutletonlineshopping.us/
    Cheap Nike NBA Jerseys http://www.nikenbajerseys.us/
    Air Max 97 http://www.nikeairmax.us/
    Air Max 2017 http://www.max2017.us/
    Jordan Shoes http://www.jordan-com.com/
    Jordan 11 Concord http://www.jordan11-concord.com/
    Cheap Yeezy Boost http://www.cs7boots1.com/
    Wholesale Cheap NBA Jerseys http://www.cheapnba-jerseys.us/
    Birkenstock UK http://www.birkenstocksandalsuk.me.uk/
    NBA Jerseys http://www.basketball-jersey.us/
    Balenciaga http://www.balenciaga.me.uk/
    Balenciaga UK http://www.balenciagauk.org.uk/
    Balenciaga http://www.balenciagatriples.org.uk/
    Balenciaga http://www.birkenstocks.me.uk/
    Balenciaga http://www.balenciagatrainers.org.uk/
    Nike Air Max 270 http://www.airmax270.org.uk/
    Adidas Yeezys http://www.adidasyeezyshoes.org.uk/
    Adidas Yeezy Shoes http://www.adidasyeezyshoes.org.uk/

Leave a Reply