Ethiopian multiplication: Difference between revisions
(C) |
(→Tcl: Added implementation) |
||
Line 174: | Line 174: | ||
<lang smalltalk>(17 ethiopianMultiplyBy: 34 withTutor: true) displayNl.</lang> |
<lang smalltalk>(17 ethiopianMultiplyBy: 34 withTutor: true) displayNl.</lang> |
||
=={{header|Tcl}}== |
|||
<lang tcl>proc tcl::mathfunc::double n {expr {$n * 2}} |
|||
proc tcl::mathfunc::halve n {expr {$n / 2}} |
|||
proc tcl::mathfunc::even n {expr {($n & 1) == 0}} |
|||
proc tcl::mathfunc::mult {a b} {expr { |
|||
$a < 1 ? 0 : |
|||
even($a) ? [logmult STRUCK] + mult(halve($a), double($b)) |
|||
: [logmult KEPT] + mult(halve($a), double($b)) + $b |
|||
}} |
|||
# Wrapper to set up the logging |
|||
proc ethiopianMultiply {a b {noisy false}} { |
|||
if {$noisy} { |
|||
set wa [expr {[string length $a]+1}] |
|||
set wb [expr {$wa+[string length $b]-1}] |
|||
puts stderr "Ethiopian multiplication of $a and $b" |
|||
interp alias {} logmult {} apply {{wa wb msg} { |
|||
upvar 1 a a b b |
|||
puts stderr [format "%*d %*d %s" $wa $a $wb $b $msg] |
|||
return 0 |
|||
}} $wa $wb |
|||
} else { |
|||
proc logmult args {return 0} |
|||
} |
|||
return [expr {mult($a,$b)}] |
|||
}</lang> |
|||
Demo code: |
|||
<lang tcl>puts "17 * 34 = [ethiopianMultiply 17 34 true]"</lang> |
|||
Output: |
|||
<pre>Ethiopian multiplication of 17 and 34 |
|||
17 34 KEPT |
|||
8 68 STRUCK |
|||
4 136 STRUCK |
|||
2 272 STRUCK |
|||
1 544 KEPT |
|||
17 * 34 = 578</pre> |
Revision as of 09:37, 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
C
<lang c>#include <stdio.h>
- include <stdbool.h>
void halve(int *x) { *x >>= 1; } void doublit(int *x) { *x <<= 1; } bool iseven(const int x) { return (x%2) == 0; }
int ethiopian(int plier, int plicand, const bool tutor) {
int result=0;
if (tutor) printf("ethiopian multiplication of %d by %d\n", plier, plicand); while(plier >= 1) { if ( iseven(plier) ) { if (tutor) printf("%4d %6d struck\n", plier, plicand); } else { if (tutor) printf("%4d %6d kept\n", plier, plicand); result += plicand; } halve(&plier); doublit(&plicand); } return result;
}
int main() {
printf("%d\n", ethiopian(17, 34, true)); return 0;
}</lang>
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>
Tcl
<lang tcl>proc tcl::mathfunc::double n {expr {$n * 2}} proc tcl::mathfunc::halve n {expr {$n / 2}} proc tcl::mathfunc::even n {expr {($n & 1) == 0}} proc tcl::mathfunc::mult {a b} {expr {
$a < 1 ? 0 : even($a) ? [logmult STRUCK] + mult(halve($a), double($b))
: [logmult KEPT] + mult(halve($a), double($b)) + $b }}
- Wrapper to set up the logging
proc ethiopianMultiply {a b {noisy false}} {
if {$noisy} {
set wa [expr {[string length $a]+1}] set wb [expr {$wa+[string length $b]-1}] puts stderr "Ethiopian multiplication of $a and $b" interp alias {} logmult {} apply {{wa wb msg} { upvar 1 a a b b puts stderr [format "%*d %*d %s" $wa $a $wb $b $msg] return 0 }} $wa $wb
} else {
proc logmult args {return 0}
} return [expr {mult($a,$b)}]
}</lang> Demo code: <lang tcl>puts "17 * 34 = [ethiopianMultiply 17 34 true]"</lang> Output:
Ethiopian multiplication of 17 and 34 17 34 KEPT 8 68 STRUCK 4 136 STRUCK 2 272 STRUCK 1 544 KEPT 17 * 34 = 578