HN Debrief

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

  • Mathematics
  • Programming
  • Hardware

The post works through a neat number theory fact with a systems flavor. If you take two 32-bit unsigned integers and multiply them, the 64-bit result is exact, but only about 3.2 quintillion of the 18.4 quintillion possible 64-bit values ever appear. That is roughly 17%. The article also points to a deeper theorem: as the bit width grows, the fraction of 2n-bit integers that can be written as a product of two n-bit integers goes to zero.

If you are treating widened multiplication as a way to spread values evenly across a larger integer space, do not assume good coverage. The usable output set is much smaller than the raw bit width suggests, which matters for hashing, randomized testing, and any encoding that relies on multiplication to generate broad 64-bit diversity.

Discussion mood

Mostly intrigued and mildly amused. Readers liked the result, but many immediately reframed it as a collision and entropy story rather than a shocking impossibility, and several drilled into the number theory to explain where the missing outputs actually go.

Key insights

  1. 01

    The asymptotic result is the real punchline

    What makes this more than a cute 64-bit fact is that the reachable fraction tends to zero for larger bit widths. The drop is incredibly slow, which is why 17% still looks sizable at 32-by-32 to 64 bits, but the long-run statement is much stronger than the headline and is the actual theorem worth remembering.

    If you generalize this to bigger integer types, expect coverage to get worse, not better. Any design that depends on multiplication spanning a large exact output space will degrade with scale even if small examples look acceptable.

      Attribution:
    • svat #1 #2
  2. 02

    Large prime factors explain most misses

    A rough sieve-style estimate says a big chunk of unreachable 64-bit integers are excluded for the simple reason that they contain a prime factor above 2^32. That already rules out numbers that cannot be split into two 32-bit factors, and commenters estimated this accounts for most of the 83% gap before you even handle the more intricate multi-factor cases.

    When you need a quick mental model for what multiplication cannot hit, start by looking for oversized prime factors. That gets you most of the way to the right intuition fast.

      Attribution:
    • danbruc #1
    • bonzini #1
    • intuitionist #1
  3. 03

    B-smooth is necessary but not sufficient

    Having no prime factor above 2^32 does not guarantee representability. The stronger requirement is that the full prime factorization can be partitioned into two groups whose products both fit under the 32-bit bound. Examples like 70 for base 10, or high powers such as 2^62×3 in the 64-bit setting, show that smooth numbers can still fail because their factors cannot be packed into two small enough buckets.

    Do not reduce this problem to a smoothness test. If you need an exact predicate, you must also solve the bounded split problem over the factorization.

      Attribution:
    • danbruc #1
    • svat #1
  4. 04

    The loss is small in bit terms

    Several readers translated 17% coverage into logarithms and got a less dramatic picture. The reachable set is about 2^61.44 values, so compared with the full 2^64 space the deficit is only around 2.56 bits of output diversity. Framed that way, the result still matters, but it stops sounding like multiplication destroys most of the available information.

    For engineering uses like entropy budgeting or hash analysis, compare reachable-set size in bits, not just percentages. The right metric depends on whether you care about exact coverage or effective diversity.

      Attribution:
    • ot #1
    • jetsamflotsam #1
  5. 05

    Sampling can estimate the fraction efficiently

    One commenter sketched and then refined a probabilistic algorithm for estimating the density without exhaustive enumeration. The key trick was to sample random integers together with their prime factors using Kalai's method, which lets you test the bounded-factor condition directly and get usable estimates even at larger bit sizes.

    If you want approximate densities for larger widths, Monte Carlo over factored samples is viable. You do not need full enumeration or complete factorization of uniformly random large integers to get a good estimate.

      Attribution:
    • _alternator_ #1

Against the grain

  1. 01

    Seventeen percent is less shocking than advertised

    The headline sounds like a deep impossibility result, but getting below 50% is already almost forced by commutativity alone. Once a symmetric operation maps 2^64 input pairs into 64-bit outputs, you should expect a huge amount of duplication before doing any number theory at all, so "most values fail" is not the interesting threshold.

    If you cite this result in product or engineering discussions, lead with collisions or asymptotics, not the word "most." That framing better matches what is genuinely non-obvious.

      Attribution:
    • Dylan16807 #1 #2
  2. 02

    Seventeen percent is actually pretty high

    At least one reaction went the other way. Given how structured multiplication is, 17% felt larger than expected rather than smaller. That is a useful corrective to the entropy-loss framing, because it reminds you that exact products still occupy a surprisingly large absolute chunk of the 64-bit range.

    Whether this feels sparse depends on your baseline. If your intuition says multiplication should hit an almost negligible subset, calibrate upward before making claims about how restrictive the image really is.

      Attribution:
    • davesque #1

In plain english

b-smooth ↩
A number whose prime factors are all less than or equal to some bound b.
entropy ↩
In information theory, a measure of uncertainty or unpredictability in data.

Reference links

Math papers and references

Floating-point and NaN references

Examples and illustrations