Results 1 to 10 of 10

Thread: Mark Nelson's 1 Million Random Digit Challenge

  1. #1
    Member JamesWasil's Avatar
    Join Date
    Dec 2017
    Location
    Arizona
    Posts
    33
    Thanks
    29
    Thanked 6 Times in 6 Posts

    Mark Nelson's 1 Million Random Digit Challenge

    I didn't see any threads here or a spot for this with Encode.ru when searching, and thought I might make a spot where people can discuss or submit their entries for it.

    Mark still has an active thread going for this with his site, however he's using Disquss now for comments which doesn't let you upload or share files (or see responses) like you are able to here.

    I figured if we have a thread here for it, anyone interested can search for it with the forum and be able to see things right away and share files.

    Mark's active page for this is: https://marknelson.us/posts/2012/10/...turns-ten.html
    Last edited by JamesWasil; 16th January 2019 at 21:04. Reason: added main link

  2. #2
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    437
    Thanks
    137
    Thanked 152 Times in 100 Posts
    Was this the same book of random digits where Matt Mahoney observed the total sum of digits on each page is always even (or some similar bizarreness), leading to 1 bit saved per page?

    I forget the link.

  3. #3
    Member JamesWasil's Avatar
    Join Date
    Dec 2017
    Location
    Arizona
    Posts
    33
    Thanks
    29
    Thanked 6 Times in 6 Posts
    Quote Originally Posted by JamesB View Post
    Was this the same book of random digits where Matt Mahoney observed the total sum of digits on each page is always even (or some similar bizarreness), leading to 1 bit saved per page?

    I forget the link.
    No, this was a series of random digits made by the RAND corporation scientists after WWII. There hasn't been any known pattern to the numerical sequences. They were generated from physical anomalies to ensure randomness, like radioactive decay.

    To this day, no one has been able to compress it to where the total sum of bytes with the decompressor is smaller by 1. There was no book of numbers as far as i'm aware, it was always a file of random digits converted to base 2 and named amillionrandomdigits.bin (if i find the file or the link to it, i'll share it if anyone wants to have a look or try to compress it)

    There's been several attempts over the past 10 years, but most of them have been data hiding or other obscurities which didn't actually compress the data. On his page, he explains it a lot better and the details for the challenge. There's actually 2 challenges, 1 which may be possible, the other which is supposed to be impossible to complete.

  4. #4
    Member
    Join Date
    Jun 2018
    Location
    Slovakia
    Posts
    80
    Thanks
    22
    Thanked 3 Times in 3 Posts
    I am interested in this challenge, but I need the text file with digits, not binary form.

  5. #5
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Here's a Java program that converts the data from compact binary representation to ASCII digits (requires Java 8 ):
    Code:
    import java.math.BigInteger;
    import java.nio.file.Files;
    import java.nio.file.Path;
    import java.nio.file.Paths;
    
    public class AMillionRandomDigits {
        public static void main(String[] args) throws Exception {
            Path inputPath = Paths.get("/tmp/AMillionRandomDigits.bin");
            Path outputPath = Paths.get("/tmp/AMillionRandomDigits.txt");
            byte[] inputInBinary = Files.readAllBytes(inputPath);
            BigInteger inputAsNumber = new BigInteger(inputInBinary);
            String inputInBase10 = inputAsNumber.toString();
            Files.write(outputPath, inputInBase10.getBytes());
        }
    }
    Output size is exactly 1e6 bytes.
    Code:
    $ sha1sum AMillionRandomDigits*
    376f1d865ad3a1f92bd07033af200addfbacc436  AMillionRandomDigits.bin
    e111bf84f27e46c260ef2713fc06070a8d2cfc36  AMillionRandomDigits.txt
    Update:
    Actually, you don't even need to run this code.

    http://www.rand.org/publications/classics/randomdigits/ (which currently redirects to https://www.rand.org/pubs/monograph_reports/MR1418.html ) allows to directly download the digits as a formatted text file (current direct link is https://www.rand.org/content/dam/ran...digits.txt.zip ). You only need to strip formatting (spaces, new lines and first column with line numbers) and you're left with raw digits.
    Last edited by Piotr Tarsa; 19th January 2019 at 22:56.

  6. The Following User Says Thank You to Piotr Tarsa For This Useful Post:

    JamesWasil (25th January 2019)

  7. #6
    Member
    Join Date
    Oct 2009
    Location
    usa
    Posts
    56
    Thanks
    1
    Thanked 9 Times in 6 Posts
    Instead of all of this tedious explanation, why not just post a .zip file with the raw digits? It would make things so much easier.

  8. #7
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Here you are. Challenge is to compress either AMillionRandomDigits.bin or AMillionRandomDigits.txt to a file smaller than AMillionRandomDigits.bin (including compressor size).
    Attached Files Attached Files

  9. The Following 2 Users Say Thank You to Piotr Tarsa For This Useful Post:

    CompressMaster (20th January 2019),JamesWasil (25th January 2019)

  10. #8
    Member
    Join Date
    Apr 2012
    Location
    London
    Posts
    239
    Thanks
    12
    Thanked 0 Times in 0 Posts
    Encode.ru community should get Yuri Miller / Zuckerberg the likes to put up $25m prize, to incentivise serious attempts

    Only then will certainly be more inclined

  11. #9
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    I think if you were able to compress any data strongly and quickly you would be rich anyway. You could set up a storage cloud company that have much lower storage prices than competition due to your miraculous compression technique.

    Compressing any random-like file doesn't prove anything in general, because we don't know how to determine if a file is truly random in the first place. Actually, if you were generating random files (of fixed length) long enough you would end up generating a file that is all zeros, so you could trivially compress that particular file. But what about all other files?
    Last edited by Piotr Tarsa; 21st January 2019 at 01:06.

  12. #10
    Member
    Join Date
    Apr 2012
    Location
    London
    Posts
    239
    Thanks
    12
    Thanked 0 Times in 0 Posts
    Once this forthcoming somebody could then show true random files ( random.org) consistent compressed smaller reconstructs exact same

    I am however very sure of this

Similar Threads

  1. Random numbers
    By nburns in forum The Off-Topic Lounge
    Replies: 9
    Last Post: 9th September 2013, 05:53
  2. US$3 Million Data compression Prize
    By LawCounsels in forum The Off-Topic Lounge
    Replies: 30
    Last Post: 2nd May 2012, 18:26
  3. Random reads vs random writes
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 22
    Last Post: 16th May 2011, 09:58
  4. Mark Forums Read
    By Surfer in forum The Off-Topic Lounge
    Replies: 6
    Last Post: 12th May 2010, 18:07
  5. Ocarina Compression Challange (Total Prize: $1 Million)
    By osmanturan in forum Data Compression
    Replies: 8
    Last Post: 2nd October 2008, 09:19

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •