Ethiopian multiplication: Difference between revisions
m (Formatting of header material) |
(fortran) |
||
Line 83: | Line 83: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|Fortran}}== |
|||
{{works with|Fortran|90 and later}} |
|||
<lang fortran>program EthiopicMult |
|||
implicit none |
|||
print *, ethiopic(17, 34, .true.) |
|||
contains |
|||
subroutine halve(v) |
|||
integer, intent(inout) :: v |
|||
v = int(v / 2) |
|||
end subroutine halve |
|||
subroutine doublit(v) |
|||
integer, intent(inout) :: v |
|||
v = v * 2 |
|||
end subroutine doublit |
|||
function iseven(x) |
|||
logical :: iseven |
|||
integer, intent(in) :: x |
|||
iseven = mod(x, 2) == 0 |
|||
end function iseven |
|||
function ethiopic(multiplier, multiplicand, tutorialized) result(r) |
|||
integer :: r |
|||
integer, intent(in) :: multiplier, multiplicand |
|||
logical, intent(in), optional :: tutorialized |
|||
integer :: plier, plicand |
|||
logical :: tutor |
|||
plier = multiplier |
|||
plicand = multiplicand |
|||
if ( .not. present(tutorialized) ) then |
|||
tutor = .false. |
|||
else |
|||
tutor = tutorialized |
|||
endif |
|||
r = 0 |
|||
if ( tutor ) write(*, '(A, I0, A, I0)') "ethiopian multiplication of ", plier, " by ", plicand |
|||
do while(plier >= 1) |
|||
if ( iseven(plier) ) then |
|||
if (tutor) write(*, '(I4, " ", I6, A)') plier, plicand, " struck" |
|||
else |
|||
if (tutor) write(*, '(I4, " ", I6, A)') plier, plicand, " kept" |
|||
r = r + plicand |
|||
endif |
|||
call halve(plier) |
|||
call doublit(plicand) |
|||
end do |
|||
end function ethiopic |
|||
end program EthiopicMult</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 11:07, 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:
- one to halve an integer,
- one 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>
Fortran
<lang fortran>program EthiopicMult
implicit none
print *, ethiopic(17, 34, .true.)
contains
subroutine halve(v) integer, intent(inout) :: v v = int(v / 2) end subroutine halve
subroutine doublit(v) integer, intent(inout) :: v v = v * 2 end subroutine doublit
function iseven(x) logical :: iseven integer, intent(in) :: x iseven = mod(x, 2) == 0 end function iseven
function ethiopic(multiplier, multiplicand, tutorialized) result(r) integer :: r integer, intent(in) :: multiplier, multiplicand logical, intent(in), optional :: tutorialized
integer :: plier, plicand logical :: tutor
plier = multiplier plicand = multiplicand
if ( .not. present(tutorialized) ) then tutor = .false. else tutor = tutorialized endif
r = 0
if ( tutor ) write(*, '(A, I0, A, I0)') "ethiopian multiplication of ", plier, " by ", plicand
do while(plier >= 1) if ( iseven(plier) ) then if (tutor) write(*, '(I4, " ", I6, A)') plier, plicand, " struck" else if (tutor) write(*, '(I4, " ", I6, A)') plier, plicand, " kept" r = r + plicand endif call halve(plier) call doublit(plicand) end do
end function ethiopic
end program EthiopicMult</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 {tutor false}} {
if {$tutor} {
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