Description

Gurpreet Singh (150259)
Introduction
When we are multiplying two 2-digit numbers, we can reduce a few cases into a simple formula, rather than actually calculating the multiplication.
Case Analysis for 2-digit Multiplication
For 2-digit multiplication of two numbers, we have two cases for which our reduction method will work. [?]
Case 1.1: When first digits are same and second digits add up to 10
Case 1.2: When second digits are same and first digits add up to 10
Case 1.1
Claim: Let the numbers be a = x:y and b = x:z, then multiplication result (c) will be x*(x+1):y*z
Proof.
a = x : y = 10x + y and b = x : z = 10x + z
c = a ∗ b
= (10x + y) ∗ (10x + z)
= 100×2 + 10x ∗ (y + z) + yz
= 100×2 + 10x ∗ 10 + yz ( ∵ y + z = 10)
= 100x ∗ (x + 1) + yz
= x ∗ (x + 1) : yz
Note
Example 1.2.1: Let the two numbers be 66 and 64 (See Figure 1)
6 ∗ (6 + 1) = 42
6 ∗ 4 = 24
66 ∗ 64 = 42 : 24 = 4224
66
X 64
264
Figure 1: Long multiplication method for example 1
Pseudocode:
Algorithm 1 Vedic Multiplication: Case 1.1
1: procedure Multiply(a,b) . Where a – first number, b – second number
x = a/10 y = a%10 z = b%10 α = x ∗ (x + 1) β = yz return 100 ∗ α + β
2: end procedure . Where / is integer division
Case 1.2
Claim: Let the numbers be a = x:y and b = x:z, then multiplication result (c) will be x*y+z:z*z
Proof.
a = x : z = 10x + z and b = y : z = 10y + z
c = a ∗ b
= (10x + z) ∗ (10y + z)
= 100xy + 10z ∗ (x + z) + z2
= 100xy + 10z ∗ 10 + z2 ( ∵ x + y = 10)
= 100(xy + z) + yz
= xy + z : z2
Note
Example 1.2.1: Let the two numbers be 34 and 74 (See Figure 2)
3 ∗ 7 + 4 = 25
4 ∗ 4 = 16
34 ∗ 74 = 25 : 16 = 2516
34
X 74
136
Figure 2: Long multiplication method for example
Pseudocode:
Algorithm 2 Vedic Multiplication: Case 1.2
1: procedure Multiply(a,b) . Where a – first number, b – second number
x = a/10 y = b/10 z = a%10 α = xy + z β = z2 return 100 ∗ α + β
2: end procedure . Where / is integer division
Do It Mentally
1. Differentiate the case
2. Compute the two different subparts of the answer, i.e. α, β
3. Generate the answer by appending α and β (add 0 before β if β < 10)
Generalization
For general case, assume the numbers are (x1x2…xn) and (y1y2…yn). We can divide this into a simpler case
(with n-1 digits) using the following two cases: [?]
Condition Case Answer
x1 = y1 Case ?? x1∗ (x1 + 1) : (x2x3…xn) ∗ (y2y3…yn)
xn = yn Case ?? (x1x2…xn−1) ∗ (y1y2…yn−1) + xn : x2n
For more details, visit this link