To reperent a number into minimum number of digits

[Man4ish]

Hi,
How a number can be represented into minimum number of digits?
5678432145151257 should be represented into 2 digit number. Like
LOC890808 should also be represented into 2 digit number. Is there any algorithm exist like that ......


Thanks in advace.

[donbock]

I'm sorry, I don't understand your question.

What do the letters "LOC" at the start of your second example mean?

In the first example (5678432145151257), it seems self-evident that 16 decimal digits are needed to represent this number -- but you suggest it can be accomplished in two digits. We must have different definitions in mind for the word digit.

[Man4ish]

I am planning to compress the number of digits/char. so if it is 16 digit number, it should be represented by 2 or 3 numbers only. is it possible?

@donbock

[sridhard2406]

Hi ,
Please explain with real time Example

[Man4ish]

I am planning to compress the data so in my mind technique is like kepping the digits
2345665 into digit number say 26 (which has come after some manipulation, addition subtraction etc). Is there any algo for that?
@sridhard2406

[JosAH]

Every integral number X can be represented with one digit in radix X+1: it'll be the last digit in that radix representation; the problem is then that you have to store that radix X+1 somewhere.

kind regards,

Jos

[Man4ish]

Please explain with example.

@JosAH

[Banfa]

Jos is talking about changing bases however it is not a solution to your problem because as Jos points out even if you change the base to conver the number ro a 1 digit number then you still have to store the base that you converted it the number to otherwise the data is meaningless.

As an example suppose the X = 15 in Jos example, I can convert to base 15+1 = 16 (hexadecimal). I can now store the number in 1 digit as F but for F to be meaningful I have to remember that the base is 16 so I need to store F and 16 which is more data.

The basic answer to your question is that it is not possible consider any decimal number with it's binary representation, for example

1234 10011010010

To remove even a single binary digit you would need to find one that has no meaning, however every single bit has a meaning in this number.

Instead then let us consider hexadecimal and find an algorithm that will compress any 4 digit hexadecimal number and lets not be ambitious lets find an algorithm that compress every number by 1 bit.

So we are going to compress every hexadecimal number

HHHH in binary BBBB BBBB BBBB BBBB

to a binary number with one less digit

CCC CCCC CCCC CCCC

Or that is we will compress any 16 digit binary number to a 15 digit binary number. And this is the crux of the problem because a 16 digit binary number has 65536 possible values but a 15 digit binary number has only 32768 possible values so regardless of the algorithm used if it existed then some of the input values would compress to the same output values and you would not be able to decompress them without additional information.

It is not possible to find an algorithm that provide lossless compression of any digit sequence by any amount let alone to specifically 2 digits.

All lossless compression algorithms rely on identifying and removing redundant data in one manner or another. If you can not identify any redundant data in the data you wish to compress then it is not compress-able.

A number sequence from 0 - N where every value has meaning by definition has no redundant values.

[donbock]

A lookup table can be used to compress a sparse distribution of large numbers. For example, if you only have to deal with 256 different 16-digit numbers then you write those values into a table and represent the values with the 1-byte index into the table. For a small sequence of large numbers the overhead of the table swamps the benefits of the compression. You can readily compute how many large numbers need to be compressed before you start to see benefits.

The lookup table approach can still be used even when there are more large numbers than slots in the table (see Hash function).

Other compression techniques share that limitation: there are conditions where the compression technique actually increases the size of the message. Google is your friend: Data compression.

@Banfa
For example, you may have heard that it is customary to add a CRC value to a data message to insure its integrity. The CRC value is much shorter than the message ... is this an example of the compression you seek? Consider a 1 KB message. That's 1024 8-bit bytes, or 8192 bits; therefore there are 2^8192 different messages that could be sent. A 16-bit CRC has 2^16 different values. This means that on average there are 2^8176 different messages that all share the same CRC value.