Ethiopian multiplication
From Rosetta Code
Ethiopian multiplication is a programming task. Visitors like you are encouraged to solve it according to the task description, using any language they may happen to 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 × 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 68
4 136
2 272
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 named 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
- Programming Praxis: Russian Peasant Multiplication
[edit] Ada
package Ethiopian is
function Multiply(Left, Right : Integer) return Integer;
end Ethiopian;
package body Ethiopian is
function Is_Even(Item : Integer) return Boolean is
begin
return Item mod 2 = 0;
end Is_Even;
function Double(Item : Integer) return Integer is
begin
return Item * 2;
end Double;
function Half(Item : Integer) return Integer is
begin
return Item / 2;
end Half;
function Multiply(Left, Right : Integer) return Integer is
Temp : Integer := 0;
Plier : Integer := Left;
Plicand : Integer := Right;
begin
while Plier >= 1 loop
if not Is_Even(Plier) then
Temp := Temp + Plicand;
end if;
Plier := Half(Plier);
Plicand := Double(Plicand);
end loop;
return Temp;
end Multiply;
end Ethiopian;
with Ethiopian; use Ethiopian;
with Ada.Text_Io; use Ada.Text_Io;
procedure Ethiopian_Test is
First : Integer := 17;
Second : Integer := 34;
begin
Put_Line(Integer'Image(First) & " times " &
Integer'Image(Second) & " = " &
Integer'Image(Multiply(First, Second)));
end Ethiopian_Test;
[edit] ALGOL 68
Translation of: C
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
PROC halve = (REF INT x)VOID: x := ABS(BIN x SHR 1);
PROC doublit = (REF INT x)VOID: x := ABS(BIN x SHL 1);
PROC iseven = (#CONST# INT x)BOOL: NOT ODD x;
PROC ethiopian = (INT in plier,
INT in plicand, #CONST# BOOL tutor)INT:
(
INT plier := in plier, plicand := in plicand;
INT result:=0;
IF tutor THEN
printf(($"ethiopian multiplication of "g(0)," by "g(0)l$, plier, plicand)) FI;
WHILE plier >= 1 DO
IF iseven(plier) THEN
IF tutor THEN printf(($" "4d," "6d" struck"l$, plier, plicand)) FI
ELSE
IF tutor THEN printf(($" "4d," "6d" kept"l$, plier, plicand)) FI;
result +:= plicand
FI;
halve(plier); doublit(plicand)
OD;
result
);
main:
(
printf(($g(0)l$, ethiopian(17, 34, TRUE)))
)
Output:
ethiopian multiplication of 17 by 34 0017 000034 kept 0008 000068 struck 0004 000136 struck 0002 000272 struck 0001 000544 kept 578
[edit] AutoHotkey
MsgBox % Ethiopian(17, 34) "`n" Ethiopian2(17, 34)
; func definitions:
half( x ) {
return x >> 1
}
double( x ) {
return x << 1
}
isEven( x ) {
return x & 1 == 0
}
Ethiopian( a, b ) {
r := 0
While (a >= 1) {
if !isEven(a)
r += b
a := half(a)
b := double(b)
}
return r
}
; or a recursive function:
Ethiopian2( a, b, r = 0 ) { ;omit r param on initial call
return a==1 ? r+b : Ethiopian2( half(a), double(b), !isEven(a) ? r+b : r )
}
[edit] AWK
Implemented without the tutor.
function halve(x)
{
return int(x/2)
}
function double(x)
{
return x*2
}
function iseven(x)
{
return x%2 == 0
}
function ethiopian(plier, plicand)
{
r = 0
while(plier >= 1) {
if ( !iseven(plier) ) {
r += plicand
}
plier = halve(plier)
plicand = double(plicand)
}
return r
}
BEGIN {
print ethiopian(17, 34)
}
[edit] BASIC
Works with: QBasic
While building the table, it's easier to simply not print unused values, rather than have to go back and strike them out afterward. (Both that and the actual adding happen in the "IF NOT (isEven(x))" block.)
DECLARE FUNCTION half% (a AS INTEGER)
DECLARE FUNCTION doub% (a AS INTEGER)
DECLARE FUNCTION isEven% (a AS INTEGER)
DIM x AS INTEGER, y AS INTEGER, outP AS INTEGER
x = 17
y = 34
DO
PRINT x,
IF NOT (isEven(x)) THEN
outP = outP + y
PRINT y
ELSE
END IF
IF x < 2 THEN EXIT DO
x = half(x)
y = doub(y)
LOOP
PRINT " =", outP
FUNCTION doub% (a AS INTEGER)
doub% = a * 2
END FUNCTION
FUNCTION half% (a AS INTEGER)
half% = a \ 2
END FUNCTION
FUNCTION isEven% (a AS INTEGER)
isEven% = (a MOD 2) - 1
END FUNCTION
Output:
17 34 8 4 2 1 544 = 578
[edit] 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 & 1) == 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;
}
[edit] C++
Using C++ templates, these kind of tasks can be implemented as meta-programs. The program runs at compile time, and the result is statically saved into regularly compiled code. Here is such an implementation without tutor, since there is no mechanism in C++ to output messages during program compilation.
template<int N>
struct Half
{
enum { Result = N >> 1 };
};
template<int N>
struct Double
{
enum { Result = N << 1 };
};
template<int N>
struct IsEven
{
static const bool Result = (N & 1) == 0;
};
template<int Multiplier, int Multiplicand>
struct EthiopianMultiplication
{
template<bool Cond, int Plier, int RunningTotal>
struct AddIfNot
{
enum { Result = Plier + RunningTotal };
};
template<int Plier, int RunningTotal>
struct AddIfNot <true, Plier, RunningTotal>
{
enum { Result = RunningTotal };
};
template<int Plier, int Plicand, int RunningTotal>
struct Loop
{
enum { Result = Loop<Half<Plier>::Result, Double<Plicand>::Result,
AddIfNot<IsEven<Plier>::Result, Plicand, RunningTotal >::Result >::Result };
};
template<int Plicand, int RunningTotal>
struct Loop <0, Plicand, RunningTotal>
{
enum { Result = RunningTotal };
};
enum { Result = Loop<Multiplier, Multiplicand, 0>::Result };
};
#include <iostream>
int main(int, char **)
{
std::cout << EthiopianMultiplication<17, 54>::Result << std::endl;
return 0;
}
[edit] C#
static void Main(string[] args)
{
EthopianMultiplication(17, 34);
Console.ReadKey();
}
static int Half(int value)
{
return value >> 1;
}
static int Double(int value)
{
return value << 1;
}
static bool Even(int value)
{
return (value % 2) == 0;
}
static void EthopianMultiplication(int lhs, int rhs)
{
int total = 0;
int col1 = lhs;
int col2 = rhs;
while (col1 > 0)
{
Console.WriteLine("{0,4} | {1,4}", col1, col2);
if (!Even(col1))
{
total = total + col2;
}
col1 = Half(col1);
col2 = Double(col2);
}
Console.WriteLine("Total = {0}", total);
}
[edit] ColdFusion
Version with as a function of functions:
<cffunction name="double">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number * 2>
<cfreturn answer>
</cffunction>
<cffunction name="halve">
<cfargument name="number" type="numeric" required="true">
<cfset answer = int(number / 2)>
<cfreturn answer>
</cffunction>
<cffunction name="even">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number mod 2>
<cfreturn answer>
</cffunction>
<cffunction name="ethiopian">
<cfargument name="Number_A" type="numeric" required="true">
<cfargument name="Number_B" type="numeric" required="true">
<cfset Result = 0>
<cfloop condition = "Number_A GTE 1">
<cfif even(Number_A) EQ 1>
<cfset Result = Result + Number_B>
</cfif>
<cfset Number_A = halve(Number_A)>
<cfset Number_B = double(Number_B)>
</cfloop>
<cfreturn Result>
</cffunction>
<cfoutput>#ethiopian(17,34)#</cfoutput>
Version with display pizza:
<cfset Number_A = 17>
<cfset Number_B = 34>
<cfset Result = 0>
<cffunction name="double">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number * 2>
<cfreturn answer>
</cffunction>
<cffunction name="halve">
<cfargument name="number" type="numeric" required="true">
<cfset answer = int(number / 2)>
<cfreturn answer>
</cffunction>
<cffunction name="even">
<cfargument name="number" type="numeric" required="true">
<cfset answer = number mod 2>
<cfreturn answer>
</cffunction>
<cfoutput>
Ethiopian multiplication of #Number_A# and #Number_B#...
<br>
<table width="512" border="0" cellspacing="20" cellpadding="0">
<cfloop condition = "Number_A GTE 1">
<cfif even(Number_A) EQ 1>
<cfset Result = Result + Number_B>
<cfset Action = "Keep">
<cfelse>
<cfset Action = "Strike">
</cfif>
<tr>
<td align="right">#Number_A#</td>
<td align="right">#Number_B#</td>
<td align="center">#Action#</td>
</tr>
<cfset Number_A = halve(Number_A)>
<cfset Number_B = double(Number_B)>
</cfloop>
</table>
...equals #Result#
</cfoutput>
Sample output:
Ethiopian multiplication of 17 and 34... 17 34 Keep 8 68 Strike 4 136 Strike 2 272 Strike 1 544 Keep ...equals 578
[edit] Clojure
(defn halve [n]
(bit-shift-right n 1))
(defn twice [n] ; 'double' is taken
(bit-shift-left n 1))
(defn even [n] ; 'even?' is the standard fn
(zero? (bit-and n 1)))
(defn emult [x y]
(reduce +
(map second
(filter #(not (even (first %))) ; a.k.a. 'odd?'
(take-while #(pos? (first %))
(map vector
(iterate halve x)
(iterate twice y)))))))
(defn emult2 [x y]
(loop [a x, b y, r 0]
(if (= a 1)
(+ r b)
(if (even a)
(recur (halve a) (twice b) r)
(recur (halve a) (twice b) (+ r b))))))
[edit] Common Lisp
Common Lisp already has evenp, but all three of halve, double, and even-p are locally defined within ethiopian-multiply. (Note that the termination condition is (zerop l) because we terminate 'after' the iteration wherein the left column contains 1, and (halve 1) is 0.)
(defun ethiopian-multiply (l r)
(flet ((halve (n) (floor n 2))
(double (n) (* n 2))
(even-p (n) (zerop (mod n 2))))
(do ((product 0 (if (even-p l) product (+ product r)))
(l l (halve l))
(r r (double r)))
((zerop l) product))))
[edit] D
int ethiopian(int n1, int n2) {
static int doubleNum(int n) { return n * 2; }
static int halveNum(int n) { return n / 2; }
static bool isEven(int n) { return !(n % 2); }
int result;
while (n1 >= 1) {
if (!isEven(n1))
result += n2;
n1 = halveNum(n1);
n2 = doubleNum(n2);
}
return result;
}
void main() {
printf("17 ethiopian 34 is %d\n", ethiopian(17, 34));
}
[edit] E
def halve(&x) { x //= 2 }
def double(&x) { x *= 2 }
def even(x) { return x %% 2 <=> 0 }
def multiply(var a, var b) {
var ab := 0
while (a > 0) {
if (!even(a)) { ab += b }
halve(&a)
double(&b)
}
return ab
}
[edit] Factor
USING: arrays kernel math multiline sequences ;
IN: ethiopian-multiplication
/*
This function is built-in
: odd? ( n -- ? ) 1 bitand 1 number= ;
*/
: double ( n -- 2*n ) 2 * ;
: halve ( n -- n/2 ) 2 /i ;
: ethiopian-mult ( a b -- a*b )
[ 0 ] 2dip
[ dup 0 > ] [
[ odd? [ + ] [ drop ] if ] 2keep
[ double ] [ halve ] bi*
] while 2drop ;
[edit] FALSE
[2/]h:
[2*]d:
[1&]o:
[0[@$][$o;![@@\$@+@]?h;!@d;!@]#%\%]m:
17 34m;!. {578}
[edit] Forth
: e* ( x y -- x*y )
dup 0= if nip exit then
over 2* over 2/ recurse
swap 1 and if + else nip then ;
The author of Forth, Chuck Moore, designed a similar primitive into his MISC Forth microprocessors. The +* instruction is a multiply step: it adds S to T if A is odd, then shifts both A and T right one. The idea is that you only need to perform as many of these multiply steps as you have significant bits in the operand. (See his core instruction set for details.)
[edit] Fortran
Works with: Fortran version 90 and later
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
[edit] Haskell
import Prelude hiding (odd)
halve, double :: Integral a => a -> a
halve = (`div` 2)
double = (2 *)
odd :: Integral a => a -> Bool
odd = (== 1) . (`mod` 2)
ethiopicmult :: Integral a => a -> a -> a
ethiopicmult a b = sum $ map snd $ filter (odd . fst) $ zip
(takeWhile (>= 1) $ iterate halve a)
(iterate double b)
main = print $ ethiopicmult 17 34 == 17 * 34
Usage example from the interpreter
*Main> ethiopicmult 17 34 578
[edit] J
Solution:
double =: 2&* NB. or the primitive +:
halve =: %&2 NB. or the primitive -:
even =: 2&|
ethiop =: +/@(even@] # (double~ <@#)) (1>.<.@halve)^:a:
Example:
17 ethiop 34
578
Note: this could be implemented more concisely as #.@(*#:), which abides by the letter of the task, but evades its spirit.
[edit] Java
Works with: Java version 1.5+
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Mult {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int first = sc.nextInt();
int second = sc.nextInt();
Map <Integer, Integer> columns = new HashMap <Integer, Integer>();
columns.put(first, second);
do{
first = doubleInt(first);
second = halveInt(second);
columns.put(first, second);
}while(first != 1);
int sum = 0;
for(Map.Entry <Integer, Integer> entry : columns.entrySet()){
if(!isEven(entry.getKey())){
sum += entry.getValue();
}
}
System.out.println(sum);
}
public static int doubleInt(int doubleMe){
return doubleMe << 1; //shift left
}
public static int halveInt(int halveMe){
return halveMe >>> 1; //shift right
}
public static boolean isEven(int num){
return num & 1 == 0;
}
}
An optimised variant using the three helper functions from the other example.
/**
* This method will use ethiopian styled multiplication.
* @param a Any non-negative integer.
* @param b Any integer.
* @result a multiplied by b
*/
public static int ethiopianMultiply(int a, int b) {
if(a==0 || b==0) {
return 0;
}
int result = 0;
while(a>=1) {
if(!isEven(a)) {
result+=b;
}
b = doubleInt(b);
a = halveInt(a);
}
return result;
}
/**
* This method is an improved version that will use
* ethiopian styled multiplication, but can fully
* support negative parameters.
* @param a Any integer.
* @param b Any integer.
* @result a multiplied by b
*/
public static int ethiopianMultiplyWithImprovement(int a, int b) {
if(a==0 || b==0) {
return 0;
}
if(a<0) {
a=-a;
b=-b;
} else if(b>0 && a>b) {
int tmp = a;
a = b;
b = tmp;
}
int result = 0;
while(a>=1) {
if(!isEven(a)) {
result+=b;
}
b = doubleInt(b);
a = halveInt(a);
}
return result;
}
[edit] JavaScript
var eth = {
halve : function ( n ){ return Math.floor(n/2); },
double: function ( n ){ return 2*n; },
isEven: function ( n ){ return n%2 === 0); },
mult: function ( a , b ){
var sum = 0, a = [a], b = [b];
while ( a[0] !== 1 ){
a.unshift( eth.halve( a[0] ) );
b.unshift( eth.double( b[0] ) );
}
for( var i = a.length - 1; i > 0 ; i -= 1 ){
if( !eth.isEven( a[i] ) ){
sum += b[i];
} else {
break;
}
}
return sum + b[0];
}
}
// eth.mult(17,34) returns 578
[edit] Logo
to double :x
output ashift :x 1
end
to halve :x
output ashift :x -1
end
to even? :x
output equal? 0 bitand 1 :x
end
to eproduct :x :y
if :x = 0 [output 0]
ifelse even? :x ~
[output eproduct halve :x double :y] ~
[output :y + eproduct halve :x double :y]
end
[edit] Metafont
Implemented without the tutor.
vardef halve(expr x) = floor(x/2) enddef;
vardef double(expr x) = x*2 enddef;
vardef iseven(expr x) = if (x mod 2) = 0: true else: false fi enddef;
primarydef a ethiopicmult b =
begingroup
save r_, plier_, plicand_;
plier_ := a; plicand_ := b;
r_ := 0;
forever: exitif plier_ < 1;
if not iseven(plier_): r_ := r_ + plicand_; fi
plier_ := halve(plier_);
plicand_ := double(plicand_);
endfor
r_
endgroup
enddef;
show( (17 ethiopicmult 34) );
end
[edit] Lua
function halve(a)
return a/2
end
function double(a)
return a*2
end
function isEven(a)
return a%2 == 0
end
function ethiopian(x, y)
local result = 0
while (x >= 1) do
if not isEven(x) then
result = result + y
end
x = math.floor(halve(x))
y = double(y)
end
return result;
end
print(ethiopian(17, 34))
[edit] MMIX
In order to assemble and run this program you'll have to install MMIXware from [1]. This provides you with a simple assembler, a simulator, example programs and full documentation.
A IS 17
B IS 34
pliar IS $255 % designating main registers
pliand GREG
acc GREG
str IS pliar % reuse reg $255 for printing
LOC Data_Segment
GREG @
BUF OCTA #3030303030303030 % reserve a buffer that's big enough to hold
OCTA #3030303030303030 % a max (signed) 64 bit integer:
OCTA #3030300a00000000 % 2^63 - 1 = 9223372036854775807
% string is terminated with NL, 0
LOC #1000 % locate program at address
GREG @
halve SR pliar,pliar,1
GO $127,$127,0
double SL pliand,pliand,1
GO $127,$127,0
odd DIV $77,pliar,2
GET $78,rR
GO $127,$127,0
% Main is the entry point of the program
Main SET pliar,A % initialize registers for calculation
SET pliand,B
SET acc,0
1H GO $127,odd
BZ $78,2F % if pliar is even skip incr. acc with pliand
ADD acc,acc,pliand %
2H GO $127,halve % halve pliar
GO $127,double % and double pliand
PBNZ pliar,1B % repeat from 1H while pliar > 0
// result: acc = 17 x 34
// next: print result --> stdout
// $0 is a temp register
LDA str,BUF+19 % points after the end of the string
2H SUB str,str,1 % update buffer pointer
DIV acc,acc,10 % do a divide and mod
GET $0,rR % get digit from special purpose reg. rR
% containing the remainder of the division
INCL $0,'0' % convert to ascii
STBU $0,str % place digit in buffer
PBNZ acc,2B % next
% 'str' points to the start of the result
TRAP 0,Fputs,StdOut % output answer to stdout
TRAP 0,Halt,0 % exit
Assembling:
~/MIX/MMIX/Progs> mmixal ethiopianmult.mms
Running:
~/MIX/MMIX/Progs> mmix ethiopianmult 578
[edit] Modula-3
Translation of: Ada
MODULE Ethiopian EXPORTS Main;
IMPORT IO, Fmt;
PROCEDURE IsEven(n: INTEGER): BOOLEAN =
BEGIN
RETURN n MOD 2 = 0;
END IsEven;
PROCEDURE Double(n: INTEGER): INTEGER =
BEGIN
RETURN n * 2;
END Double;
PROCEDURE Half(n: INTEGER): INTEGER =
BEGIN
RETURN n DIV 2;
END Half;
PROCEDURE Multiply(a, b: INTEGER): INTEGER =
VAR
temp := 0;
plier := a;
plicand := b;
BEGIN
WHILE plier >= 1 DO
IF NOT IsEven(plier) THEN
temp := temp + plicand;
END;
plier := Half(plier);
plicand := Double(plicand);
END;
RETURN temp;
END Multiply;
BEGIN
IO.Put("17 times 34 = " & Fmt.Int(Multiply(17, 34)) & "\n");
END Ethiopian.
[edit] Objective-C
Using class methods except for the generic useful function iseven.
#import <stdio.h>
#import <objc/Object.h>
BOOL iseven(int x)
{
return (x&1) == 0;
}
@interface EthiopicMult : Object
+ (int)mult: (int)plier by: (int)plicand;
+ (int)halve: (int)a;
+ (int)double: (int)a;
@end
@implementation EthiopicMult
+ (int)mult: (int)plier by: (int)plicand
{
int r = 0;
while(plier >= 1) {
if ( !iseven(plier) ) r += plicand;
plier = [EthiopicMult halve: plier];
plicand = [EthiopicMult double: plicand];
}
return r;
}
+ (int)halve: (int)a
{
return (a>>1);
}
+ (int)double: (int)a
{
return (a<<1);
}
@end
int main()
{
printf("%d\n", [EthiopicMult mult: 17 by: 34]);
return 0;
}
[edit] OCaml
(* We optimize a bit by not keeping the intermediate lists, and summing
the right column on-the-fly, like in the C version.
The function takes "halve" and "double" operators and "is_even" predicate as arguments,
but also "is_zero", "zero" and "add". This allows for more general uses of the
ethiopian multiplication. *)
let ethiopian is_zero is_even halve zero double add b a =
let rec g a b r =
if is_zero a
then (r)
else g (halve a) (double b) (if not (is_even a) then (add b r) else (r))
in
g a b zero
;;
let imul =
ethiopian (( = ) 0) (fun x -> x mod 2 = 0) (fun x -> x / 2) 0 (( * ) 2) ( + );;
imul 17 34;;
(* - : int = 578 *)
(* Now, we have implemented the same algorithm as "rapid exponentiation",
merely changing operator names *)
let ipow =
ethiopian (( = ) 0) (fun x -> x mod 2 = 0) (fun x -> x / 2) 1 (fun x -> x*x) ( * )
;;
ipow 2 16;;
(* - : int = 65536 *)
(* still renaming operators, if "halving" is just subtracting one,
and "doubling", adding one, then we get an addition *)
let iadd a b =
ethiopian (( = ) 0) (fun x -> false) (pred) b (function x -> x) (fun x y -> succ y) 0 a
;;
iadd 421 1000;;
(* - : int = 1421 *)
(* One can do much more with "ethiopian multiplication",
since the two "multiplicands" and the result may be of three different types,
as shown by the typing system of ocaml *)
ethiopian;;
- : ('a -> bool) -> (* is_zero *)
('a -> bool) -> (* is_even *)
('a -> 'a) -> (* halve *)
'b -> (* zero *)
('c -> 'c) -> (* double *)
('c -> 'b -> 'b) -> (* add *)
'c -> (* b *)
'a -> (* a *)
'b (* result *)
= <fun>
(* Here zero is the starting value for the accumulator of the sums
of values in the right column in the original algorithm. But the "add"
me do something else, see for example the RosettaCode page on
"Exponentiation operator". *)
[edit] Octave
function r = halve(a)
r = floor(a/2);
endfunction
function r = doublit(a)
r = a*2;
endfunction
function r = iseven(a)
r = mod(a,2) == 0;
endfunction
function r = ethiopicmult(plier, plicand, tutor=false)
r = 0;
if (tutor)
printf("ethiopic multiplication of %d and %d\n", plier, plicand);
endif
while(plier >= 1)
if ( iseven(plier) )
if (tutor)
printf("%4d %6d struck\n", plier, plicand);
endif
else
r = r + plicand;
if (tutor)
printf("%4d %6d kept\n", plier, plicand);
endif
endif
plier = halve(plier);
plicand = doublit(plicand);
endwhile
endfunction
disp(ethiopicmult(17, 34, true))
[edit] Oz
declare
fun {Halve X} X div 2 end
fun {Double X} X * 2 end
fun {Even X} {Abs X mod 2} == 0 end %% standard function: Int.isEven
fun {EthiopicMult X Y}
X >= 0 = true %% assert: X must not be negative
Rows = for
L in X; L>0; {Halve L} %% C-like iterator: "Init; While; Next"
R in Y; true; {Double R}
collect:Collect
do
{Collect L#R}
end
OddRows = {Filter Rows LeftIsOdd}
RightColumn = {Map OddRows SelectRight}
in
{Sum RightColumn}
end
%% Helpers
fun {LeftIsOdd L#_} {Not {Even L}} end
fun {SelectRight _#R} R end
fun {Sum Xs} {FoldL Xs Number.'+' 0} end
in
{Show {EthiopicMult 17 34}}
[edit] Perl
use strict;
sub halve { int((shift) / 2); }
sub double { (shift) * 2; }
sub iseven { ((shift) & 1) == 0; }
sub ethiopicmult
{
my ($plier, $plicand, $tutor) = @_;
print "ethiopic multiplication of $plier and $plicand\n" if $tutor;
my $r = 0;
while ($plier >= 1)
{
$r += $plicand unless iseven($plier);
if ($tutor) {
print "$plier, $plicand ", (iseven($plier) ? " struck" : " kept"), "\n";
}
$plier = halve($plier);
$plicand = double($plicand);
}
return $r;
}
print ethiopicmult(17,34, 1), "\n";
[edit] Perl 6
Works with: Rakudo version #21 "Seattle"
sub halve (Int $n is rw) { $n div= 2 }
sub double (Int $n is rw) { $n *= 2 }
sub even (Int $n --> Bool) { $n !% 2 }
sub ethiopicmult (Int $a is copy, Int $b is copy --> Int) {
my Int $r = 0;
while $a {
even $a or $r += $b;
halve $a;
double $b;
}
return $r;
}
[edit] PHP
<?php
function halve($x)
{
return floor($x/2);
}
function double($x)
{
return $x*2;
}
function iseven($x)
{
return $x % 2 === 0;
}
function ethiopicmult($plier, $plicand, $tutor)
{
if ($tutor) echo "ethiopic multiplication of $plier and $plicand\n";
$r = 0;
while($plier >= 1) {
if ( !iseven($plier) ) $r += $plicand;
if ($tutor)
echo "$plier, $plicand ", (iseven($plier) ? "struck" : "kept"), "\n";
$plier = halve($plier);
$plicand = double($plicand);
}
return $r;
}
echo ethiopicmult(17, 34, true), "\n";
?>
Output
ethiopic multiplication of 17 and 34 17, 34 kept 8, 68 struck 4, 136 struck 2, 272 struck 1, 544 kept 578
[edit] PicoLisp
(de halve (N)
(/ N 2) )
(de double (N)
(* N 2) )
(de even? (N)
(not (bit? 1 N)) )
(de ethiopian (X Y)
(let R 0
(while (>= X 1)
(or (even? X) (inc 'R Y))
(setq
X (halve X)
Y (double Y) ) )
R ) )
[edit] PL/I
declare (L(30), R(30)) fixed binary;
declare (i, s) fixed binary;
L, R = 0;
put skip list
('Hello, please type two values and I will print their product:');
get list (L(1), R(1));
put edit ('The product of ', trim(L(1)), ' and ', trim(R(1)), ' is ') (a);
do i = 1 by 1 while (L(i) ^= 0);
L(i+1) = halve(L(i));
R(i+1) = double(R(i));
end;
s = 0;
do i = 1 by 1 while (L(i) > 0);
if odd(L(i)) then s = s + R(i);
end;
put edit (trim(s)) (a);
halve: procedure (k) returns (fixed binary);
declare k fixed binary;
return (k/2);
end halve;
double: procedure (k) returns (fixed binary);
declare k fixed binary;
return (2*k);
end;
odd: procedure (k) returns (bit (1));
return (iand(k, 1) ^= 0);
end odd;
[edit] PL/SQL
This code was taken from the ADA example above - very minor differences.
CREATE OR REPLACE PACKAGE ethiopian IS
FUNCTION multiply
( left IN INTEGER,
right IN INTEGER)
RETURN INTEGER;
END ethiopian;
/
CREATE OR REPLACE PACKAGE BODY ethiopian IS
FUNCTION is_even(item IN INTEGER) RETURN BOOLEAN IS
BEGIN
RETURN item MOD 2 = 0;
END is_even;
FUNCTION double(item IN INTEGER) RETURN INTEGER IS
BEGIN
RETURN item * 2;
END double;
FUNCTION half(item IN INTEGER) RETURN INTEGER IS
BEGIN
RETURN TRUNC(item / 2);
END half;
FUNCTION multiply
( left IN INTEGER,
right IN INTEGER)
RETURN INTEGER
IS
temp INTEGER := 0;
plier INTEGER := left;
plicand INTEGER := right;
BEGIN
LOOP
IF NOT is_even(plier) THEN
temp := temp + plicand;
END IF;
plier := half(plier);
plicand := double(plicand);
EXIT WHEN plier <= 1;
END LOOP;
temp := temp + plicand;
RETURN temp;
END multiply;
END ethiopian;
/
/* example call */
BEGIN
DBMS_OUTPUT.put_line(ethiopian.multiply(17, 34));
END;
/
[edit] PowerShell
function isEven {
param ([int]$value)
return [bool]($value % 2 -eq 0)
}
function doubleValue {
param ([int]$value)
return [int]($value * 2)
}
function halveValue {
param ([int]$value)
return [int]($value / 2)
}
function multiplyValues {
param (
[int]$plier,
[int]$plicand,
[int]$temp = 0
)
while ($plier -ge 1)
{
if (!(isEven $plier)) {
$temp += $plicand
}
$plier = halveValue $plier
$plicand = doubleValue $plicand
}
return $temp
}
multiplyValues 17 34
[edit] PureBasic
Procedure isEven(x)
ProcedureReturn (x & 1) ! 1
EndProcedure
Procedure halveValue(x)
ProcedureReturn x / 2
EndProcedure
Procedure doubleValue(x)
ProcedureReturn x << 1
EndProcedure
Procedure EthiopianMultiply(x, y)
Protected sum
Print("Ethiopian multiplication of " + Str(x) + " and " + Str(y) + " ... ")
Repeat
If Not isEven(x)
sum + y
EndIf
x = halveValue(x)
y = doubleValue(y)
Until x < 1
PrintN(" equals " + Str(sum))
ProcedureReturn sum
EndProcedure
If OpenConsole()
EthiopianMultiply(17,34)
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf
Sample output:
Ethiopian multiplication of 17 and 34 ... equals 578
It became apparent that according to the way the Ethiopian method is described above it can't produce a correct result if the first multiplicand (the one being repeatedly halved) is negative. I've addressed that in this variation. If the first multiplicand is negative then the resulting sum (which may already be positive or negative) is negated.
Procedure isEven(x)
ProcedureReturn (x & 1) ! 1
EndProcedure
Procedure halveValue(x)
ProcedureReturn x / 2
EndProcedure
Procedure doubleValue(x)
ProcedureReturn x << 1
EndProcedure
Procedure EthiopianMultiply(x, y)
Protected sum, sign = x
Print("Ethiopian multiplication of " + Str(x) + " and " + Str(y) + " ...")
Repeat
If Not isEven(x)
sum + y
EndIf
x = halveValue(x)
y = doubleValue(y)
Until x = 0
If sign < 0 : sum * -1: EndIf
PrintN(" equals " + Str(sum))
ProcedureReturn sum
EndProcedure
If OpenConsole()
EthiopianMultiply(17,34)
EthiopianMultiply(-17,34)
EthiopianMultiply(-17,-34)
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf
Sample output:
Ethiopian multiplication of 17 and 34 ... equals 578 Ethiopian multiplication of -17 and 34 ... equals -578 Ethiopian multiplication of -17 and -34 ... equals 578
[edit] 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
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 >>>
Without the tutorial code, and taking advantage of Python's lambda:
halve = lambda x: x // 2
double = lambda x: x*2
even = lambda x : not x % 2
def ethiopian(multiplier, multiplicand):
result = 0
while multiplier >= 1:
if not even(multiplier):
result += multiplicand
multiplier = halve(multiplier)
multiplicand = double(multiplicand)
return result
[edit] R
halve <- function(a) floor(a/2)
double <- function(a) a*2
iseven <- function(a) (a%%2)==0
ethiopicmult <- function(plier, plicand, tutor=FALSE) {
if (tutor) { cat("ethiopic multiplication of", plier, "and", plicand, "\n") }
result <- 0
while(plier >= 1) {
if (!iseven(plier)) { result <- result + plicand }
if (tutor) {
cat(plier, ", ", plicand, " ", ifelse(iseven(plier), "struck", "kept"), "\n", sep="")
}
plier <- halve(plier)
plicand <- double(plicand)
}
result
}
print(ethiopicmult(17, 34, TRUE))
[edit] Ruby
Iterative and recursive implementations here. I've chosen to highlight the example 20*5 which I think is more illustrative.
def even(x); x.even?; end
def halve(x); x/2; end
def double(x); x*2; end
# iterative
def ethopian_multiply(a, b)
product = 0
while a >= 1
p [a, b, even(a) ? "STRIKE" : "KEEP"] if $DEBUG
product += b if not even(a)
a = halve(a)
b = double(b)
end
product
end
# recursive
def rec_ethopian_multiply(a, b)
return 0 if a < 1
p [a, b, even(a) ? "STRIKE" : "KEEP"] if $DEBUG
(even(a) ? 0 : b) + rec_ethopian_multiply(halve(a), double(b))
end
$DEBUG = true # $DEBUG also set to true if "-d" option given
a, b = 20, 5
puts "#{a} * #{b} = #{ethopian_multiply(a,b)}"; puts
Output:
[20, 5, "STRIKE"] [10, 10, "STRIKE"] [5, 20, "KEEP"] [2, 40, "STRIKE"] [1, 80, "KEEP"] 20 * 5 = 100
A test suite:
require 'test/unit'
class EthiopianTests < Test::Unit::TestCase
def test_iter1; assert_equal(578, ethopian_multiply(17,34)); end
def test_iter2; assert_equal(100, ethopian_multiply(20,5)); end
def test_iter3; assert_equal(5, ethopian_multiply(5,1)); end
def test_iter4; assert_equal(5, ethopian_multiply(1,5)); end
def test_iter5; assert_equal(0, ethopian_multiply(5,0)); end
def test_iter6; assert_equal(0, ethopian_multiply(0,5)); end
def test_rec1; assert_equal(578, rec_ethopian_multiply(17,34)); end
def test_rec2; assert_equal(100, rec_ethopian_multiply(20,5)); end
def test_rec3; assert_equal(5, rec_ethopian_multiply(5,1)); end
def test_rec4; assert_equal(5, rec_ethopian_multiply(1,5)); end
def test_rec5; assert_equal(0, rec_ethopian_multiply(5,0)); end
def test_rec6; assert_equal(0, rec_ethopian_multiply(0,5)); end
end
Loaded suite ethopian Started ............ Finished in 0.001 seconds. 12 tests, 12 assertions, 0 failures, 0 errors
[edit] Scheme
In Scheme, even? is a standard procedure.
(define (halve num)
(quotient num 2))
(define (double num)
(* num 2))
(define (*mul-eth plier plicand acc)
(cond ((zero? plier) acc)
((even? plier) (*mul-eth (halve plier) (double plicand) acc))
(else (*mul-eth (halve plier) (double plicand) (+ acc plicand)))))
(define (mul-eth plier plicand)
(*mul-eth plier plicand 0))
(display (mul-eth 17 34))
(newline)
Output:
578
[edit] Seed7
Ethiopian Multiplication is another name for the peasant multiplication:
const proc: double (inout integer: a) is func
begin
a *:= 2;
end func;
const proc: halve (inout integer: a) is func
begin
a := a div 2;
end func;
const func boolean: even (in integer: a) is
return not odd(a);
const func integer: peasantMult (in var integer: a, in var integer: b) is func
result
var integer: result is 0;
begin
while a <> 0 do
if not even(a) then
result +:= b;
end if;
halve(a);
double(b);
end while;
end func;
Original source (without separate functions for doubling, halving, and checking if a number is even): [2]
[edit] Smalltalk
Works with: GNU 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 ]
].
(17 ethiopianMultiplyBy: 34 withTutor: true) displayNl.
[edit] SNOBOL4
define('halve(num)') :(halve_end)
halve eq(num,1) :s(freturn)
halve = num / 2 :(return)
halve_end
define('double(num)') :(double_end)
double double = num * 2 :(return)
double_end
define('odd(num)') :(odd_end)
odd eq(num,1) :s(return)
eq(num,double(halve(num))) :s(freturn)f(return)
odd_end l = trim(input)
r = trim(input)
s = 0
next s = odd(l) s + r
r = double(r)
l = halve(l) :s(next)
stop output = s
end
[edit] SNUSP
/==!/==atoi==@@@-@-----#
| | /-\ /recurse\ #/?\ zero
$>,@/>,@/?\<=zero=!\?/<=print==!\@\>?!\@/<@\.!\-/
< @ # | \=/ \=itoa=@@@+@+++++#
/==\ \===?!/===-?\>>+# halve ! /+ !/+ !/+ !/+ \ mod10
# ! @ | #>>\?-<+>/ /<+> -\!?-\!?-\!?-\!?-\!
/-<+>\ > ? />+<<++>-\ \?!\-?!\-?!\-?!\-?!\-?/\ div10
?down? | \-<<<!\=======?/\ add & # +/! +/! +/! +/! +/
\>+<-/ | \=<<<!/====?\=\ | double
! # | \<++>-/ | |
\=======\!@>============/!/
This is possibly the smallest multiply routine so far discovered for SNUSP.
[edit] Tcl
# This is how to declare functions - the mathematical entities - as opposed to procedures
proc function {name arguments body} {
uplevel 1 [list proc tcl::mathfunc::$name $arguments [list expr $body]]
}
function double n {$n * 2}
function halve n {$n / 2}
function even n {($n & 1) == 0}
function mult {a b} {
$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)}]
}
Demo code:
puts "17 * 34 = [ethiopianMultiply 17 34 true]"
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
[edit] UNIX Shell
(Tried with bash --posix, so it should run in sh too)
halve()
{
echo $(( $1 / 2 ))
}
double()
{
echo $(( $1 * 2 ))
}
iseven()
{
echo $(( $1 % 2 == 0 ))
}
ethiopicmult()
{
plier=$1
plicand=$2
r=0
while [ $plier -ge 1 ]; do
if [ $(iseven $plier) -eq 0 ]; then
r=$(( r + plicand))
fi
plier=$(halve $plier)
plicand=$(double $plicand)
done
echo $r
}
echo $(ethiopicmult 17 34)
[edit] Ursala
This solution makes use of the functions odd, double, and half, which respectively check the parity, double a given natural number, or perform truncating division by two. These functions are normally imported from the nat library but defined here explicitly for the sake of completeness.
odd = ~&ihB
double = ~&iNiCB
half = ~&itB
The functions above are defined in terms of bit manipulations exploiting the concrete representations of natural numbers. The remaining code treats natural numbers instead as abstract types by way of the library API, and uses the operators for distribution (*-), triangular iteration (|\), and filtering (*~) among others.
#import nat
emul = sum:-0@rS+ odd@l*~+ ^|(~&,double)|\+ *-^|\~& @iNC ~&h~=0->tx :^/half@h ~&
test program:
#cast %n
test = emul(34,17)
output:
578
[edit] VBScript
Nowhere near as optimal a solution as the Ada. Yes, it could have made as optimal, but the long way seemed more interesting.
Demonstrates a List class. The .recall and .replace methods have bounds checking but the code does not test for the exception that would be raised. List class extends the storage allocated for the list when the occupation of the list goes beyond the original allocation.
option explicit makes sure that all variables are declared.
[edit] Implementation
option explicit
class List
private theList
private nOccupiable
private nTop
sub class_initialize
nTop = 0
nOccupiable = 100
redim theList( nOccupiable )
end sub
public sub store( x )
if nTop >= nOccupiable then
nOccupiable = nOccupiable + 100
redim preserve theList( nOccupiable )
end if
theList( nTop ) = x
nTop = nTop + 1
end sub
public function recall( n )
if n >= 0 and n <= nOccupiable then
recall = theList( n )
else
err.raise vbObjectError + 1000,,"Recall bounds error"
end if
end function
public sub replace( n, x )
if n >= 0 and n <= nOccupiable then
theList( n ) = x
else
err.raise vbObjectError + 1001,,"Replace bounds error"
end if
end sub
public property get listCount
listCount = nTop
end property
end class
function halve( n )
halve = int( n / 2 )
end function
function twice( n )
twice = int( n * 2 )
end function
function iseven( n )
iseven = ( ( n mod 2 ) = 0 )
end function
function multiply( n1, n2 )
dim LL
set LL = new List
dim RR
set RR = new List
LL.store n1
RR.store n2
do while n1 <> 1
n1 = halve( n1 )
LL.store n1
n2 = twice( n2 )
RR.store n2
loop
dim i
for i = 0 to LL.listCount
if iseven( LL.recall( i ) ) then
RR.replace i, 0
end if
next
dim total
total = 0
for i = 0 to RR.listCount
total = total + RR.recall( i )
next
multiply = total
end function
[edit] Invocation
wscript.echo multiply(17,34)
[edit] Output
578
[edit] x86 Assembly
Works with: nasm, linking with the C standard library and start code.
extern printf
global main
section .text
halve
shr ebx, 1
ret
double
shl ebx, 1
ret
iseven
and ebx, 1
cmp ebx, 0
ret ; ret preserves flags
main
push 1 ; tutor = true
push 34 ; 2nd operand
push 17 ; 1st operand
call ethiopicmult
add esp, 12
push eax ; result of 17*34
push fmt
call printf
add esp, 8
ret
%define plier 8
%define plicand 12
%define tutor 16
ethiopicmult
enter 0, 0
cmp dword [ebp + tutor], 0
je .notut0
push dword [ebp + plicand]
push dword [ebp + plier]
push preamblefmt
call printf
add esp, 12
.notut0
xor eax, eax ; eax -> result
mov ecx, [ebp + plier] ; ecx -> plier
mov edx, [ebp + plicand] ; edx -> plicand
.whileloop
cmp ecx, 1
jl .multend
cmp dword [ebp + tutor], 0
je .notut1
call tutorme
.notut1
mov ebx, ecx
call iseven
je .iseven
add eax, edx ; result += plicand
.iseven
mov ebx, ecx ; plier >>= 1
call halve
mov ecx, ebx
mov ebx, edx ; plicand <<= 1
call double
mov edx, ebx
jmp .whileloop
.multend
leave
ret
tutorme
push eax
push strucktxt
mov ebx, ecx
call iseven
je .nostruck
mov dword [esp], kepttxt
.nostruck
push edx
push ecx
push tutorfmt
call printf
add esp, 4
pop ecx
pop edx
add esp, 4
pop eax
ret
section .data
fmt
db "%d", 10, 0
preamblefmt
db "ethiopic multiplication of %d and %d", 10, 0
tutorfmt
db "%4d %6d %s", 10, 0
strucktxt
db "struck", 0
kepttxt
db "kept", 0
[edit] Smaller version
Using old style 16 bit registers created in debug
The functions to halve double and even are coded inline. To half a value
shr,1
to double a value
shl,1
to test if the value is even
test,01
jz Even
Odd:
Even:
;calling program
1BDC:0100 6A11 PUSH 11 ;17 Put operands on the stack
1BDC:0102 6A22 PUSH 22 ;34
1BDC:0104 E80900 CALL 0110 ; call the mulitplcation routine
;putting some space in, (not needed)
1BDC:0107 90 NOP
1BDC:0108 90 NOP
1BDC:0109 90 NOP
1BDC:010A 90 NOP
1BDC:010B 90 NOP
1BDC:010C 90 NOP
1BDC:010D 90 NOP
1BDC:010E 90 NOP
1BDC:010F 90 NOP
;mulitplication routine
1BDC:0110 89E5 MOV BP,SP ; prepare to get operands off stack
1BDC:0112 8B4E02 MOV CX,[BP+02] ; Get the first operand
1BDC:0115 8B5E04 MOV BX,[BP+04] ; get the second oerand
1BDC:0118 31C0 XOR AX,AX ; zero out the result
1BDC:011A F7C10100 TEST CX,0001 ; are we odd
1BDC:011E 7402 JZ 0122 ; no skip the next instruction
1BDC:0120 01D8 ADD AX,BX ; we are odd so add to the result
1BDC:0122 D1E9 SHR CX,1 ; divide by 2
1BDC:0124 D1E3 SHL BX,1 ; multiply by 2
1BDC:0126 83F901 CMP CX,+01 ; are we done (==1)
1BDC:0129 75EF JNZ 011A ; no, go back and do it again
1BDC:012B 01D8 ADD AX,BX ; final add
1BDC:012D C3 RET ; return with the result in AX
;pretty small
Categories: Programming Tasks | Arithmetic operations | Ada | ALGOL 68 | AutoHotkey | AWK | BASIC | C | C++ | C sharp | ColdFusion | Clojure | Common Lisp | D | E | Factor | FALSE | Forth | Fortran | Haskell | J | Java | JavaScript | Logo | Metafont | Lua | MMIX | Modula-3 | Objective-C | OCaml | Octave | Oz | Perl | Perl 6 | PHP | PicoLisp | PL/I | PL/SQL | PowerShell | PureBasic | Python | R | Ruby | Scheme | Seed7 | Smalltalk | SNOBOL4 | SNUSP | Tcl | UNIX Shell | Ursala | VBScript | X86 Assembly
