Función de potencia de escritura para números grandes

Hemos dado dos números x y n que son base y exponente respectivamente. Escriba una función para calcular x^n donde 1 <= x, n <= 10000 y puede ocurrir un desbordamiento
. Ejemplos: 
 

Input : x = 5, n = 20
Output : 95367431640625

Input : x = 2, n = 100
Output : 1267650600228229401496703205376

En el ejemplo anterior, 2^100 tiene 31 dígitos y no es posible almacenar estos dígitos incluso si usamos long long int que puede almacenar un máximo de 18 dígitos. La idea detrás es multiplicar x, n veces y almacenar el resultado en la array res[]. 
Aquí está el algoritmo para encontrar la potencia de un número.
Power(n) 
1. Cree una array res[] de tamaño MAX y almacene x en la array res[] e inicialice res_size como el número de dígitos en x. 
2. Haga lo siguiente para todos los números desde i=2 hasta n 
…..Multiplique x con res[] y actualice res[] y res_size para almacenar el resultado de la multiplicación.
Multiply(res[], x) 
1. Inicialice carry como 0. 
2. Haga lo siguiente para i=0 a res_size-1 
….a. Encuentre prod = res[i]*x+carry. 
….b. Almacene el último dígito de prod en res[i] y los dígitos restantes en carry. 
3. Almacene todos los dígitos de carry en res[] y aumente res_size por número de dígitos. 
 

C++

// C++ program to compute
// factorial of big numbers
#include <iostream>
using namespace std;
 
// Maximum number of digits in
// output
#define MAX 100000
 
// 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
int multiply(int x, int res[], int res_size) {
 
// 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;
}
 
// This function finds
// power of a number x
void power(int x, int n)
{
 
//printing value "1" for power = 0
if(n == 0 ){
    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);
 
cout << x << "^" << n << " = ";
for (int i = res_size - 1; i >= 0; i--)
    cout << res[i];
}
 
// Driver program
int main() {
int exponent = 100;
int base = 20;
power(base, exponent);
return 0;
}

Java

// Java program to compute
// factorial of big numbers
class GFG {
// Maximum number of digits in
// output
static final int MAX = 100000;
 
// 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
static int multiply(int x, int res[], int res_size) {
 
    // 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 > 0) {
    res[res_size] = carry % 10;
    carry = carry / 10;
    res_size++;
    }
    return res_size;
}
 
// This function finds
// power of a number x
static void power(int x, int n) {
     
    //printing value "1" for power = 0
    if(n == 0 ){
    System.out.print("1");
    return;
}
    int res[] = new int[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);
 
    System.out.print(x + "^" + n + " = ");
    for (int i = res_size - 1; i >= 0; i--)
    System.out.print(res[i]);
}
// Driver code
public static void main(String[] args) {
    int exponent = 100;
    int base = 2;
    power(base, exponent);
}
}
// This code is contributed by Anant Agarwal.

Python3

# Python program to compute
# factorial of big numbers
 
# Maximum number of digits in
# output
MAX=100000
 
# 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
def multiply(x, res, res_size):
 
    # Initialize carry
    carry = 0
 
    # One by one multiply n with
    # individual digits of res[]
    for i in range(res_size):
        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+=1
 
    return res_size
 
 
# This function finds
# power of a number x
def power(x,n):
     
    # printing value "1" for power = 0
     if (n == 0) :
        print("1")
        return
     
    res=[0 for i in range(MAX)]
    res_size = 0
    temp = x
 
    # Initialize result
    while (temp != 0):
        res[res_size] = temp % 10;
        res_size+=1
        temp = temp // 10
 
 
    # Multiply x n times
    # (x^n = x*x*x....n times)
    for i in range(2, n + 1):
        res_size = multiply(x, res, res_size)
 
    print(x , "^" , n , " = ",end="")
    for i in range(res_size - 1, -1, -1):
        print(res[i], end="")
 
 
# Driver program
 
exponent = 100
base = 2
power(base, exponent)
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program to compute
// factorial of big numbers
using System;
 
class GFG {
     
    // Maximum number of digits in
    // output
    static int MAX = 100000;
     
    // 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
    static int multiply(int x, int []res,
                            int res_size)
    {
     
        // 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 > 0)
        {
            res[res_size] = carry % 10;
            carry = carry / 10;
            res_size++;
        }
         
        return res_size;
    }
     
    // This function finds
    // power of a number x
    static void power(int x, int n)
    {
        //printing value "1" for power = 0
    if(n == 0 ){
    Console.Write("1");
    return;
    }
        int []res = new int[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);
     
        Console.Write(x + "^" + n + " = ");
         
        for (int i = res_size - 1; i >= 0; i--)
            Console.Write(res[i]);
    }
     
    // Driver code
    public static void Main()
    {
        int exponent = 100;
        int b_ase = 2;
        power(b_ase, exponent);
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to compute
// factorial of big numbers
 
// Maximum number of
// digits in output
 
// 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
function multiply($x, $res)
{
     
// Initialize carry
$carry = 0;
$res_size = count($res);
 
// One by one multiply
// n with individual
// digits of res[]
for ($i = 0;
    $i < $res_size; $i++)
{
    $prod = $res[$i] *
            $x + $carry;
 
    // Store last digit of
    // 'prod' in res[]
    $res[$i] = $prod % 10;
     
    // Put rest in carry
    $carry = (int)($prod / 10);
}
 
// Put carry in res and
// increase result size
while ($carry)
{
    if($carry % 10)
    $res[$res_size++] = $carry % 10;
    $carry = (int)($carry / 10);
}
return $res;
}
 
// This function finds
// power of a number x
function power($x, $n)
{
     //printing value "1" for power = 0
    if($n == 0 ){
    echo "1";
    return;
    }
$res_size = 0;
$res = array();
$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 ($i = 2; $i <= $n; $i++)
    $res = multiply($x, $res);
 
echo $x . "^" .
    $n . " = ";
$O = 0;
for ($i = count($res) - 1;
    $i >= 0; $i--, $O++)
if($res[$i])
break;
for ($i = count($res) - $O - 1;
            $i >= 0; $i--)
    echo $res[$i];
}
 
// Driver Code
$exponent = 100;
$base = 2;
power($base, $exponent);
 
// This code is contributed
// by mits
?>

Javascript

<script>
 
// Javascript program to compute
// factorial of big numbers
 
// Maximum number of digits in
// output
let MAX = 100000
 
// 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
function multiply( x,  res, res_size) {
 
// Initialize carry
let carry = 0;
 
// One by one multiply n with
// individual digits of res[]
for (let i = 0; i < res_size; i++) {
    let prod = res[i] * x + carry;
 
    // Store last digit of
    // 'prod' in res[]
    res[i] = prod % 10;
 
    // Put rest in carry
    carry = Math.floor(prod / 10);
}
 
// Put carry in res and
// increase result size
while (carry) {
    res[res_size] = carry % 10;
    carry =  Math.floor(carry / 10);
    res_size++;
}
return res_size;
}
 
// This function finds
// power of a number x
function power( x, n)
{
 
//printing value "1" for power = 0
if(n == 0 ){
    document.write("1");
    return;
}
 
 
 
let res = new Array(MAX);
let res_size = 0;
let temp = x;
 
// Initialize result
while (temp != 0) {
    res[res_size++] = temp % 10;
    temp =  Math.floor(temp / 10);
}
 
// Multiply x n times
// (x^n = x*x*x....n times)
for (let i = 2; i <= n; i++)
    res_size = multiply(x, res, res_size);
 
document.write( x + "^" + n + " = ");
for (let i = res_size - 1; i >= 0; i--)
    document.write(res[i]);
}
 
 
// Driver Code
 
let exponent = 100;
let base = 2;
power(base, exponent);
 
</script>

Producción: 
 

2^100 = 1267650600228229401496703205376

Publicación traducida automáticamente

Artículo escrito por shivani.mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *