Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Only 17% of all 64-bit Integers are products of two 32-bit integers

lemire.me

Post reply on HN
Print view View original

51–60 of 115 posts

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#51

Post by topaz0 »

danbruc wrote: post #6
Dylan16807 wrote: post #3

> I find it interesting to consider that if you pick a value at random, it will usually fail! That is, most 64-bit integers cannot be written as the product of two 32-bit integers. While I find the 17% number interesting to think about, "most" is far less interesting. Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. That's a hair's breadth away from "most" alr…

All the primes above 2^32 are out, but that accounts for only two point something percent.

But also all of their multiples. I suspect that those account for the vast majority.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#54

Post by mplanchard »

cobbzilla wrote: post #53

I must be missing something. Aren’t ~50% of 64-bit integers the product of the number 2 and another 32-bit integer?

I don’t think so, because that only gets you up to 2x2^32, which is nowhere near halfway to 2^64

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#55

Post by bo1024 »

HWR_14 wrote: post #13
henry2023 wrote: post #9

There are about 4 billion 64 bit integers for each 32 bit integer. The chance of a random 64 bit integer being a 32 bit integer is 0.0000000233 % The chance of a random 64 bit integer being a product of two 32 bit integers is 17% Nice

There are about 18.446 quintillion more 64-bit integers than 32-bit integers.

There are about 2^64 more 64-bit integers than 32-bit integers.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#56

Post by slazaro »

cobbzilla wrote: post #53

I must be missing something. Aren’t ~50% of 64-bit integers the product of the number 2 and another 32-bit integer?

Going from 32 bits to 64 bits doesn't double the range (that would be adding 1 bit), it squares the range.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#58

Post by orlp »

HarHarVeryFunny wrote: post #44
Dylan16807 wrote: post #3

> I find it interesting to consider that if you pick a value at random, it will usually fail! That is, most 64-bit integers cannot be written as the product of two 32-bit integers. While I find the 17% number interesting to think about, "most" is far less interesting. Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. That's a hair's breadth away from "most" alr…

Why does order matter? Whether a 64-bit number can be written as the product of two 32-bit ones depends only on the prime factors of the 64-bit number - it's a property of the number itself, and apparently 17% of 64-bit numbers have this property.

The input space is 32 + 32 = 64 bits. The output space is 64 bits. So the best you can do is an 1-to-1 mapping.

However, since a * b = b * a, our input space has a lot of duplicate outputs. So from this alone you can conclude roughly half of the output space must be uncovered by any input pair, simply because there aren't enough input pairs.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#59

Post by sdenton4 »

Dylan16807 wrote: post #50
sdenton4 wrote: post #36

Earlier quoted context omitted.

Concatenating arbitrary 32 bit ints covers all possible 64 bit ints. So the space of all pairs of 32 bit ints is in bijection with 64 bit ints. Commutativity introduces a relation on pairs of 32 bit ints (a,b) ~ (b,a), which accounts for one bit of information. Thus, at most 50% of 64bit ints show up as products of 32 bit ints.

Except the perfect squares don't reduce by half, so it's not quite 50% but it's very close.

Ha, fair!
Post reply on HN