通过平方求幂(获得乘法数) [英] Exponentiation by squaring (getting the number of multiplications)

问题描述

我正在做作业，因为我必须使用通过平方求幂做两件事.一种是获取乘法数，另一种是获取实际结果.

I'm doing a homework were I have to do two things using exponentiation by squaring. One is to get the number of multiplications and the other is getting the actual result.

以下是一些示例:

2
11

应该输出

2048
5

因为 2 ^ 11 = 2(2(((2)²)²)²)²

我这样做是没有递归的，但是我得到的结果是正确的，但是乘法的次数是错误的.如果我输入 2 ^ 6 ，我得到 3 乘法，那是可以的，但是如果我输入 2 ^ 8 ，我得到> 4 乘法，这是错误的.

I'm doing this without recursion and I'm getting the result right but the number of multiplications is wrong. If I input 2^6 I'm getting 3 multiplications and that is OK but If I input 2^8 I'm getting 4 multiplications and this is wrong.

您能指出我在进行正确乘法运算时做错了什么吗?

Can you point me to what I'm doing wrong in getting the correct multiplications involved?

这是代码:

public static void main(String[] args) {
    double x, result = 1;
    int n, multiplications = 0;
    DecimalFormat df = new DecimalFormat("#.00");
    Scanner readLine = new Scanner(System.in);

    x = readLine.nextDouble();
    n = readLine.nextInt();

    if (n == 1) {
        multiplications++;
        System.out.print(df.format(x) + "\n" + multiplications + "\n");
    } else if (n == 2) {
        x *= x;
        multiplications++;
        System.out.print(df.format(x) + "\n" + multiplications + "\n");
    } else {
        while (n > 0) {
            if (n % 2 == 0) {
                multiplications++;
            } else {
                multiplications++;
                result *= x;
                n--;
            }
            x *= x;
            n /= 2;
        }
        System.out.print(df.format(result) + "\n" + multiplications + "\n");
    }
}

推荐答案

如果 n％2 == 0 ，则不相乘；你只是广场.因此，请远离 multiplications ++ .

If n % 2 == 0, you do not multiply; you just square. so leave the multiplications++ away.

然后，对于2 ^ 8，您将得到:

Then for 2^8 you get:

n  |  n % 2  |  multiplications
----------------------
8  |  0      |  0
4  |  0      |  0
2  |  0      |  0
1  |  1      |  1

1乘法应该是正确的.由于 2 ^ 8 =((((1²* 2)²)²)²)²

And 1 multiplication should be correct. Since 2^8 = (((1² * 2)²)²)²

如果您想将平方算作乘法，则应该这样做

If you want to count squaring as a multiplication, you should do

... else
    multiplications = multiplications + 2

然后减去2进行初始平方和乘法.

And afterwards subtract 2 for the initial squaring and multiplication.

总的来说:

while (n > 0) {       
    if(n % 2 == 1) {
        multiplications++;
        result *= x;
        n--;
    }
    multiplications++;
    x *= x; // shouldn't that be result *= result?
    n /= 2;
}
multiplications -= 2;

这篇关于通过平方求幂(获得乘法数)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！