8(r, s, a) = {(3r, (s – 1)/3,a+r) if 3| (s – 1) (3r, (s – 2)/3,a+ 2r) otherwise. 2. Verify the partial correctness of Algorithm 1. (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.

Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
icon
Related questions
icon
Concept explainers
Topic Video
Question
100%

It is a discrete math problem. I need your help with the question attached.thanks. 

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 1 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.
2. Verify the partial correctness of Algorithm 1.
(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.
Transcribed Image Text: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 1 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. 2. Verify the partial correctness of Algorithm 1. (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.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps with 26 images

Blurred answer
Knowledge Booster
Application of Algebra
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, advanced-math and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,