HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Calculating harmonic sum

Submitted by: @import:stackexchange-codereview··
0
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).

#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:

#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.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.

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

Context

StackExchange Code Review Q#85932, answer score: 3

Revisions (0)

No revisions yet.