Armstrong numbers checker

[arczi w]

I saw somewhere a task to check whether a number is an Armstrong number or not.

Armstrong numbers are those that are the sum of each of their digit to the power of digits it has.
153 = 1^3 + 5^3 + 3^3.

Shortly after I decided to write a program to accomplish this. I also found solutions that would help me, but I specifically want my idea to work (if possible).

The code below outputs bizzare numbers and I don't really know where the mistake is.

#include <iostream>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

int main()
{
    int k;
    cin>>k;

    stringstream x;
    char arr[256];
    x << k;
    x>>arr;

    int exchange = 0;
    int sum = 0;

    for(int i = 0; i < x.str().length(); i++)
    {
        exchange = pow(arr[i], x.str().length());
        sum += exchange;
    }
    cout<<exchange<<'\n';
    cout<<sum<<'\n';

    if(k == sum)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
return 0;
}

[jonnin]

its messy to mix char array and stringstream. Use strings, or use C, but mixing the two is not really clean.

arr[i] is a character. The number '1' is NOT 1. You want arr[i] - '0' I think, or convert the ascii digits to real number digits correctly here... 123 is like 40^3+41^3+42^3 (^ being power) or something along those lines...

[arczi w]

That explains why everytime I type 0 I get 48.

Should I convert it using static_cast? I tried doing so inside the for loop but it refuses to work properly.

[lastchance]

@Gieniusz Krab
Why are you using strings, stringstreams or (heaven forbid) complex numbers?

The number of digits is just the number of times that you would have to integer-divide by 10 before you got 0.

e.g. 153 -> 15 -> 1 -> 0, so it has three digits.

Alternatively, and more expensively, use logs.

If you work entirely with integers you won't have to worry about casting anything.

Also, repeated-multiply is going to be considerably cheaper (and less prone to floating-point rounding) than using the pow function.

[arczi w]

As I said, I wanted to try out other possibilites.

Also, I am still looking for a way to convert those characters, but I wondered what would happen if I just type

arr[i] = arr[i] - 48

.
I obviously do not intend to do this this way, but it kind of works. Outputs correct answers sometimes, it has problems with some numbers, says sum is 152 in case of 153, 9800816 in case of 9800817 so that it seems a minor flaw is playing a role. Can someone explain me why is that?

[JLBorges]

> says sum is 152 in case of 153, 9800816 in case of 9800817 so that it seems a minor flaw is playing a role.

The floating point representation is an inexact representation, and floating point arithmetic is inexact arithmetic.
Use integer arithmetic (which is exact).

#include <iostream>

unsigned int ipow( unsigned int base, unsigned int exponent )
{ return exponent == 0 ? 1 : base * ipow( base, exponent-1 ) ; }

unsigned int num_digits( unsigned int number, unsigned int base = 10 ) // base != 0
{ return number < base ? 1 : 1 + num_digits( number/base ) ; }

unsigned int sum_pow_digits( unsigned int number, unsigned int base = 10 ) // base != 0
{
    if( number < base ) return number ;

    const unsigned int ndigits = num_digits( number, base ) ;
    unsigned int sum = 0 ;
    for( ; number > 0 ; number /= base ) sum += ipow( number%base, ndigits ) ;
    return sum ;
}

bool is_armstrong( unsigned int number, int base = 10 ) // base != 0
{ return number > 0 && number == sum_pow_digits( number, base ) ; }

int main()
{
    for( unsigned int n = 0 ; n < 10'000'000 ; ++n )
        if( is_armstrong(n) ) std::cout << n << '\n' ;
}

http://coliru.stacked-crooked.com/a/b3f580632d5e90e4

[lastchance]

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

int numDigits( int n ) { return n < 10 ? 1 : 1 + numDigits( n / 10 ); }

bool isArmstrong( int n )
{
   int power = numDigits( n );
   valarray<int> digits( power );
   for ( int p = 0, nn = n; p < power; p++, nn /= 10 ) digits[p] = nn % 10;
   valarray<int> product = digits;
   while ( --power ) product *= digits;
   return product.sum() == n;
}

int main()
{
   for ( int n = 1; n <= 10000000; n++ ) if ( isArmstrong( n ) ) cout << n << '\n';
}

[lastchance]

#include <iostream>
using namespace std;

using INT = unsigned long long;
const int MAXDIGITS= 9;
INT powers[11][1+MAXDIGITS];                     // may be more efficient to precompute powers


void setPowers()
{
   for ( int d = 0; d <= 10; d++ )
   {
      powers[d][0] = 1;
      for ( int p = 1; p <= MAXDIGITS; p++ ) powers[d][p] = d * powers[d][p-1];
   }
}


bool isArmstrong( INT n, int digits )
{ 
   INT sum = 0, nn = n;
   while ( nn > 0 )
   {
      sum += powers[nn%10][digits];
      if ( sum > n ) return false;               // quick exit
      nn /= 10;
   }
   return sum == n;
}


int main()
{
   setPowers();

   for ( int digits = 1; digits <= MAXDIGITS; digits++ )
   {
      for ( int n = powers[10][digits-1]; n < powers[10][digits]; n++ ) if ( isArmstrong( n, digits ) ) cout << n << endl;
   }
}

1
2
3
4
5
6
7
8
9
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153

[jonnin]

you can use pow for integers, x = pow(a,b) + 0.5; will fix the issue. Floating point errors are going to be either something like 3 represented as 2.99999999999999999 or 3.0000000000001
and in either case adding 1/2 will give the correct integer. Whether this is any 'better' ... I can't say. The nature of powers are that they tend to be small for integer math making any choice fine.

[JLBorges]

> Floating point errors are going to be either something like 3 represented as 2.99999999999999999
> or 3.0000000000001 and in either case adding 1/2 will give the correct integer.

The errors in floating point computations depend on the ulps involved in the intermediate values generated during the computation. There is no guarantee that adding 0.5 would yield the exact nearest integer result.

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    const double value = 1234567890123456789 ;
    double start = std::nextafter( value, value/2 ) ;
    double end   = std::nextafter( value, value*2 ) ;
    const double delta = (end-start)/4 - 1 ;

    std::cout << std::fixed << std::setprecision(0)
              << "initially, start == " << start << '\n'
              << "             end == " << end << '\n'
              << "       end-start == " << end-start << '\n'
              << "           delta == " << delta << "\n\n" ;

    std::cout << "execute start += " << delta << " ; and end -= " << delta
              << " ; in a loop\n\n" ;

    for( int cnt = 1 ; cnt < 1'000'000 && start < end ; ++cnt )
    {
        start += delta ;
        end -= delta ;
        if( cnt%100'000 == 0 )
            std::cout << "after " << cnt << " iterations, start == "
                      << start << " and end == " << end << '\n' ;
    }
} 

http://coliru.stacked-crooked.com/a/28d02a720589b7e7

[jonnin]

In general, I agree, but specifically for pow, there should not be any (or at most 1) intermediate values for rounding error accumulation. It isnt computed via iteration, its a O(1) calculation. Adding 1/2 obviously does not work for negative values either, for another issue.

I would be very interested to see an int to a positive int power where this does not work. I could be wrong ... I am assuming pow is done via bit twiddles or something that directly produces the value.

[JLBorges]

> there should not be any (or at most 1) intermediate values for rounding error accumulation

The accuracy of a floating point computation does not depend only on the number of intermediate values;
it also depends on the ulps of the values that are involved.


> I would be very interested to see an int to a positive int power where this does not work.

It would work for a sufficiently small int raised to a sufficiently small positive int, yielding a sufficiently small result, where all the ulps involved are small.

When the ulps are larger it doesn't work.

#include <iostream>
#include <iomanip>
#include <limits>
#include <cstdint>
#include <cmath>

int main()
{
     constexpr unsigned long long int_val = std::numeric_limits<std::uint16_t>::max() - 1 ;
     constexpr unsigned long long pow = int_val*int_val*int_val*int_val ;
     const double pow_plus_1000 = std::pow( int_val, 4 ) + 1000 ;

     std::cout << "      integer (exact) value of pow: " << pow << '\n'
               << "computed floating_point_pow + 1000: " << std::fixed << pow_plus_1000 << '\n' ;
}

      integer (exact) value of pow: 18444492376972984336
computed floating_point_pow + 1000: 18444492376972984320.000000

http://coliru.stacked-crooked.com/a/7b8072a6549fa63b

[jonnin]

thanks!

[jonnin]

That is a lot harder problem than I expected. You can hack around with doubles and logs and stuff to get the answer quickly, in O(1), but it is just as prone to roundoff and problems as the above and accomplishes nothing at all. There are a couple of hacks that can approximate the value as well but approximate won't do.

I took a play-time crack at it and the best I could do for 64 bit ints raised to a positive int power was 13 multiplies. My approach did all 13 whether we need them or not, so its worse than the loop approach for small powers, and better for any power > 13.

Here is what I came up with. I am trying to see if there is a cleaner way to avoid the excess memory allocation & the unnecessary multiplies. I will play with it a bit more but here is what I have so far.

--edit, my trivial cases are out of order. I will fix that too, duh. Also, the high end multiplies can overflow for some values. I haven't handled that, obviously.

given that 2 can get to 64th power tops and 10 19th power tops and it falls off very rapidly from there, the loop is really the better solution. This is just messing around, admittedly.

long long intpwr(long long b, unsigned long long e)
{
//13 multiplies and 3 jumps works for 64 bit ints. 
//2^64 is the largest that will fit in a 64 bit int. 
//1^any and 0^ any are handled.  
  long long pwrs[65]; //wastes a lot of space, improve?
  if(e > 64) return 0;  //won't fit!
  if(e == 0) return 1; //shortcuts for trivial cases  
  if(e ==1 || b == 1 || b==0 ) return b;  
  
  long long result = 1;  
  pwrs[0] = 1;
  pwrs[1] = b;
  pwrs[2] = b*b;  
  pwrs[4] = pwrs[2]*pwrs[2];
  pwrs[8] = pwrs[4]*pwrs[4];
  pwrs[16] = pwrs[8]*pwrs[8];
  pwrs[32] = pwrs[16]*pwrs[16];
  pwrs[64] = pwrs[32]*pwrs[32]; 
  result *= pwrs[1&e];   
  result *= pwrs[2&e];   
  result *= pwrs[4&e];   
  result *= pwrs[8&e];   
  result *= pwrs[16&e];   
  result *= pwrs[32&e];   
  result *= pwrs[64&e];   
  return result;
}