CODEWITHSUNDEEP
c#java
Farhad-Taran
Farhad-Taran

Reputation: 6540

Logic of adding double values

I was given the following question in an interview...

Compute the following sum:
1/2 + 1/4 + 1/8 + ... + 1/1048576

I was told that this was a logic question and they weren't looking for the source code, however my answer was the following...

    private static double computeSum(){
        double x = 0.0;
        for(double i=2; i<=1048576; i*=2){
            x += (1 / i);
        }
        return x;         
    }

What is the correct logical answer to this question?

Upvotes: 1

Views: 428

Answers (4)

kasavbere
kasavbere

Reputation: 6003

This is a simple convergent geometric series 

  s=a+ar+ar^2+ar^3+... to infinity

So the sum is

s=1/(1-r) where in this case r =1/2

However, we are seeking s-a, since the given series starts at 1/2 and not at 1. hence

s-a = 1/(1-r) - a = 1/(1-1/2) -1 = 1.

Why they call it a logic problem is not clear to me, except that they may want an explanation why the given geometric series converges -- which is a simple proof: i.e. the ratio between any two consecutive terms is a constant less than 1.

Upvotes: 0

Tom Chantler
Tom Chantler

Reputation: 14951

I fi was presented with that sum I would say the answer is 1 minus the nth term, so in your case it's

1 - 1/1048576 = 1048575/1048576

I wouldn't do any maths or code or anything. I guess that's the kind of answer they were looking for.

I might show some "working" by saying 1/2 + 1/4 = 3/4 = 1 - 1/4; // Edit here

1/2 + 1/4 + 1/8 = 7/8 = 1 - 1/8

Upvotes: 11

Andreas Brinck
Andreas Brinck

Reputation: 52549

The sum:

1/2 + 1/4 + 1/8 + ... + 1/1048576

is equivalent to:

(1 + 2 + ... 2 ^ 20) / (2 ^ 20) - 1 =
(2 ^ 21 - 1) / (2 ^ 20) - 1 =
2 - 1 / (2 ^ 20) - 1 =
1 - 1 / (2 ^ 20) ~= 0.99999

The sum will tend to one if the length of the series is increased.

Upvotes: 3

Azhar Khorasany
Azhar Khorasany

Reputation: 2709

They are adding fractions together until they come up with a fraction 1/1048576 which has a very negligible value. This means that the answer to the above will be very close to 1 but not exactly one.

Upvotes: 0

Related Questions