Karatsuba's algorithm: split the digit sequences about the middle

Question

Here is a pseudocode of karatsuba's algorithm:

procedure karatsuba(num1, num2)
    if (num1 < 10) or (num2 < 10)
        return num1*num2

    /* calculates the size of the numbers */
    m = max(size_base10(num1), size_base10(num2))
    m2 = m/2

    /* split the digit sequences about the middle */
    high1, low1 = split_at(num1, m2)
    high2, low2 = split_at(num2, m2)

    /* 3 calls made to numbers approximately half the size */
    z0 = karatsuba(low1, low2)
    z1 = karatsuba((low1+high1), (low2+high2))
    z2 = karatsuba(high1, high2)

    return (z2*10^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0)

I didn't understand the step "split the digit sequences about the middle" especially after looking at the python implementation of Karatsuba's algorithm

Can you explain me, how exactly should we split digit sequence?

I don't understand where you're stuck. On each iteration, you break the numbers in the middle by textual length, base 10. For instance, the six-digit number `123456` becomes `123` and `456`. — Prune, Oct 03 '18 at 17:53
@Prune for example the first number is 12345678 and the second is 100. Then m2 = 4. According to the code we have to split two numbers at the 4-th digit. But in the comment it's mentioned, that we should split numbers in the middle. Which statement is correct? — DY92, Oct 03 '18 at 17:57

score 2 · Accepted Answer · answered Oct 03 '18 at 18:04

On each iteration, you break the numbers in the middle by textual length, base 10. For instance, the six-digit number 123456 becomes 123 and 456.

For the case of numbers of different lengths, note that the implementation works with the max of the two. Given 12345678 and 100, this effective pads the shorter number with zeros, to 00000100. Split into two 4-digit numbers each and continue.

Note that as an algorithm, this represents the simple binomial expansion:

(a + b) * (c + d) = ac + ad + bc + bd

In the 8-digit case, our numbers are

(1234*10^4 + 5678) * (0000*10^4 + 0100)

Does that help your understanding?

score 0 · Answer 2 · answered Oct 03 '18 at 18:17

I have written a very simple code for Karatsuba algorithm you can try this as well...

import timeit
import math
#loading math and time module

start_time = timeit.default_timer()
# creating a start time count down initilise to 0

def karatsuba_multiplication(nu1,nu2):          #defining a function
    num1 = str(nu1)                             #converting inteager into string because object of type inteager has no lenght
     num2 = str(nu2)
     x = len(num1)
     y = len(num2)

    if x == 1 or y == 1:
        print('----result----',nu1*nu2)
    else:
        if x >= y:
            n = x
        else:
            n = y
        if n % 2 == 0:
            n  = n
        else:
            n = n + 1
        a = int(num1[0:math.floor(x/2)])        #slicing the numbers for ltiplication
        b = int(num1[math.ceil(x/2):x])
        c = int(num2[0:math.floor(y/2)])
        d = int(num2[math.ceil(y/2):y])
        print('----reslut----',int((10**n)*(a*c) + (10**(n/2))*(a*d + b*c) + b*d))  
#formula of karatsuba

karatsuba_multiplication(9,1234)
karatsuba_multiplication(7,12345)
karatsuba_multiplication(213,1234)
karatsuba_multiplication(1234,5678)
karatsuba_multiplication(12345,987)
karatsuba_multiplication(314159265358979323846264338327950288419716939937510582097494  
4592,2718281828459045235360287471352662497757247093699959574966967627)

stop = timeit.default_timer()                   #countdown ends here
print('program time--',stop)

may be this code is lenghty but it is simple.

Karatsuba's algorithm: split the digit sequences about the middle

2 Answers2