How to resolve the algorithm First power of 2 that has leading decimal digits of 12 step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm First power of 2 that has leading decimal digits of 12 step by step in the C++ programming language

Table of Contents

Problem Statement

(This task is taken from a   Project Euler   problem.) (All numbers herein are expressed in base ten.)

27   =   128   and   7   is the first power of   2   whose leading decimal digits are   12. The next power of   2   whose leading decimal digits are   12   is   80, 280   =   1208925819614629174706176.

Define     p(L,n)     to be the nth-smallest value of   j   such that the base ten representation of   2j   begins with the digits of   L .

You are also given that:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm First power of 2 that has leading decimal digits of 12 step by step in the C++ programming language

This C++ program contains three different implementations of a function that finds the number of leading digits that satisfy a given condition and provides a detailed analysis of each implementation's performance. Here's a breakdown of the code:

  1. Function Implementations:

    • js(int l, int n): This function is translated from a Java example and follows a simple approach. It uses logarithmic calculations to find the number of leading digits that satisfy the condition.
    • gi(int ld, int n): This function is translated from a Go example and uses integer operations to find the leading digits. It iterates through a large range of numbers, checking if they satisfy the condition.
    • pa(int ld, int n): This function is translated from a Pascal example and uses double-precision floating-point calculations to find the number of leading digits. It employs a mathematical formula to determine the range of numbers to check.

  2. params[] Array:

    • This array contains pairs of parameters used for testing the functions. Each pair consists of two integers: ld (leading digit) and n (the number of leading digits to find).

  3. doOne(string name, unsigned int (*func)(int a, int b)) Function:

    • This function takes a function pointer and its name as arguments.
    • It prints the name of the function version being tested.
    • It runs the function with the specified parameters, measuring the execution time and printing the results in a formatted manner.

  4. main() Function:

    • Sets the locale to the user's default locale to ensure consistent output formatting.
    • Calls doOne() for each of the three function implementations, providing the function pointer and its name.
    • Prints the execution time for each function.

In summary, this program provides an empirical comparison of the performance and behavior of three different implementations of a function that finds the count of leading digits that meet a specific condition. It runs the functions with various parameters and reports the execution time for each implementation.

Source code in the cpp programming language

// a mini chrestomathy solution

#include <string>
#include <chrono>
#include <cmath>
#include <locale>

using namespace std;
using namespace chrono;

// translated from java example
unsigned int js(int l, int n) {
  unsigned int res = 0, f = 1; 
  double lf = log(2) / log(10), ip;
  for (int i = l; i > 10; i /= 10) f *= 10;
  while (n > 0)
    if ((int)(f * pow(10, modf(++res * lf, &ip))) == l) n--;
  return res;
}

// translated from go integer example (a.k.a. go translation of pascal alternative example)
unsigned int gi(int ld, int n) {
  string Ls = to_string(ld);
  unsigned int res = 0, count = 0; unsigned long long f = 1;
  for (int i = 1; i <= 18 - Ls.length(); i++) f *= 10;
  const unsigned long long ten18 = 1e18; unsigned long long probe = 1;
  do {
    probe <<= 1; res++; if (probe >= ten18) {
      do {
        if (probe >= ten18) probe /= 10;
        if (probe / f == ld) if (++count >= n) { count--; break; }
        probe <<= 1; res++;
      } while (1);
    }
    string ps = to_string(probe);
    if (ps.substr(0, min(Ls.length(), ps.length())) == Ls) if (++count >= n) break;
  } while (1);
  return res;
}

// translated from pascal alternative example
unsigned int pa(int ld, int n) {
  const double L_float64 = pow(2, 64);
  const unsigned long long Log10_2_64 = (unsigned long long)(L_float64 * log(2) / log(10));
  double Log10Num; unsigned long long LmtUpper, LmtLower, Frac64;
  int res = 0, dgts = 1, cnt;
  for (int i = ld; i >= 10; i /= 10) dgts *= 10;
  Log10Num = log((ld + 1.0) / dgts) / log(10);
  // '316' was a limit
  if (Log10Num >= 0.5) {
    LmtUpper = (ld + 1.0) / dgts < 10.0 ? (unsigned long long)(Log10Num * (L_float64 * 0.5)) * 2 + (unsigned long long)(Log10Num * 2) : 0;
    Log10Num = log((double)ld / dgts) / log(10);
    LmtLower = (unsigned long long)(Log10Num * (L_float64 * 0.5)) * 2 + (unsigned long long)(Log10Num * 2);
  } else {
    LmtUpper = (unsigned long long)(Log10Num * L_float64);    
    LmtLower = (unsigned long long)(log((double)ld / dgts) / log(10) * L_float64);
  }
  cnt = 0; Frac64 = 0; if (LmtUpper != 0) {
    do {
      res++; Frac64 += Log10_2_64;
      if ((Frac64 >= LmtLower) & (Frac64 < LmtUpper))
        if (++cnt >= n) break;
    } while (1);
  } else { // '999..'
    do {
      res++; Frac64 += Log10_2_64;
      if (Frac64 >= LmtLower) if (++cnt >= n) break;
    } while (1);
  };
  return res;
}

int params[] = { 12, 1, 12, 2, 123, 45, 123, 12345, 123, 678910, 99, 1 };

void doOne(string name, unsigned int (*func)(int a, int b)) {
  printf("%s version:\n", name.c_str());
  auto start = steady_clock::now();
  for (int i = 0; i < size(params); i += 2)
    printf("p(%3d, %6d) = %'11u\n", params[i], params[i + 1], func(params[i], params[i + 1]));
  printf("Took %f seconds\n\n", duration<double>(steady_clock::now() - start).count());
}

int main() {
  setlocale(LC_ALL, ""); 
  doOne("java simple", js);
  doOne("go integer", gi);
  doOne("pascal alternative", pa);
}

You may also check:How to resolve the algorithm Abundant odd numbers step by step in the C++ programming language
You may also check:How to resolve the algorithm Accumulator factory step by step in the Delphi programming language
You may also check:How to resolve the algorithm Hostname step by step in the F# programming language
You may also check:How to resolve the algorithm Calendar step by step in the Prolog programming language
You may also check:How to resolve the algorithm Non-decimal radices/Convert step by step in the Delphi programming language