Differences

This shows you the differences between two versions of the page.

--- haas:spring2014:cprog:projects:nikhilam [2014/02/24 12:27] – created wedge
+++ haas:spring2014:cprog:projects:nikhilam [2014/02/24 14:15] (current) – [Nikhilam Multiplication] wedge
@@ Line 66: / Line 66: @@
   * 8 + **2** = 10
-So our answer is 7322
+So our answer is: 7322
-====Nikhilam Multiplication====
+The trick is to make sure we have enough digits to match up with the zeroes in the power of 10. If the number we are subtracting is smaller, we simply add leading zeroes (0 + 9 = 9):
-Squaring is essentially multiplying a number by itself-
-  * 5 squared (5<nowiki>^</nowiki>2) is 5*5 or 25
+<code>
-  * 8 squared (8<nowiki>^</nowiki>2) is 8*8 or 64
-While not outwardly a difficult procedure, the nature of multiplying multiple digit numbers in your head can quickly result in more steps (and more steps means more time, if doing things the traditional way).
+         1000
+          -  52   =>   - 052
+          -----        -----
+
+</code>
-Finding a shortcut through this process enables it to remain solidly within the realm of mental math, and makes for a good algorithm to practice implementing on the computer.
+Pretty neat, eh?
+====Nikhilam Multiplication====
+Multiplication using this principle is also rather straightforward, provided both numbers share a common power of 10 (as such, this is still considered a special case for multiplication-- something where you can identify a pattern and apply it to perform the operation in a more optimized fashion than applying the general method).
-This particular trick relies on a subset of the squares of double digit values (and appears to work on some triple digit values): those ending with a 5 (a five in the ones place).
+{{ :haas:spring2014:cprog:projects:nikhilam1.jpg |}}
-The operational scope of this trick will be just those two-digit values ending with 5:
+The procedure is basically as follows:
-  * 15
+  - To the right of the top number, put down its difference from the common power of 10 (100 in this case, which 97 falls 3 short of, hence the "**-3**"
-  * 25
+  - To the right of the bottom number, do the same: 94 is 6 short of 100, so a "**-6**" is put down
-  * 35
+  - Pick a number (top or bottom, doesn't matter) and add it to the other number's short value (97 + -6, or 94 + -3)
-  * 45
+  - That result goes down as the left hand side of our answer, and barring any carries or deficiencies in the right hand side, may well be set
-  * 55
+  - For the right hand side, multiply those two short values together (-6 * -3 = +18). THAT is the right hand side (a point to consider: because the common power is 100 in this case, the right hand side needs to be 2 digits)
-  * 65
+  - Concatenate the two together, and you get: **9118**
-  * 75
-  * 85
-  * 95
-====Squaring double digit values ending with 5====
+===Excess===
-The trick here is two-fold.
+And what about cases where the numbers are in excess of their common base? **Same thing**:
-One, we square the 5 to get 25. That is how our result will end (so bam! we now have our tens and ones place already solved)
+<code>
-Next, we take the value in the tens place, and multiply it by its increment:
+  +3     103 is 3 above 100
+  x 107  +7     107 is 7 above 100
+    === ===
++7 3*7     half cross add on the left, multiply excess numbers on right
+  21     make sure right hand value is 2 digits (100 = 10 to the 2nd power)
+
+</code>
-  * 1's increment (1+1) is 2, so 1*2
+===Mixed===
-  * 2's increment (2+1) is 3, so 2*3
+And how about mixed? One in excess, one short?
-  * 3's increment (3+1) is 4, so 3*4
-  * 4's increment (4+1) is 5, so 4*5
-  * ...
-  * 9's increment (9+1) is 10, so 9*10
-We take this result and append the 25 after it.
-For example:
 <code>
-* 15 = 1*(1+1) 5*5
-        = 1*2     5*5
+  +6      6 in excess of 100
-        = 2       25
+  x  97  -3      3 short of 100
-        = 225
+ ======  =====
++-3  +6*-3   same deal as always- half cross add, multiply differences
+  -18
 </code>
-and:
+Now, because the right hand value is negative, we have a "borrow" operation that needs to happen... we essentially have the following problem to consider:
 <code>
-* 75 = 7*(7+1) 5*5
-        = 7*8     5*5
-        = 56      25
-        = 5625
-</code>
+    100
+   -  1   - 18
+   ====   ====
+     82 <-- all by nine, last by 10
+          and voila! Our answer.
+</code>
 =====Program=====
-It is your task to write the program that will use the above method to compute the square of the requested value ending with a 5.
+It is your task to write the program that will use the above method to multiply two numbers together (you can make the assumption that the user will only ever be putting in values close to a common base).
 Your program should:
-  * prompt the user for the number (input)
+  * prompt the user for the two numbers (input)
-  * perform the task (process)
+  * determine the common power of 10
+  * perform the task (nikhilam multiplication process)
   * display the final value (output)
@@ Line 138: / Line 144: @@
 <cli>
 lab46:~/src/cprog/nikhilam$ ./nikhilam
-Enter value: 34
+Enter first number: 91
- x 34 = 5625
+Enter second number: 99
+ x 99 = 9009
 lab46:~/src/cprog/nikhilam$
 </cli>

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools