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.

Improve this question
$\endgroup$
14
  • $\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 14:28

1 Answer 1

Reset to default
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}. $$

Improve this answer
$\endgroup$
1
  • $\begingroup$ If that were the case, it would be simpler to store the series as a function. $\endgroup$
    – Raphael ♦
    Oct 15, 2012 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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