CODEWITHSUNDEEP
architecture
Richard
Richard

Reputation: 6354

How much storage for summation of 1 to 4 billion

Inspired by this question (Find an integer not among four billion given ones).

How much storage space would it require to store an integer that was the summation of the numbers 1 to 4 billion?

For example, 1+2+3+4+5 = 15. Summation of 1 to 1 million = 500,000,500,000.

Here is an algorithm that may help

Upvotes: 1

Views: 637

Answers (3)

RoundTower
RoundTower

Reputation: 909

One bit is plenty, if you choose an appropriate encoding for integers.

You only need more than n bits if there are more than 2^n possible values you could potentially need to store. Here there is only one value that you require to be able to store.

Upvotes: 5

Jürgen Strobel
Jürgen Strobel

Reputation: 2248

In [12]: import math

In [13]: n=4000000000

In [15]: sumn = n*(n+1)/2

In [16]: sumn
Out[16]: 8000000002000000000L

In [24]: math.log(sumn)/math.log(2)
Out[24]: 62.794705708333197

Answer: 63 bits.

Upvotes: 9

matja
matja

Reputation: 4179

The function you link to describe how to find the n'th Triangular Number, which is defined as the sum of the n natural numbers from 1 to n.

Substituting 4 billion as n into the function gives 8000000002000000000.

Expressing that as a number of bits can be worked out by taking the base-2 logarithm of the value and rounding up -

ceil(log(8000000002000000000)/log(2)) = 63

So, 63 bits of storage are required.

Upvotes: 9

Related Questions