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

1. ## ----------------------------------------------

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

2. 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. ----------------------------------------------

4. 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. ----------------------------------------------

6. ----------------------------------------------

7. 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. In fact, Matt IS an alien. He just ran a million miles.

9. Originally Posted by Menno de Ruiter
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. ----------------------------------------------

11. ----------------------------------------------------

12. You are welcome to post your data compression programs here to prove your theories.

13. I've seen lots of men who want to do compression with DATA=A2+B, are you the next one?

14. ----------------------------------------------

15. ----------------------------------------------------

16. ----------------------------------------------

17. ----------------------------------------------------

18. 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. ----------------------------------------------

20. 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. The universe is a reality, mathematics is a symbol at best to describe reality, but like all symbols it is inherently limited

22. ----------------------------------------------

23. ----------------------------------------------

24. ----------------------------------------------

25. 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. ----------------------------------------------

27. ----------------------------------------------

28. ----------------------------------------------------

29. ----------------------------------------------

30. ----------------------------------------------

Page 1 of 2 12 Last

#### Posting Permissions

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