Prev: Sometimes when you embrace the impossible you discover truth.
Next: IF P THEN N = 2N/2P-N?
From: Casey Hawthorne on 9 Apr 2010 21:30
As a rough rule of thumb: 2^10 = 1024 ~= 10^3

Since 20 digits is just a little less than (10^3)^7, which is
approximately equal to (2^10)^7 = 2^70 bits.

And 8 bytes is 2^64 bits,

So, 2^70 bits is (2^70)/(2^64) = 2^6 = 64 (8 byte groups).


On Fri, 9 Apr 2010 11:13:57 -0700 (PDT), Rafael Anschau
<rafael.anschau(a)gmail.com> wrote:

>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
--
Regards,
Casey
From: osmium on 9 Apr 2010 22:22
Rafael Anschau wrote:

> 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 ?

I would expect Claude Shannon's paper on information theory to prove that it
couldn't be done.

My take: log[10]2 = .3010, so you can store 64 * .301 or about 19.264
decimal digits in 64 bits. Any hopes for compression to help is a hoax or
some kind of a word game.


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