Armstrong Number Checking

What is an armstrong number ?

A number n is said to be an armstrong number of order o (o is number of digits in the number n) if it meets following condition.

d₁d₂d₃d₄d₅d₆d₇ d....do = d₁^o + d₂^o + d₃^o + d₄^o + d₅^o + d₆^o + .... d_o^o  = n
where d₁,d2,d3,d4,d₁, ... are digits in a number.
           o is number of digits in a number.
           n is the number that needs to be checked if it is an armstrong number.

Example :
1 = 1¹ = 1
2 = 2¹ = 2
.
9 = 2¹ = 9
153 = 1³ + 5³ + 3³  = 1 + 125 + 27 = 153
371 = 3³ + 7³ + 1³  = 27 + 343 + 1 = 371
.
1634 = 1⁴ + 6⁴ + 3⁴  + 4⁴ = 1 + 1296 + 81 + 256 = 1634

Algorithm : 
The steps involved in finding is a number is an armstrong or not are as follows :
1. Find the number of digits of the number - this will be our order, say O.
2. Take the last digit.
3. Calculate power O of this digit - use any function from here.
4. Add this to some predeclared sum.
5. Remove the last digit from the number.
6. Repeat steps 2 to 5 until number becomes 0.
7. Compare sum and the number - if both are same, it is armstrong number.

/*

 * C Program to check if a number is armstrong or not.

 */

// Includes

#include <stdio.h>

// Declarations

/* isArmstrong

 * Description : A function to check if given number is armstrong or not.

 * Parameters  : i_number is a number to be checked for armstrong.

 * Returns     : unsigned short 0 - for non armstrong number,

                                1 - for armstrong number.

 */

unsigned short isArmstrong(int i_number);

// Definitions

int main()

{

    int i_number;

    printf("Enter number to be checkd for armstrong : ");

    scanf("%d",&i_number);

    

    // Check if the number is armstrong

    if (isArmstrong(i_number))

    {

        printf("Entered number %d is armstrong.",i_number);

    }

    else

    {

        printf("Entered number %d is not armstrong.",i_number);

    }

}

unsigned short isArmstrong(int i_number)

{

    // numbers copy, so that when we remove last digit every time,

    // we don't loose the original number.

    int i_numberCopy = i_number;

    // stores the sum of powers if digits of a number.

    unsigned int sum = 0;

    

    unsigned int   i_numberOfDigits;

    unsigned short us_lastDigit;

    

    // Negative numbers are not armstrong numbers.

    if (i_number > 0)

    {

        i_numberOfDigits = getNumberOfDigits(i_number);

        if (i_numberOfDigits > 0)

        {

            while (0 != i_numberCopy)

            {

                // Take last digit

                us_lastDigit = i_numberCopy%10;

                

                // Calculate the power and add it in sum

                sum += bitwisePower(us_lastDigit, i_numberOfDigits);

                

                // remove the last digit

                i_numberCopy /= 10;

            }

            

            // Check if number is same as that of sum of powers of digit.

            if (i_number == sum)

            {

                return 1;

            }

        }

    }

   

    return 0 ;

}

Calculate Power Of A Number

Calculation of power of a number i.e. a^n or also called as exponent of a number - which means how many times to use a number in multiplication
Example :
7^4 - means 7 to fourth power
       - means use 7 four times in multiplication
       - means 7x7x7x7

A negative exponent on the other hand means, how many times to divide a number.
So a^-n = 1/a^n

There are different ways to implement. We will discuss about each algorithm and then write appropriate function for the same.

Algorithm 1 :
Let us talk about the simplest of the algorithm. power(a,n) literally means n times a
1. Accept number and power.
2. Multiply number with number itself power number of times.
3. Display final result.

Example : Power (3,5) = 3*3*3*3*3

So using this approach takes n-1 calculations to be performed.

/* simplePower

 * Description : A function that calculates power of number by using multplication.

 * Parameters  : f_number - number for which power needs to be calculated

 *               i_power  - power of a number

 * Returns     : float - power of number.

 */

float simplePower(float f_number, int i_power)

{

    // Initialisation

    register int powerItr;                  // Variable to traverse from 1 to n-1

    register int tempPower = abs(i_power);  // Take positive power.
    float result = 1;                       // result value

    

    for (powerItr = 1; powerItr <= tempPower; powerItr++)
    {
        result *= f_number;
    }

    

    // If power is negative number - we need to divide 1 by the final result

    return i_power<0 ? 1.0/result : result;

}

Algorithm 2 :
So far above method looks simple and logical. But, there is an optimisation for the above method.
Let us take the same example from above algorithm 1
Power (3,5) = 3*3^4                    // have to perform only one operation.
                    = 3*3^2*3^2            // have to perform only 2 operations.
                    = 3*3*3*3*3            // usual method where n-1 operations were performed.

So the steps for the algorithm would be as follows :
1. If the power of a number is even call power(a,n/2)*power(a,n/2).
2. else if power is odd call a*power(n/2)*power(n/2)
3. repeat steps 1 and 2 until power becomes 0. For power 0, return 1.

So using above approach takes O(logn) calculations.

/* recursivePower

 * Description : Calculates power of number by using recursive function call.

 * Parameters  : f_number - number for which power needs to be calculated

 *               i_power  - power of a number

 * Returns     : float - power of number.

 */

float recursivePower(float f_number, int i_power)

{

    float tempPower;

    // Power 0 results in 1

    if (0 == i_power)

    {

        return 1;

    }

    

    // Calculate f_number^(i_power/2)

    tempPower = recursivePower(f_number, i_power/2);

    

    // Check if power is even - 

    // multiply temp power to itself to calculate f_number^i_power

    if (0 == (i_power%2))

    {

        return tempPower*tempPower;

    }

    // Otherwise multiply f_number once again.

    else

    {

        // If power is negative - divide by number

        if (i_power<0)

          return (tempPower*tempPower)/f_number;

        else

          return f_number*tempPower*tempPower;

    }

}

Algorithm 3 :
We can achieve somewhat performance improvement in above algorithm by using bitwise operator. The number of iterations that are performed are decreasing as the power increases. This is what we do to achieve power for a number using bitwise operator
1. We take the number
2. If the last bit of power is 1 - then we multiply result with number
3. Right shift power by 1.
4. multiply number by itself.
5. Repeat steps 2-4 unless power becomes 0.

/* bitwisePower

 * Description : Calculates power of number by using bitwise operator.

 * Parameters  : f_number - number for which power needs to be calculated

 *               i_power  - power of a number

 * Returns     : float - power of number.

 */

float bitwisePower(float f_number, int i_power)

{

    // Initialise

    register int tempPower = abs(i_power);  // Take positive power.

    float result = 1;                       // result value

    

    // Until power becomes 0

    while (tempPower)

    {

        // Check if last bit of power is 1.

        // If yes, update the result.

        if (tempPower&1)

        {

            result *= f_number;

        }

        

        // Move on to next bit

        tempPower >>=1 ;

        

        // update number

        f_number *= f_number;

    }

    

    return  i_power<0 ? 1/result : result;

}

Test function

int main()

{

    // Initialisation

    float f_number;

    int   i_power;

    

    // Accept values

    printf("Enter number and its power to be calculated : ");

    scanf("%f %d",&f_number,&i_power);

    

    // Calculate power

    printf("Simple    %g^%d: %g\n",f_number,i_power,simplePower(f_number,i_power));

    printf("Recursive %g^%d: %g\n",f_number,i_power,recursivePower(f_number,i_power));

    printf("Bitwise   %g^%d: %g\n",f_number,i_power,bitwisePower(f_number,i_power));

}

Sample Output : 

Enter number and its power to be calculated : 2 4

Simple    2^4: 16

Recursive 2^4: 16

Bitwise   2^4: 16

Enter number and its power to be calculated : 2 -4

Simple    2^-4: 0.0625

Recursive 2^-4: 0.0625

Bitwise   2^-4: 0.0625

Enter number and its power to be calculated : 3.2 3

Simple    3.2^3: 32.768

Recursive 3.2^3: 32.768

Bitwise   3.2^3: 32.768

Calculate Factorial Of a Number

/*

 * C Program to calculate factorial of a number.

 * A factorial of a number n is calculated and represented as follows : 

 * n! = n*(n-1)*(n-2)* ...... 1

 * 0! is considered as 1.

 * factorial of negative number is undefined.

 * Example : 4! = 4*3*2*1 = 24

 *

 * Limitation : Can calculate factorial upto 65 only. 

 * We can increase this number by using unsigned long long, 

 * but it may not be supported on all the compilers.

 */

// Include

#include<stdio.h>

// Declarations

/* factorialSimple

 * Description : Simple factorial function. 

 *               Calculates factorial of a number by using loop.

 * Parameters  : ui_number is the number of which factorial is to be calculated.

 * Return      : returns calculated factorial as an unsigned int.

 */

unsigned long factorialSimple(unsigned long ui_number);

/* factorialRecursive

 * Description : Recursive factorial function. 

 *               Calculates factorial of a number by using recursive function call.

 * Parameters  : ui_number is the number of which factorial is to be calculated.

 * Return      : returns calculated factorial as an unsigned int.

 */

unsigned long factorialRecursive(unsigned long ui_number);

// Definitions

int main()

{

    int i_number;

    unsigned long ui_result;

    printf("Enter number of which factorial needs to be calculated : ");

    scanf("%d",&i_number);

    

    if (i_number >=0 )

    {

        // Let us calculate factorial by using simple method of looping

        ui_result = factorialSimple(i_number);

        printf("Factorial using simple method    : %lu\n",ui_result);

        

        // Now let's try using recursive function call

        ui_result = factorialRecursive(i_number);

        printf("Factorial using recursive method : %lu\n",ui_result);

    }

    else

    {

        printf("Factorial of negative number is undefined.\n");

    }

}

unsigned long factorialSimple(unsigned long ui_number)

{

    unsigned long result = 1;

    

    // If number is 0 or 1 - return 1

    if ((0 == ui_number) || (1 == ui_number))

        return 1;

    // Calculate by multiplying each number starting with ui_number till 2

    for (; ui_number > 1; ui_number--)

        result *= ui_number;

    

    return result;

}

unsigned long factorialRecursive(unsigned long ui_number)

{

    // If number is 0 or 1 - return 1

    if ((0 == ui_number) || (1 == ui_number))

        return 1;

    

    // Calculate factorial by giving recursive call

    return ui_number*factorialRecursive(ui_number-1);

}

Sample Output :
Enter number of which factorial needs to be calculated : 4
Factorial using simple method    : 24
Factorial using recursive method : 24

Enter number of which factorial needs to be calculated : 65

Factorial using simple method    : 9223372036854775808

Factorial using recursive method : 9223372036854775808

Enter number of which factorial needs to be calculated : 0

Factorial using simple method    : 1

Factorial using recursive method : 1

Enter number of which factorial needs to be calculated : 1

Factorial using simple method    : 1

Factorial using recursive method : 1

Enter number of which factorial needs to be calculated : -8

Factorial of negative number is undefined.

Solve Quadratic Equation

/*

 * C Program to solve quadratic equation.

 * Quadratic Equation ->  ax^2 + bx + c = 0

 * Given - values of a, b and c.

 * We need to find out values of roots of x.

 * Formula to calculate roots of x is as follows : 

 *        

 *     

 *          

 */

// Include section

#include<stdio.h>

#include<string.h>

#include<math.h>

// Declarations

// Structure to represent roots of a quadratic equation.

typedef struct

{

    float root1;                // quadratic root 1

    float root2;                // quadratic root 2

    int   isImaginary:1;        // to represent imaginary value.

    int   errorCode;            // In case there is any problem - error code.

    char  errorDescription[50]; // Short error description.

} quadRoots;

/*

 * solveQuadraticEq

 * Description : Function to solve quadratic equation.

 * Parameters  : a, b, c values of a quadratic equation.

 * Return      : Returns quadRoots structure containing roots of a quadratic equation.

 */

quadRoots solveQuadraticEq(int a, int b, int c);

// Definitions

int main()

{

int a=0,b=0,c=0;

printf("Enter values of a,b,c in following quadratic equation :\n");

printf("ax^2 + bx + c = 0\n");

scanf("%d %d %d",&a,&b,&c);

    

    // Solve Quadratic Equation

    quadRoots result = solveQuadraticEq(a,b,c);

    if (result.errorCode != 0)  // Error occurred

    {

        printf("Error : %s\n",result.errorDescription);

    }

    else if (result.isImaginary)

    {

        // Roots are imaginary - 

        // So root 1 contains -b/2a and root 2 contains sqrt(-d)/2a

        printf("Quadratic equation %dx^2%+dx%+d = 0 has complex roots : ",a,b,c);

        printf("[ %.2f%+.2fi, %.2f%+.2fi]\n", result.root1,result.root2,result.root1,-result.root2);

    }

    else

    {

        printf("Roots of Quadratic equation %dx^2%+dx%+d = 0 are : ",a,b,c);

        printf("[ %.2f, %.2f] \n", result.root1, result.root2);

    }

return 0;

}

quadRoots solveQuadraticEq(int a, int b, int c)

{

    // Initialisations

    quadRoots roots = {0,0,0,0,""};

    float discriminant;

    

    // Value of a is 0 - meaning this is not quadratic equation.

    if (0 == a)

    {

        roots.errorCode = 1000;

        strcpy(roots.errorDescription, "Not a quadratic equation");

        return roots;

    }

    

    // discriminant = b^2 - 4*a*c

    discriminant = b*b - 4*a*c;

    

    if (discriminant == 0)      // Both roots are equal

    {

        roots.root1 = roots.root2 = -b/2.0*a;

    }

    else if (discriminant < 0)  // Roots are imaginary

    {

        roots.root1 = -b/(2.0*a);

        roots.root2 = sqrt(-discriminant)/(2.0*a);

        roots.isImaginary = 1;

    }

    else                        // Roots are real numbers

    {

        roots.root1 = (-b + sqrt(discriminant)) / (2.0*a);

        roots.root2 = (-b - sqrt(discriminant)) / (2.0*a);

    }

    return roots;

}