big_rational.cpp

#include "big_rational.h"
#include <bits/stdc++.h>

BigRational::BigRational(const string& num, const string& den, int s) {
    numerator = num;
    denominator = den;
    sign = s;
}

string remove_leading_zeros(const string& num) {
    if (num.empty()) return "0";
    
    int i = 0;
    while (i < num.size() - 1 && num[i] == '0') {
        i++;
    }
    return num.substr(i);
}

namespace {
    int TRIG_PRECISION = 5;  // Reduced for practical speed
    int MAX_FRACTION_SIZE = 100; // Limit fraction string length
}

void set_trig_precision(int precision) {
    if (precision < 5 || precision > 50) {
        throw invalid_argument("Precision must be between 5 and 50");
    }
    TRIG_PRECISION = precision;
}

int get_trig_precision() {
    return TRIG_PRECISION;
}

static string factorial(int n) {
    if (n == 0 || n == 1) return "1";
    if (n < 0) throw invalid_argument("Factorial of negative number");
    
    string result = "1";
    for (int i = 2; i <= n; i++) {
        result = mul_strings(result, to_string(i));
    }
    return result;
}

/**
 * OPTIMIZED: Reduce fraction size periodically during calculation
 */
static BigRational smart_normalize(const BigRational& r) {
    BigRational result = r;
    
    if (is_zero(result.numerator)) {
        return BigRational("0", "1", 1);
    }
    
    // If fraction is getting too large, normalize it
    if (result.numerator.length() > MAX_FRACTION_SIZE || 
        result.denominator.length() > MAX_FRACTION_SIZE) {
        
        string gcd_val = gcd_strings(result.numerator, result.denominator);
        if (gcd_val != "1" && gcd_val.length() > 1) {
            result.numerator = div_strings(result.numerator, gcd_val);
            result.denominator = div_strings(result.denominator, gcd_val);
        }
    }
    
    return result;
}

static BigRational power_rational(const BigRational& base, int exp) {
    if (exp == 0) return BigRational("1", "1", 1);
    if (exp == 1) return base;
    
    if (exp < 0) {
        BigRational pos_power = power_rational(base, -exp);
        return division_rational(BigRational("1", "1", 1), pos_power);
    }
    
    // Use binary exponentiation
    BigRational result("1", "1", 1);
    BigRational temp = base;
    
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = multiplication_rational(result, temp);
            result = smart_normalize(result); // Normalize periodically
        }
        temp = multiplication_rational(temp, temp);
        temp = smart_normalize(temp); // Normalize periodically
        exp /= 2;
    }
    
    return result;
}

static BigRational reduce_angle(const BigRational& angle) {
    if (is_zero(angle.numerator)) {
        return BigRational("0", "1", 1);
    }

    BigRational two_pi("62831", "10000", 1);
    
    // Step 1: Convert both angle and 2π to common denominator
    string common_denom = mul_strings(angle.denominator, two_pi.denominator);
    
    // Scale numerators to common denominator
    string angle_num_scaled = mul_strings(angle.numerator, two_pi.denominator);
    string two_pi_num_scaled = mul_strings(two_pi.numerator, angle.denominator);
    
    // Step 2: Perform modulo operation on the scaled numerators
    // This gives us: (angle_numerator % two_pi_numerator) / common_denominator
    string result_num;
    int result_sign;
    
    if (angle.sign == 1) {
        // Positive angle: simple modulo
        result_num = mod_strings(angle_num_scaled, two_pi_num_scaled);
        result_sign = 1;
    } else {
        // Negative angle: compute modulo then adjust
        result_num = mod_strings(angle_num_scaled, two_pi_num_scaled);
        
        if (is_zero(result_num)) {
            result_sign = 1;
        } else {
            // For negative: 2π - (|angle| mod 2π)
            result_num = sub_strings(two_pi_num_scaled, result_num);
            result_sign = 1;
        }
    }
    
    // Step 3: Create result with common denominator
    BigRational result(result_num, common_denom, result_sign);
    
    // Step 4: Normalize to reduce fraction
    return normalize_rational(result);
}

// Convert rational -> long double
static long double rational_to_ld_rad(const BigRational &r) {
    long double num = stold(r.numerator);
    long double den = stold(r.denominator);
    long double val = num / den;
    if (r.sign == -1) val = -val;
    return val;
}

// Convert long double -> BigRational with 1e12 precision
static BigRational ld_to_rational_rad(long double x) {
    int sign = (x < 0 ? -1 : 1);
    if (x < 0) x = -x;

    long double scaled = x * 1000000000000.0L; // 1e12
    long long integer = (long long) llround(scaled);

    return normalize_rational(BigRational(
        to_string(integer),
        "1000000000000",
        sign
    ));
}
//-------------------TRIGNOMETRIC FUNCTIONS-------------

// ------------------- SIN -------------------
BigRational sine_rational(const BigRational& x) {
    long double val = sinl(rational_to_ld_rad(x));
    return ld_to_rational_rad(val);
}

// ------------------- COS -------------------
BigRational cosine_rational(const BigRational& x) {
    long double val = cosl(rational_to_ld_rad(x));
    return ld_to_rational_rad(val);
}

// ------------------- TAN -------------------
BigRational tangent_rational(const BigRational& x) {
    long double c = cosl(rational_to_ld_rad(x));
    if (fabsl(c) < 1e-18L)
        throw invalid_argument("Tangent undefined (cos(x)=0)");
    long double val = tanl(rational_to_ld_rad(x));
    return ld_to_rational_rad(val);
}

// ------------------- CSC -------------------
BigRational cosecant_rational(const BigRational& x) {
    long double s = sinl(rational_to_ld_rad(x));
    if (fabsl(s) < 1e-18L)
        throw invalid_argument("Cosecant undefined (sin(x)=0)");
    return ld_to_rational_rad(1.0L / s);
}

// ------------------- SEC -------------------
BigRational secant_rational(const BigRational& x) {
    long double c = cosl(rational_to_ld_rad(x));
    if (fabsl(c) < 1e-18L)
        throw invalid_argument("Secant undefined (cos(x)=0)");
    return ld_to_rational_rad(1.0L / c);
}

// ------------------- COT -------------------
BigRational cotangent_rational(const BigRational& x) {
    long double s = sinl(rational_to_ld_rad(x));
    if (fabsl(s) < 1e-18L)
        throw invalid_argument("Cotangent undefined (sin(x)=0)");
    long double c = cosl(rational_to_ld_rad(x));
    return ld_to_rational_rad(c / s);
}

// Initialize global data structures
stack<HistoryEntry> calculationHistory;
queue<OperationQueueEntry> operationQueue;

// ============ HISTORY MANAGEMENT FUNCTIONS ============

void add_to_history(const BigRational& op1, const BigRational& op2, 
                   const BigRational& result, const string& operation) {
    calculationHistory.push(HistoryEntry(op1, op2, result, operation));
}

void display_history(bool decimal_mode) {
    if (calculationHistory.empty()) {
        cout << "No history available." << endl;
        return;
    }
    
    stack<HistoryEntry> tempStack = calculationHistory;
    vector<HistoryEntry> entries;
    
    while (!tempStack.empty()) {
        entries.push_back(tempStack.top());
        tempStack.pop();
    }
    
    cout << "\n========== CALCULATION HISTORY ==========" << endl;
    cout << "Total entries: " << entries.size() << endl << endl;
    
    for (int i = entries.size() - 1; i >= 0; i--) {
        cout << "Entry " << (entries.size() - i) << ": ";
        
        if (entries[i].operand1.sign == -1) cout << "-";
        if (decimal_mode) {
            cout << to_decimal(entries[i].operand1, 6);
        } else {
            cout << entries[i].operand1.numerator;
            if (entries[i].operand1.denominator != "1") 
                cout << "/" << entries[i].operand1.denominator;
        }
        
        cout << " " << entries[i].operation << " ";
        
        if (entries[i].operand2.sign == -1) cout << "-";
        if (decimal_mode) {
            cout << to_decimal(entries[i].operand2, 6);
        } else {
            cout << entries[i].operand2.numerator;
            if (entries[i].operand2.denominator != "1") 
                cout << "/" << entries[i].operand2.denominator;
        }
        
        cout << " = ";
        
        if (entries[i].result.sign == -1) cout << "-";
        if (decimal_mode) {
            cout << to_decimal(entries[i].result, 6);
        } else {
            cout << entries[i].result.numerator;
            if (entries[i].result.denominator != "1") 
                cout << "/" << entries[i].result.denominator;
        }
        
        cout << endl;
    }
    cout << "=========================================" << endl << endl;
}

void clear_history() {
    while (!calculationHistory.empty()) {
        calculationHistory.pop();
    }
    cout << "History cleared." << endl;
}

BigRational get_last_result() {
    if (calculationHistory.empty()) {
        throw runtime_error("No history available");
    }
    return calculationHistory.top().result;
}

bool history_is_empty() {
    return calculationHistory.empty();
}

// ============ QUEUE MANAGEMENT FUNCTIONS ============

void enqueue_operation(const BigRational& op1, const BigRational& op2, const string& operation) {
    operationQueue.push(OperationQueueEntry(op1, op2, operation));
    cout << "Operation added to queue. Queue size: " << operationQueue.size() << endl;
}

void process_queue(bool decimal_mode) {
    if (operationQueue.empty()) {
        cout << "Queue is empty. No operations to process." << endl;
        return;
    }
    
    cout << "\n========== PROCESSING QUEUED OPERATIONS ==========" << endl;
    int count = 1;
    
    while (!operationQueue.empty()) {
        OperationQueueEntry entry = operationQueue.front();
        operationQueue.pop();
        
        cout << "\nOperation " << count++ << ": ";
        BigRational result;
        
        try {
            if (entry.operation == "+") {
                result = perform_addition(entry.operand1, entry.operand2, true);
            } else if (entry.operation == "-") {
                result = perform_subtraction(entry.operand1, entry.operand2, true);
            } else if (entry.operation == "*") {
                result = perform_multiplication(entry.operand1, entry.operand2, true);
            } else if (entry.operation == "/") {
                result = perform_division(entry.operand1, entry.operand2, true);
            } else {
                cout << "Unknown operation: " << entry.operation << endl;
                continue;
            }
            
            print_rational(result, decimal_mode);
        } catch (const exception& e) {
            cout << "Error: " << e.what() << endl;
        }
    }
    
    cout << "=========================================" << endl << endl;
}

void display_queue(bool decimal_mode) {
    if (operationQueue.empty()) {
        cout << "Queue is empty." << endl;
        return;
    }
    
    queue<OperationQueueEntry> tempQueue = operationQueue;
    cout << "\n========== QUEUED OPERATIONS ==========" << endl;
    cout << "Total operations in queue: " << tempQueue.size() << endl << endl;
    
    int count = 1;
    while (!tempQueue.empty()) {
        OperationQueueEntry entry = tempQueue.front();
        tempQueue.pop();
        
        cout << count++ << ". ";
        
        if (entry.operand1.sign == -1) cout << "-";
        if (decimal_mode) {
            cout << to_decimal(entry.operand1, 6);
        } else {
            cout << entry.operand1.numerator;
            if (entry.operand1.denominator != "1") 
                cout << "/" << entry.operand1.denominator;
        }
        
        cout << " " << entry.operation << " ";
        
        if (entry.operand2.sign == -1) cout << "-";
        if (decimal_mode) {
            cout << to_decimal(entry.operand2, 6);
        } else {
            cout << entry.operand2.numerator;
            if (entry.operand2.denominator != "1") 
                cout << "/" << entry.operand2.denominator;
        }
        
        cout << endl;
    }
    cout << "=========================================" << endl << endl;
}

void clear_queue() {
    while (!operationQueue.empty()) {
        operationQueue.pop();
    }
    cout << "Queue cleared." << endl;
}

bool queue_is_empty() {
    return operationQueue.empty();
}

// ============ ENHANCED OPERATION FUNCTIONS ============

BigRational perform_addition(const BigRational& a, const BigRational& b, bool record_history) {
    BigRational result = addition_rational(a, b);
    if (record_history) {
        add_to_history(a, b, result, "+");
    }
    return result;
}

BigRational perform_subtraction(const BigRational& a, const BigRational& b, bool record_history) {
    BigRational result = subtraction_rational(a, b);
    if (record_history) {
        add_to_history(a, b, result, "-");
    }
    return result;
}

BigRational perform_multiplication(const BigRational& a, const BigRational& b, bool record_history) {
    BigRational result = multiplication_rational(a, b);
    if (record_history) {
        add_to_history(a, b, result, "*");
    }
    return result;
}

BigRational perform_division(const BigRational& a, const BigRational& b, bool record_history) {
    BigRational result = division_rational(a, b);
    if (record_history) {
        add_to_history(a, b, result, "/");
    }
    return result;
}

bool is_zero(const string& num) {
    return remove_leading_zeros(num) == "0";
}

string string_abs(const string& num) {
    if (num[0] == '-') {
        return num.substr(1);
    }
    return num;
}

bool compare_strings(const string& a, const string& b) {
    string a_clean = remove_leading_zeros(a);
    string b_clean = remove_leading_zeros(b);
    
    if (a_clean.length() > b_clean.length()) return true;
    if (a_clean.length() < b_clean.length()) return false;
    
    return a_clean >= b_clean;
}

string add_strings(const string& a, const string& b) {
    string result;
    int carry = 0;
    int i = a.length() - 1;
    int j = b.length() - 1;
    
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        
        carry = sum / 10;
        result.push_back((sum % 10) + '0');
    }
    
    reverse(result.begin(), result.end());
    return remove_leading_zeros(result);
}

string sub_strings(const string& a, const string& b) {
    if (!compare_strings(a, b)) {
        return sub_strings(b, a);
    }
    
    string result;
    int borrow = 0;
    int i = a.length() - 1;
    int j = b.length() - 1;
    
    while (i >= 0) {
        int digit_a = a[i--] - '0';
        int digit_b = (j >= 0) ? b[j--] - '0' : 0;
        
        digit_a -= borrow;
        if (digit_a < digit_b) {
            digit_a += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        result.push_back((digit_a - digit_b) + '0');
    }
    
    reverse(result.begin(), result.end());
    return remove_leading_zeros(result);
}

string mul_strings(const string& a, const string& b) {
    if (is_zero(a) || is_zero(b)) return "0";
    
    int n = a.length(), m = b.length();
    vector<int> result(n + m, 0);
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int sum = mul + result[i + j + 1];
            
            result[i + j + 1] = sum % 10;
            result[i + j] += sum / 10;
        }
    }
    
    string product;
    for (int num : result) {
        product.push_back(num + '0');
    }
    product = remove_leading_zeros(product);    
    return product.empty() ? "0" : product;
}

string div_by_2(const string& num) {
    if (num == "0") return "0";
    
    string result;
    int carry = 0;
    
    for (char digit_char : num) {
        int digit = (digit_char - '0') + carry * 10;
        result.push_back((digit / 2) + '0');
        carry = digit % 2;
    }
    
    return remove_leading_zeros(result);
}

string div_strings(const string& a, const string& b) {
    if (is_zero(b)) {
        throw invalid_argument("Division by zero");
    }

    string a_clean = remove_leading_zeros(a);
    string b_clean = remove_leading_zeros(b);

    if (!compare_strings(a_clean, b_clean)) {
        return "0";
    }

    if (b_clean == "1") {
        return a_clean;
    }

    if (a_clean == b_clean) {
        return "1";
    }

    string low = "1";
    string high = a_clean;
    string result = "0";
    
    while (compare_strings(high, low)) {
        string mid = div_by_2(add_strings(low, high));
        string product = mul_strings(mid, b_clean);

        if (product == a_clean) {
            return mid;
        }
        
        if (compare_strings(product, a_clean)) {
            result = mid;
            high = sub_strings(mid, "1");
        } else {
            low = add_strings(mid, "1");
        }
    }
    
    if (compare_strings(mul_strings(result, b_clean), a_clean) && 
        mul_strings(result, b_clean) != a_clean) {
        result = sub_strings(result, "1");
    }
    
    return result;
}

string mod_strings(const string& a, const string& b) {
    if (is_zero(b)) {
        throw invalid_argument("Modulus by zero");
    }
    if (!compare_strings(a, b)) {
        return a;
    }
    string quotient = div_strings(a, b);
    string product = mul_strings(quotient, b);
    return sub_strings(a, product);
}

string gcd_strings(const string& a, const string& b) {
    if (is_zero(b)) {
        return a;
    }
    return gcd_strings(b, mod_strings(a, b));
}

BigRational normalize_rational(const BigRational& r) {
    BigRational result = r;
    
    if (is_zero(result.numerator)) {
        result.sign = 1;
        result.denominator = "1";
        return result;
    }
    
    if (result.denominator[0] == '-') {
        result.sign *= -1;
        result.denominator = result.denominator.substr(1);
    }
    
    string gcd_val = gcd_strings(result.numerator, result.denominator);
    if (gcd_val != "1") {
        result.numerator = div_strings(result.numerator, gcd_val);
        result.denominator = div_strings(result.denominator, gcd_val);
    }
    
    return result;
}

BigRational addition_rational(const BigRational& a, const BigRational& b) {
    string term1 = mul_strings(a.numerator, b.denominator);
    string term2 = mul_strings(b.numerator, a.denominator);
    
    string new_num;
    int new_sign;
    
    if (a.sign == b.sign) {
        new_num = add_strings(term1, term2);
        new_sign = a.sign;
    } else {
        if (compare_strings(term1, term2)) {
            new_num = sub_strings(term1, term2);
            new_sign = a.sign;
        } else {
            new_num = sub_strings(term2, term1);
            new_sign = b.sign;
        }
    }
    
    string new_den = mul_strings(a.denominator, b.denominator);
    return normalize_rational(BigRational(new_num, new_den, new_sign));
}

BigRational subtraction_rational(const BigRational& a, const BigRational& b) {
    BigRational negative_b = b;
    negative_b.sign *= -1;
    return addition_rational(a, negative_b);
}

BigRational multiplication_rational(const BigRational& a, const BigRational& b) {
    string new_num = mul_strings(a.numerator, b.numerator);
    string new_den = mul_strings(a.denominator, b.denominator);
    
    if (is_zero(new_den)) {
        throw invalid_argument("Division by zero in multiplication result");
    }
    
    int new_sign = a.sign * b.sign;
    
    return normalize_rational(BigRational(new_num, new_den, new_sign));
}

BigRational division_rational(const BigRational& a, const BigRational& b) {
    if (is_zero(b.numerator)) {
        throw invalid_argument("Division by zero");
    }
    
    BigRational reciprocal(b.denominator, b.numerator, b.sign);
    return multiplication_rational(a, reciprocal);
}

string to_decimal(const BigRational& r, int precision) {
    if (is_zero(r.numerator)) {
        return "0";
    }
    
    string integer_part = div_strings(r.numerator, r.denominator);
    string remainder = mod_strings(r.numerator, r.denominator);
    
    if (is_zero(remainder)) {
        return integer_part;
    }
    
    string decimal_part;
    for (int i = 0; i < precision; i++) {
        remainder = mul_strings(remainder, "10");
        string digit = div_strings(remainder, r.denominator);
        remainder = mod_strings(remainder, r.denominator);
        decimal_part += digit;
    }
    
    return integer_part + "." + decimal_part;
}

void print_rational(const BigRational& r, bool decimal_output) {
    cout << "Result : " << endl;
    if (decimal_output) {
        string decimal = to_decimal(r, 6);
        if (r.sign == -1) {
            cout << "-";
        }
        cout << decimal;
    } else {
        if (r.sign == -1) {
            cout << "-";
        }
        cout << r.numerator;
        if (r.denominator != "1") {
            cout << "/" << r.denominator;
        }
    }
    cout << endl;
}

string skip_whitespace(string &input) {
    int i;
    for (i = 0; i < input.length(); i++) {
        if (!isspace(input[i])) {
            break;
        }
    }
    return input.substr(i);
}

BigRational input_number(bool decimal_input) {
    int j = 0;
    string input;
    BigRational number;
    number.sign = 1;
    number.numerator = "";
    number.denominator = "";

    getline(cin >> std::ws, input);
    input = skip_whitespace(input);

    while (j < input.length() && (input[j] == '+' || input[j] == '-')) {
        if (input[j] == '-') {
            number.sign *= -1;
        }
        j++;
    }

    for (int i = j; i < input.length(); i++) {
        if (isspace(input[i])) {
            continue;
        }
        if (isdigit(input[i])) {
            number.numerator += input[i];
        }
        else if (input[i] == '/' || input[i] == '.') {
            if (decimal_input && input[i] == '/') {
                throw invalid_argument("Invalid input: Decimal mode does not support fractions.");
            }
            if (!decimal_input && input[i] == '.') {
                throw invalid_argument("Invalid input: Fractional mode does not support decimals.");
            }
            
            number.denominator = "";
            i++;
            
            int decimal_places = 0;
            
            for (; i < input.length(); i++) {
                if (isspace(input[i])) {
                    continue;
                }
                if (isdigit(input[i])) {
                    number.denominator += input[i];
                    if (decimal_input) {
                        decimal_places++;
                    }
                }
                else {
                    throw invalid_argument("Invalid character in denominator/decimal part.");
                }
            }
            
            if (decimal_input) {
                number.numerator += number.denominator;
                number.denominator = "1";
                for (int k = 0; k < decimal_places; k++) {
                    number.denominator += "0";
                }
            }
            break;
        }
        else {
            throw invalid_argument("Invalid character in numerator.");
        }
    }
    
    if (number.denominator.empty()) {
        number.denominator = "1";
    }
    
    return number;
}

BigRational input_rational(bool decimal_input)
{

    cout << "Enter rational number: " << endl;
    BigRational number;
    number = input_number(decimal_input);
    return normalize_rational(number);
}

// Function to input a rational number in hex or decimal
BigRational input_rational_hex(bool decimal_mode) {
    string num_str, den_str;
    int sign = 1;
    
    cin.ignore(); // Clear any leftover newline
    
    if (decimal_mode) {
        cout << "Enter numerator (decimal): ";
        getline(cin, num_str);
        
        // Validate input
        if (num_str.empty()) {
            cout << "Invalid input, defaulting to 0" << endl;
            return BigRational("0", "1", 1);
        }
        
        // Check for negative sign
        if (num_str[0] == '-') {
            sign = -1;
            num_str = num_str.substr(1);
        }
        
        // Validate decimal
        if (!is_valid_decimal(num_str)) {
            cout << "Invalid decimal number, defaulting to 0" << endl;
            return BigRational("0", "1", 1);
        }
        
        num_str = remove_leading_zeros(num_str);
        if (num_str.empty()) num_str = "0";
        
        cout << "Enter denominator (decimal, press Enter for 1): ";
        getline(cin, den_str);
        
        if (den_str.empty()) {
            den_str = "1";
        } else {
            if (!is_valid_decimal(den_str)) {
                cout << "Invalid denominator, defaulting to 1" << endl;
                den_str = "1";
            } else {
                den_str = remove_leading_zeros(den_str);
                if (den_str.empty() || den_str == "0") {
                    cout << "Denominator cannot be 0, defaulting to 1" << endl;
                    den_str = "1";
                }
            }
        }
        
    } else {
        cout << "Enter numerator (hexadecimal): ";
        getline(cin, num_str);
        
        // Validate input
        if (num_str.empty()) {
            cout << "Invalid input, defaulting to 0" << endl;
            return BigRational("0", "1", 1);
        }
        
        // Check for negative sign
        if (num_str[0] == '-') {
            sign = -1;
            num_str = num_str.substr(1);
        }
        
        // Validate hex
        if (!is_valid_hex(num_str)) {
            cout << "Invalid hexadecimal number, defaulting to 0" << endl;
            return BigRational("0", "1", 1);
        }
        
        // Convert hex to decimal
        num_str = hex_to_decimal(num_str);
        
        cout << "Enter denominator (hexadecimal, press Enter for 1): ";
        getline(cin, den_str);
        
        if (den_str.empty()) {
            den_str = "1";
        } else {
            if (!is_valid_hex(den_str)) {
                cout << "Invalid denominator, defaulting to 1" << endl;
                den_str = "1";
            } else {
                den_str = hex_to_decimal(den_str);
                if (den_str == "0") {
                    cout << "Denominator cannot be 0, defaulting to 1" << endl;
                    den_str = "1";
                }
            }
        }
    }
    
    return BigRational(num_str, den_str, sign);
}

// Bitwise AND operation on two BigRational numbers (integers only)
BigRational and_rational(const BigRational& a, const BigRational& b) {
    string result = bitwise_and_strings(a.numerator, b.numerator);
    return BigRational(result, "1", 1);
}

// Bitwise OR operation on two BigRational numbers (integers only)
BigRational or_rational(const BigRational& a, const BigRational& b) {
    string result = bitwise_or_strings(a.numerator, b.numerator);
    return BigRational(result, "1", 1);
}

// Bitwise NOT operation on a BigRational number (integers only)
// Uses adaptive bit width based on the number's actual bit length
BigRational not_rational(const BigRational& a) {
    vector<int> bin_a = decimal_to_binary(a.numerator);
    int bit_width = bin_a.size();
    
    // Use minimum of 8 bits for small numbers
    if (bit_width < 8) bit_width = 8;
    
    string result = bitwise_not_string(a.numerator, bit_width);
    return BigRational(result, "1", 1);
}

// Helper function: Bitwise AND on string numbers
string bitwise_and_strings(const string& a, const string& b) {
    if (a == "0" || b == "0") return "0";
    
    vector<int> bin_a = decimal_to_binary(a);
    vector<int> bin_b = decimal_to_binary(b);
    
    // Pad to same length
    int max_len = max(bin_a.size(), bin_b.size());
    while (bin_a.size() < max_len) bin_a.insert(bin_a.begin(), 0);
    while (bin_b.size() < max_len) bin_b.insert(bin_b.begin(), 0);
    
    vector<int> result;
    for (int i = 0; i < max_len; i++) {
        result.push_back(bin_a[i] & bin_b[i]);
    }
    
    return binary_to_decimal(result);
}

// Helper function: Bitwise OR on string numbers
string bitwise_or_strings(const string& a, const string& b) {
    if (a == "0") return b;
    if (b == "0") return a;
    
    vector<int> bin_a = decimal_to_binary(a);
    vector<int> bin_b = decimal_to_binary(b);
    
    int max_len = max(bin_a.size(), bin_b.size());
    while (bin_a.size() < max_len) bin_a.insert(bin_a.begin(), 0);
    while (bin_b.size() < max_len) bin_b.insert(bin_b.begin(), 0);
    
    vector<int> result;
    for (int i = 0; i < max_len; i++) {
        result.push_back(bin_a[i] | bin_b[i]);
    }
    
    return binary_to_decimal(result);
}

// Helper function: Bitwise NOT on string number
string bitwise_not_string(const string& a, int bit_width) {
    vector<int> bin_a = decimal_to_binary(a);
    
    // Pad to specified bit width
    while (bin_a.size() < bit_width) {
        bin_a.insert(bin_a.begin(), 0);
    }
    
    vector<int> result;
    for (int i = 0; i < bin_a.size(); i++) {
        result.push_back(bin_a[i] ^ 1); // Flip bits
    }
    
    return binary_to_decimal(result);
}

// Helper: Convert decimal string to binary vector
vector<int> decimal_to_binary(const string& decimal) {
    vector<int> binary;
    string num = decimal;
    
    if (num.empty() || num == "0") {
        binary.push_back(0);
        return binary;
    }
    
    while (num != "0") {
        int remainder = 0;
        string quotient = "";
        
        for (char digit : num) {
            int current = remainder * 10 + (digit - '0');
            quotient += (current / 2) + '0';
            remainder = current % 2;
        }
        
        binary.insert(binary.begin(), remainder);
        
        // Remove leading zeros
        size_t pos = quotient.find_first_not_of('0');
        num = (pos == string::npos) ? "0" : quotient.substr(pos);
    }
    
    return binary;
}

// Helper: Convert binary vector to decimal string
string binary_to_decimal(const vector<int>& binary) {
    if (binary.empty()) return "0";
    
    string result = "0";
    
    for (int bit : binary) {
        // Multiply result by 2
        int carry = 0;
        for (int i = result.length() - 1; i >= 0; i--) {
            int val = (result[i] - '0') * 2 + carry;
            result[i] = (val % 10) + '0';
            carry = val / 10;
        }
        if (carry) result = char(carry + '0') + result;
        
        // Add current bit
        if (bit) {
            carry = 1;
            for (int i = result.length() - 1; i >= 0 && carry; i--) {
                int val = (result[i] - '0') + carry;
                result[i] = (val % 10) + '0';
                carry = val / 10;
            }
            if (carry) result = '1' + result;
        }
    }
    
    return result;
}

// Helper: Convert hex string to decimal string
string hex_to_decimal(const string& hex) {
    if (hex.empty()) return "0";
    
    string result = "0";
    
    for (char c : hex) {
        int digit_val;
        if (c >= '0' && c <= '9') digit_val = c - '0';
        else if (c >= 'A' && c <= 'F') digit_val = c - 'A' + 10;
        else if (c >= 'a' && c <= 'f') digit_val = c - 'a' + 10;
        else continue; // Skip invalid characters
        
        // Multiply result by 16
        int carry = 0;
        for (int i = result.length() - 1; i >= 0; i--) {
            int val = (result[i] - '0') * 16 + carry;
            result[i] = (val % 10) + '0';
            carry = val / 10;
        }
        while (carry) {
            result = char(carry % 10 + '0') + result;
            carry /= 10;
        }
        
        // Add digit_val
        carry = digit_val;
        for (int i = result.length() - 1; i >= 0 && carry; i--) {
            int val = (result[i] - '0') + carry;
            result[i] = (val % 10) + '0';
            carry = val / 10;
        }
        if (carry) result = char(carry + '0') + result;
    }
    
    return result;
}

// Helper: Validate hexadecimal string
bool is_valid_hex(const string& str) {
    if (str.empty()) return false;
    for (char c : str) {
        if (!isxdigit(c)) return false;
    }
    return true;
}

// Helper: Validate decimal string
bool is_valid_decimal(const string& str) {
    if (str.empty()) return false;
    for (char c : str) {
        if (!isdigit(c)) return false;
    }
    return true;
}

// ===================== LOGICAL OPERATIONS =====================

// Multiply r by 2^shift
BigRational left_shift(const BigRational& r, int shift) {
    if (shift < 0) {
        return right_shift(r, -shift);
    }

    // 2^shift = "1" followed by shift zeros in string form
    string multiplier = "1";
    for (int i = 0; i < shift; i++) {
        multiplier = mul_strings(multiplier, "2");
    }

    string new_num = mul_strings(r.numerator, multiplier);
    BigRational res(new_num, r.denominator, r.sign);

    return normalize_rational(res);
}

// Divide r by 2^shift
BigRational right_shift(const BigRational& r, int shift) {
    if (shift < 0) {
        return left_shift(r, -shift);
    }

    string divisor = "1";
    for (int i = 0; i < shift; i++) {
        divisor = mul_strings(divisor, "2");
    }

    string new_den = mul_strings(r.denominator, divisor);
    BigRational res(r.numerator, new_den, r.sign);

    return normalize_rational(res);
}

// =================== UNIT CONVERSION ===================
// NOTE: Each unit map stores a factor that converts *FROM that unit TO the base unit*.
// i.e. base_value = unit_value * factor

static unordered_map<string, BigRational> length_units = {
    // base: meter (m)
    {"m",   BigRational("1", "1", 1)},        // 1 m = 1 m
    {"cm",  BigRational("1", "100", 1)},      // 1 cm = 0.01 m
    {"mm",  BigRational("1", "1000", 1)},     // 1 mm = 0.001 m
    {"km",  BigRational("1000", "1", 1)},     // 1 km = 1000 m
    {"inch",BigRational("254", "10000", 1)},  // 1 inch = 0.0254 m
    {"ft",  BigRational("3048", "10000", 1)}  // 1 ft = 0.3048 m
};

static unordered_map<string, BigRational> mass_units = {
    // base: kilogram (kg)
    {"kg", BigRational("1", "1", 1)},            // 1 kg = 1 kg
    {"g",  BigRational("1", "1000", 1)},         // 1 g = 0.001 kg
    {"mg", BigRational("1", "1000000", 1)},      // 1 mg = 1e-6 kg
    {"lb", BigRational("45359237", "100000000", 1)} // 1 lb = 0.45359237 kg
};

static unordered_map<string, BigRational> volume_units = {
    // base: liter (l)
    {"l",  BigRational("1", "1", 1)},       // 1 l = 1 l
    {"ml", BigRational("1", "1000", 1)},    // 1 ml = 0.001 l
    {"m3", BigRational("1000", "1", 1)}     // 1 m^3 = 1000 l
};

static unordered_map<string, BigRational> angle_units = {
    // base: radian (rad)
    {"rad", BigRational("1", "1", 1)},
    {"deg", BigRational("31416", "1800000", 1)} // deg -> rad factor = pi/180 ≈ 3.1416/180
};

// NEW: Force (base: Newton)
static unordered_map<string, BigRational> force_units = {
    // base: newton (N)
    {"N",   BigRational("1", "1", 1)},                 // 1 N = 1 N
    {"kN",  BigRational("1000", "1", 1)},              // 1 kN = 1000 N
    {"dyne",BigRational("1", "100000", 1)},            // 1 dyne = 1e-5 N  => factor = 1/100000
    {"lbf", BigRational("44482216", "10000000", 1)}    // 1 lbf ≈ 4.44822162 N
};

// NEW: Pressure (base: Pascal)
static unordered_map<string, BigRational> pressure_units = {
    // base: pascal (Pa)
    {"Pa",  BigRational("1", "1", 1)},              // 1 Pa = 1 Pa
    {"kPa", BigRational("1000", "1", 1)},           // 1 kPa = 1000 Pa
    {"bar", BigRational("100000", "1", 1)},         // 1 bar = 100000 Pa
    {"atm", BigRational("101325", "1", 1)}          // 1 atm = 101325 Pa
};

// NEW: Density (base: kg/m^3)
static unordered_map<string, BigRational> density_units = {
    // base: kilogram per cubic meter (kg/m3)
    {"kg/m3",   BigRational("1", "1", 1)},         // 1 kg/m3 = 1 kg/m3
    {"g/cm3",   BigRational("1000", "1", 1)},      // 1 g/cm3 = 1000 kg/m3
    {"kg/l",    BigRational("1000", "1", 1)},      // 1 kg/L = 1000 kg/m3
    {"g/mL",    BigRational("1000", "1", 1)}       // 1 g/mL = 1000 kg/m3 (same as g/cm3)
};

// ---------------- TEMPERATURE (unchanged, but kept here) -------------------
static BigRational convert_temperature(const BigRational& value, 
                                       const string& from_unit, 
                                       const string& to_unit)
{
    // Celsius to Kelvin (K = C + 273.15)
    if (from_unit == "C" && to_unit == "K")
        return addition_rational(value, BigRational("27315", "100", 1));

    if (from_unit == "K" && to_unit == "C")
        return subtraction_rational(value, BigRational("27315", "100", 1));

    if (from_unit == "C" && to_unit == "F") {
        BigRational t = multiplication_rational(value, BigRational("9", "5", 1));
        return addition_rational(t, BigRational("32", "1", 1));
    }

    if (from_unit == "F" && to_unit == "C") {
        BigRational t = subtraction_rational(value, BigRational("32", "1", 1));
        return multiplication_rational(t, BigRational("5", "9", 1));
    }

    if (from_unit == "F" && to_unit == "K") {
        BigRational c = convert_temperature(value, "F", "C");
        return convert_temperature(c, "C", "K");
    }

    if (from_unit == "K" && to_unit == "F") {
        BigRational c = convert_temperature(value, "K", "C");
        return convert_temperature(c, "C", "F");
    }

    if (from_unit == to_unit) return value;

    throw invalid_argument("Invalid temperature conversion: " + from_unit + " -> " + to_unit);
}

// ------------------- GENERIC UNIT CONVERSION (FIXED DIRECTION) -------------------
//
// Conversion logic (correct):
//   base_value = value * factor_of_from_unit
//   result     = base_value / factor_of_to_unit
//
BigRational convert_units(const BigRational& value, const string& from_unit, const string& to_unit)
{
    // Temperature handled separately
    if (from_unit == "C" || from_unit == "F" || from_unit == "K" ||
        to_unit == "C" || to_unit == "F" || to_unit == "K")
    {
        return convert_temperature(value, from_unit, to_unit);
    }

    // find category
    unordered_map<string, BigRational> *category = nullptr;

    if (length_units.count(from_unit) || length_units.count(to_unit))      category = &length_units;
    else if (mass_units.count(from_unit) || mass_units.count(to_unit))   category = &mass_units;
    else if (volume_units.count(from_unit) || volume_units.count(to_unit)) category = &volume_units;
    else if (angle_units.count(from_unit) || angle_units.count(to_unit)) category = &angle_units;
    else if (force_units.count(from_unit) || force_units.count(to_unit)) category = &force_units;
    else if (pressure_units.count(from_unit) || pressure_units.count(to_unit)) category = &pressure_units;
    else if (density_units.count(from_unit) || density_units.count(to_unit)) category = &density_units;
    else throw invalid_argument("Unknown or mismatched units: " + from_unit + " / " + to_unit);

    if (!category->count(from_unit) || !category->count(to_unit)) {
        throw invalid_argument("Units not in same category or unknown: " + from_unit + " / " + to_unit);
    }

    BigRational from_factor = (*category)[from_unit];
    BigRational to_factor   = (*category)[to_unit];

    // base_value = value * from_factor
    BigRational base_val = multiplication_rational(value, from_factor);

    // result = base_value / to_factor
    BigRational result = division_rational(base_val, to_factor);

    return result;
}

// -------------- PRINT UNIT CATEGORIES -----------------

void display_unit_categories()
{
    cout << "\nAvailable Categories and units:\n";
    cout << "1. Length    : m, cm, mm, km, inch, ft\n";
    cout << "2. Mass      : kg, g, mg, lb\n";
    cout << "3. Volume    : l, ml, m3\n";
    cout << "4. Temperature: C, F, K\n";
    cout << "5. Angle     : rad, deg\n";
    cout << "6. Force     : N, kN, dyne, lbf\n";
    cout << "7. Pressure  : Pa, kPa, bar, atm\n";
    cout << "8. Density   : kg/m3, g/cm3, kg/l, g/mL\n";
}

// --------------- MAIN MENU HANDLER ------------------

// Handles unit conversion with explicit category selection to avoid ambiguity
void handle_unit_conversion(bool decimal_mode)
{
    cout << "\n=== UNIT CONVERSION MENU ===\n";
    display_unit_categories();

    cout << "\nSelect category (enter number): ";
    int cat;
    cin >> cat;

    unordered_map<string, BigRational>* category_map = nullptr;
    vector<string> allowed_units;

    switch (cat) {
        case 1: category_map = &length_units;   break;
        case 2: category_map = &mass_units;     break;
        case 3: category_map = &volume_units;   break;
        case 4: /* temperature handled specially */ break;
        case 5: category_map = &angle_units;    break;
        case 6: category_map = &force_units;    break;
        case 7: category_map = &pressure_units; break;
        case 8: category_map = &density_units;  break;
        default:
            cout << "Invalid category choice." << endl;
            return;
    }

    cout << "\nEnter value: ";
    BigRational value = input_rational(decimal_mode);

    string from_u, to_u;
    if (cat == 4) {
        cout << "Enter FROM unit (C, F or K): ";
        cin >> from_u;
        cout << "Enter TO unit (C, F or K): ";
        cin >> to_u;
    } else {
        cout << "Enter FROM unit: ";
        cin >> from_u;
        cout << "Enter TO unit: ";
        cin >> to_u;
    }

    try {
        BigRational result = convert_units(value, from_u, to_u);
        cout << "\nConverted Value: ";
        print_rational(result, decimal_mode);
        add_to_history(value, BigRational("0", "1", 1), result, "unit_convert");
    } catch (const exception& e) {
        cout << "Error: " << e.what() << endl;
    }
}

// ==================== LOG / EXP IMPLEMENTATION =================

// Helper: convert BigRational to high-precision double
static long double rational_to_ld(const BigRational &r) {
    long double num = stold(r.numerator);
    long double den = stold(r.denominator);
    long double val = num / den;
    if (r.sign == -1) val = -val;
    return val;
}

// Helper: convert long double → BigRational (scaled to 10^12)
static BigRational ld_to_rational(long double x) {
    int sign = (x < 0 ? -1 : 1);
    if (x < 0) x = -x;

    long double scaled = x * 1000000000000.0L; // 1e12 precision
    string num = to_string((long long) scaled);
    BigRational r(num, "1000000000000", sign);
    return normalize_rational(r);
}

// Natural logarithm using Newton iteration
BigRational ln_rational(const BigRational& x) {
    long double v = rational_to_ld(x);
    if (v <= 0) throw invalid_argument("ln(x) undefined for x ≤ 0");

    long double y = logl(v); // use machine ln
    return ld_to_rational(y);
}

// log_b(x) = ln(x) / ln(b)
BigRational log_rational(const BigRational& base, const BigRational& x) {
    BigRational ln_x = ln_rational(x);
    BigRational ln_b = ln_rational(base);
    return division_rational(ln_x, ln_b);
}

// Exponential: base^exp = exp(exp * ln(base))
BigRational exp_rational(const BigRational& base, const BigRational& exponent) {
    long double b = rational_to_ld(base);
    long double e = rational_to_ld(exponent);
    if (b <= 0) throw invalid_argument("base must be positive");

    long double val = powl(b, e);
    return ld_to_rational(val);
}

// ======================= MENU HANDLER ========================

void handle_log_exp_menu(bool decimal_mode)
{
    cout << "\n=== LOGARITHMIC & EXPONENTIAL FUNCTIONS ===\n";
    cout << "1. Logarithm (log base b of x)\n";
    cout << "2. Exponentiation (b^x)\n";
    cout << "Select option: ";

    int choice;
    cin >> choice;

    BigRational b, x;

    if (choice == 1) {
        cout << "Enter base b: ";
        b = input_rational(decimal_mode);
        cout << "Enter argument x: ";
        x = input_rational(decimal_mode);

        try {
            BigRational result = log_rational(b, x);
            cout << "\nlog_" << to_decimal(b,6)
                 << "(" << to_decimal(x,6) << ") = "
                 << to_decimal(result,12) << endl;

            add_to_history(b, x, result, "log");
        }
        catch (const exception &e) {
            cout << "Error: " << e.what() << endl;
        }

    } else if (choice == 2) {
        cout << "Enter base b: ";
        b = input_rational(decimal_mode);
        cout << "Enter exponent x: ";
        x = input_rational(decimal_mode);

        try {
            BigRational result = exp_rational(b, x);
            cout << "\n" << to_decimal(b,6)
                 << "^(" << to_decimal(x,6) << ") = "
                 << to_decimal(result,12) << endl;

            add_to_history(b, x, result, "exp");
        }
        catch (const exception &e) {
            cout << "Error: " << e.what() << endl;
        }

    } else {
        cout << "Invalid selection.\n";
    }
}