I need help with the last function which is \"power\", this is what i have so fa
ID: 3887979 • Letter: I
Question
I need help with the last function which is "power", this is what i have so far:
Package arithmetic
%% This package provides functions for working with integers,
%% represented as binary lists.
%% Lists begin with the low order end of the number.
%% For example, list [1,1,0,0,1] stands for the binary number
%% 10011, or 19 in decimal.
%%
%% A list is *normalized if it does not end on 0. All of the
%% following functions produce normalized results, even if the
%% parameter(s) are not normalized.
================================================================
export
================================================================
Abbrev Bit = Integer.
Expect
inc : [Bit] -> [Bit]
%: inc(x) is x+1, where both x and the result are
%: binary numbers represented as lists.
%: For example inc([1,0,1,1]) = [0,1,1,1]
;
sum : ([Bit], [Bit]) -> [Bit]
%: sum(x,y) = x + y, where x, y and the result are
%: binary numbers represented as lists. For example,
%: sum([0,1,1], [1,1,1]) = [1,0,1,1]. (6 + 7 = 13)
;
product : ([Bit], [Bit]) -> [Bit]
%: product(x,y) = x * y, where x, y and the result are
%: binary numbers represented as lists. For example,
%: product([1,1], [1,1]) = [1,0,0,1]. (3*3 = 9)
;
power : ([Bit], [Bit]) -> [Bit]
%: power(x,y) = x ^ y, where x, y and the result are
%: binary numbers represented as lists. For example,
%: power([1,1], [1,1]) = [0,0,0,1]. (1^1 = 1)
;
%Expect
================================================================
implementation
================================================================
Import removeTrailing from "collect/list".
Import "math/functions".
Define normalize = removeTrailing 0.
===============================================================
%% inc
===============================================================
%% incn is similar to inc, but does not normalize its result.
%% (n stands for non-normalizing)
Define
----------------------------------------------
%% 0 + 1 = 1
case incn ([]) = [1]
----------------------------------------------
%% (2t) + 1 = 2t + 1
case incn (0::t) = 1 :: t
----------------------------------------------
%% (2t+1) + 1 = 2(t+1)
case incn (1::t) = 0 :: incn t
----------------------------------------------
%Define
Define inc x = normalize(incn x).
Example inc [1,1,0,1,1,0,0] = [0,0,1,1,1].
Example inc [1] = [0,1].
Example inc [1,0,0] = [0,1].
===============================================================
%% sum
===============================================================
%% sumn is simliar to sum, but does not normalize its result.
%% (n stands for non-normalizing)
Define
----------------------------------------------
%% x is 0 or empty
case sumn (x,y) = y when x == []
----------------------------------------------
%% y is 0 or empty
case sumn (x,y) = x when y == []
----------------------------------------------
%% (2x + 1) + (2y + 1) = 2(x + y + 1)
case sumn ((1::x),(1::y)) = 0 :: incn(sumn(x,y))
----------------------------------------------
%% (2x + 1) + (2y) = 2(x+y) + 1
case sumn ((1::x),(0::y)) = 1 :: sumn (x,y)
----------------------------------------------
%% 2x + (2y + 1) = 2(x+y) + 1
case sumn ((0::x),(1::y)) = 1 :: sumn (x,y)
----------------------------------------------
%% 2x + 2y = 2(x+y)
case sumn ((0::x),(0::y)) = 0 :: sumn (x,y)
----------------------------------------------
%Define
Define sum (x,y) = normalize(sumn (x,y)).
Example sum ([],[1,0,1,1]) = [1,0,1,1].
Example sum ([0,1,1],[1,1]) = [1,0,0,1].
Example sum ([0,1,1],[1,1,1]) = [1,0,1,1].
===============================================================
%% product
===============================================================
%% productn is similar to product, but does not normalize its result.
%% (n stands for non-normalizing)
Define
----------------------------------------------
%% (x) * 0 = 0
case productn(?,[]) = [0]
----------------------------------------------
%% 0 * (y) = 0
case productn([],?) = [0]
----------------------------------------------
%% 2y * x = 2yx
case productn(x,0::y) = 0::productn(x,y)
----------------------------------------------
%% 2x * y = 2xy
case productn(0::x,y) = 0::productn(x,y)
----------------------------------------------
%% x * (2y+1) = 2xy + x
case productn(x,1::y) = sumn(0::productn(x,y),x)
----------------------------------------------
%% (2x + 1) * y = 2xy + y
case productn(1::x,y) = sumn(0::productn(x,y),y)
----------------------------------------------
%Define
Define product (x,y) = normalize(productn (x,y)).
Example product ([1,1], [1,1]) = [1,0,0,1].
Example product ([1,0,1],[0,1]) = [0,1,0,1].
Example product ([1,0,0,1],[0,0,1]) = [0,0,1,0,0,1].
%Package
Explanation / Answer
I hope all the functions are working fine, then
In order to implement power, I can use product funtion and inc function.
output_list power(list1,list2) /* This function will do power on list1, list2 times*/
{
list3 = [] /*list3 is empty which means number 0, it will act as counter */
out_list = [1] /*Out_list will output the result which is initialised to 1*/
while(!list2.equals(list3)) /*checking if list3 become equal to list2*/
{
inc(list3) /*Increment list3 after every iteration till it will be equal to list2*/
out_list = product(out_list,list1) /*At every iteration, out_list contain power upto list3 times*/
}
return out_list /* power output*/
}
Feel free for any clarification