Egyptian multiplication
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.
Use this boilerplate code as a starting point:
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.
- `first_number` is assigned to be itself integer divided by 2.
- Put `first_number` into a list called `column1`.
- 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:
- `second_number` is assigned to be itself multiplied by 2.
- Put `second_number` into a list called `column2`.
- Use a loop to repeat the previous two steps until both lists contain the same number of numbers.
3 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: 22
If you score less than 17 you need more practice at levels 1-6 before you continue to the next level.
Help
Use these resources as a reference to help you meet the success criteria.
Programming guide:
Flowcharts:
Evaluate
Run the unit tests below to check that your program has met the success criteria.
Enter the first number: 82
Enter the second number: 91
7462
Enter the first number: 18
Enter the second number: 63
1134
