5 ms·
Could this trick be used to improve compression? Since palindromes contain repeated digits by definition, perhaps they are more compressible than the original n
by markstos 8y ago
Could this trick be used to improve compression? Since palindromes contain repeated digits by definition, perhaps they are more compressible than the original number? Of course, you'd have three numbers to compress instead of one...
- totalZero 8y agoonly if the two decomposed numbers together take up the same space or less as the original number. no idea in what cases that happens.
- exikyut 8y agoPalindrome detection in general is a rather interesting consideration to keep in mind...
- yorwba 8y agoPalindromes can be compressed 50% by using their symmetry. Representing a number as 3 palindromes would "compress" a number to 1.5 times the original size in the worst case. Obviously not an improvement. If the number itself happens to be a palindrome, you can get down to 50%, but that's completely unrelated to this trick. In general, it's impossible for a compression algorithm to losslessly compress all numbers to a shorter representation, it can only make some numbers shorter and others longer. (Pigeonhole principle: there are not enough short codes, so if you assign a shorter code to all numbers, some will get the same code, making the compression not lossless.) Practical uses of compression are all about reducing the average length given a nonuniform probability distribution, so a palindrome-based compression scheme would only be useful if you could expect most numbers you're dealing with to be palindromes.