How ancient Egyptians multiplied two numbers.

One method used by the ancient Egyptians to multiply two numbers was discovered in the Rhind Mathematical Papyri written in approximately 1550 B.C. and discovered in Thebes in 1650. It inspired how binary computers could perform such arithmetic as many had no multiply operator until the late 1970s.

The algorithm requires taking the first number and repeatedly integer dividing it by two until the number equals one, writing each new number in a list. The second number is then multiplied by two the same number of times with the results recorded in a second list. A number is removed from the list if the number in the first column is even. The sum of the remaining numbers in the second column is the result of the multiplication.

13 * 28 = 364

Assessment

These objectives get progressively harder. Attempt as much of the program as you can in the order presented below. Remember to use a comment to describe a subpprogram, selection or iteration.

Success Criteria

Input the two numbers

• Define a subprogram called input_numbers that takes no parameters.
  • Prompt the user to input the two numbers to be multiplied.
  • Return a list containing the two numbers.
• In the main program assign a list to be the numbers returned from calling the subprogram input_numbers.

4 marks

The output should now look like this:

Enter the first number: 13
Enter the second number: 28

Calculate the numbers in the first (blue) list

• Define a subprogram called mul that takes one parameter that is the list containing the two numbers to multiply.
  • Assign two variables, first_number and second_number to be the two numbers in the list.
  • Put first_number into a list called column1.
  • first_number is assigned to be itself integer divided by 2.
  • Append first_number to the column1 list.
  • Use a loop to repeat the two previous steps while first number is greater than 1.

5 marks

Calculate the numbers in the second (orange) list

Continuing code in the mul subprogram:

• Put second_number into a list called column2.
• second_number is assigned to be itself multiplied by 2.
• Append second_number to the column2 list.
• Use a loop to repeat the previous two steps until both lists contain the same number of numbers.

4 marks

Removing a row in the second (orange) list for all even numbers in the first (blue) list

Continuing code in the mul subprogram:

• Calculate if the first number in column1 is an even number.
• Remove the first number in list column2 if the number was an even number.
• Use a loop to repeat the previous two steps for all the numbers.

3 marks

Adding all the numbers in the second (orange) list and outputting the result

Continuing code in the mul subprogram:

• Sum all the numbers in list column2.
• Return the sum.
• In the main program call the subprogram mul with the list containing just the two numbers to multiply.
• Output the correct result to the calculation.

4 marks

The output should now look like this:

Enter the first number: 13
Enter the second number: 28
364

Good programming practices

• The subprograms and main program sections are signified with comments.
• The subprograms have a comment to describe their purpose.
• Each part of the algorithm in the mul subprogram has a comment to describe what it does.

3 marks

Maximum mark: 23

If you score less than 17 you need more practice at levels 1-6 before you continue to the next level.