patterncMinor
Calculating harmonic sum
Viewed 0 times
calculatingharmonicsum
Problem
The problem is that I have executed the program for the last hour and it hasn't returned a value till now for input 1022. How can I make the program a bit faster? How can I increase the efficiency of program? Is there a faster algorithm?
I have Intel Core2 Duo (2.93GHz).
I have Intel Core2 Duo (2.93GHz).
#include
int main() {
unsigned long long n;
double m;
double sum=0;
scanf("%llu", &n);
while (n>0) {
m=1.0/n;
sum+=m;
n--;
}
printf("%lf",sum);
return(0);
}Solution
To illustrate my comment about accuracy, I wrote a small test program:
The following tests give this output:
My machine is not very fast, but it would take 10^13 seconds to complete the
calculation for 10^22 using your code. Given the estimated age of the universe,
5.10^17 seconds, you should kill the process and think about a better algorithm.
Looking at the accumulated error for just 10^9 iterations between
computing in
#include
#include
int main(int argc, char **argv) {
unsigned long long n;
double sum = 0;
float fsum = 0;
long double lsum = 0;
if (argc > 1)
n = strtoull(argv[1], NULL, 0);
else
scanf("%llu", &n);
while (n > 0) {
/* computing using double arithmetic */
double m = 1.0 / n;
sum += m;
/* computing using float arithmetic */
float fm = (float)1 / n;
fsum += fm;
/* computing using long double arithmetic */
long double lm = (long double)1 / n;
lsum += lm;
n--;
}
printf("long double: %Lf\n", lsum);
printf("double: %f, delta=%Lg\n", sum, lsum - sum);
printf("float: %f, delta=%f\n", fsum, sum - fsum);
return 0;
}The following tests give this output:
~/dev/stackoverflow > time ./t41 10000000
long double: 16.695311
double: 16.695311, delta=-1.12868e-13
float: 16.686031, delta=0.009280
real 0m0.257s
user 0m0.244s
sys 0m0.004s
~/dev/stackoverflow > time ./t41 100000000
long double: 18.997896
double: 18.997896, delta=4.51783e-13
float: 18.807919, delta=0.189978
real 0m2.585s
user 0m2.558s
sys 0m0.010s
~/dev/stackoverflow > time ./t41 1000000000
make: `t41' is up to date.
long double: 21.300482
double: 21.300482, delta=1.79655e-12
float: 18.807919, delta=2.492563
real 0m25.287s
user 0m25.116s
sys 0m0.073sMy machine is not very fast, but it would take 10^13 seconds to complete the
calculation for 10^22 using your code. Given the estimated age of the universe,
5.10^17 seconds, you should kill the process and think about a better algorithm.
Looking at the accumulated error for just 10^9 iterations between
long double and double,computing in
double for 10^13 more iterations would given useless results.Code Snippets
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
unsigned long long n;
double sum = 0;
float fsum = 0;
long double lsum = 0;
if (argc > 1)
n = strtoull(argv[1], NULL, 0);
else
scanf("%llu", &n);
while (n > 0) {
/* computing using double arithmetic */
double m = 1.0 / n;
sum += m;
/* computing using float arithmetic */
float fm = (float)1 / n;
fsum += fm;
/* computing using long double arithmetic */
long double lm = (long double)1 / n;
lsum += lm;
n--;
}
printf("long double: %Lf\n", lsum);
printf("double: %f, delta=%Lg\n", sum, lsum - sum);
printf("float: %f, delta=%f\n", fsum, sum - fsum);
return 0;
}~/dev/stackoverflow > time ./t41 10000000
long double: 16.695311
double: 16.695311, delta=-1.12868e-13
float: 16.686031, delta=0.009280
real 0m0.257s
user 0m0.244s
sys 0m0.004s
~/dev/stackoverflow > time ./t41 100000000
long double: 18.997896
double: 18.997896, delta=4.51783e-13
float: 18.807919, delta=0.189978
real 0m2.585s
user 0m2.558s
sys 0m0.010s
~/dev/stackoverflow > time ./t41 1000000000
make: `t41' is up to date.
long double: 21.300482
double: 21.300482, delta=1.79655e-12
float: 18.807919, delta=2.492563
real 0m25.287s
user 0m25.116s
sys 0m0.073sContext
StackExchange Code Review Q#85932, answer score: 3
Revisions (0)
No revisions yet.