Ask Dr. Math FAQ: Russian Peasant Multiplication



the Russian peasant algorithm. You don't need multiplication facts to use the Russian peasant algorithm; you only need to double numbers, cut them in half, and add them up. Here are the rules:
  • Write each number at the head of a column.
  • Double the number in the first column, and halve the number in the second column.
       If the number in the second column is odd, divide it by two and drop the remainder.
  • If the number in the second column is even, cross out that entire row.
  • Keep doubling, halving, and crossing out until the number in the second column is 1.
  • Add up the remaining numbers in the first column. The total is the product of your original numbers.
If we multiply 8 * 9, we should get the same answer. Can we explain our answer the same way?
     16  4 
     32  2 
    + 64 
    72 
When we cut 9 in half, we dropped the remainder because 9 is an odd number. Because we have "lost" a one, the product of each row should be smaller from now on. Let's find the difference between the first row and the second row:
    8*9 - 16*4
    = 72 - 64
    = 8.
We can rewrite the subtraction as a sum:
    8 * 9
    = 16 * 4 + 8.
Because our product has decreased by 8, we have to add 8 back in again at the end. 
Read full article from Math Forum: Ask Dr. Math FAQ: Russian Peasant Multiplication

No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts