Russian Multiplication

Russian Multiplication

Say what.....!

What does this have to do with coding?

The Basics

• To mulitply two numbers together

• Essentially doubling one number and halving the other, with a twist

Basics - MODULUS

• Divide by a number and keep the remainder

• Python - %

• Other languages - MOD

• Example 14 % 4 = 2 (4 goes into 14, 3 times (12) with remainder 2 )

• Try it in Python

Multiple Choice

Try it - 35 % 5

in your head and in Python Print(35 %5)

• 5

• 3

• 0

• 1

Multiple Choice

Try it 77 % 6

• 5

• 7

• 2

• 8

Basics - INTEGER or FLOOR DIVISION

• Divide by a number and ignore the remainder

• Python - // (double forward slash)

• Other languages - DIV

• Example 14 // 4 = 3 (4 goes into 14 3 times (12) ignore the remainder)

• Try it in Python

Multiple Choice

Try it - 45 // 6

in Python and your head

• 4

• 5

• 6

• 7

Multiple Choice

Try it - 66 // 6

• 6

• 11

• 9

• 3

Step by Step

• We are going to multiply 23 x 47

• The correct answer is 1081

• REMINDER, one side is doubled the other side integer divide by 2 (halving)

We know the answer as a check

Work across each row, double one side and integer divide the other.

Any row where there is a remainder highlight, the other rows we don't need

Then add up the doubling numbers.. 23 + 46 + 92 + 184 + 736 = 1081

Your turn, an easier one

• Find the product of 17 * 5

• Answer we are looking for is

• 17*5 = 85

Multiple Choice

17 doubled is

• 17

• 52

• 34

• 6

Multiple Choice

5 // 2 is

• 2.5

• 3

• 2

• 1

Keep building up your table

• Russian peasants would do all of this in the head out in the field

• Me, I'd need a little more time

• You should have something looking like this

Why are we doing this??

We are going to create a flowchart of this process and then code it up in Python....

Flowcharts

Help with your algorithm and then help you with your code

(Main symbols shown, for exam don't need to remember the annotation one)

The predefined process symbol would typically have a full flowchart created

Image from Wikipedia

Russian Multiplication - Flowchart

• Should ALWAYS have a start and end

• All routes should eventually reach the end

• This is a first untested draft!! BEWARE

Multiple Choice

What does this symbol mean

• Terminator

• Decision

• Sub Process

• Process

• Input / output

Multiple Choice

What does this symbol mean

• Decsion

• Terminator

• Sub Process

• Process

• Input / output

Multiple Choice

What does this symbol mean

• Process

• Terminator

• Sub Process

• Decision

• Input / output

Multiple Choice

What does this symbol mean

• Process

• Terminator

• Input / output

• Decision

• Sub Process

Multiple Choice

What does this symbol mean

• Process

• Terminator

• Input / output

• Decision

• Sub Process

Trace Table

• To check our flowchart does what we expect we can create a trace table

• Trace table simply allows us to check each step

• Let's do one for our example of 17 * 5

Create a table with the following headings

• num1

• num2

• total

• num2 = 1?

• num2(MOD2) =1?

• Can use any tool ( excel, word, powerpoint or pen an paper!)

This is what mine looks like to start

• Work logically down the page

• Don't trust what I have done!

• Use that thing on top of your shoulders!!

• DON'T change slide until you have a thought in your head that what I've done is ok...

• REMINDER:- DON'T change slide until you have a thought in your head that what I've done is ok...

This is what mine looked like

• so I boobed!!

• can you work out what needs to change?

• total = 17, when it ought to total 85

Problem area

Discuss if this is the right error and if where I think it should go fixes the problem

Problem area

Or is this a better way to correct, why have I put a line through the zero?

Ask me why!

Discussion

• Original problem

• Algorithm

• Flow Chart

• Trace Table

• And we've not done some pseudocode 

• We've not coded it yet!

• All steps are not always needed

pseudocode ( describes the steps )

input first number

input second number

set total to zero

while num2 not equal to Zero

____if num2 is ODD (MOD2):

________add num1 to total

____num1 doubled

____num2 DIV 2 (integer divide)

print out total

(note I have had to use _ here to pad out)

Programming Constructs we have ued

• Sequence - Writing down in the order that they happen

• Selection - If this then do this or something else

• Iteration - Loops, Do or Repeat loops when you know how many times, While loops when testing for a condition

Now you can code it!

Next two slide are my first attempt and then a tidy up taking on board other concepts

Don't peep forward until you have had a go!!

No peeping!!

First Attempt

• num1 = input("What is the first number? ")

  num2 = input("What is the second number? ")

  total = 0

  
  

  while num2 != 0:

  ____if (num2%2 != 0):

  ________total= total+num1

  ____num1 = num1 * 2

  ____num2 = num2 //2

  
  

  print("the product is",(total))

• NOTE_ has been used for padding

Second Attempt

num1 = int(input("What is the first number? "))

num2 = int(input("What is the second number? "))

total = 0

# != 0 is not needed: num2 is True if it is not 0

while num2:

# no need to have brackets here

____if num2 % 2:

________total += num1 # shorthand for total = total + num1

____num1 *= 2 # shorthand for num1 = num1 * 2

____num2 / /= 2 # shorthand for num2 = num2 DIV 2

print("the product is", (total))

Discuss what you have learnt

• Programming constructs

• Sequence ( the order of the code )

• Selection ( if statements )

• Iteration ( loops)

• Flowcharts

• Psudocode

• It's OK to make mistakes! It's important to learn from them!!