CODEWITHSUNDEEP
c++algorithm
user466534
user466534

Reputation:

How to prove correctness of following algorithm?

i need to prove that following algorithm works correctly,i know induction,but don't know how to use it here?also i will be happy if would know complexity of algorithm,how optimal it is? what is it's run time?please help me

#include <cstdlib>
#include <iostream>
#define c 2
//we should take c   more ot equal  then 2
using namespace std;
int multiply(int y,int z){
      // product yz
    if(z==0) return 0;
    return (multiply(c*y,int(z/c))+y*(z %c));
}

int main(int argc, char *argv[])
{
    int y=5;
    int z=7;
    cout<<multiply(y,z)<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

thanks

Upvotes: 0

Views: 826

Answers (4)

celtschk
celtschk

Reputation: 19721

Since this is a homework, I'm only going to give hints.

First, there's an if in the function. In the case of z=0, proving correctness is trivial.

Next, if z>0, then there are two things to check:

First, the invariant: You have to check that, assuming multiply works correctly with the recursive call, the value returned is indeed the product of the two numbers.

Second: You have to prove that this function eventually returns, i.e. that no matter which numbers you give, eventually you'll get to the point where the function doesn't recursively call itself any more. A hint for this: Look at the binary representation of the arguments, and what multiplication by two and division by two do to it.

At that point, it should also be easy to determine the complexity of the algorithm.

Upvotes: 4

Naveen Babu
Naveen Babu

Reputation: 1584

  1. i would not use '*' operator

    multiply(c*y,int(z/c))+y*(z %c)

should be

multiply(multiply(c,y),int(z/c))+multiply(y,(z %c))
  1. as Josep has mentioned do calculation using '*' operator and do the same using ur multiply(). compare results to a level of precision.

  2. for getting time run. before executing the time method in main method. call time library

    time_t startTime= time (NULL); cout<<multiply(y,z)<<endl; time_t endTime= time (NULL); cout<<(endTime-startTime)<<" sec";

Upvotes: 0

jpalecek
jpalecek

Reputation: 47762

1) for z=0 your function is obviously correct

2) suppose multiply(x, y) returns x*y for 0 <= y < y0. Then

  x*y
= x*((y/c)*c + y%c)    # by the definition of %
= x*c*(y/c) + x*(y%c)  # distributive, commutative laws
= multiply(x*c, y/c) + x*(y%c) # 0 <= y/c < y, induction hypothesis

Upvotes: 5

duedl0r
duedl0r

Reputation: 9424

Extract a formula for an iteration. Then prove it for n=1, n=2, .. After that prove the step n => n+1.. if you don't know how to do that ask at https://math.stackexchange.com/

Upvotes: 1

Related Questions