Mathologer Googol code

//How many ways are there to get a googol dollars?
//Well, given enough time and a high enough precision value this'll find out, but good luck reaching it :P
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cmath>
#include <cmath>
#include <boost/multiprecision/gmp.hpp>
using stringstream = std::stringstream;
using string = std::string;
using mpf_float = boost::multiprecision::mpf_float;

//Using cygwin64, compile with g++ -O3 ./googol.cpp -o ./googol.out -lgmp
//I'm pretty sure you can do something similar with linux/mac since those have native g++
//I'd drop a compiled version here, but i keep getting a "cannot find lgmp" error when compiling with -static. Sorry about that.

//MINI-CONFIG:
u_int precision = 256; //Larger = bigger number
bool intermediates = false; //Show intermediate values. Set to false to only show dollars. True will show everything, from pennies to half-dollars and everything in between.
//MINI-CONFIG END

//The rest is code for you to look through. You can probably make it more efficient if you know more than me.

//What if I could do each big coin type in just 1 function, maybe even in O(n) timescale if I'm actually competent at figuring out big-O notation?
//Hahaha just kidding...
//Unless?
mpf_float quarterSum (mpf_float d, int ID) {
    mpf_float sum = 0;
    mpf_float q = 0;
    mpf_float mul0 = 1;
    mpf_float mul1 = 1;
    switch (ID) {
        case 2:
            do {
                sum += ceil(10*d-2.5*q+1)*floor(10*d-2.5*q+1)*mul0*mul1;
                if (fmod(q,4) == 1) { mul0++; }
                if (fmod(q,4) == 3) { mul1++; }
            } while (++q <= floor(4*d));
            break;
        case 1:
            do {
                sum += ceil(10*d-2.5*q+1)*floor(10*d-2.5*q+1)*mul0;
                if (fmod(q,2) == 1) { mul0++; }
            } while (++q <= floor(4*d));
            break;
        default:
            do {
                sum += ceil(10*d-2.5*q+1)*floor(10*d-2.5*q+1);
            } while (++q <= floor(4*d));
    }
    return sum;
}

mpf_float inputParser (string str) {
    stringstream in(str);
    mpf_float out = 0;
    in >> out;
    if (in.fail()) {
        string er = "";
        throw (er + "Unable to format " + str + "as a number!");
   }
   return out;
}

int main () {
    string input;
    mpf_float count = 0;
    mpf_float::default_precision(precision);

    std::cout << "Input the amount of dollars (Scientific notation is okay; the memetic googol value is 1e100):\n";
    std::cin >> input;
    count = inputParser(input);

    std::cout << std::setprecision(precision);
    if (intermediates) {
        std::cout << "With only pennies: 1 way. What were you expecting? :p\n";
        std::cout << "Adding nickels: " << (floor(count*20)+1) << " ways.\n";
        std::cout << "Adding dimes: " << pow(floor(count*10)+1, 2) << " ways.\n";
        std::cout << "these three will take a bit depending on how big the number is.\n";
        std::cout << "Adding quarters: " << quarterSum(count,0) << " ways.\n";
        std::cout << "Adding half-dollars: " << quarterSum(count,1) << " ways.\n";
        std::cout << "Adding dollars: " << quarterSum(count,2) << " ways.\n";
    } else {
        std::cout << "this might take a while...\n";
        std::cout << "How to split change: " << quarterSum(count,2) << " ways.\n";
    }
    std::cout << "hope it worked ;)";
    return 0;
}


//COOL TIDBITS (aka the process)
    //Things that we know:
    //We get n+1 values for dollars
    //We get 2n+1 values for half-dollars
    //We get 4n+1 values for quarters
    //We get 10n+1 values for dimes
    //We get 20n+1 values for nickels
    //Any remainder is made up of pennies, they can be ignored

    //At the same time if we just plug in (n+1)*(4n+1)*(10n+1)*(20n+1) we certainly don't get 293, now do we?
    //Technically it's the sum of all inputs that add up to 100, but we can exclude pennies. It's instead the sum of all inputs that add up to a value <= 100!

    //We COULD accomplish this with 4 nested while loops (nickels omitted for efficiency)
    /*
    register long double d = 0;
    register long double h = 0;
    register long double q = 0;
    register long double i = 0;
    do
        do {
            do {
                do {
                    count += floor(2*(2.5*(2*(2*(inDoub-d)-h)-q)-i))+1;
                } while (++i <= 2.5*(2*(2*(inDoub-d)-h)-q)
            } while (++q <= 2*(2*(inDoub-d)-h))
        } while (++h <= 2*(inDoub-d))
    } while (++d <= inDoub)
    */
    //Just imagine how laggy that would be at higher inputs! The key is to avoid loops as much as possible
    //But it does give us insight as to how the future will perform if we count it manually...
    //If we could only use dimes and nickels
    //@q=0: 21 + 19 + 17 + 15 + 13 + 11 + 9 + 7 + 5 + 3 + 1 = 121
    //@q=1: 16 + 14 + 12 + 10 + 8 + 6 + 4 + 2 + 0 = 72
    //@q=2: 11 + 9 + 7 + 5 + 3 + 1 = 36
    //@q=3: 6 + 4 + 2 + 0 = 12
    //@q=4: 1 = 1
    //@d=1: 1 = 1
    //Total: 121 + 72 + 36 + 12 + 1 + 1 = 243, which matches expectations not counting half dollars
    //A potential series. Going to 1.50 introduces a +135 for a total of 256 possibilities, so it's safe to assume that it's a +35+50i.
    //In a similar vein, q=3 is equivalent to q=1 with a bit extra tacked on. This turns out to have a base of 12, and an adder of +10+50(i+1). (12 > 72 > 182, 10 > 60 > 110)

    //Notice how it's basically a sum.
    //@q=0: sum(2*i+1,0,10)
    //@q=1: sum(2*i,0,8)
    //@q=2: sum(2*i+1,0,5)
    //@q=3: sum(2*i,0,3)

    //The thing is about this while loop is that it layers them together. Is there an efficient way to get these numbers?
    //Well, actually yes. q=2 is equivalent to q=0 with a bit extra tacked on, right? 85 + 36, or 85 + 35 + 1, or (35+50*1) + (35+50*0) + 1.
    //A note if you're astute that allows for simplification. This (2n+1)-type sum is equal to a square of n+1.
    //So for an even number of quarters, sum((5i+1)^2, 0, n/2) is a viable solution if we only deal in intervals of 25.
    //Even 15 works with this, same with 5
    //If it were 45 > 95, like 1.99
    //@q=0: 20 + 18 + 16 + 14 + 12 + 10 + 8 + 6 + 4 + 2 + 0 = 110
    //@q=2: 10 + 8 + 6 + 4 + 2 + 0 = 30
    //Isn't this just n*(n-1)?
    //Therefore instead of sums, we can re-summarize

    //@q=0: 11^2 = (10+1)^2
    //@q=1: 9*8 = (7+2)*(7+1)
    //@q=2: 6^2 = (5+1)^2
    //@q=3: 4*3 = (2+2)*(2+1)
    //@q=4: 1^2 = (0+1)^2
    //in other words
    //@q=n: ceil(10d-2.5q+1)*floor(10d-2.5q+1)
    //This might be the one case we need a sum :P

    //With half-dollars, you make another instance of the sum starting 2 below (in effect, adding 1). Simple enough, after all it's just layering.
    //So what about dollars? You make another instance of the half dollar sum starting 2 below and add it to the first sum.
    //How do you quantify that?
    //Try with 2 dollars.
    //q=[0,8] represents the 0 half-dollar sum. h=0: 21^2+19*18+16^2+14*13+11^2+9*8+6^2+4*3+1^2 = 1463
    //q=[2,8] represents the 1 half-dollar sum. h=1: 16^2+14*13+11^2+9*8+6^2+4*3+1^2 = 680
    //q=[4,8] represents the 2 half-dollar sum. h=2: 11^2+9*8+6^2+4*3+1^2 = 242
    //q=[6,8] represents the 3 half-dollar sum. h=3: 6^2+4*3+1^2 = 49
    //q=[8,8] represents the 4 half-dollar sum. h=4: 1^2 = 1
    //In total, q=[0,1] is counted once, q=[2,3] is counted twice, q=[4,5] is counted thrice, q=[6,7] is counted quartice, and q=[8,8] is counted... quintice? (honestly i made up quartice too)

    //Stepping up 1 layer
    //h=[0,4] represents the 0 dollar sum. In other words, q=[0~8,8]. d=0: 1463+680+242+49+1 = 2435
    //h=[2,4] represents the 1 dollar sum. In other words, q=[4~8,8]. d=1: 242+49+1 = 292
    //h=[4,4] represents the 2 dollar sum. In other words, q=[8~8,8]. d=2: 1 = 1
    //sum to get the 2 dollar total described in the video. 2728.
    //In total, h=[0,1] is counted once, h=[2,3] is counted twice, h=[4,4] is counted thrice.
    //In other words.
    //  q=[0,1]: only in h[0,1], so 1 time
    //  q=[2,3]: only in h[0,1], so 2 times
    //  q=[4,5]: in both h[0,1] and h[2,3], so 3*2 = 6 times
    //  q=[6,7]: in both h[0,1] and h[2,3], so 4*2 = 8 times
    //  q=[8,8]: in all three, so 5*3 = 15 times
    //But you probably saw a problem with your eyes the second I hit the 3rd line. It wasn't that at all.
    //In fact, the pattern through manual counting is 1, 2, 4, 6, 9. That's different.
    //Brief hypothesis: they both alternate in terms of incrementation. Try and see if it matches the already listed values?

    //Empirically checking, it actually does match the given examples. Huh, neat.
    //Here's some other cool information that you may not know immediately because I don't just report dollars.
    //Coins all actually follow a similar pattern as you multiply by 10. In essence, where {} indicates a repeating chain of the same length as every other {}
    //Nickels: 2{0}1
    //Dimes: 1{0}2{0}1
    //Quarters: 1{3}42{3}51{0}1
    //Half-dollars: 6{6}79{3}412{6}85{0}01
    //Dollars: 13{3}398{3}445{3}4138{3}545{0}01

    //You also start to see this with 2*10^n (42{6}770{6}7562{6}988{6}7090{0}01 | @2e6, len=3).
    //For fun, I also ran it on other values, up to 10^6, to try and find other patterns. Here's the results.
    //3*10^n: 3240{0}5265{0}3024{0}072450{0}6350{0}01 | @3e6, len=2
    //4*10^n: 1365{3}4997{3}40501{3}46213{3}4180{0}001 | @4e6, len=2
    //5*10^n: 41{6}707291806{6}68679167250{0}1 | @5e6, len=3
    //6*10^n: 10368{0}8424{0}24192{0}28980{0}1270{0}01 | @6e6, len=2
    //7*10^n: 224093489398371749{3}72778{3}48150{0}01 | @7e6, len=2
    //8*10^n: 436906932906724010671818{6}8360{0}01| @8e6, len=3
    //9*10^n: 787320426465081648{0}65205{0}19050{0}01| @9e6, len=2
    //Intriguingly, every number that repeats, regardless of whether nickels, dimes, quarters, or anything else is processed, is either a 0, a 3, or a 6.
    //I should mention that this isn't every growing pattern. There are more past 1e7 that you can potentially explore, as I noticed some numbers popping up while I was figuring these out.
    //Perhaps that could be a fun homework assignment?