Notes and Thoughts

An experiment to spark conversation

Home

Why did I write code like this?

Today while I was simply browsing through my old git repos for a snippet of code that I wrote years ago, I came across one of the only two problems that I've ever attempted on The Euler Project. The interesting thing however is that in this process of reminiscing the old piece of code, that is of no relevance or value to me whatsoever at this point in time, I spent almost an hour trying to understand why I did what I did. Although I did eventually figure out the thought process that led me to this approach, I thought this would be a nice bit of anecdote for people to see how thought continuity and state of mind plays a huge role in problem solving.

Here is the problem:

Find the sum of digits of the result of 210002^{1000}

And here is the solution (Skip the solution and scroll down if you are here just for the story):

#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>

void multiply(std::vector<unsigned long int>& prod, std::vector<unsigned long int> twoPow25)
{
  std::vector<std::vector<unsigned long int>> resVec;
  std::vector<unsigned long int> resVec1;
  int zeroAppCnt = 0;
  int zeroPrepCnt = 0;
  unsigned long int carry = 0;
  int prodPlusCarry = 1;
  for (auto digIn2Pow25 : twoPow25) {
    for (auto digInProd : prod) {
      prodPlusCarry = (digIn2Pow25 * digInProd) + carry;
      resVec1.push_back(prodPlusCarry % 10);
      carry = prodPlusCarry / 10; 
    }
    if (carry) {
      resVec1.push_back(carry);
    }
    resVec1.insert(resVec1.begin(), zeroAppCnt, 0);
    zeroAppCnt = zeroAppCnt + 1;
    if (resVec1.size() > zeroPrepCnt) {
      zeroPrepCnt = resVec1.size();
    }
    resVec.push_back(resVec1);
    resVec1.clear();
    carry = 0;
    prodPlusCarry = 1;
  }
  for (auto& rv : resVec) {
    rv.insert(rv.end(), zeroPrepCnt - rv.size(), 0);
  }

  prod.clear();
  carry = 0;
  unsigned long int size = resVec[0].size();
  unsigned long int sum = 0;
  for (unsigned long int i = 0; i < size; i++) {
    for (auto rv : resVec) {
      sum += rv[i];
    }
    sum += carry;
    prod.push_back(sum % 10);
    carry = sum / 10;
    sum = 0;
  }
  if (carry) { 
    prod.push_back(carry);
  }
}

int main()
{
  std::vector<unsigned long int> twoPowerTwentyFive = { 2, 3, 4, 4, 5, 5, 3, 3 };
  std::vector<unsigned long int> product = twoPowerTwentyFive;
  for (int i = 0; i < 39; i++) {
    multiply(product, twoPowerTwentyFive);
  }
  std::cout << std::accumulate(product.begin(), product.end(), 0) << std::endl;
  return 0;
}

To be honest, there is nothing special about this piece of code. All it does is multiplies 2252^{25}, 40 times in a very naïve manner. What made me sit on it for an hour was the choice of this arbitrary value of 2252^{25}. Why did I choose an arbitrary number when I could have easily used something like BigInt or used the same vector to multiply 2 with itself thousand times? Why?

To me it is all the more interesting because if you are willing to skip through the steps and go directly to 2252^{25} then why not go directly to a higher number like 21002^{100} or even directly to 210002^{1000}?

To understand the reason behind this decision, one would first need to know what I was working on just before that.

Here is the commit message from a work related fix that I was working on for multiple days just before that:

Plain Text Fixed [...] serialization issue for objects with values above 2^25(23445533). Issue with custom big integer implementation. ... ...

Yes, I was working on a serialization bug that failed when serializing an object with values above 2252^{25}; and yes we were using an inhouse BigInt library that had an edge case for numbers between 2252^{25} and 2322^{32}. Also yes, I jumped on The Euler Project immediately after that as a way to relax. 🤷‍♂️

In fact, I even feel me that this might also have played a role in me choosing that particular problem, but I am not very sure about that. That said, I am also not claiming that this alone was the reason, for it could have been due to myriad of things, but something tells me that I was mindless and erratic, and that without an initial value it is not possible to go that direction. Problem solving takes a clear mind. Problem solving requires that you are in the right mental state. And most importantly problem solving is less like a virtuoso musician playing a complex piece on a musical instrument and more like a pseudo-random pattern generation process that is dependent on the seed value.