Page 1 of 2 12 LastLast
Results 1 to 30 of 42

Thread: If a computer could calculate the square root of a number of billions of digits...

  1. #1
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts

    ----------------------------------------------

    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:32.

  2. #2
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    I think the fastest methods for calculating square roots are O(n log n) in the number of digits using Newton's method and FFT multiplication.

    But that has nothing to do with data compression. For an introduction you might enjoy http://mattmahoney.net/dc/dce.html

  3. #3
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:32.

  4. #4
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    I assume you know how to do arithmetic on arrays of digits. Also, seriously, you should do some reading about the basics of data compression before spouting nonsense.

  5. #5
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:32.

  6. #6
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:33.

  7. #7
    Member
    Join Date
    Nov 2011
    Location
    France
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I'm sure that thanks to matt and all other great inventors, we have more elaborate compression system than aliens, if they would exist.

  8. #8
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    In fact, Matt IS an alien. He just ran a million miles.
    Last edited by Piotr Tarsa; 7th April 2012 at 13:06.

  9. #9
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    437
    Thanks
    1
    Thanked 96 Times in 57 Posts
    Quote Originally Posted by Menno de Ruiter View Post
    I believe aliens on other planets some few million years more advanced, are really laughing a lot about lzh huffman and other stone age 'inventions' of us monkeys

    but nonetheless, it's a start !!
    Not really. The point is, there are already pretty hard results on how well you can entropy code a source - for simple sources at least, and one can theoretically check how far existing entropy coders are from the absolute maximum, and arithmetic coding comes very close (real length is in the limit of infinite sources at most one bit off from the optimum, or the # of bits per symbol <= 1/n + entropy rate).

    The "gold" does not lie in the entropy coding procedure, but in the proper modeling of the source...

    As far as the square root goes: Newton's method is not exactly a good one for this simple procedure. There is an algorithm for the square root that works pretty much like the classical "egyptian" division algorithm just by shifts and adds, so it is blazingly fast. Unfortunately, if you look at the performance as a function of digits, I believe it is only O(n^2) (one shift = n operations, and it takes n/2 shifts in total plus n/2 adds). Nevertheless, it is more or less the standard procedure for binary square roots which converges linearly.

  10. #10
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:33.

  11. #11
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------------
    Last edited by Menno de Ruiter; 13th October 2012 at 16:25.

  12. #12
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    You are welcome to post your data compression programs here to prove your theories.

  13. #13
    Member RichSelian's Avatar
    Join Date
    Aug 2011
    Location
    Shenzhen, China
    Posts
    156
    Thanks
    18
    Thanked 50 Times in 26 Posts
    I've seen lots of men who want to do compression with DATA=A2+B, are you the next one?

  14. #14
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:33.

  15. #15
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------------
    Last edited by Menno de Ruiter; 13th October 2012 at 16:26.

  16. #16
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:33.

  17. #17
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------------
    Last edited by Menno de Ruiter; 13th October 2012 at 16:26.

  18. #18
    Member
    Join Date
    Sep 2010
    Location
    Australia
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    There are plenty of forums that deal with theoretical mathematics, this forum is aimed at the more practical. If you search through the forums here you will find that it comes up from time to time, but you never see a product based it. taking any random number and finding a smaller equation to represent it might sound appealing but it might just be a dead end

  19. #19
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:33.

  20. #20
    Member
    Join Date
    Sep 2010
    Location
    Australia
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Also i might add one can tend to forget to sleep when spiraling down this rabbit hole! i know from personal experience. If magic is possible then make it, dont waste your time trying to convince others of what you think SHOULD be true

  21. #21
    Member
    Join Date
    Sep 2010
    Location
    Australia
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    The universe is a reality, mathematics is a symbol at best to describe reality, but like all symbols it is inherently limited

  22. #22
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:33.

  23. #23
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:34.

  24. #24
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:34.

  25. #25
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Programming computers is a lot easier than quantum-something. I suggest to learn some programming language.

    Talks about context-mixing are already hard engough to grasp so that few individuals on this forum takes part in them, so it's no wonder that no one talks with you about quantum-something.

    But there are many people on this forum wanting to test the efficiency of provided binaries. So if you post something working (ie efficient and fully reversible), there surely will be a lot more noise.

  26. #26
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:34.

  27. #27
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:34.

  28. #28
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------------

  29. #29
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:34.

  30. #30
    Member Menno de Ruiter's Avatar
    Join Date
    Mar 2012
    Location
    ----------------------------------------------
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ----------------------------------------------
    Last edited by Menno de Ruiter; 7th October 2013 at 14:34.

Page 1 of 2 12 LastLast

Similar Threads

  1. Euler's Number Triangle and Random Data
    By BetaTester in forum Data Compression
    Replies: 55
    Last Post: 19th February 2013, 05:02
  2. Announcing 5 trillion digits of Pi!
    By Sanmayce in forum The Off-Topic Lounge
    Replies: 0
    Last Post: 16th October 2010, 18:25
  3. rnd - simple pseudo random number generator
    By encode in forum Forum Archive
    Replies: 21
    Last Post: 14th January 2008, 03:41

Posting Permissions

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