2
$\begingroup$

I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading.

I'm writing a bunch of integers to disk. Lot's of them.

Starting with the integer 2, I add it to another integer, write the result to disk, and start the process again using the result as the seed.

This pattern is helping me generate data I need for other research, but I need to apply this pattern until I've reached integers with a length of 10,000 digits or more.

So, here is my simple question: given a set of data of a known data type, how do I calculate the storage space required to store that set?

At the moment, I'm doing this incredibly simple task in Python, recording longs to disk as binary in a single file. But, on my very small machine, I was only able to store the integers my process produced with values between 0 and 42 billion.

Short of my goal of recording a data set with values between 0 and 1e10000.

Given that I have no exposure to formulas for calculating hardware requirements for storing data like this, I have no idea if I'm using the most efficient language and data type for storing as many integers as possible in as little space as possible.

$\endgroup$
  • $\begingroup$ You could generate the numbers and keep a tally of how much space would be required to store them, without actually storing them. $\endgroup$ – Dave Clarke Oct 12 '12 at 7:27
  • $\begingroup$ You will need to pick a representation for arbitrary-size integers. Can you pick your own? If you can it may be possible to optimize it for their distribution (density as a function of value). You don't want to use a fixed-length representation. $\endgroup$ – reinierpost Oct 12 '12 at 9:44
  • 2
    $\begingroup$ If you use Java there is a quick way to store arbitrary precision (arbitrary long) integers efficiently: use BigInteger type and its toByteArray() method to convert them in a byte array having the required length (and easily store them on a file). In order to store a 10000 digits integer you need only 4K (4153 bytes). So in a 1GB of disk space you can store ~240000 10000 digits integers. $\endgroup$ – Vor Oct 12 '12 at 12:07
  • $\begingroup$ Is your process generating $2,4,6,8,10,\ldots,10^{10000}$, or is it generating $2,4,8,16,\ldots$? In the first case, you won't be able to store everything, since there are $10^{10000}$ number in total, each requiring at least one bit. In the second case, the amount of storage required is roughly double the amount required to store the last one. If the last one is $N$, you need about $\log N/\log 256$ bytes to represent it. $\endgroup$ – Yuval Filmus Oct 12 '12 at 18:23
  • 1
    $\begingroup$ @lmizuhashi This is basic arithmetic, and doesn't have anything to do with hardware requirements. $\endgroup$ – Yuval Filmus Oct 13 '12 at 14:28
2
$\begingroup$

There are two ways to interpret your dataset generating process. The first produces all even numbers between $2$ and your bound: $2$, $4$, $6$, $8$, …; the second produces all powers of $2$ between $2$ and your bound: $2$, $4$, $8$, $16$, … An integer $N$ requires roughly $\log_{256} N$ bytes to store. Therefore, if your bound is $N$, the first interpretation will take about $$ \sum_{k=1}^{N/2} \log_{256} (2k) \approx \int_1^{N/2} \log_{256} (2x) \, dx \approx (N/2) \log_{256} N \text{ bytes}. $$ The second interpretation, assuming $N=2^m$, will take about $$ \sum_{k=1}^m \log_{256} 2^k = \sum_{k=1}^m (k/8) \approx m^2/16 = 4(\log_{256} N)^2 \text{ bytes}. $$

$\endgroup$
  • $\begingroup$ If that were the case, it would be simpler to store the series as a function. $\endgroup$ – Raphael Oct 15 '12 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.