0

Problem:

In a given range (a, b) ( a <= b, 2 <= a, b <= 1000000 ) find all natural numbers that can be expressed in format x ^ n ( x and n are natural numbers ). If there are more than one possibility to present expressed number, present it with a bigger exponential value.

U1.txt Screen
40 110 49 = 7^2; 64 = 2^6; 81 = 3^4; 100 = 10^2; 
#include <iostream>
#include <fstream>
#include <cmath>

int Power(int number, int base);

int main()
{
    int a, b;

    std::ifstream fin("U1.txt");
    fin >> a >> b;
    fin.close();
    
    for (int i = a; i <= b; i++)
    {
        int max_power = 0;
        int min_base = 10;
        bool found = false;
        for (int j = 2; j <= 10; j++)
        {
            int power = Power(i, j);
            if (power > 0)
            {
                if (max_power < power) { max_power = power; }
                if (min_base > j) { min_base = j; }
                found = true;
            }
        }
        if (found)
        {
            std::cout << i << " = " << min_base << " ^ " << max_power << "; ";
        }
    }
    
    return 0;
}

int Power(int number, int base)
{
    int power = (log(number) / log(base) + 0.5);
    if (pow(base, power) == number)
    {
        return power;
    }
    return 0;
}

I solved the problem. However, I don't understand few things:

  1. How the int Power(int number, int base) function works. Why the log function is used? Why after division of two log functions the 0.5 is added? I found the Idea on the Internet.
  2. I am not sure if this solution works on all cases. I didn't know what could be the biggest value of the base number so my for (int j = 2; j <= 10; j++) loop is going from 2 to 10. If there is a number that base is bigger the solution won't work.

Are there any easier ways to solve this problem?

user10203585
  • 105
  • 6
  • 1
    The `+ 0.5` is a crude way of implementing `std::round(log(number) / log(base))`. It doesn't always work. Personally I'd avoid any floating point stuff when solving an integer problem. – Bathsheba Aug 04 '21 at 09:13
  • The `log(a) / log(b)` (both are some base `c`) is the same as the `log(a)` base `b`. And the addition of the `0.5` is intended to round up when we initiate the `int` variable `power`. – rawrex Aug 04 '21 at 09:17
  • You could detail that the exponent `n` must be at least equal to 2. Did you write this code ? Moreover, do you have any efficiency constraint? – Damien Aug 04 '21 at 09:50
  • There are given no details about exponent `n` in the problem. Yes, I wrote this code myself, but `int Power(int number, int base)` is not my idea. There are no efficiency constrants. This is a problem from one university in my country. – user10203585 Aug 04 '21 at 10:00
  • @rawrex what is the point of rounding value? Shouldn't it be either correct or incorrect using only integer values? – user10203585 Aug 04 '21 at 10:33
  • @user10203585 as has been noted, that's where the troubles will come from - from mixing floats and integers. The `log(a) / log(b)` well may not be an integer. – rawrex Aug 04 '21 at 10:39
  • Please note that both `pow` and `log` return (and [convert their arguments to](https://en.cppreference.com/w/cpp/numeric/math/log)) a `double`, so that the posted code isn't using *only* integer values. – Bob__ Aug 04 '21 at 11:33
  • @rawrex so removing + 0.5 won't change anything, as I use only integer values? – user10203585 Aug 04 '21 at 11:36
  • @Bob_ Yes, but using these functions should not make any impacts to the results, because either 7 or 7.0 still has to be powered by either 2 or 2.0 to get 49. Am I wrong? Then + 0.5 has no impacts when my input is only natural numbers? – user10203585 Aug 04 '21 at 12:25
  • Except, e.g. `log(1000)/log(10)` may evaluate to a `double` *close* to 3, but less than 3, like `2.9999999999999996` and when you store it in an `int` it's truncated to `2`. – Bob__ Aug 04 '21 at 13:49

1 Answers1

0

How does the function work?

That's something the OP should have asked to the authors of that snippet (assuming it was copied verbatim or close).

The intent seems to check if a whole number power exists, such that in combination with the integral arguments number and base the following equation is satisfied:

number = base power

The function returns it or 0 if it doesn't exist, meaning that number is not an integral power of some integral base. To do so,

  • it uses a property of the logarithms:

    n = bp
    log(n) = p log(b)
    p = log(n) / log(b)

  • it rounds the number[1] to the "closest" integer, to avoid cases where the limited precision of floating-point types and operations would have yield incorrect results in case of a simple truncation.

    In the comments I've already made the example of std::log(1000)/std::log(10), which may produce a double result close to 3.0, but less than 3.0 (something like 2.9999999999999996). When stored in an int it would be truncated to 2.

  • It checks if the number found is the exact power which solve the previous equation, but that comparison has the same problems I mentioned before.

    pow(base, power) == number  // It compares a double with an int

Just like std::log, std::pow returns a double value, making all the calculations performed with those functions prone to subtle numerical errors (either by rounding or by accumulation when multiple operations are involved). It's often preferable to use integral types and operations, if possible, when accuracy (or absolute exactness[2]) is needed.

Is the algorithm correct?

I didn't know what could be the biggest value of the base number so my for loop is going from 2 to 10

That's just wrong. One of the constraints of the problem is b <= 1'000'000, but the posted solution couldn't find any power greater than 102.

An extimate of the greatest possible base is the square root of said b.

Are there any easier ways to solve this problem?

Easiness is subjective and we don't know all the requirements and constraints of OP's assignment. I'll describe an alternative solution without posting the code I wrote to test it[3].

OP's code considers all the numbers between a and b checking for every (well, up to 10) base if there exists a whole power.

My proposal uses only integral variables, of a wide enough type, say long (any 32-bit integer is enough).

  • The outer loop starts from base = 2 and increments it by one at every step.

  • Inside this loop, exponent is set to 2 and value to base * base

  • If value is greater than b, the algorithm stops.

  • While value is less than a, updates it (multiplying it by base) and the exponent (it's incremented by one). We need to find the first power of base which is greater or equal to a.

  • While value is less than or equal to b, store the triplet of variables value, base and exponent in suitable container.

    Consider a std::map<long, std::pair<long, long>>, it lets us associate all the values with the corresponding pair of base and exponent. Also, it could be later traversed to obtain all the values in ascending order.

    The assignment requires, in case of multiple powers, to present only the one with the bigger exponent. In the example, it shows 64 = 26, ignoring 64 = 43. Note the needed one is the one with the smaller base, so that it's enough to ignore any further value if it's already present in the map.

    value and exponent are updated as before.

Note that this algorithm only consider bases up to the square root of b (in the outer loop) and the number of iterations of the inner loop is much more limited (with base = 2, it would be less than 20, beeing 220 > 1'000'000. Greater bases would stop sooner and sooner).

[1] See e.g. Why do lots of (old) programs use floor(0.5 + input) instead of round(input)?

[2] See e.g. The most efficient way to implement an integer based power function pow(int, int)

[3] How do I ask and answer homework questions?

Bob__
  • 12,361
  • 3
  • 28
  • 42