java - 为什么我的快速求幂算法在 lambda 参数中出现 'cannot find symbol' 错误？

Question

背景/我要实现的目标:

我正在尝试从头开始(作为练习)在 Java 中实现快速求幂算法。算法如下(解释摘自johndcook.com):

输入:基数b，指数n。

用二进制写出指数 n。从左数第二位开始，从左到右读取二进制表示形式。从数字 a 开始，每次读到 0 位时，将得到的值平方。每次读到 1 位时，将得到的结果平方并乘以 a。因此，可以使用不超过 2 次 log2(n) 次乘法来计算 an。

我不是在寻找更好的方法来实现这个算法，而是在寻找为什么会出现这个特定错误。

问题是什么

我试图在 Java 中使用递归 lambda 来实现这个算法，当我去运行这个程序时，我得到了以下错误:

Main.java:11: error: cannot find symbol

exponentiator = (int runningResult, int binLength, int binInt, int expBase) -> {
                                                               ^

Main.java:11: error: lambda expression not expected here

exponentiator = (int runningResult, int binLength, int binInt, int expBase) -> {
^

Main.java:23: error: cannot find symbol

exponentiator(b, length, nBinInt, b);
^

我无法解释这些错误，任何人都可以帮助我吗？

代码:

class Main {
  public static void main(String[] args) {
    fastExp(2, 13);
  }
  //This is the algorithm itself
  public static int fastExp(int b, int n) {
    //converts n (b^n) to binary for algorithm
    String nBinStr = Integer.toBinaryString(n);
    int nBinInt = Integer.parseInt(nBinStr);
    int length = String.valueOf(nBinInt).length();
    exponentiator = (int runningResult, int binLength, int binInt, int expBase) -> {
      int firstDigit = Integer.parseInt(Integer.toString(binInt).substring(1, 2));
      if(binLength = 0){
        return runningResult;
      }
      else if(firstDigit = 0){
        exponentiator((runningResult * runningResult), (binLength - 1), (binInt % (int) Math.pow(10, (int) Math.log10(binInt))), expBase);
      }
      else {
      exponentiator((runningResult * runningResult * base), (binLength - 1), (binInt % (int) Math.pow(10, (int) Math.log10(binInt))), expBase);
      }
    };
    exponentiator(b, length, nBinInt, b);
  }
}

https://repl.it/@Jodastt/Fast-Exponentiation

Answer 1

您遇到的一个主要问题是您的 lambda 没有类型。你需要给它一个。我不知道 java.util.function 中有任何类型可以表示采用 4 个参数的函数，因此您可能需要自己声明此类型。

另一个主要问题是您在其声明中使用了变量 exponentiator，这是无效的。要解决此问题，您需要向 lambda 添加第五个参数，lambda 本身将传递给该参数。然后，您将用对此参数的调用替换递归调用。

让我们先声明表示此 lambda 的类型。

interface IntQuadRecursiveFunction {
    int apply(int a, int b, int c, int d, IntQuadRecursiveFunction f);
}

然后 exponentiator 可以像这样重新声明:

// note the type and extra parameter "f"
IntQuadRecursiveFunction exponentiator = (runningResult, binLength, binInt, expBase, f) -> {
   int firstDigit = Integer.parseInt(Integer.toString(binInt).substring(1, 2));
   if (binLength == 0) { // It's "==", not "="
       return runningResult;
   } else if (firstDigit == 0) {
        // note the word "return", which you were missing
        // also the extra argument "f"
       return f.apply((runningResult * runningResult), (binLength - 1), (binInt % (int) Math.pow(10, (int) Math.log10(binInt))), expBase, f);
   } else {
       // should be "expBase", not "base"
       return f.apply((runningResult * runningResult * expBase), (binLength - 1), (binInt % (int) Math.pow(10, (int) Math.log10(binInt))), expBase, f);
   }
};

用法:

// you are missing a return in "fastExp" as well
return exponentiator.apply(b, length, nBinInt, b, exponentiator); // note the last argument

---

老实说，如果我是你，我会省去所有这些麻烦，而是编写一个普通的方法:

public static int fastExp(int b, int n) {
    //converts n (b^n) to binary for algorithm
    String nBinStr = Integer.toBinaryString(n);
    int nBinInt = Integer.parseInt(nBinStr);
    int length = String.valueOf(nBinInt).length();
    return exponentiator(b, length, nBinInt, b);
}

private static int exponentiator(int runningResult, int binLength, int binInt, int expBase) {
    int firstDigit = Integer.parseInt(Integer.toString(binInt).substring(1, 2));
    if (binLength == 0) { 
        return runningResult;
    } else if (firstDigit == 0) {
        return exponentiator((runningResult * runningResult), (binLength - 1), (binInt % (int) Math.pow(10, (int) Math.log10(binInt))), expBase);
    } else {
        return exponentiator((runningResult * runningResult * expBase), (binLength - 1), (binInt % (int) Math.pow(10, (int) Math.log10(binInt))), expBase);
    }
}