power_for_huge_numbers.cpp File Reference

Compute powers of large numbers. More...

#include <iostream>

Include dependency graph for power_for_huge_numbers.cpp:

Macros
#define	MAX   100000

Functions
int	multiply (int x, int res[], int res_size)
void	power (int x, int n)
int	main ()

Detailed Description

Compute powers of large numbers.

Macro Definition Documentation

MAX

#define MAX   100000

Maximum number of digits in output \(x^n\) where \(1 <= x,\; n <= 10000\) and overflow may happen

Function Documentation

main()

int main

(

void

)

Main function

           {
    int exponent, base;
    std::cout << "Enter base ";
    std::cin >> base;
    std::cout << "Enter exponent ";
    std::cin >> exponent;
    power(base, exponent);
    return 0;
}

Here is the call graph for this function:

multiply()

int multiply	(	int	x,
		int	res[],
		int	res_size )

This function multiplies x with the number represented by res[]. res_size is size of res[] or number of digits in the number represented by res[]. This function uses simple school mathematics for multiplication. This function may value of res_size and returns the new value of res_size

Parameters

x	multiplicand
res	large number representation using array
res_size	number of digits in res

                                             {
    // Initialize carry
    int carry = 0;
 
    // One by one multiply n with
    // individual digits of res[]
    for (int i = 0; i < res_size; i++) {
        int prod = res[i] * x + carry;
 
        // Store last digit of
        // 'prod' in res[]
        res[i] = prod % 10;
 
        // Put rest in carry
        carry = prod / 10;
    }
 
    // Put carry in res and
    // increase result size
    while (carry) {
        res[res_size] = carry % 10;
        carry = carry / 10;
        res_size++;
    }
    return res_size;
}

power()

void power	(	int	x,
		int	n )

This function finds power of a number x and print \(x^n\)

Parameters

x	base
n	exponent

                         {
    // printing value "1" for power = 0
    if (n == 0) {
        std::cout << "1";
        return;
    }
 
    int res[MAX];
    int res_size = 0;
    int temp = x;
 
    // Initialize result
    while (temp != 0) {
        res[res_size++] = temp % 10;
        temp = temp / 10;
    }
 
    // Multiply x n times
    // (x^n = x*x*x....n times)
    for (int i = 2; i <= n; i++) res_size = multiply(x, res, res_size);
 
    std::cout << x << "^" << n << " = ";
    for (int i = res_size - 1; i >= 0; i--) std::cout << res[i];
}

Here is the call graph for this function: