算法，数字fractionning [英] algorithm, number fractionning

问题描述

我哈瓦大约算法一般性的问题（主要涉及数学）：

I hava a general question about algorithm (mainly involving maths):

让我们假设有一个数字（可能非常大），我们希望减少到前pression涉及到基本的算术运算，这将是做的最好的，更有效的方法是什么？

Let's suppose we have a number (probably very big) that we would like to reduce to an expression involving basic arithmetic operations, what would be the best and more effective way to do it ?

让我们看一个例子：

假设我们要分数数131：

Suppose we want to fraction the number 131 :

一步一步，我会得到更多的东西或多或少这样

step by step i would obtain something more or less like this

131 =（2 * 65）+ 1

131 = (2 * 65) + 1

131 =（4 * 30）+（2 * 5）+1

131 = (4 * 30) + (2 * 5) + 1

131 = ...（我们可以继续下去。）

131 = ... (we could go on and on ..)

在我的情况，131是一个坏榜样，因为它是一个很小的数字，但如果我被操纵像10254541524587872157，这将是不同的。

In my case, 131 is a bad example since it is a very small number, but if i were manipulating something like 10254541524587872157 , it would be different.

我的目标是要连接codea的大数字，以更小的数字的前pression（将分别适合于为unsigned long long），由此，通过拆分前pression我可以得到最初的数了。

My goal is to encode a big number to an expression of smaller numbers (that would separately fit in an unsigned long long) from which, by resolving the expression i could obtain the initial number again.

有关的那一刻我只是想出了，我给了做为一个例子，一个非常基本的解决方案，但如果你知道一个更好的方式，或约数学或东西，可以帮助我的各种概念的一些环节，我会感谢你永远！

For the moment i just came up with a very basic solution that i gave here as an example, but if you know a better way, or some link about various notions of maths or something that could help me, i would thank you for ever !

编辑：

这将永远是一个无符号数

This will always be an unsigned number

编辑2：

我在明确需要的是有初始号更轻量级重新presentation。 如果最初的数字是16ko，我想最后的EX pression以适应（远）低于16ko

My need in definitive is to have a more lightweight representation of the initial number. If the initial number is 16ko, i would like the final expression to fit in (far) less than 16ko

谢谢， jav974

Thanks, jav974

推荐答案

你要的是不可能的事情。你问一个无损的COM pression 算法的二进制内容，并更重要的是，制约算法到一个特定的类，它的定义不可能产生较小的再presentation。

What you want is impossible. You are asking for a Lossless Compression algorithm on binary content, and what's more, restricting the algorithms to a specific class which by definition cannot possibly produce a smaller representation.

让D（x）为x中位数。它不应该是很难看到下面的两个真理适用于所有的非负整数A和B：

Let D(x) be the number of digits in x. It should not be hard to see that the following two truths hold for all non-negative integers A and B:

D(A+B) <  D(A) + D(B) + 1  ("Digits in (A+B) < Characters in 'A+B'")
D(A*B) <= D(A) + D(B)      ("Digits in (A*B) < Characters in 'A*B'")

这样，你给任何数量的X任何COM pression，保证如果你允许使用的指数运营商至少需要尽可能多的字符的数字X的，^，这改变：显然，9 ^ 9重presents一批具有远远超过3个字符。

Thus, any "compression" of any number X you give is guaranteed to require at least as many characters as that of the number X. If you permit the use of the exponent operator, ^, this changes: Clearly, 9^9 represents a number with far more than 3 characters.

但事实仍然是，无损COM pression吸。对于你拿出任何的算法，至少有一半的所有可能的输入会比原来的，COM pressed 不低于1个字符短。 16K-1不是一个整体，让超过16K更好。

But the fact remains that lossless compression sucks. For any algorithm you come up with, at least half of all possible inputs will be no less than 1 character shorter than the original, compressed. 16k-1 isn't a whole let better than 16k.

要具备良好的COM pression算法，你需要知道的东西对你的数据：是否重复？是否遵循某种模式？某些数字比其他人更常见？有了这样的信息，你可能能够拿出的东西，对你所关心的输入效果很好，和吮吸那些你不 - 这是很现代的文本，图像，视频，音频融为一体pression算法工作。他们把这些数据的predictable性能优势。

To have a good compression algorithm, you need to know stuff about your data: Is it repeating? Does it follow some sort of pattern? Are certain digits more common than others? With information like this, you might be able to come up with something that works well on the inputs you care about, and sucks on the ones you don't - this is how modern text, image, video, and audio compression algorithms work. They take advantage of these predictable properties of the data.

这篇关于算法，数字fractionning的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！