---
title: Algorithm's Program 1
description: 程式作業
---

# Group 2
組員: 王承隆、賴文宏、施宗佑、王昱翔、王柏喬、莊淳方、傅文宗

# 1.
## Time complexity: $O(n^2)$

n = half length of $x$
$x = a*10^n + b$
$y = c*10^n + d$
$x*y = (a*10^n + b) * (c*10^n + d)$
$= a*c*10^{2n} + (a*d + b*c)*10^{n} + b*d$
using only int and string
## pseudocode && analysis

Psuedocode
mul(num1, num2)
    //num1 and num2 are strings of integer
    //the addition, subtract and multiplication are procedures 
        //taking two strings of integer and returning a string
    if num1*num2 doen't overflow
	    return num1*num2
    if num1[0] == '-'
        return -karatsuba(-num1, num2)
    if num2[0] == '-'
        return -karatsuba(num1, -num2)
    if num1.length() < 2 or num2.length() < 2
        return num1 * num2
    
    n = num1.length()
    splitPosition = n / 2
    
    high1 = num1[0:splitPosition-1]
    low1 = num1[splitPosition:n-1]
    high2 = num2[0:splitPosition-1]
    low2 = num2[splitPosition: n-1]
    
    z0 = karatsuba(low1, low2)
    z1 = karatsuba(low1, high2)
    z2 = karatsuba(high1, low2)
    z3 = karatsuba(high1, high2)
    return z3 * 10 ^ (2 * splitPosition) + (z1 + z2) * 10 ^ (splitPosition) + z0

4 multiplication of 2 integers of length n/2 give $4 T(n/2)$
4 additions give $O(n)$
$T(n) = 4T(n/2)+O(n)=O(n^{2}).$(by Master theorem)

## code

#include <iostream>
#include <string>
 #include <ctime> 

#define max(a,b) ((a) > (b) ? (a) : (b))

using namespace std;
string add(string lhs, string rhs);
string subtract(string lhs, string rhs);
string add(string lhs, string rhs) {
	bool lne = false, rne = false;
    if (lhs[0]=='-')
		lne = true;
	if (rhs[0]=='-')
		rne = true;
	if(lne&&rne)
		return '-'+add(lhs.substr(1,lhs.length()-1), rhs.substr(1,rhs.length()-1));
	else if(lne&&!rne)
		return subtract(rhs, lhs.substr(1,lhs.length()-1));
	else if(!lne&&rne)
		return subtract(lhs, rhs.substr(1,rhs.length()-1));
    int length = max(lhs.size(), rhs.size());
    int carry = 0;
    int sum_col;
    string result;

    while (lhs.size() < length) 
      lhs.insert(0,"0");
            
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    for (int i = length-1; i >= 0; i--) {
      sum_col = (lhs[i]-'0') + (rhs[i]-'0') + carry;
      carry = sum_col/10;
      result.insert(0,to_string(sum_col % 10));
    }
    
    if (carry)
      result.insert(0,to_string(carry));
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string subtract(string lhs, string rhs) {
	bool lne = false, rne = false;
    if (lhs[0]=='-')
		lne = true;
	if (rhs[0]=='-')
		rne = true;
	if(lne&&rne)
		return subtract(rhs.substr(1,rhs.length()-1), lhs.substr(1,lhs.length()-1));
	else if(lne&&!rne)
		return subtract(rhs, lhs.substr(1,lhs.length()-1));
	else if(!lne&&rne)
		return add(lhs, rhs.substr(1,rhs.length()-1));
    int length = max(lhs.size(), rhs.size());
    int diff;
    string result;

    while (lhs.size() < length) 
      lhs.insert(0,"0");
            
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    for (int i = length-1; i >= 0; i--) {
        diff = (lhs[i]-'0') - (rhs[i]-'0');
        if (diff >= 0)
            result.insert(0, to_string(diff));
        else {
            // borrow from the previous column
            int j = i - 1;
            while (j >= 0) {
                lhs[j] = ((lhs[j]-'0') - 1) % 10 + '0';
                if (lhs[j] != '9') 
                    break;
                else 
                    j--;
            }
            result.insert(0, to_string(diff+10));
        }
    }
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string multiply(string lhs, string rhs) {
	if (lhs[0] == '-')
		return '-'+multiply(lhs.substr(1,lhs.length()-1), rhs);
	if (rhs[0] == '-')
		return '-'+multiply(lhs, rhs.substr(1,rhs.length()-1));
    int length = max(lhs.size(), rhs.size());
    
    while (lhs.size() < length) 
      lhs.insert(0,"0");

    while (rhs.size() < length) 
      rhs.insert(0,"0");

    if (length == 1)
        return to_string((lhs[0]-'0')*(rhs[0]-'0'));

    string lhs0 = lhs.substr(0,length/2);
    string lhs1 = lhs.substr(length/2,length-length/2);
    string rhs0 = rhs.substr(0,length/2);
    string rhs1 = rhs.substr(length/2,length-length/2);
    
    string p0 = multiply(lhs0,rhs0);
    string p1 = multiply(lhs1,rhs1);
    string p2 = multiply(lhs0, rhs1);
	string p3 = multiply(lhs1, rhs0);

    for (int i = 0; i < 2*(length-length/2); i++)
        p0.append("0");
    for (int i = 0; i < length-length/2; i++)
        p2.append("0");
	for (int i = 0; i < length-length/2; i++)
        p3.append("0");
        
    string result = add(add(add(p0,p1),p2), p3);

    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
	clock_t a,b;
	a=clock(); 
    cout << multiply(s1,s2) << endl;
	b=clock();
	cout<<double(b-a)/1000;
    return 0;
}

## graph

# 2.
## Time complexity: $O(n^{lg3})$

by Karatsuba algorithm
n = half length of $x$
$x = a*10^n + b$
$y = c*10^n + d$

$x*y = (a*10^n + b) * (c*10^n + d)$
$= a*c*10^{2n} + (a*d + b*c)*10^{n} + b*d$
$= a*c*10^{2n} + ((a+b)*(c+d)-a*b - b*d)*10^{n} + b*d$
using only int and string

## pseudocode && analysis

karatsuba(num1, num2)
    //num1 and num2 are strings of integer
    //the addition, subtract and multiplication are procedures 
        //taking two strings of integer and returning a string
    if num1*num2 doen't overflow
        return num1*num2
    if num1[0] == '-'
        return -karatsuba(-num1, num2)
    if num2[0] == '-'
        return -karatsuba(num1, -num2)
    if num1.length() < 2 or num2.length() < 2
        return num1 * num2
    
    n = num1.length()
    splitPosition = n / 2
    
    high1 = num1[0:splitPosition-1]
    low1 = num1[splitPosition:n-1]
    high2 = num2[0:splitPosition-1]
    low2 = num2[splitPosition: n-1]
    
    z0 = karatsuba(low1, low2)
    z1 = karatsuba(low1+high1, low2+high2)
    z2 = karatsuba(high1, high2)
    return z2 * 10 ^ (2 * splitPosition) + (z1 - z2 - z0) * 10 ^ (splitPosition) + z0

3 multiplication of 2 integers of length n/2 give $3T(n/2)$
4 additions,and 2 subtractions of integers of at most 2n bits give $O(n)$
$T(n) = 3T(n/2)+O(n)=O(n^{log3}).$(by Master theorem)

## code

#include <iostream>
#include <string>
#include <ctime> 

#define max(a,b) ((a) > (b) ? (a) : (b))

using namespace std;
string add(string lhs, string rhs);
string subtract(string lhs, string rhs);
string add(string lhs, string rhs) {
	bool lne = false, rne = false;
    if (lhs[0]=='-')
		lne = true;
    if (rhs[0]=='-')
		rne = true;
    if(lne&&rne)
		return '-'+add(lhs.substr(1,lhs.length()-1), rhs.substr(1,rhs.length()-1));
    else if(lne&&!rne)
		return subtract(rhs, lhs.substr(1,lhs.length()-1));
    else if(!lne&&rne)
		return subtract(lhs, rhs.substr(1,rhs.length()-1));
    int length = max(lhs.size(), rhs.size());
    int carry = 0;
    int sum_col;
    string result;

    while (lhs.size() < length) 
      lhs.insert(0,"0");
            
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    for (int i = length-1; i >= 0; i--) {
      sum_col = (lhs[i]-'0') + (rhs[i]-'0') + carry;
      carry = sum_col/10;
      result.insert(0,to_string(sum_col % 10));
    }
    
    if (carry)
      result.insert(0,to_string(carry));
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string subtract(string lhs, string rhs) {
    bool lne = false, rne = false;
    if (lhs[0]=='-')
		lne = true;
	if (rhs[0]=='-')
		rne = true;
	if(lne&&rne)
		return subtract(rhs.substr(1,rhs.length()-1), lhs.substr(1,lhs.length()-1));
	else if(lne&&!rne)
		return subtract(rhs, lhs.substr(1,lhs.length()-1));
	else if(!lne&&rne)
		return add(lhs, rhs.substr(1,rhs.length()-1));
    int length = max(lhs.size(), rhs.size());
    int diff;
    string result;

    while (lhs.size() < length) 
      lhs.insert(0,"0");
            
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    for (int i = length-1; i >= 0; i--) {
        diff = (lhs[i]-'0') - (rhs[i]-'0');
        if (diff >= 0)
            result.insert(0, to_string(diff));
        else {
            // borrow from the previous column
            int j = i - 1;
            while (j >= 0) {
                lhs[j] = ((lhs[j]-'0') - 1) % 10 + '0';
                if (lhs[j] != '9') 
                    break;
                else 
                    j--;
            }
            result.insert(0, to_string(diff+10));
        }
    }
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string multiply(string lhs, string rhs) {
    if (lhs[0] == '-')
		return '-'+multiply(lhs.substr(1,lhs.length()-1), rhs);
    if (rhs[0] == '-')
		return '-'+multiply(lhs, rhs.substr(1,rhs.length()-1));
    int length = max(lhs.size(), rhs.size());
    
    while (lhs.size() < length) 
      lhs.insert(0,"0");

    while (rhs.size() < length) 
      rhs.insert(0,"0");

    if (length == 1)
        return to_string((lhs[0]-'0')*(rhs[0]-'0'));

    string lhs0 = lhs.substr(0,length/2);
    string lhs1 = lhs.substr(length/2,length-length/2);
    string rhs0 = rhs.substr(0,length/2);
    string rhs1 = rhs.substr(length/2,length-length/2);
    
    string p0 = multiply(lhs0,rhs0);
    string p1 = multiply(lhs1,rhs1);
    string p2 = multiply(add(lhs0,lhs1),add(rhs0,rhs1));
    string p3 = subtract(p2,add(p0,p1));

    for (int i = 0; i < 2*(length-length/2); i++)
        p0.append("0");
    for (int i = 0; i < length-length/2; i++)
        p3.append("0");
        
    string result = add(add(p0,p1),p3);

    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
	clock_t a,b;
	a=clock(); 
    cout << multiply(s1,s2) << endl;
	b=clock();
	cout<<double(b-a)/1000;
    return 0;
}

## graph