ANALYSIS OF ALGORITHM Please write a program that takes any two large arbitrary

Question

ANALYSIS OF ALGORITHM

Please write a program that takes any two large arbitrary integers (up to 256 digits per each number) as inputs, apply the divide-and-conquer algorithm of multiplication, and print the results of the multiplication of the two integers.

**THE CODE BELOW IS WHAT I HAVE NOW, I NEED HELP FINISHING THE CODE** THANKS!

//Multiplier.h

#ifndef MULTIPLIER_H
#define MULTIPLIER_H

class Multiplier

{
public:
   Multiplier(int* a, int* b, int* length)
};

#endif

*****************************

//Source.cpp

#include
#include "Multiplier.h"
#include

using namespace std;

Multiplier::Multiplier(int* new_a, int* new_b, int len)
{
   a = new_a;
   b = new_b;
   length = len;

};
  
Multiplier::Multiplier()
{

}

int* Multiplier::Multiply()
{
   int* Result = new int[length * 2];
   if (length == 1)
   {
       Result[0] = a[0] * b[0];
       return Result;
   }

   int* a1 = new int[length / 2];
   int* a2 = new int[length / 2];
   int* b1 = new int[length / 2];
   int* b2 = new int[length / 2];

   for (int i = 0; i < length / 2; i++)
   {
       a1[i] = a[i];
       a2[i] = a[length / 2 + i];
       b1[i] = b[i];
       b2[i] = b[length / 2 + i];
   }

   Multiplier m1(a1, b1, length / 2);
   Multiplier m2(a1, b2, length / 2);
   Multiplier m3(a2, b1, length / 2);
   Multiplier m4(a2, b2, length / 2);

   int *r1 = m1.Multiply();
   int *r2 = m2.Multiply();
   int *r3 = m3.Multiply();
   int *r4 = m4.Multiply();

   Result[0] = r1[0] * pow(10, length) + (r2[0] + r3[0])*pow(10, length / 2) + r4[0];
   return Result;

}

***************************************

//Main.cpp

#include
#include "Multiplier.h"

using namespace std;

int main()
{
   int A[] = { 2, 1, 0, 3 };
   int B[] = { 4, 0, 1, 4 };

   Multiplier m(A, B, 4);
   int *Result = m.Multiply();

   cout << "Multiplication of A * B == " << endl;
}

Explanation / Answer

Hi below i have written divide-and-conquer algorithm of multiplication and a sample program for your understanding,

A divide-and-conquer algorithm for integer multiplication.

function multiply(x, y)

Input: Positive integers x and y, in binary

Output: Their product

n = max(size of x, size of y)

if n = 1: return xy

xL, xR = leftmost dn/2e, rightmost bn/2c bits of x

yL, yR = leftmost dn/2e, rightmost bn/2c bits of y

P1 = multiply(xL, yL)

P2 = multiply(xR, yR)

P3 = multiply(xL + xR, yL + yR)

return P1 × 2 n + (P3 P1 P2) × 2 n/2 + P2

Sample Program:

// A utility function to multiply single bits of strings a and b

int multiplyiSingleBit(string a, string b)

{ return (a[0] - '0')*(b[0] - '0'); }

// The main function that multiplies two bit strings X and Y and returns

// result as long integer

long int multiply(string X, string Y)

{

    // Find the maximum of lengths of x and Y and make length

    // of smaller string same as that of larger string

    int n = makeEqualLength(X, Y);

    // Base cases

    if (n == 0) return 0;

    if (n == 1) return multiplyiSingleBit(X, Y);

    int fh = n/2;   // First half of string, floor(n/2)

    int sh = (n-fh); // Second half of string, ceil(n/2)

    // Find the first half and second half of first string.

    // Refer http://goo.gl/lLmgn for substr method

    string Xl = X.substr(0, fh);

    string Xr = X.substr(fh, sh);

    // Find the first half and second half of second string

    string Yl = Y.substr(0, fh);

    string Yr = Y.substr(fh, sh);

    // Recursively calculate the three products of inputs of size n/2

    long int P1 = multiply(Xl, Yl);

    long int P2 = multiply(Xr, Yr);

    long int P3 = multiply(addBitStrings(Xl, Xr), addBitStrings(Yl, Yr));

    // Combine the three products to get the final result.

    return P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2;

}

// Driver program to test aboev functions

int main()

{

    printf ("%ld ", multiply("1100", "1010"));

    printf ("%ld ", multiply("110", "1010"));

    printf ("%ld ", multiply("11", "1010"));

    printf ("%ld ", multiply("1", "1010"));

    printf ("%ld ", multiply("0", "1010"));

    printf ("%ld ", multiply("111", "111"));

    printf ("%ld ", multiply("11", "11"));

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.