2022-07-04 / Bartłomiej Kurek
Project Euler #6: Sum square difference

Problem 6: Sum square difference

The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural
numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred
natural numbers and the square of the sum.

Kod: repozytorium git.


Python (variant 1: for loop)

Najprostszy wariant:
- iterujemy liczby w zadanym przedziale
- w jednej zmiennej śledzimy sumę (s)
- w drugiej zmiennej zliczamy kwadraty liczb (sq)
- w wyniku zwracamy (s * s - sq)

def simple(n):
    sq = 0
    s = 0
    for i in range(1, n + 1):
        s += i
        sq += i * i

    return s * s - sq

Uruchamiamy:

$ time python code/python/prog.py
25164150

real    0m0.022s
user    0m0.022s
sys 0m0.000s


$ time python code/python/prog.py 10000000
2500000166666641666665000000

real    0m1.241s
user    0m1.233s
sys 0m0.008s

Python (variant 2: map, sum, zip)

def lispy(n):
    s, sq = map(sum, zip(*[(_, _ * _) for _ in range(1, n + 1)]))
    return s * s - sq

Uruchamiamy:

$ # original number
$ time python code/python/prog.py
25164150

real    0m0.022s
user    0m0.022s
sys 0m0.000s


$ # larger number
$ time python code/python/prog.py 10000000
2500000166666641666665000000

real    0m7.208s
user    0m6.231s
sys 0m0.936s

Tutaj widzimy, że koszt wywołania funkcji jest wysoki. Wariant z pętlą for trwał około sekundy.

Python (variant 3: "perl golf")

"Czy da się w jednej linii kodu?"

def perl_golf(n):
    return [
        (k * k - v) for k, v in [
            list(map(sum, zip(*[(_, _ * _) for _ in range(1, 100 + 1)])))
        ]
    ][0]

Uruchamiamy:

$ time python code/python/prog.py
25164150

real    0m0.022s
user    0m0.022s
sys 0m0.000s

$ time python code/python/prog.py 10000000
2500000166666641666665000000

real    0m6.928s
user    0m6.251s
sys 0m0.663s

Praktycznie to samo (wynika to z kodu, tutaj również mamy całość map/sum/zip).

Benchmark (Python)

$ python code/python/prog.py -t 5
--------------------------------------------------------------------------------
→ simple
   →              simple-1000        5 0.00054079
   →             simple-10000        5 0.00561517
   →            simple-100000        5 0.05979806
   →           simple-1000000        5 0.63093591
--------------------------------------------------------------------------------
→ lispy
   →               lispy-1000        5 0.01849611
   →              lispy-10000        5 0.03481176
   →             lispy-100000        5 0.39263855
   →            lispy-1000000        5 3.54200853
--------------------------------------------------------------------------------
→ perl_golf
   →           perl_golf-1000        5 0.00100775
   →          perl_golf-10000        5 0.01173795
   →         perl_golf-100000        5 0.34136081
   →        perl_golf-1000000        5 3.51904615
================================================================================
RESULTS
================================================================================
GROUP               | CASE                | N_TIMES | TOTAL TIME  | N/SEC
--------------------------------------------------------------------------------
simple              | simple-1000         | 5       | 0.00054079  | 9245.77
simple              | simple-10000        | 5       | 0.00561517  | 890.44
simple              | simple-100000       | 5       | 0.05979806  | 83.61
simple              | simple-1000000      | 5       | 0.63093591  | 7.92
--------------------------------------------------------------------------------
lispy               | lispy-1000          | 5       | 0.01849611  | 270.33
lispy               | lispy-10000         | 5       | 0.03481176  | 143.63
lispy               | lispy-100000        | 5       | 0.39263855  | 12.73
lispy               | lispy-1000000       | 5       | 3.54200853  | 1.41
--------------------------------------------------------------------------------
perl_golf           | perl_golf-1000      | 5       | 0.00100775  | 4961.54
perl_golf           | perl_golf-10000     | 5       | 0.01173795  | 425.97
perl_golf           | perl_golf-100000    | 5       | 0.34136081  | 14.65
perl_golf           | perl_golf-1000000   | 5       | 3.51904615  | 1.42
--------------------------------------------------------------------------------

C

Rozwiązanie analogiczne w C. Niespecjalnie jest co omawiać, zwykła pętla, w środku arytmetyka.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>


/* Overflows. */

int main(int argc, char** argv)
{
    unsigned long max = (argc > 1 ? strtoul(argv[1], 0, 10) :  100);

    printf("Range: 1 - %ld\n", max);

    unsigned long long sum = 0;
    unsigned long long sum_of_squares = 0;

    unsigned long i;
    for(i = 1; i <= max; i++) {
        sum += i;
        sum_of_squares += i * i;
    }

    // The problem seems to be worded the other way around.
    unsigned long long result = (sum * sum) - sum_of_squares;

    printf("Sum: %lld, sum squared: %lld\n", sum, (sum * sum));
    printf("Sum of squares: %lld\nDifference: %lld\n",
           sum_of_squares, result);

    return 0;
}

Uruchamiamy:

100:

$ time ./prog.bin
Range: 1 - 100
Sum: 5050, sum squared: 25502500
Sum of squares: 338350
Difference: 25164150

real    0m0.001s
user    0m0.001s
sys 0m0.000s

100000:

$ time ./prog.bin 100000
Range: 1 - 100000
Sum: 5000050000, sum squared: 6553755928790448384
Sum of squares: 333338333350000
Difference: 6553422590457098384

real    0m0.001s
user    0m0.000s
sys 0m0.001s

9999999:

$ time ./prog.bin 9999999
Range: 1 - 9999999
Sum: 49999995000000, sum squared: 8404984032111005696
Sum of squares: 1291890006563070912
Difference: 7113094025547934784

real    0m0.009s
user    0m0.009s
sys 0m0.000s

Przy wyższej wartości wejściowej wszystko nam się niestety przekręci.