Prev: Sometimes when you embrace the impossible you discover truth.
Next: IF P THEN N = 2N/2P-N?
From: Rafael Anschau on 9 Apr 2010 14:13
Most databases attest they can hold 20 digits bigints into 8 bytes.
How ?

Someone answered me "binary conversion" but then
2^64=18446744073709551616 covering only 18% of the total 20 digits
range.
One possible explanation is that in the rare cases where we need
values from the
rest 82% range, the databases will use 9 bytes.

Another explanation is that the resulting binary is then compressed.
Being a sequence
of 1s and 0s that could generate a fairly compressed value, but the
overhead
of the information *about* the compression could make it unpractical
for
a small value.

There´s also the conjecture(which I agree based only on intuition)
that there
are no algorithms(in this case outside the set of binary conversion
algorithms) to put the full 20 decimal digits range into 8 bytes. But
is there a proof of that ?

Thanks to anyone willing to answer,

Rafael
From: Rafael Anschau on 9 Apr 2010 16:54
On Apr 9, 3:13 pm, Rafael Anschau <rafael.ansc...(a)gmail.com> wrote:
> Most databases attest they can hold 20 digits bigints into 8 bytes.
> How ?
Update:

The truth is that only the early 18% of all 20 digits numbers fit
there, in practice. That´s possible with binary conversion only.

But the research,theoretical topic is open: "Could you possibly put
all 20 digits into 8 bytes ?"
Converting to binary and then compressing it? That wold require that
the frequency of repetitions
is high enough, and that all 20 digits numbers have enough repetitions
to justify.Since it all seems unlikely the answer so far seems to be
no.

Rafael
From: tchow on 9 Apr 2010 19:44
In article <1c1b0669-9b70-4459-b806-3573a826e601(a)o24g2000vbo.googlegroups.com>,
Rafael Anschau <rafael.anschau(a)gmail.com> wrote:
>But the research,theoretical topic is open: "Could you possibly put
>all 20 digits into 8 bytes ?"
>Converting to binary and then compressing it? That wold require that
>the frequency of repetitions
>is high enough, and that all 20 digits numbers have enough repetitions
>to justify.Since it all seems unlikely the answer so far seems to be no.

Not sure exactly what your question is. If the question is whether there
is any way that you could represent an *arbitrary* 20-digit number using
only 8 bytes, then the answer is no, by basically the same argument you
gave at the start. 2^64 < 10^20, so if you try to represent a 20-digit
number using only 8 bytes, then there must exist two (in fact, many more
than that, but two is enough for the argument) distinct 20-digit numbers
that are assigned the same 8-byte representation. There is no way to
disambiguate these two numbers so the system must fail. This argument
applies to any algorithm, no matter how complex.

Now if you have a situation in which only 2^64 twenty-digit numbers will
ever show up, and you know which ones they will be, then it will certainly
be possible to represent them using 8 bytes. In the worst case, just list
all the 20-digit numbers in order, and use "n" to represent the nth number
on your list. This might not be computationally very efficient, but it
will work.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Tim Little on 9 Apr 2010 20:48
On 2010-04-09, Rafael Anschau <rafael.anschau(a)gmail.com> wrote:
> Most databases attest they can hold 20 digits bigints into 8 bytes.
> How ?

Wrong way around. Most databases attest that they can store 8-byte
bigints, some values of which require 20 decimal digits.


- Tim
From: Tim Little on 9 Apr 2010 20:52
On 2010-04-09, Rafael Anschau <rafael.anschau(a)gmail.com> wrote:
> But the research,theoretical topic is open: "Could you possibly put
> all 20 digits into 8 bytes ?"

It's very much a closed topic: no. 10^20 > 256^8, which according to
at least one common *definition* for the > symbol, means there is no
injection from a set of 10^20 elements into one of 256^8 elements.


- Tim
 |  Next  |  Last
Pages: 1 2
Prev: Sometimes when you embrace the impossible you discover truth.
Next: IF P THEN N = 2N/2P-N?