User:BIMEG1

From www.norsemathology.org

Jump to: navigation, search

Topic: Using recursive thinking to improve the efficiency of an iterative algorithm.

Contents

Introduction.

Recursive thinking can be defined as the process of solving large problems by breaking them down into smaller, simpler problems that have identical forms. Computer scientist are always aiming for efficient and shortest means to solve a problem. Using a recursive approach is one of the many ways complex computations are carried out.

Project Description.

In this project, I am going to be demonstrating how linear approach to multiplication of values with large exponents is not efficient compared to doing the same computations of values with huge exponents using recursive approach is much efficient. I will be using the C++ object oriented programming language. The code is in a class called “MAT385Project.cpp”, and a header file “MAT385Project.h” with a default constructor, a destructor, six methods and one private member variable. There is also a main() method in the main.cpp file which is acting as the point if entry when the program first executes.

Code Analysis.

In the main(), the MAT385Project object is created. Two variables number and exponent are declare to hold the values from user input used to carried the multiplication which in English is described as number raised to the power exponent. When the user enters the inputs, they are verified by the methods verifyDouble() and verifyInteger(). verifyDouble() takes as argument a floating point value and verifies that the first input is none other than a floating point number and returns the value if the user input is valid. verifyInteger() takes as argument an integer and verifies that the second input is none other than an integer and returns the value if the user input is valid. The verifyDouble() and verifyInteger() asks the user to enter a valid input using a do-while loop. The loop ends when the user enters the correct value.

The getCount() method returns the number of times each multiplication approach loops while performing the calculations. The counter member variable gets reset to zero accordingly by the various multiplication methods before the counting begins.

When the user input verification is done, the values are passed as argument to methods multiplyWithoutRecursion() and multiplyWithRecursion() which both take as argument the verifiedNumber and verifiedExponent variables as argument and computes the multiplication of the verifiedNumber raised to the power verifiedExponent. multiplyWithoutRecursion() and multiplyWithRecursion() checks if the verifiedExponent is zero. If it is zero, the return one. If verifiedExponent is one, they return the verifiedNumber. If the verifiedExponent is greater than one and verifiedNumber is greater than zero, multiplyWithoutRecursion() loops for “verifiedExponent” times and in each iteration, verifiedNumber is multiplied by the valued of the result variable and the value is stored in the result variable. When the loop is done, the results is return and the counter member variable gets incremented after each loop. Until the user inputs a valid value in terms of an integer and a double, the loop will keep asking them to provide the correct value. Some important library methods that play a key role in verifying user input in the verifyDouble() and verifyInteger() methods include:

The cin.fail() function returns true when an input failure occurs. In this case it would be an input that is not an integer or a floating point number. If user input fails, then the input buffer is kept in an error state.

cin.clear() is then used to clear the error state of the buffer so that further processing of input can take place. This ensures that the input does not lead to an infinite loop of error message display.

The cin.ignore() function is used to ignore the rest of the line after the first instance of error that has occurred and it skips to or moves to the next line. cin.eof() function can be used to check end of file errors. This returns 1 if the program tried reading something but, it was from the end of the file.

Furthermore, in the method multiplyWithRecursion(), the method takes two arguments a floating point number and an integer. This method calls the tail recursive helper method that carries out the multiplication. recursiveHelper() method takes three arguments, the floating point number, the integer which acts as the exponent of the floating point number and an auxiliary value. The result variable in the recursiveHelper() acts as an accumulator to hold the results of the multiplications. To simplify this multiplication process, the recursive helper method checks if the exponent input is zero then it returns the value of the accumulator.

                             result*number0=result

If the value of the exponent is greater than zero and the exponent is even, the counter variable is incremented, the recursive helper method calls itself which gets passed the auxiliary value, the value of the floating point number gets doubled, then the value of the exponent gets divided by two.

   result*numberexponent=result*(number2)exponent/2 if exponent > 0 and exponent % 2 = 0

Finally, if the value of the exponent is greater than zero and the exponent is odd, the counter variable gets incremented, the recursive helper method calls itself and in the arguments, the auxiliary value gets multiplied by the floating point number, the floating point number gets doubled and the exponent gets divided by two.

     result*numberexponent=(result*number)*(number2)exponent/2  if exponent > 0 and exponent % 2 != 0

Conclusion.

In conclusion, it should be noted that using a recursive approach to solve a problem does not work on every problem. This is due to the fact that as an application is growing bigger, there is need for optimization in situations where the recursive approach doe does not hold anymore. Example of problems that recursive approach to problem solving is not feasible include “NP” problems in computer science.

Source Code.

MAT385Project.h

#ifndef SOURCECODE_MAT385PROJECT_H

#define SOURCECODE_MAT385PROJECT_H

class MAT385Project {

public:

   explicit MAT385Project();
   ~MAT385Project();
   double multiplyWithoutRecursion(double number, int exponent);
   int getCount();
   double recursiveHelper(double auxiliary, double  number, int exponent);
   double multiplyWithRecursion(double  number, int exponent);
   double verifyDouble(double number);
   int verifyInteger(int exponent);

private:

    int counter;

};

#endif //SOURCECODE_MAT385PROJECT_H


MAT385Project.cpp

#include "MAT385Project.h"

#include <iostream>

#include <limits>

using namespace std;

MAT385Project::MAT385Project() {}

MAT385Project::~MAT385Project() {}

double MAT385Project::multiplyWithoutRecursion(double number, int exponent) {

   counter = 0;
   double result = 1.0;
   if (exponent == 0){
       return result;
   } else if(exponent == 1){
       return number;
   } else if(exponent > 1 && number > 0){
       for(int i = 0; i < exponent; i++){
           result *= number;
           counter++;
       }
   }
   return result;

}

double MAT385Project::recursiveHelper(double auxiliary, double number, int exponent) {

   double result = 0.0;
   if (exponent == 0){
       counter++;
       result = auxiliary;
   } else if(exponent > 0 && exponent % 2 == 0){
       counter++;
       result = recursiveHelper(auxiliary, number * number, exponent / 2);
   } else{
       counter++;
       result = recursiveHelper(auxiliary * number, number * number, (exponent) / 2);
   }
   return result;

}

double MAT385Project::multiplyWithRecursion(double number, int exponent) {

   counter = 0;
   return recursiveHelper(1, number, exponent);

}

int MAT385Project::getCount() {

   return counter;

}

double MAT385Project::verifyDouble(double number) {

   do {
       if (cin.fail()){
           cin.clear();
           cin.ignore(numeric_limits<streamsize>::max(), '\n');
           cout<<"Please try again: ";
           cin >> number;
       }
   } while (cin.fail());
   return number;

}

int MAT385Project::verifyInteger(int exponent) {

   do {
       if (cin.fail()) {
           cin.clear();
           cin.ignore(numeric_limits<streamsize>::max(), '\n');
           cout << "Please try again: ";
           cin>>exponent;
       }
   } while (cin.fail());
   return exponent;

}


main.cpp

#include "MAT385Project.h"

#include <iostream>

using namespace std;

int main(){

   MAT385Project mat385Project;
   double number = 0.0;
   int exponent = 0;
   double verifiedNumber = 0.0;
   int verifiedExponent = 0;
   cout<<"Enter a double value less than 2 and greater than 1: ";
   cin>>number;
   verifiedNumber = mat385Project.verifyDouble(number);
   cout << endl;
   cout<<"Enter an integer value from 500 to 1000: ";
   cin>> exponent;
   verifiedExponent = mat385Project.verifyInteger(exponent);
   cout << endl;
   double resultWithoutRecursion = mat385Project.multiplyWithoutRecursion(verifiedNumber, verifiedExponent);
   cout <<"Case one:" << endl;
   cout <<"Without recursion, " << verifiedNumber << " ^ " << verifiedExponent << " is " << resultWithoutRecursion << endl;
   cout << mat385Project.getCount() << " multiplications without recursion were carried out." << endl;
   cout <<"\nCase two:" << endl;
   double resultWithRecursion = mat385Project.multiplyWithRecursion(verifiedNumber, verifiedExponent);
   cout << "With recursion, " << verifiedNumber << " ^ " << verifiedExponent << " is " << resultWithRecursion << endl;
   cout << mat385Project.getCount() << " recursive multiplications were carried out." << endl;
   return 0;

}

Sample Output.

For demonstration purposes, the user is recommended the range of the values to input. However, other values can still work. The image below shows a sample output when a user inputs the values without any errors.

Image:outputImage.png

Personal tools