JAVA The best way to calculate 3 ^ n - 3 * 2 ^ n + 3.

Question

I am trying to calculate ((3 ^ n) - (3 * (2 ^ n)) + 3) for 1 <= N <109 in JAVA.

But it seems like it takes a long time to calculate this to describe the problem.

double mul =  Math.pow(3,k);
double mul2 = Math.pow(2,k);    
double res =  ((mul - ((3* mul2)) + 3 ) % (1000000000 + 7));

The problems I am facing are

1) Time limit exceeded in java.(which should be less than 1 sec)
2) The result goes out of limit and thus provides wrong output.

Any suggestion for improving the code / calculation method would be helpful. As you can see, the result to be displayed must be modulo (1,000,000,000 + 7). I also tried to write my own power function, in which I do it modulo after each multiplication, which also does not help.

thank

Answer 1

BigIntegers , .

.

, Aₙ:= 3ⁿ mod 1000000007 Bₙ:= 3×2ⁿ mod 1000000007.

: Aₙ₊ₗ= 3×Aₙ mod 1000000007 Bₙ₊ₗ= 2×Bₙ mod 1000000007.

%.

, 2×1000000007 32- . 3×1000000007, 3 .

, , , 1000000007.

private static int sum(int x, int y)
{
    return x >= 1000000007 - y ? x - (1000000007 - y) : x + y;
}

private static int sub(int x, int y)
{
    return x < y ? x + (1000000007 - y) : x - y;
}

int n;
int a= 1;
int b= 3;
for (n= 1; n <= 109; n++)
{
    a= sum(sum(a, a), a);
    b= sum(b, b);
    int res= sum(sub(a, b), 3);
}

Answer 2

JAVA , a ^ b b. , , O (log (b)).

  long long power(long long a,long long b)
  {
        if(b==0)return 1;
        long long ans=power(a,b/2);
        ans=(ans*ans)%1000000007;
        if(b%2)ans=(ans*a)%1000000007;
        return ans;
  }

c/++, JAVA.

, 1 <= N <= 109, . , , .

• GP 3, 9,.... 3 ^ (109), 3 (3 ^ (109) -1)/2, 3 ^ (109) MOD 1000000007 , . ( MOD, 2) . O (log (109)).
• GP .
• - 3 * 109

Answer 3

BigInteger .  ,

private static final BigInteger TWO = new BigInteger("2");
private static final BigInteger THREE = new BigInteger("3");

//input n, m (modulo)
public static BigInteger getResult(BigInteger n, BigInteger m) {
    BigInteger a = THREE.modPow(n, m);
    BigInteger b = TWO.modPow(n, m);

    return a.subtract(THREE.multiply(b)).add(THREE).mod(m);

}

* for, , n n-1 . , 3 ^ n 3 ^ (n-1) * 3

Answer 4

, BigInteger. -, BigInteger , -, :

BigInteger  modPow(BigInteger exponent, BigInteger m)

BigInteger, ( mod m).

If you are wondering, on the other hand, why this is not working (i.e. too slow), I would recommend you the following article explaining the efficiency of an integer exponent .