问Naive的算法变体
EN

Stack Overflow用户

提问于 2013-12-03 11:32:22

回答 1查看 125关注 0票数 0

伙计们，我正在做多项式计算，并使用Naive，Horner和FFT等算法，现在我的问题中有一句话说。

Run a variation of the naïve algorithm, where the exponentiation
is performed by repeated squaring, a decrease-by-half algorithm

我不明白，我目前的朴素算法是：

public Complex naive(Polynomial poly, Complex x) {
    Complex p = new Complex();
    for (int i = poly.getCoef().length - 1; i >= 0; i--) {
        Complex power = new Complex(1, 0);
        for (int j = 1; j <= i; j++) {
            power = power.multiply(x);

        }
        p = p.add(poly.getCoef()[i].multiply(power));
        multiplyCountNaive++;
    }
    return p;

}

请解释需要修改的内容。谢谢

java

回答 1

Stack Overflow用户

发布于 2013-12-03 19:38:28

我明白了，应该是这样的。

public Complex naive2(Polynomial poly, Complex x) {
    Complex p = new Complex();
    for (int i = poly.getCoef().length - 1; i >= 0; i--) {
        p = p.add(poly.getCoef()[i].multiply(expo(x, i)));
        multiplyCountNaive2++;
    }
    return p;

}

private Complex expo(Complex a, int b) {
    if (b == 0) {
        return new Complex(1, 0);
    } else if (b == 1) {
        return a;
    }

    if (b % 2 == 0) {
        return expo(a.multiply(a), b / 2);
    } else {
        return a.multiply(expo(a.multiply(a), (b - 1) / 2));
    }

}

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/20342364

复制

相似问题

问Naive的算法变体
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Naive的算法变体EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Naive的算法变体
EN