0
$\begingroup$

I have a simple script to calculate gaps in a sequence of digits of the square root of 2 (or any other multi-precision constant). As input, I generated files with the bigfloat module in Python:

from bigfloat import sqrt, precision

MAX_PRECISION_BITS: int = 1 << 30
CONSTANT = 2

precision_bits: int = 8
while precision_bits < MAX_PRECISION_BITS:
    with open(f"input/square_root_of_{CONSTANT}_with_{precision_bits}_bits.txt", 'w') as fd:
        fd.write(str(sqrt(CONSTANT, precision(precision_bits))))
        fd.flush()
    precision_bits *= 2

Although I can run the script any time, I decided to compress the input files, and I was surprised that a 646.5 MB got compressed to 632 KB, ie less than 1 MB! This value was obtained with the standard Zip method that is available in Mac OS X. I performed a diff command in the original and expanded file to check for possible differences and none was found.

I understand that every decimal digit takes about 3.32 bits, and the square root of 2 is conjectured to be normal, so I was expecting a compression to 40% or so.

How is this compression attained?

$\endgroup$
2
  • $\begingroup$ A compressor will also look at repeated sequences. That is another major part in how they get good compression $\endgroup$ – ratchet freak Jun 24 '20 at 15:01
  • 1
    $\begingroup$ As Jakube commented below, sqrt(2) is irrational so you shouldn't expect any repeating pattern. But in fact, the input files, as he discovered, represented rational numbers as they finished with a long tail of zeros. And of course, that compresses very well. $\endgroup$ – Javier Ruiz Jun 24 '20 at 16:20
3
$\begingroup$

Clearly that's a way too good compression rate. $\sqrt{2}$ is not a rational number, so the decimal expansion will not start repeating. So there has to be something really fishy going on.

I run your script, and looked at the resulting file.

On my machine, the file square_root_of_2_with_536870912_bits.txt contains 161.614.250 digits, and the last 161.597.755 digits are all zeros. Only the first 16.495 digits are different from zero.

So given that pretty much almost everything in the files are zeros, it's not unexpected that the compression rate is so high.


I'm not experienced with the bigfloat package, so I can't tell if the bug is in your program or in the package itself. If you can't figure the error out yourself, open an issue on their Github page.

Btw, from those 16.495 digits, only about 5.000 of those are correct.

$\endgroup$
5
  • $\begingroup$ Thanks Jakube! You are absolutely right. I think the bigfloat package has a hard limit, a bug, or the mpfr package in my Mac is damaged. I have to test it in a Linux machine. I rewrote the script using the decimal module from the standard Python library, and so far is producing real digits. Not sure about the correctness though. This should teach me to inspect the files with an hex editor before reaching to conclusions. $\endgroup$ – Javier Ruiz Jun 24 '20 at 16:17
  • $\begingroup$ I have run the code on Linux. So it's definitely not only happening on MacOS. $\endgroup$ – Jakube Jun 24 '20 at 16:19
  • $\begingroup$ "√2 is not a rational number, so there shouldn't be any recurring pattern in the digit expansion." That doesn't follow. It is unknown if the square root of 2 is a normal number. $\endgroup$ – Pseudonym Jun 25 '20 at 0:24
  • $\begingroup$ @JavierRuiz I was actually interested in the bug, and reported it myself: issue link This is actually a design flaw of the library. At the moment if you want to compute so many digits, you also need to adjust emin to a smaller number. $\endgroup$ – Jakube Jun 25 '20 at 10:54
  • $\begingroup$ @Jakube Thanks for reporting the issue! It's a pity because bigfloat is a wrapper to GNU mpfr that as far as I know does not have any limitation regarding precision. The decimal module seems to work well, although I don't know how good in terms of speed in relation to mpfr. $\endgroup$ – Javier Ruiz Jun 29 '20 at 15:36
1
$\begingroup$

At the risk of stating the obvious, it depends on your compression method. 600MB of digits of the square root of 2 can be compressed to the code that you have written in this very question, which is smaller than 1KB.

$\endgroup$
0
$\begingroup$

Pertaining to your specific question and as stated by Jakube, √2 is an irrational number, in which case there are no specific patterns that should exist in the fractional digits to the right of the decimal point. I understand that bigfloat is an arbitrary precision arithmetic package; however, it appears to be somewhat limited if the decimal precision is approximately 16,500 digits after the decimal point (with the remaining digits being zero).

As I am sure you're aware, the whole point of lossless text compression is to reduce symbol redundancy. At present, there is no way that one could conceivably compress a 614400 KB (600 MB) text file of random ASCII symbols (i.e., √2 to 600 MB, which is 629,145,600 numbers in a random sequence) into a 600 KB compressed archive. In this context, 99.9% losslesss compression efficiency is not possible. It appears that you achieved an extremely high level of compression because of the limits of bigfloat. Your script generated millions of zeroes when computing √2, which constitutes a massive amount of redundancy.

$\endgroup$

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.