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

31–40 of 115 posts

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

#31

Post by FabHK »

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…

> Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63.

Not sure I understand.

Adding two 32 bit integers takes you to 33 bit integers. (1111 + 1111 = 11110).

Addition doesn't care about order, so you're instantly cutting 2^33 possibilities down to 2^32. Or so is your argument. But in reality you can reach nearly all of those 2^33 numbers.

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

#32

Post by topaz0 »

PaulHoule wrote: post #5
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…

... or just considering the even numbers almost all of them are 2 x N where N>2^32 and that gets you to within a hair of "most" and if you add in the odd thirds for which the same is true you get a bound of 2/3 - epsilon.

It's a bit more subtle than that -- most n>2^32 are not prime in which case 2 x n has more factorizations you would have to check.

(Just by way of example, for n=2^33, 2n=2^34 but also =2^17*2^17)

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

#33

Post by ot »

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…

Yeah the number sounds a lot less impressive if you say that you only get 2^61.44 integers out of 2^64. In other words, a 4% entropy loss.

Information quantities are more meaningfully expressed in number of bits.

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

#34

Post by klodolph »

FabHK wrote: post #31
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…

> Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. Not sure I understand. Adding two 32 bit integers takes you to 33 bit integers. (1111 + 1111 = 11110). Addition doesn't care about order, so you're instantly cutting 2^33 possibilities down to 2^32. Or so is your argument. But in reality you can reach nearly all of those 2^33 numbers.

Addition in this case is cutting from 2^64 to 2^33-1.

The 2^64 number is the number of inputs. For an operation which is commutative, you expect the outputs to be 2^63+2^32 or smaller, since you’ve introduced symmetry.

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

#35

Post by henry2023 »

moefh wrote: post #23
HWR_14 wrote: post #13

Earlier quoted context omitted.

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

I think they meant to write "There are about 4 billion TIMES more 64 bit integers than 32 bit integers".

Indeed, edited the mistake

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

#36

Post by sdenton4 »

FabHK wrote: post #31
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…

> Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. Not sure I understand. Adding two 32 bit integers takes you to 33 bit integers. (1111 + 1111 = 11110). Addition doesn't care about order, so you're instantly cutting 2^33 possibilities down to 2^32. Or so is your argument. But in reality you can reach nearly all of those 2^33 numbers.

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.

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

#37

Post by [deleted] »

FabHK wrote: post #31
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…

> Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. Not sure I understand. Adding two 32 bit integers takes you to 33 bit integers. (1111 + 1111 = 11110). Addition doesn't care about order, so you're instantly cutting 2^33 possibilities down to 2^32. Or so is your argument. But in reality you can reach nearly all of those 2^33 numbers.

[deleted]

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

#38

Post by topaz0 »

FabHK wrote: post #31
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…

> Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. Not sure I understand. Adding two 32 bit integers takes you to 33 bit integers. (1111 + 1111 = 11110). Addition doesn't care about order, so you're instantly cutting 2^33 possibilities down to 2^32. Or so is your argument. But in reality you can reach nearly all of those 2^33 numbers.

The 2^64 in gps argument comes from the number of pairs of 32 bit numbers, not from the upper bound of multiplying two 32 bit numbers. So for the addition case the symmetry argument is still only good enough to get you down to about 2^63, which doesn't help you at all because you have much stronger information from the upper bound.

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

#39

Post by [deleted] »

thaumasiotes wrote: post #25
rao-v wrote: post #22

Earlier quoted context omitted.

Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?

If you're allowed to multiply as many 32-bit numbers as you want, the only numbers you won't be able to achieve by so doing are those with any prime factor larger than 2^32. This is more than just the prime numbers. For example, a 41-bit prime can be multiplied by 16 and it will still fit into 64 bits.

[deleted]

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

#40

Post by mswphd »

childintime wrote: post #26
MarkusQ wrote: post #11

If this seems counterintuitive, consider that only about a third of the two-digit numbers ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72, 81}) can be written as the product of two one-digit numbers.

where is the graph and the theorem for integers of n bits, with n going to infinity?

The math was linked in the article

https://arxiv.org/pdf/1908.04251

Post reply on HN