I 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).
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.
