Calculating harmonic sum

Question

The problem is that I have executed the program for the last hour and it hasn't returned a value till now for input 10²². 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).

#include <stdio.h>
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);
}

Answer 1

To illustrate my comment about accuracy, I wrote a small test program:

#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;
}

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.073s

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 long double and double, computing in double for 10^13 more iterations would given useless results.