JAVA计算3 ^ n - 3*2 ^ n + 3的最佳方法.

Question

我试图计算
((3 ^ n) - (3*(2 ^ n))+ 3)在JAVA中1 <= N <= 109.

但看起来根据问题陈述计算这个需要花费很多时间.

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

我面临的问题是

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.

任何改进代码/计算方法的建议都会有所帮助.如您所见,要显示的结果是模数(1000000000 + 7).此外,我已经尝试编写自己的幂函数,其中我在每次乘法后都在做这个模数,这也无济于事.

谢谢

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);
}