Estimating Pi

Here, we look at the Archimedes' method to calculate/estimate the Pi number where simpler polygons are used to find the area of a unit circle. The video is inspired from a talk given by MIT Professor John Guttag within MITx - 6.00.2x.

Simple remedy on CLANG error: no member named * in namespace *

Given the following code snippet in C++, when it is compiled with gcc, there is no issue. However, when compiled using the clang, then we see the following error:

Compilation:

clang++ -std=c++14 -pedantic -Wall  main.cpp

Output:

main.cpp:12:18: error: no member named 'runtime_error' in namespace 'std'
      throw std::runtime_error("Cannot find the input file...");
            ~~~~~^
1 error generated.

Code snippet given the above error with Clang.

#include <fstream>
#include <iostream>

using namespace std;

int main() {

   ifstream input;
   input.open("test.txt");

   if (!input.is_open()){
      throw std::runtime_error("Cannot find the input file...");
   }

   input.close();

   return 0;
}

This is because clang cannot find the header file. Either it should be included or simply telling clang which header file to look at solves the problem. In this particular example, including the header file where runtime_error() is defined which is the #include is good enough. 

Sedona, Arizona trip - Caught by snow

While expecting to see the wonderful rock formations, we were caught in the snow. This was a bit surprising but the city still looked beautiful.

Fast C++ Solution to Huge Fibonacci number modulo m

This is a fast solution in C++ to Huge Fibonacci number modulo m question asked in the Algorithms course in UC San Diego Coursera course on Algorithms. It first calculates the Pisano period, then utilizes it to reduce the problem to a smaller size. The code also contains iterative solver to calculate Fibonacci number modulo m.

#include <iostream>
#include <vector>
using namespace std;

// This iteratively calculates the mod m of Fn, i.e. Fn % m [cost: O(n)]
template <typename T>
T calc_fibModm(T n, T m) {

  T fn=0, fn_minus1=1,fn_minus2=1;

  if (n==0)
      return 0;
  else if (n==1 || n==2)
      return 1;
  else {
     for (T i=2; i<n; i++){
      fn =( fn_minus1 % m + fn_minus2 % m) %m ;
      fn_minus2 = fn_minus1;
      fn_minus1 = fn;
     }
   }

  return fn;
}

template <typename T>
T findPeriod(T  n,T  m){ // Find the periodicity of Fibanacci series (i.e. Pisano period)

  vector<T > vMod;
  for (T i=0; i<n; i++){
    T modi = calc_fibModm(i,m);
    vMod.push_back(modi);

    if (i>2 && vMod[i] ==1 && vMod[i-1] == 0) {// this might be the start of a new periods as all new period start with 01 sequence

      // now calculate forward (i-2) new elements and check with the first set 
      // whether all elements are same (to establish periodicity)
      bool bAllOk= true;
      for (T j=i-1; j<2*i-3+1; j++){
          T modi_forward =  calc_fibModm(j,m);
          if (vMod[j-(i-1)] != modi_forward) {
            bAllOk=false;
            break;
          }
      }
      
      if (bAllOk) {
        T period = i-1;
        cout<<"n="<<n<<", m="<<m<<" --> period ="<<period<<endl;
        return period;
      }
    }
  } 
  // if reached here, that means the periodicty hasn't started yet, increase n
  string errStr="Not big enough n=("+to_string(n)+") to catch periodicity. Increase n to get periodicity";
  throw runtime_error(errStr);
  return -1;
}

template <typename T>
T get_fibonacci_huge(T n,T m) { // note that Fn % m = F_(n % period) % m

  if (m==1){
    return 0;
  } else { // general case
    T period = findPeriod(n,m);
    return calc_fibModm((n%period), m); 
  }
}

int main() {
    long long n, m;
    // try n=281621358815590 m=30524  output should be 11963
    std::cin >> n >> m;
    std::cout <<"Fn % m ="<< get_fibonacci_huge(n, m) << '\n';
}

Answer to MaxCounters question at Codility

Below is the Python solution to MaxCounters programming lesson in Codility. This gives the O(M+N) time complexity. The link to the question is here.

MaxCounters:
Calculate the values of counters after applying all alternating operations: increase counter by 1 and set value of all counters to current maximum

# Detected time complexity: O(N + M) %100 from codility

def solution(N,A):
 
 B=[0]*N

 baseValue =0;
 maxCount = 0; 
 for x in A:
   if 1 <= x <= N:
      B[x-1] = max(B[x-1],baseValue) + 1 
      maxCount=max(B[x-1],maxCount)
   else: 
      baseValue = maxCount

 for i in xrange(N):
    B[i]=max(B[i],baseValue)


 return B ;

Unix ls command - How to Exclude Certain Patterns using Wildcard?

Let's say you have a directory where there are too many files/folders having similar names and you want to exclude them during an ls operation. The command to use is as follows:

ls --ignore="PATTERN*"

Below is an example where there are folders named run_* and other files. The results obtained after typing plain ls and with the exclude options are shown below:

With the option: (Note the usage of the wildcard)

Travels of Ibn Jubayr from Granada, Spain to Mecca between 1183-1185 AD

Ibn Jubayr traveled almost 150 years before Ibn Battuta started his epic journey around the world. In his book, Ibn Battuta has used Ibn Jubayr's book as a reference for the cities he has already wrote about.


.... to be completed

References:

• Roland Broadhurst, "The Travels of Ibn Jubayr", Goodword Books, 2013 (first published in 1952)

Time Lapse from King's Mountain and Table Mountain tops

I had the chance to capture time lapse photos during two recent hikes. Here are the outcomes: King's Mountain: Here the camera is positioned westward towards the Pacific Ocean

Table Mountain: Overlooking the Columbia Gorge in a very cloudy morning. Once we got back to the trailhead, the clouds were completely gone.
 

Boost Library Compilation Error (using CMake): undefined reference to `boost::iostreams::detail::

While using CMake to compile a simple c++ code containing boost library utilization, I encountered the following linkage problem:

main.cpp:(.text._ZN5boost9iostreams6detail9close_allINS0_21basic_gzip_compressorISaIcEEENS1_16linked_streambufIcSt11char_traitsIcEEEEEvRT_RT0_[void boost::iostreams::detail::close_all >, boost::iostreams::detail::linked_streambuf > >(boost::iostreams::basic_gzip_compressor >&, boost::iostreams::detail::linked_streambuf >&)]+0x18e): undefined reference to `boost::iostreams::detail::zlib_base::reset(bool, bool)'

collect2: ld returned 1 exit status

make[2]: *** [test.exe] Error 1

make[1]: *** [CMakeFiles/test.exe.dir/all] Error 2

make: *** [all] Error 2

For reference, the code I was trying to compile was the following ( a simple zipping and reading from a zipped file).:

#include <fstream>

#include <iostream>
#include <boost/iostreams/device/file.hpp>
#include <boost/iostreams/filtering_streambuf.hpp>
#include <boost/iostreams/filtering_stream.hpp>
#include <boost/iostreams/copy.hpp>
#include <boost/iostreams/filter/gzip.hpp>
using namespace std;
using namespace boost::iostreams;

int main()
{
   //The following code decompresses data from a file and writes it to standard output.
   ifstream file("hello.txt.gz", ios_base::in | ios_base::binary);
   filtering_streambuf<input> in;
   in.push(gzip_decompressor());
   in.push(file);
   boost::iostreams::copy(in, cout);

   boost::iostreams::filtering_ostream geometry;
   geometry.push(boost::iostreams::gzip_compressor(boost::iostreams::gzip::best_compression));

   // Generating a Zip file
   string filename = "example1.txt.gz";
   filtering_ostream out;
   unsigned int compressionLevel = boost::iostreams::gzip::best_compression;
   out.push(gzip_compressor(compressionLevel));

   out.push(file_sink(filename.c_str(), std::ios::binary));
   out << "This is a gz file\n";
   out << "This is the second line\n";
}

How I solved this problem is as follows: 

1)  I already had the following setting in the CMakeList.txt file:

SET(BOOST_DIR /usr/intel/pkgs/boost/1.54.0-gcc-4.7.2 CACHE PATH "Boost directory")


2)  Then, I added the bold and red lines below to have it compile without linkage error (the black lines already existed)

SET(BOOST_LIBDIR ${BOOST_DIR}/lib64)

SET(BOOST_LIB -L${BOOST_LIBDIR} boost_thread.a pthread.a  )

SET(BOOST_INCLUDE_DIR ${BOOST_DIR}/include )
LINK_DIRECTORIES(${BOOST_LIBDIR})
INCLUDE_DIRECTORIES(${BOOST_INCLUDE_DIR}  )
find_package(Boost COMPONENTS system filesystem iostreams regex  REQUIRED)
set (EXE test.exe)
add_executable(${EXE} main.cpp )
TARGET_LINK_LIBRARIES(${EXE} ${Boost_LIBRARIES} )

This made the trick and it worked without problems

Mansa Musa's Hajj Route (circa 1324)

--- will be updated later ---

References: 
1) P.J. Oliver, Mansa Musa and the Empire of Mali, CreateSpace Independent Publishing Platform (March 26, 2013) amazon

Map of Ibn Battuta's Africa trip including Mali circa 1337