views:

101

answers:

1

Possible Duplicate:
Programming Logic: Finding the smallest equation to a large number.

I'm looking for an algorithm that will take an arbitrary number from the Aleph-Null set (all positive integers)(likely to be absolutely enormous) and attempt to simplify it into a computable number (if the computable number takes up less space than the integer value it is trying to represent)(specifically not floating point). Involving tetration/hyperoperators would be optimal.

Does anyone know if anything like this exists? I've looked around quite a bit this morning, but have been unable to find anything. C# code would be optimal, but really, it could be in any language

Edit: http://stackoverflow.com/questions/3409363 : http://mrob.com/pub/ries/index.html looks promising, but I wonder how well it will deal with large numbers, and if it's capable of implementing hyperoperators. I'll try it out.

+1  A: 

(all positive integers) and attempt to simplify it into a computable number (if the computable number takes up less space than the integer value it is trying to represent)(specifically not floating point). Involving tetration/hyperoperators would be optimal.

Yes, and then again, no.

First, you can't actually take inputs from "all positive integers" in a physical computer. At best, you can have an integer whose representational length is the size of your hard drive.

So your input is now physically constrained to the set I = [0, MAX], where MAX is a physical constant. Congratulations, that makes this problem solvable.

You can consider this from an information-theoretic point of view- each member of I is possible and representable. The compressability comes in when you consider representations. If each representation is unique, your goal is to reduce each i in I to the representation that is nearest the entropy of the number of i itself.

Or, restated, compression comes in by removing redundancy. If your representation has redundancy, it can be compressed.

Possibly - this would be domain knowledge - you can write the formula for generating the number in a fashion that is highly compressed. But that relies on a certain regularity in how you get the number, it becomes no longer arbitrary.

Paul Nathan
well, this is as much a theoretical investigation of mine, as it is an applied one. I would like to find an algorithm that could theoretically produce an equation for any number; but true, it is limited by the hardware.I'm not looking for compression algorithms that relies on regularity for compression, I'm looking for an algorithm that will produce an equation that can then be interpreted to reproduce the number. The assumption is that the number does not have any regularity.
Nicholas Baldwin
@Nich: No regularity -> no compression (on average).
Steven Sudit
@Nich: Information theory *applies* to compression, but is broader. You are definitely asking for something which lies in the region of computing Kolmogorov Complexity for arbitrary strings, which is not computable for the general case. You should spend some time investigating the entropy of arbitrary integers in different representations, which will give you some reasonable notions of minimal representability for your numbers.
Paul Nathan