Verständnisschwierigkeiten bei (einfacher) Optimierung

Java-Forum Allgemeine Themen
1 
public class HalvingSum {
    public int halvingSum(final int n) {
        int sum = n;
        int i = 2;
        while (n / i != 0) {
            sum += n / i;
            i *= 2; // or: <<= 1
        }
        return sum;
    }

    public int halvingSum_B(final int n) {
        int sum = 0;
        int n1 = n;
        while (n1 != 0) {
            sum += n1;
            n1 /= 2; // or: >>>= 1 if n1 is not negative
        }
        return sum;
    }

    public static void main(String[] args) {
        HalvingSum s = new HalvingSum();
        System.out.println(s.halvingSum(25)); // => 47
        System.out.println(s.halvingSum_B(25)); // => 47
        for (int i = -10; i < 10; i++) {
            System.out.println(i + " " + s.halvingSum(i) + " " + s.halvingSum_B(i));
        }
    }
}

halvingSum_B stellt eine Optimierung von halvingSum dar (in einer Schleife sind zwei Rechenoperationen weniger). Ich verstehe nicht, wie man zu dieser Transformation gelangt… Habt ihr da einen Tipp für mich? Vielen Dank.

2

Keiner?

Also, wie kommt man hier vom zweiten zum dritten Schritt?

                                                                i      
                                                         i  - > - ; 0  
        n      n      n          __ n        n       __         2      
sum  =  -  +   -  +   - ...  =  \          ----  =  \                 i
        1      2      4         /__ i = 0    i      /__ i = n          
                                            2

(Ich hoffe, ich blamiere mich nicht zu sehr … )

3

Ich hab doch noch eine Verallgemeinerung gefunden:

image

    public static void a(int n, double x) {
        double sum = 0;
        for (int i = 0; i < n; i++) {
            sum += i * x;
        }
        System.out.println("sum = " + sum);
    }

    public static void b(int n, double x) {
        double epsilon = 1e-5;
        System.out.println("epsilon = " + epsilon);
        double sum = 0;
        for (double i = 0; i < n * x - epsilon; i += x) {
            sum += i;
        }
        System.out.println("sum = " + sum);
    }

    public static void main(String[] args) {
        a(10, 0.755);
        b(10, 0.755);
        a(10, 2.755);
        b(10, 2.755);
    }

b ist die Verallgemeinerung, und das * x fließt also einfach „nach oben“ in den Schleifenkopf…

Ist doch richtig, oder?