Ethiopian multiplication: Difference between revisions
(smalltalk) |
|||
Line 103: | Line 103: | ||
578 |
578 |
||
>>> </pre> |
>>> </pre> |
||
=={{header|Smalltalk}}== |
|||
{{works with|GNU Smalltalk}} |
|||
<lang smalltalk>Number extend [ |
|||
double [ ^ self * 2 ] |
|||
halve [ ^ self // 2 ] |
|||
ethiopianMultiplyBy: aNumber withTutor: tutor [ |
|||
|result multiplier multiplicand| |
|||
multiplier := self. |
|||
multiplicand := aNumber. |
|||
tutor ifTrue: [ ('ethiopian multiplication of %1 and %2' % |
|||
{ multiplier. multiplicand }) displayNl ]. |
|||
result := 0. |
|||
[ multiplier >= 1 ] |
|||
whileTrue: [ |
|||
multiplier even ifFalse: [ |
|||
result := result + multiplicand. |
|||
tutor ifTrue: [ |
|||
('%1, %2 kept' % { multiplier. multiplicand }) |
|||
displayNl |
|||
] |
|||
] |
|||
ifTrue: [ |
|||
tutor ifTrue: [ |
|||
('%1, %2 struck' % { multiplier. multiplicand }) |
|||
displayNl |
|||
] |
|||
]. |
|||
multiplier := multiplier halve. |
|||
multiplicand := multiplicand double. |
|||
]. |
|||
^result |
|||
] |
|||
ethiopianMultiplyBy: aNumber [ ^ self ethiopianMultiplyBy: aNumber withTutor: false ] |
|||
].</lang> |
|||
<lang smalltalk>(17 ethiopianMultiplyBy: 34 withTutor: true) displayNl.</lang> |
Revision as of 09:23, 23 July 2009
You are encouraged to solve this task according to the task description, using any language you may know.
A method of multiplying integers using only addition, doubling, and halving.
Method:
- Take two numbers to be multiplied and write them down at the top of two columns.
- In the left-hand column repeatedly halve the last number, discarding any remainders, and write the result below the last in the same column, until you write a value of 1.
- In the right-hand column repeatedly double the last number and write the result below. stop when you add a result in the same row as where the left hand column shows 1.
- Examine the table produced and discard any row where the value in the left column is even.
- Sum the values in the right-hand column that remain to produce the result of multiplying the original two numbers together
For example: 17 x 34
17 34
Halving the first column:
17 34 8 4 2 1
Doubling the second column:
17 34 8 68 4 136 2 272 1 544
Strike-out rows whose first cell is even:
17 34 8 -- 4 --- 2 --- 1 544
Sum the remaining numbers in the right-hand column:
17 34 8 -- 4 --- 2 --- 1 544 ==== 578
So 17 multiplied by 34, by the Ethiopian method is 578.
The task is to define three functions/methods/procedures/subroutines: to half an integer; to double an integer; and one to state if an integer is even. Use these functions to create a function that does Ethiopian multiplication.
References
- A Night Of Numbers - Go Forth And Multiply (Video)
- Ethiopian multiplication
- Russian Peasant Multiplication
Python
<lang python> tutor = True
def halve(x):
return x//2
def double(x):
return x*2
def even(x):
return not x % 2
def ethiopian(multiplier, multiplicand):
if tutor: print( "Ethiopian multiplication of %i and %i" % (multiplier, multiplicand) ) result = 0 while multiplier >= 1: if even(multiplier): if tutor: print( "%4i %6i STRUCK" % (multiplier, multiplicand) ) else: if tutor: print( "%4i %6i KEPT" % (multiplier, multiplicand) ) result += multiplicand multiplier = halve(multiplier) multiplicand = double(multiplicand) if tutor: print() return result
</lang>
Sample output
Python 3.1 (r31:73574, Jun 26 2009, 20:21:35) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ethiopian(17, 34) Ethiopian multiplication of 17 and 34 17 34 KEPT 8 68 STRUCK 4 136 STRUCK 2 272 STRUCK 1 544 KEPT 578 >>>
Smalltalk
<lang smalltalk>Number extend [
double [ ^ self * 2 ] halve [ ^ self // 2 ] ethiopianMultiplyBy: aNumber withTutor: tutor [ |result multiplier multiplicand| multiplier := self. multiplicand := aNumber. tutor ifTrue: [ ('ethiopian multiplication of %1 and %2' % { multiplier. multiplicand }) displayNl ]. result := 0. [ multiplier >= 1 ] whileTrue: [ multiplier even ifFalse: [ result := result + multiplicand. tutor ifTrue: [ ('%1, %2 kept' % { multiplier. multiplicand }) displayNl ] ] ifTrue: [ tutor ifTrue: [ ('%1, %2 struck' % { multiplier. multiplicand })
displayNl
] ]. multiplier := multiplier halve. multiplicand := multiplicand double. ]. ^result ] ethiopianMultiplyBy: aNumber [ ^ self ethiopianMultiplyBy: aNumber withTutor: false ]
].</lang>
<lang smalltalk>(17 ethiopianMultiplyBy: 34 withTutor: true) displayNl.</lang>