-6

I want to calculate the power of huge number using C#

I've used this code. it works but I want to calculate it in less time.

BigInteger a;
a = Math.Pow(4100000000,4100000000);
Console.Writeline(a);
President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
Guufulltun
  • 1
  • 1
  • 1
    Can you share the current time? – Elminson De Oleo Baez May 04 '19 at 20:05
  • Is your exponent an integer number (doesn't have a decimal point)? – Maxim Khanov May 04 '19 at 20:06
  • I don't remember exactly but more than 2 hours. – Guufulltun May 04 '19 at 20:12
  • Yes it is an integer. – Guufulltun May 04 '19 at 20:12
  • 2
    1. Not a C# coder but Are you sure `Math.Pow(4100000000,4100000000)` is computed on BigIntegers? 2. The result of your operation is `~130925204732` bits long. The floating `pow` is using `log,exp` functions and I would expect that is way slower than the Integer power by squaring on such big numbers. See [Power by squaring for negative exponents](https://stackoverflow.com/a/30962495/2521214) Anyway You would need a lot of big multiplications so even with [Schönhage-Strassen fsqr](https://stackoverflow.com/q/18465326/2521214) it will take time so 2hr looks reasonable. – Spektre May 05 '19 at 07:32
  • Your code doesn't compile, so we have to guess your meaning. Please edit your question to correct this. – President James K. Polk May 05 '19 at 14:07
  • I think there is no optimization for this problem. – Guufulltun May 05 '19 at 17:53
  • @Guufulltun such big numbers powered are usually taken in some modulo arithmetics that is way faster (see `modpow` in the NTT implementation from the `fsqr` link). I see no practically real use for the full value anyway. – Spektre May 06 '19 at 07:08

1 Answers1

-1

You can test this but not sure if this is faster than the native function Math.Pow

using System; 

public class GFG{ 

    static float power(float x, int y) 
    { 
        float temp; 

        if( y == 0) 
            return 1; 
        temp = power(x, y/2);  

        if (y % 2 == 0) 
            return temp * temp; 
        else
        { 
            if(y > 0) 
                return x * temp * temp; 
            else
                return (temp * temp) / x; 
        } 
    }  

    // Program to test function power  
    public static void Main() 
    { 
        float x = 2; 
        int y = -3; 

        Console.Write(power(x, y));

        float x = 4100000000; 
        int y = 4100000000; 

        Console.Write(power(x, y)); 

    } 
}

Time Complexity: O(logn)

Space Complexity: O(1)

Algorithmic Paradigm: Divide and conquer.

Elminson De Oleo Baez
  • 580
  • 5
  • 13