Thread: help with my namespace

hey, so I have been working on project euler again, and I have been putting all of my non-problem functions under the namespace utility_functions. What should I do to improve clarity, and what would be a better name for this namespace?

Also, what is wrong with sum_of_divisors()? It consistently gives low values. The formula is from http://planetmath.org/FormulaForSumOfDivisors.html

Code:

#ifndef utility_functions
#define utility_functions

#include <vector>
#include <cstdlib>
#include <cmath>

using namespace std;

namespace utility_functions
{
  long long sqrt_number;
  long long number;

  void set_common_numbers(long long number_in)
  {
    sqrt_number = sqrt(number_in);
    number = number_in;
    return;
  }

  bool is_prime(long long number_in)
  {
    set_common_numbers(number_in);
    if(number == 0 || number == 1)
      return 0;
    for(long long b = 2; b < sqrt_number; b++)
    {
      if(number % b == 0)
        return 0;
    }
    return 1;
  }

  int smallest_divisor(long long number_in)
  {
    int my_sqrt_number = sqrt(number_in);
    for(long long a = 2; a < my_sqrt_number; a++)
      if(number_in % a == 0)
        return a;
    return number_in;
  }

  vector<short> prime_factor_field() //returns a vector of shorts that tell the multiplicity of each prime factor up to the square root of the number
  {
    vector<short> factor_field (sqrt_number, 0);
    bool all_prime_factors_found = 0;
    long long working_number = number;
    while(!all_prime_factors_found)
    {
      int current_factor = smallest_divisor(working_number);
      if(current_factor == working_number)
      {
        all_prime_factors_found = true;
      }
      else
      {
        factor_field[current_factor]++;
        working_number /= current_factor;
      }
    }
    return factor_field;
  }

  long long number_of_divisors(long long number_in)
  {
    set_common_numbers(number_in);
    int divisors = 2;
    vector<short> factor_field = prime_factor_field();
    for(int a = 0; a < sqrt_number; a++)
        divisors *= factor_field[a] + 1;
    return divisors;
  }

  long long sum_of_divisors(long long number_in)
  {
    set_common_numbers(number_in);
    int sum = 1;
    vector<short> factor_field = prime_factor_field();
    for(int a = 2; a < sqrt_number; a++)
    {
      if(factor_field[a] > 0)
      {
        sum *= (pow(a, factor_field[a] + 1) - 1) / (a - 1);
      }
    }
    return sum;
  }
}
#endif

I'd suggest the name of the namespace reflect what the functions in it achieve, such as SolveProjectEulerProblemX where X is the problem you're addressing.

If I'm reading the formula on planetmath right (haven't tried to validate) the line

Code:

sum *= (pow(a, factor_field[a] + 1) - 1) / (a - 1);

should be

Code:

sum *= pow(a, factor_field[a] + 1) - 1 / a - 1;

In other words, you have assumed groupings (or operator precedence) that the math formulas have not.

More generally, your code is likely to be inaccurate since it uses floating point variables and functions (and relies on integer divisions producing real results, which they do not). Floating point variables are NOT a general representation of real numbers - they are an approximation.

Thank for the help on naming and the formula, it is working far better now, but I might still need to validate the formula.
I don't quite understand the part about floating points, the only place that I use anything other than integers is sqrt(), and IIRC any float transferred into an integer will simply ignore the decimal, similar to floor().

BTW: (x^n)-1 is always evenly divisible by x-1

Originally Posted by bobknows

I don't quite understand the part about floating points, the only place that I use anything other than integers is sqrt(), and IIRC any float transferred into an integer will simply ignore the decimal, similar to floor().

pow() is also a floating point function.

My basic point is that your code is making certain implicit but incorrect assumptions about how floating point calculations work, and about how conversions between floating point and integral types work.

The maximum value of a 64-bit floating point type (the typical double) can exceed the maximum value of a 64-bit integral type (the typical long long, whether signed or unsigned) by some orders of magnitude. It therefore doesn't take a lot of work to show that converting a floating point value to an integral type does more than "ignoring the decimal". It also doesn't take much work to show that a 64-bit integer type can represent some integral values that a 64-bit floating point type cannot.

As I said, your code embodies several invalid assumptions. It might work when playing with some small primes but, as the prime values or their powers increase, the results will be increasingly inaccurate.