Re: What´s the algorithm that compresses a 20 digit big int, into 8 bytes ?

On Apr 9, 12:57 pm, Rafael Anschau <rafael.ansc..._at_gmail.com> wrote:
> On Apr 9, 12:44 pm, paul c <toledobythe..._at_oohay.ac> wrote:
>
> > Open up your calculator and look at the result of 2 to the power of 63.
> >   I get 9,223,372,036,854,775,808.  Only nineteen digits.
>
> Yes, it proves pure binary conversion won´t do
> it(2^64=18446744073709551616)
> the 18% Sampo talked about.
>
> But it doesn´t prove(demonstrates truth from a fixed set of given
> axioms)
> that no other algorithms will ever do it(although it serves as strong
> evidence for that).
>
> But that´s the mathematician in me going off topic, I might debate
> that
> on alt.math or else.
>
> Thanks anyway,

Let D = the set of 20-digit decimal numbers
Let B = the set of 64-digit binary numbers
Let F = be an encoding function from D to B

By definition for F to be an encoding it must be the case that

  ForAll {x, y} . [x .E. D and y .E. D]
  F(x) = F(y) implies x = y

therefore F is injective.

from the definition of cardinality :

   |Y| >= |X| ie the cardinality of Y is greater than or equal    to the cardinality of X if-and-only-if there exists an    injective function (G : X -> Y) mapping X onto Y.

(1) Since F is an injective function D -> B then |B| >= |D|.

However, by counting permutations we have that

   |D| = 10^20
   |B| = 2^64

and 10^20 > 2^64 therefore |D| > |B| which contradicts (1) above therefore there cannot exist an injective function so F cannot be injective. Therefore no encoding F from D to B exists.

You might also want to google the "pigeon hole principle" for some interesting related discussions.

KHD Received on Fri Apr 09 2010 - 22:21:53 CEST