Data Structures Program 1

#include <iostream>
#include <string>
#include <cstdlib>
#include "sqroot.h"
#include "LL.h"
using namespace std;

int main (int argc, char **argv) {

    cout << "Enter a radicand:";
    string in;
    getline (cin,in);
    root(in);
    system ("pause");
    return 0;
}
//implements string multiplications
string mult (string a, string b) {
    //makes a place for us to store our output
    string out = "";
    //interates through the both the strings
    for (int i=0; i < (int)a.length(); i++)
        for (int j=0; j < (int)b.length(); j++) {
            //multiplies each value
            int p = (a[i]-'0')*(b[j]-'0');
            //breaks that value into the first digit and the second digit
            string pstr = ((string)"")+(char)(p/10+'0')+(char)(p%10+'0');
            //adds zeroes to get to the place that i is at
            for (int k=0; k < (int)a.length()-i-1 + (int)b.length()-j-1; k++)
                pstr += "0";
            //adds the output of that case of multiplication to the output
            out = sum (out,pstr);
        }
    return out;
}
//implements string addition
string sum (string a, string b) {
    string out = "";
    while (a.length() < b.length()) a = "0"+a;
    while (b.length() < a.length()) b = "0"+b;
    int carry = 0;
    for (int i=a.length()-1; i >= 0; i--) {
        int l = a[i]-'0' + b[i]-'0' + carry;
        carry = l/10;
        l %= 10;
        out = ((char)(l+'0')) + out;
    }
    if (carry == 1){
        out ="1" + out;
    }
    return out;
}
//implements string subtraction
string sub (string a, string b){
    string out = "";
    while (b.length() < a.length()){
        b = "0"+b;
    }
    for (int i=b.length()-1; i>= 0; i--) {
        int k= b[i]-'0';
        k= 9-k;
        out=(char)(k+'0') + out;
    }
    out = sum(out,"1");
    out = sum(a,out);
    out[0]= '0';
    return out;
}
//does the meat and potatoes of the program, square roots
void root (string input){
    string rem = input;
    string ans = "0";
    //get the linked list of powers of 4
    LL fours = LL ();
    fours.addtofront("1");
    while (comp(rem,mult(fours.head->word,"4"))){
        fours.addtofront(mult(fours.head->word,"4"));
    }
    /*while(fours.head!=NULL){
        cout<<"squares: "<<endl;
        cout<<fours.head->word<<endl;
        fours.pop();
    }*/
    string check;
    while(fours.head!=NULL){
        //check = table value*(4*ans+1)
        check = mult(fours.head->word, sum(mult("4",ans),"1"));
        //Implement the decision of the formula as to whether to just multiply by two or add one afterwards
        //multiplies the answer by two and adds one if rem is greater than the sum of the previous formula
        if(comp(rem,check)){
            //subtracts the value of the formula from the remainder
            rem = sub(rem,check);
            ans = sum(mult(ans,"2"),"1");
            fours.pop();
        }
        //if the remainder is less than the formula value just multiply remainder by 2
        else{
            ans = mult(ans,"2");
            fours.pop();
        }
    }
    //cuts leading zeroes off everything
    input=realzero(input);
    ans=realzero(ans);
    rem=realzero(rem);
    //prints off the final line
    cout<<"the square root of " + input + " is " + ans + " and the remainder is " + rem<<endl;
}
//returns if a is larger than b as a number
bool comp(string a,string b){
    //removes leading zeroes as they'd screw up the length check
    a=realzero(a);
    b=realzero(b);
    //finds if a or b has more character than the other and returns if a is either longer or shorter than b if true
    if (a.length()>b.length())return true;
    else if (a.length()<b.length())return false;
    //if that check didn't work we move into checking every individual character to see if there is any discrepancy
    for(int i = 0; i<a.length(); i++){
        //only check a value if they don't equal each other
        if ((int)a[i]!=(int)b[i]){
            //returns if at the first non equal value is less
            if((int)a[i]<(int)b[i]){
                return false;
            }
            //If it isn't equal or lesser only greater than is left to return, also if both values are equal it will return true, because that's what the implementations need.
            else return true;

        }
    }
    //extra return just in case, should not get down here under normal circumstances
    return true;
}
//removes leading zeroes
string realzero(string a){
    while (a!="" && a[0]=='0') a = a.substr(1);
    if (a=="") a= "0";
    return a;
}