- #1
SpiffyEh
- 194
- 0
Homework Statement
Prove the correctness of the following recursive algorithm to multiply two
natural numbers, for all integer constants c ≥ 2.
function multiply(y, z)
comment Return the product yz.
1. if z = 0 then return(0) else
2. return(multiply(cy,[ z/c]) + y · (z mod c))
Homework Equations
The Attempt at a Solution
I know I have to use an inductive proof
Base case: z=0
the vaule returned by line 1 is 0 which is correct
Inductive Step:
Inductive Hypothesis: The algorithm works for z =n
Show: the algorithm works for z=n+1
I know I have to do both even and odd due to the mod in the function but I'm confused because I don't know what y is or c and I'm not sure where to go with it. Can someone please help me?
Last edited: