digits - What are various methods to store very large integer value in a variable with less compilation time in C++ when doing operation on that variable

Question

What should I do with this variable to make it store following large number without downloading any new libraries.I am talking about using some manipulation like hashing or arrays or something I don't know.

Answer 1

For fun I've written something that works only on strings. By the way, that number you gave is awfully large number, it's something like a quintillion times the mass of our solar system in kg.

There are two methods. The first one adds one to the number and checks if it's a palindrome. This is a slow version, but can still works for numbers up to like about 16 digits in a reasonable time.

The second method is the method better way, it basically copies the left side of the number to the right side, it's pretty much instant. As the code is now you can run it through both to cross-reference the results.

I can't say it's fool-proof and I'm sure there's errors in it, but it seems to work, and I did have fun writing it. Also, if you're not allowed to use ANY libraries whatsoever, it's rather easy to refactor, just use raw strings and pass the size in the function.

#include <iostream>
#include <string>
#include <chrono>
#include <stdexcept>
#include <cstring>

using namespace std::chrono;
using namespace std;

auto startT = high_resolution_clock::now();
auto endT = high_resolution_clock::now();
double timeTaken;

#define STARTCLOCK startT = high_resolution_clock::now();
#define STOPCLOCK endT = high_resolution_clock::now();
#define PRINT_ELAPSED_TIME timeTaken = duration_cast<milliseconds>(endT - startT).count() / 1000.0; 
                            cout << "Process took " << timeTaken << " seconds

";


void addOneTo(std::string& value)
{
    int64_t idx = value.size();

    do 
    {
        --idx;
        if (idx < 0) {
            memset(&value[0], '0', value.size());
            value.insert(value.begin(), '1');
            return;
        }
        value[idx] += char(1);
        if (value[idx] > '9') { value[idx] = '0'; }

    } while (value[idx] == '0');
}

bool isPalindrome(const std::string& number)
{
    const char* start = &number[0];
    const char* end = &number[number.size() - 1];

    while (start <= end)
    {
        if (*start != *end) return false;
        ++start;
        --end;
    }
    return true;
}

std::string getSmallestPalindromeByBruteForceBiggerThan(std::string num)
{
    if (num.empty()) throw std::runtime_error("Empty string");

    while (true)
    {
        addOneTo(num);
        if (isPalindrome(num)) return num;
    }
}


std::string getSmallestPalindromeOptimisedWayBiggerThan(std::string num)
{
    if (num.empty()) throw std::runtime_error("Empty string");

    addOneTo(num);
    if (num.size() == 1) return num;
    int64_t left;
    int64_t right;

    left = num.size() / 2 - 1;

    if (num.size() % 2 == 0)  right = num.size() / 2; 
    else right = num.size() / 2 + 1;

    if (num[left] < num[right])
    {
        ++num[left];
        num[right] = num[left];
    }

    for (; left >= 0 && right < num.size(); --left, ++right)
    {
        num[right] = num[left];
    }

    return num;
}

int main()
{
    string number = "60819750046451377";

    STARTCLOCK
    string palindrome = getSmallestPalindromeByBruteForceBiggerThan(number);

    cout << "____BRUTE FORCE____
";
    cout << "Smallest palindrome = 
" << palindrome << '
';

    STOPCLOCK
    PRINT_ELAPSED_TIME

    STARTCLOCK

    palindrome = getSmallestPalindromeOptimisedWayBiggerThan(number);

    cout << "____OPTIMISED____
";
    cout << "Smallest palindrome = 
" << palindrome << '
';

    STOPCLOCK
    PRINT_ELAPSED_TIME

    cin.ignore();
}