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.