0

I started a new course in algorithms. The professor is trying to create a multiplication algorithm with other rules.

He divides the digits of the numbers we are trying to multiply into two groups for example. x = 3452 then a = 34, b = 52 (the same applies for y).

slide

According to him, the base operation would be:

If you're given two numbers that have the just one digit each. Then you just multiply them in one basic operation and return the result.

How would you compute ac, ad, bc and bd recursively if those are very simple operations?

rfkortekaas
  • 6,049
  • 2
  • 27
  • 34
Alesso
  • 1

1 Answers1

0

Here's how you would write the code (in python) for karatsuba (this assumes x and y always have the same number of even digits):

def numDigits(x):
  """
  Returns the number of digits in x
  """
  if x == 0:
    return 1

  digits = 0
  while x >= 1:
    x = int(x / 10)
    digits+=1
  return digits

def multiply(x, y):
  x_digits = numDigits(x)
  y_digits = numDigits(y)

  if x_digits != y_digits:
    return -1                    # not valid

  n = x_digits

  if n == 1:                     # checks if x (and y) are only 1 digit
    return x*y                   # single digit multiplication

  half_n = int(n / 2)

  a = int(x / (10**half_n))
  b = x - (a*(10**half_n))
  c = int(y / (10**half_n))
  d = y - (c*(10**half_n))

  ac = multiply(a, c)
  ad = multiply(a, d)
  bc = multiply(b, c)
  bd = multiply(b, d)

  return (10**n)*ac + (10**half_n)*(ad + bc) + bd



assert multiply(1, 2) == 2
assert multiply(10, 20) == 200
assert multiply(15, 21) == 315
assert multiply(1710, 2450) == 4189500
print("all pass!")

You can modify the code to allow x and y to have odd number of digits and to be of different lengths with a little more work.

Aziz Sonawalla
  • 2,482
  • 1
  • 5
  • 6
  • so to code `*` you need `/,**` that does not sound right... yes it might lead to correct answer but you are using higher operations to compute lower one. That is slow and also what if you want to implement `**` latter ? would it use `*` if yes (which is usually the case) it would not be possible to use your current implementation as it would cause stack overflow instantly. Karatsuba can be done with lower operations only easily ... – Spektre Jun 01 '20 at 05:50
  • The recursive part is incomplete but that is the problem with Python as you do not handle datatypes ... In most languages you need to have a mechanism that handle the changing bitwidth of arguments and return value. – Spektre Jun 01 '20 at 05:53
  • Multiplying and dividing by 10 to the power of something can be done using left-shift / right-shift. This takes the CPU O(n) time. – Aziz Sonawalla Jun 01 '20 at 13:34
  • bit shifts are power of 2 division/multiplication, for power of 10 its combination of bitshift and addition. However for bignums if internal representation is done properly its such operation just a pure copy of data (like inserting or removing character into/from string) instead of expensive log/exp pow approach which usually breaks the functionality of Karatsuba on bigger numbers in most rookie implementations ... – Spektre Jun 01 '20 at 20:15
  • @Spektre what improvements do you suggest then to the code above? – Aziz Sonawalla Jun 01 '20 at 20:32
  • the most important: removing `*,**,/` operations on numbers (on digits its using `*,/,+,-` more or less ok). However hence power of 10 is used that would be hard to do/understand in Python for rookies. I think much better (more didactic) would be to compute it on strings instead of on numbers ... Ideally multiplication should use only lower operation. The main problem is how to pass the variable bitwidth data into recursion effectively see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214). – Spektre Jun 02 '20 at 07:37