Writing Prompt Consider the following algorithmic procedure: Input :Non-negative integers x, y Output : Non-negative integer a r:= x; s:= y; a:= 0; while s + 0 do if 3 | s then r:=r+r+r; s:= s/3; end else if 3 | (s– 1) then a:= a+r; r:=r+r+r; s:= (s – 1)/3; end else a:= a+r+r; r:=r+r+r; s:= (s – 2)/3; end end return a Algorithm 1: Multiply We can model Algorithm ]as a state machine whose states are triples of non-negative integers (r, s, a). The initial state is (x, y,0). The transitions are given by the rule 8 that for s > 0: (3r,s/3,a) if 3|s 8(r,s,a) = {(3r, (s –1)/3,a+r) if 3| (s– 1) (3r, (s – 2)/3,a+ 2r) otherwise. 1. List the sequence of steps that appears in the execution of the algorithm for inputs x = 20 and y = 21. In other words, walk us through the algorithm starting from the initial state, showing
Operations
In mathematics and computer science, an operation is an event that is carried out to satisfy a given task. Basic operations of a computer system are input, processing, output, storage, and control.
Basic Operators
An operator is a symbol that indicates an operation to be performed. We are familiar with operators in mathematics; operators used in computer programming are—in many ways—similar to mathematical operators.
Division Operator
We all learnt about division—and the division operator—in school. You probably know of both these symbols as representing division:
Modulus Operator
Modulus can be represented either as (mod or modulo) in computing operation. Modulus comes under arithmetic operations. Any number or variable which produces absolute value is modulus functionality. Magnitude of any function is totally changed by modulo operator as it changes even negative value to positive.
Operators
In the realm of programming, operators refer to the symbols that perform some function. They are tasked with instructing the compiler on the type of action that needs to be performed on the values passed as operands. Operators can be used in mathematical formulas and equations. In programming languages like Python, C, and Java, a variety of operators are defined.
This is a discerete maths assignment
![Writing Prompt
Consider the following algorithmic procedure:
Input :Non-negative integers x, y
Output : Non-negative integer a
r:= x;
s:= y;
a := 0;
while s + 0 do
if 3 | s then
r:=r+r+r;
s:= s/3;
end
else if 3 | (s-1) then
а:3а+r;
r:=r+r+r;
s:= (s – 1)/3;
end
else
а:3а+r+r;
r:=r+r+r;
s:= (s – 2)/3;
end
end
return a
Algorithm 1: Multiply
We can model Algorithm I as a state machine whose states are triples of non-negative integers
(r, s, a). The initial state is (x, y, 0). The transitions are given by the rule & that for s > 0:
[(3r,s/3,a)
8(r, s,a) = {(3r, (s - 1)/3,a+r)
if 3 | s
if 3 | (s– 1)
(3r, (s – 2)/3,a+ 2r) otherwise.
1. List the sequence of steps that appears in the execution of the algorithm for inputs x = 20 and
y = 21. In other words, walk us through the algorithm starting from the initial state, showing
the values of r, s, a after each transition, and ending with the final state. Note that for the rest
of the prompt, you are considering arbitrary inputs x, y. The above example inputs are just to
help you familiarize yourself with the algorithm.
2. Verify the partial correctness of Algorithm [I
(a) Define a predicate P on the states that you believe is a preserved invariant. (Suggestion:
Think about why the loop condition is s # 0 and look at your sequence of steps from
Part 1.)
(b) Prove that P is a preserved invariant.
(c) Apply the Invariant Principle to prove that if s = 0, then a = xy.
3. Verify that Algorithm [] terminates.
(a) Define a strictly decreasing derived variable on the states.
(b) Prove that the algorithm terminates after at most 1 + logą y executions of the body of the
do statement. (Suggestion: Review the Fast Exponentiation program in [1).)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fdff3a2b7-00ec-4ff4-a55e-28054be2aaca%2F641c16ce-ae31-4b29-949b-9f36cc848019%2Flu7prda_processed.png&w=3840&q=75)
Step by step
Solved in 2 steps with 42 images
