Determining the difficulty of Arithmetic Operations

kid math problemI am trying to write a program to test my arithmetic skills. The program should pose arithmetic problems involving the four basic operations – addition, subtraction, multiplication and division. When the testing session starts, the program should issue problems of less difficulty and the difficulty should be ramped up gradually. A score should be computed based on number of questions and the difficulty of questions. The hope is that if I keep using this program for a little time every day, I’ll be able to improve my abysmal arithmetic performance :)

Note that you will need to have Python installed to try out the script and the examples in this article. I believe that the code is simple enough to be understood with minimal or no understanding of the Python language. If any part of the article is not clear, feel free to point it out to me. Thank you.

Estimating difficulty

Let us take a look at the following problems.

Problem 1

5 +
3


Problem 2

99999 +
12345


Now, which problem is more difficult? It is quite obvious that Problem 2 is more difficult. But why? One answer would be – “because Problem 2 involves the addition of two large numbers”. Fine. Consider this now …

Problem 3

1000000 +
1000001


Is Problem 3 more difficult than Problem 2 because the numbers undergoing addition are bigger? The intuitive answer is “No”. But why? Because the time it takes to compute the result is lesser. Why? Because the number of operations performed during the course of solving Problem 3 are lesser than those of Problem 2? No.

Problem 3 is easier than Problem 2 because the nature of the operations performed in Problem 3. The operations there are simpler.

0 + 1,
0 + 0,
1 + 1


are arguably simpler operations than

9 + 5,
9 + 2,
4 + 9


I’ve attempted to capture the basic operations we perform while doing arithmetic and assign a level of difficulty to each. I’ve then emulated the algorithms we follow to compute solutions to such problems. By doing the following, it becomes possible to estimate the “difficulty” of an arithmetic problem (involving the basic operations).

math cartoon yesterday x

Operation difficulties


Addition

addition_difficulties = {
    'digit_zero' : 1,   # any digit added to zero
    'even_even'  : 2,   # sum of even digits
    'odd_odd'    : 2,   # sum of odd digits 
    'even_odd'   : 3,   # sum of even and odd digits
    'carry'      : 2    # difficulty of carry (for remembering and then adding)
}


Here is the function which computes the addition difficulty. It is a recursive function that can compute the addition difficulty for n numbers. It computes the sum and difficulty of the first two numbers and then inserts the sum at the head of the list of n numbers in place of the two numbers just summed. It then calls itself with the modified list.

def compute_addition_difficulty(*numbers):
    '''
    Generates a difficulty number and sum for given
    list of numbers for the addition operation
    *args - integers
    returns: (sum, difficulty)

    >>> compute_addition_difficulty(0, 0)
    (0, 1)

    >>> compute_addition_difficulty(0, 1)
    (1, 1)

    >>> compute_addition_difficulty(1, 1)
    (2, 2)

    >>> compute_addition_difficulty(1, 2)
    (3, 3)

    >>> compute_addition_difficulty(2, 2)
    (4, 2)

    >>> compute_addition_difficulty(19, 9)
    (28, 5)

    >>> compute_addition_difficulty(99999, 12345)
    (112344, 22)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 0, 0


    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    num1 = str(num1)
    num2 = str(num2)

    max_length = max([len(num1), len(num2)])
    num1 = num1.rjust(max_length, '0')
    num2 = num2.rjust(max_length, '0')

    difficulty = 0
    carry = 0
    r = reversed
    ad = addition_difficulties
    sum = []

    for index, (d1, d2) in enumerate( izip( r(num1), r(num2) ) ):
        d1 = int(d1)
        d2 = int(d2)

        d1_is_even = is_even(d1)
        d2_is_even = is_even(d2)
        
        if not d1 or not d2: difficulty += ad['digit_zero']
        elif d1_is_even and d2_is_even: difficulty += ad['even_even']
        elif not d1_is_even and not d2_is_even: difficulty += ad['odd_odd']
        elif d1_is_even != d2_is_even: difficulty += ad['even_odd']
    
        dsum = d1 + d2 + carry

        if dsum > 9:
            carry = 1
            difficulty += ad['carry']
        else:
            carry = 0
        
        sum.append( str(dsum % 10) )

    if carry:
        sum.append( str(carry) )

    sum.reverse()
    sum = ''.join(sum)
    sum = int (sum)

    numbers = [sum] + numbers[2:]

    sum, sub_difficulty = compute_addition_difficulty(*numbers)

    difficulty += sub_difficulty

    return sum, difficulty


Subtraction

subtraction_difficulties = {
    'digit_zero' : 1,    # difference of zero and any digit
    'same_digits': 1,    # difference of same values digits
    'even_even'  : 2,    # difference of even digits
    'odd_odd'    : 2,    # difference of odd digits
    'even_odd'   : 3,    # difference of even and odd digits
    'borrow'     : 2,    # doing a borrow
    'twodigit_digit' : 4 # difference of two-digit number and digit
}


The subtraction function is also recursive and operates similar to addition in that respect. Before looking at the subtraction algorithm, take a look at how “borrowing” is implemented. Let us say we are trying to perform the following,

200005 -
     6


After borrowing the number would be, 19999(1)5. We would then subtract 6 from 15 and proceed. The do_borrow() function captures this aspect of substraction.

def do_borrow(num, index):
    if index == len(num)-1: raise Exception('cannot perform borrow')

    num_borrows = 1
    next_digit = int(num[index+1])
    
    if next_digit > 0:
        num[index+1] = str(next_digit-1)

    else:
        num[index+1] = str(9)
        num_borrows += do_borrow(num, index+1)

    return num_borrows


This implementation is a bit confusing so check out this example (do_borrow() applied to the problem mentioned above).

>>> x = list('200005')
>>> x.reverse()
>>> x
['5', '0', '0', '0', '0', '2']
>>> do_borrow(x, 1)
4
>>> ''.join(x)
'509991'
>>> x.reverse()
>>> x
['1', '9', '9', '9', '0', '5']


Note that do_borrow returned 4, which indicates that the difficulty of performing this borrow operation is 4. Also note that do_borrow takes a list of digits in reversed order. It takes a list because the result is provided in-place (remember that Python strings are immutable). Now that you have seen how the borrowing works, all introduce the subtraction function.

def compute_subtraction_difficulty(*numbers):
    '''
    Generates a difficulty number and result for given
    list of numbers for the subtraction operation
    *args (tuple) - integers
    returns: (difference, difficulty)

    >>> compute_subtraction_difficulty(0,0)
    (0, 1)
    
    >>> compute_subtraction_difficulty(1,0)
    (1, 1)
    
    >>> compute_subtraction_difficulty(1,1)
    (0, 1)
    
    >>> compute_subtraction_difficulty(2,1)
    (1, 3)
    
    >>> compute_subtraction_difficulty(4,2)
    (2, 2)
    
    >>> compute_subtraction_difficulty(4,3)
    (1, 3)
    
    >>> compute_subtraction_difficulty(100,1)
    (99, 10)

    >>> compute_subtraction_difficulty(5000007,9)
    (4999998, 22)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 0, 0
    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    if num1 < num2: num1, num2 = num2, num1

    num1 = str(num1)
    num2 = str(num2)

    max_length = max([len(num1), len(num2)])
    num1 = list(num1.rjust(max_length, '0'))
    num2 = list(num2.rjust(max_length, '0'))

    difficulty = 0
    borrow = 0
    sd = subtraction_difficulties
    difference = []
    num1.reverse()
    num2.reverse()

    for index, (d1, d2) in enumerate( izip( num1, num2 ) ):
        d1 = int(d1)
        d2 = int(d2)

        d1_is_even = is_even(d1)
        d2_is_even = is_even(d2)

        if d1 > d2:
            if not d1 or not d2: difficulty += sd['digit_zero']
            elif d1_is_even and d2_is_even: difficulty += sd['even_even']
            elif not d1_is_even and not d1_is_even: difficulty += sd['odd_odd']
            elif d1_is_even != d2_is_even: difficulty += sd['even_odd']
            ddiff = d1 - d2

        elif d1 < d2:
            num_borrows = do_borrow(num1, index)
            difficulty += sd['borrow']*num_borrows
            ddiff = 10 + d1 - d2
            difficulty += sd['twodigit_digit']

        elif d1 == d2:
            difficulty += sd['same_digits']
            ddiff = 0

        difference.append( str(ddiff) )

    difference.reverse()
    difference = ''.join(difference)
    difference = int (difference)

    numbers = [difference] + numbers[2:]

    difference, sub_difficulty = compute_subtraction_difficulty(*numbers)

    difficulty += sub_difficulty

    return difference, difficulty


Multiplication

multiplication_difficulties = {
    'carry'  : 1,   # carry operation, summation difficulty is seperate
    'offset' : 1,
}


The basic operation of multiplying big numbers is one digit by one digit multiplication. I've tried to capture the difficulty of this operation as follows

def get_single_digit_multiplication_difficulty(d1, d2):
    '''
    Max value of multiplication of two digits is 81 (9*9).
    Difficulty of d1*d2 increases as the resulting value
    of the multiplication increases. thereby 9*9=81 is most difficult
    and 0*0 is least difficult.

    We will represent this difficult with value from 1-4 (inclusive)

    Note that the difficulty will be incremented by 1 for presence
    of odd digit in the operands (except for 1 and 5 because it is arguably
    easier to multiply)
    
    >>> get_single_digit_multiplication_difficulty(0, 1)
    (0, 1)
    >>> get_single_digit_multiplication_difficulty(1, 1)
    (1, 1)
    >>> get_single_digit_multiplication_difficulty(2, 5)
    (10, 1)
    >>> get_single_digit_multiplication_difficulty(2, 7)
    (14, 2)
    >>> get_single_digit_multiplication_difficulty(2, 6)
    (12, 1)
    >>> get_single_digit_multiplication_difficulty(8, 9)
    (72, 5)
    >>> get_single_digit_multiplication_difficulty(8, 8)
    (64, 4)
    '''

    if not d1 or not d2: return 0, 1 

    res = d1 * d2
    difficulty = math.ceil((4/81.) * res)

    # odd numbers are harder to multiply except 1 and 5
    if d1 not in [1,5] and d2 not in [1,5] and (is_odd(d1) or is_odd(d2)):
        difficulty += 1

    return res, int(difficulty)


At the next level, the operation would be multiplying a multi-digit number by a single digit, which I call simple multiplication. Over here I take into account the difficulty of carry. I hope the following code is self explanatory.

def compute_simple_multiplication_difficulty(num, digit):
    '''
    >>> compute_simple_multiplication_difficulty(1, 0)
    (0, 1)
    >>> compute_simple_multiplication_difficulty(1, 1)
    (1, 1)
    >>> compute_simple_multiplication_difficulty(2, 1)
    (2, 1)
    >>> compute_simple_multiplication_difficulty(10, 1)
    (10, 2)
    >>> compute_simple_multiplication_difficulty(15, 1)
    (15, 2)
    >>> compute_simple_multiplication_difficulty(15, 5)
    (75, 7)
    >>> compute_simple_multiplication_difficulty(999, 7)
    (6993, 25)
    '''
    num = str(num)

    result = []
    md = multiplication_difficulties
    carry = 0
    difficulty = 0

    for index, d in enumerate(reversed(num)):
        d = int(d)
        res, s_diff = get_single_digit_multiplication_difficulty(d, digit)
        difficulty += s_diff

        if (carry):
            res, carry_sum_difficulty = compute_addition_difficulty(res, carry)
            difficulty += carry_sum_difficulty + md['carry']

        carry = res/10
        result_digit = int(str(res)[-1:])
        result.append( str(result_digit) )

    if carry:
        result.append( str(carry) )

    result.reverse()
    result = ''.join(result)
    result = int(result)

    return result, difficulty


Simple multiplication is a basic operation of complex multiplication (multi-digit multiplied by multi-digit). Let us see an example of "complex multiplication" which the multiplication code follows.

    345 x
    123
  -----
   1035
   690x  # result is "offset" or multiplied by 10
  345xx  # result if "offset" or multiplied by 100
  -----
  42435  # result of summation of above numbers
  -----


The first part of the multiplication is to perform simple multiplications - 345x3, 345x2, 345x1 and to offset the numbers accordingly. The second part of the operation is to sum the numbers. I used the addition algorithm to achieve the second part. Check out the multiplication function.

def compute_multiplication_difficulty(*numbers):
    '''
    Generates a difficulty number and result for given
    list of numbers for the multiplication operation
    *args (tuple) - integers
    returns: (product, difficulty)

    >>> compute_multiplication_difficulty(0,0)
    (0, 1)
    >>> compute_multiplication_difficulty(1,0)
    (0, 1)
    >>> compute_multiplication_difficulty(1,1)
    (1, 1)
    >>> compute_multiplication_difficulty(2,1)
    (2, 1)
    >>> compute_multiplication_difficulty(5,1)
    (5, 1)
    >>> compute_multiplication_difficulty(5,2)
    (10, 1)
    >>> compute_multiplication_difficulty(17,2)
    (34, 7)
    >>> compute_multiplication_difficulty(17,29)
    (493, 20)
    >>> compute_multiplication_difficulty(17,29,3)
    (1479, 31)
    >>> compute_multiplication_difficulty(1776,29,3)
    (154512, 77)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 1, 0
    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    if num1 < num2: num1, num2 = num2, num1

    num2 = str(num2)

    difficulty = 0
    borrow = 0
    md = multiplication_difficulties
    m_numbers = []

    for index, d in enumerate(reversed(num2)):

        d = int(d)
        
        m_number, m_diff = compute_simple_multiplication_difficulty(num1, d)
        difficulty += m_diff

        if index:
            m_number = int(m_number * math.pow(10, index))
            difficulty += md['offset']
        
        m_numbers.append(m_number)
    
    m_numbers_sum, m_numbers_diff = compute_addition_difficulty(*m_numbers)
    difficulty += m_numbers_diff

    numbers = [m_numbers_sum] + numbers[2:]
    product, m_diff = compute_multiplication_difficulty(*numbers)

    difficulty += m_diff

    return product, difficulty


Division

division_difficulties = {
    # long division
    'use_digit'       : 1,  # brinding down digit from dividend
    'multiple_lookup' : 1,  # looking up precomputed multiple of divisor
    'quotient_update' : 1,  # updating quotient with digit or period
}


Implementing long division posed a problem because my understanding of the mechanics behind the long division algorithm was minimal if not inexistent. I spent some time trying to "reverse-engineer" it. I came across "Egyptian Division" which made things clearer. With a little help, I managed to implement the following division algorithm. Please let me know, if you come up with a better approach.

def compute_division_difficulty(dividend, divisor, precision):
    '''
    Generates a difficulty number, quotient and remainder
    for dividend / divisor
    @precision (int) -- max required number of digits after decimal point in quotient
    returns: (quotient, remainder, difficulty)

    >>> compute_division_difficulty(54, 5, 0)
    (10.0, 4, 6)
    >>> compute_division_difficulty(50, 5, 0)
    (10.0, 0, 6)
    >>> compute_division_difficulty(575, 6, 0)
    (95.0, 5, 60)
    >>> compute_division_difficulty(575, 6, 1)
    (95.829999999999998, 20, 112)
    >>> compute_division_difficulty(6, 9, 1)
    (0.66000000000000003, 60, 50)
    >>> compute_division_difficulty(410, 2, 1)
    (205.0, 0, 54)
    '''

    if not divisor: raise Exception('Division by Zero')
    if not dividend: return 0, 0, 1

    dividend = str(dividend)

    divisor  = str(divisor)

    difficulty = 0
    previous_multiples_difficulty = 0
    precision_reached = 0
    decimal_point_used = 0
    dd = division_difficulties
    num = []
    quotient = []

    num = dividend[0]
    difficulty += dd['use_digit']
    index = 0

    while 1:
        q_digit = int(num) / int(divisor)

        multiple, multiple_difficulty = compute_multiples_difficulty(int(divisor), q_digit)
        difficulty += int(math.fabs(multiple_difficulty - previous_multiples_difficulty))
        if previous_multiples_difficulty: difficulty += dd['multiple_lookup']
        previous_multiples_difficulty = max(multiple_difficulty, previous_multiples_difficulty)

        quotient.append( str(q_digit) )
        difficulty += dd['quotient_update']

        if decimal_point_used:
            precision_reached += 1

        num, sub_difficulty = compute_subtraction_difficulty(int(num), multiple)
        difficulty += sub_difficulty
        num = str(num)
        
        index += 1

        if index == len(dividend):
            if precision == 0: break
            quotient.append('.')
            difficulty += dd['quotient_update']
            decimal_point_used = 1

        if not decimal_point_used:
            num += dividend[index]
        else:
            num += '0'
        
        difficulty += dd['use_digit']

        if (len(num) == 1 and not int(num)) or precision_reached >= precision + 1:
            break
        
    remainder = int(num)
    quotient = float(''.join(quotient))

    return quotient, remainder, difficulty


You must've noticed the usage of compute_multiples_difficulty(). In long division, at every step, you will try to find the largest multiple of the divisor less than or equal to the number in hand to proceed further. During the process of division, if you've computed the 5th (say) multiple of the divisor with difficulty N. The computation of 6th multiple at a later point in the division is difficulty(lookup of 5th multiple) + difficulty(6-5th multiple).

Results

#Problem 1
>>> compute_addition_difficulty(5, 3)
(8, 2)

#Problem 2
>>> compute_addition_difficulty(99999, 12345)
(112344, 22)

#Problem 3
>>> compute_addition_difficulty(1000000, 1000001)
(2000001, 8)


Problem 1: 2
Problem 2: 22
Problem 3: 8

The End

I wish I could have written a more detailed explanation instead of sprinkling this article with code. Time however prevents me from doing so :( . It is some relief that Python is a wonderful language for readability and the code samples above are pretty close to pseudo-code.

I will post back when I complete the program to generate arithmetic problems by order of difficulty. Until then, Adios amigos. Almost forgot! Here is the code.

meaning of life math cartoon

No Trackbacks

5 Comments

  1. bg

    omg! i think u cud have figured the addition/multiplication of ‘large’ ‘difficult’ numbers manually by the time u wrote the code! but good one indeed. I have a feeling the code will be a lot simpler if you used the tricks of Vedic Math

    Posted July 30, 2008 at 4:18 pm | Permalink
  2. Hehe! I could not have used Vedic math here because I am trying to reproduce the mental process that most people go through when computing these kind of problems.

    Posted July 30, 2008 at 6:52 pm | Permalink
  3. brilliant work prashanth, algorithms are simply superb, didnt got time to look into the details
    addition_difficulties = {
    ‘digit_zero’ : 1, # any digit added to zero
    ‘even_even’ : 2, # sum of even digits
    ‘odd_odd’ : 2, # sum of odd digits
    ‘even_odd’ : 3, # sum of even and odd digits
    ‘carry’ : 2 # difficulty of carry (for remembering and then adding)
    }
    i don’t c a difference for a no. is either odd or even, i c complexity increases as the no.s moves on the scale of 0-9. adding 7+6(odd_even) is equally difficult as adding 7+5(odd_odd) and even equally difficult as 8+6(even_even) i feel the patterns that we remember like 6+4, 5+5, 7+3 (i think we love 10) make adding some no.s easy, another example i remember is 8+4. I remember as a child i don’t know these patterns, so not taking any patterns into consideration for me its only the bigger the no.s more the complexity.
    i fear if there is any technique thts helping all the humans make the odd_odd or even_even additions easier which am missing all these years :(

    Posted August 1, 2008 at 12:52 pm | Permalink
  4. Karthik, the odd-even combinations I came up with for assessing difficulty may be subjective. We memorize a lot of simple operations thereby making them lookups. I have not found a convincing way of capturing this aspect.

    Posted August 4, 2008 at 9:14 pm | Permalink
  5. James

    Hi, I found your blog on this new directory of WordPress Blogs at blackhatbootcamp.com/listofwordpressblogs. I dont know how your blog came up, must have been a typo, i duno. Anyways, I just clicked it and here I am. Your blog looks good. Have a nice day. James.

    Posted September 19, 2008 at 10:50 am | Permalink