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

101–110 of 115 posts

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

#101

Post by svat »

AnotherGoodName wrote: post #86

The mathematical term for this is the probability of a number being b-smooth. Here ‘b’ is 2^32

It's related, but not the same thing. For example, for b=10, the number 70=2x5x7 is b-smooth, but it cannot be written as the product of two numbers less than b. Here are the other b-smooth (counter)examples for b=10:

    | n   | factorization  | products of two numbers
    |-----|----------------|------------------------------------
    | 50  | 2 * 5^2        | 1x50, 2x25, 5x10
    | 60  | 2^2 * 3 * 5    | 1x60, 2x30, 3x20, 4x15, 5x12, 6x10
    | 70  | 2 * 5 * 7      | 1x70, 2x35, 5x14, 7x10
    | 75  | 3 * 5^2        | 1x75, 3x25, 5x15
    | 80  | 2^4 * 5        | 1x80, 2x40, 4x20, 5x16, 8x10
    | 84  | 2^2 * 3 * 7    | 1x84, 2x42, 3x28, 4x21, 6x14, 7x12
    | 90  | 2 * 3^2 * 5    | 1x90, 2x45, 3x30, 5x18, 6x15, 9x10
    | 96  | 2^5 * 3        | 1x96, 2x48, 3x32, 4x24, 6x16, 8x12
    | 98  | 2 * 7^2        | 1x98, 2x49, 7x14

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

#102

Post by adgjlsfhk1 »

kens wrote: post #90
jetsamflotsam wrote: post #83

Earlier quoted context omitted.

Exactly. Being precise about logarithmic vs linear utilizations is key here. I tried making a similar point about the inefficiency of IEEE-754 redundant NaN encodings here: https://arxiv.org/pdf/2508.05621 Having ~a quadrillion redundant bitstrings all mapping to NaN sounds pretty bad, but logarithmic/information utilization-wise, this is actually not too bad.

I've been looking at the 8087 NaN circuitry lately. Having 2^53 (or whatever) values for NaN was supposedly a feature: "the large number of NAN values that are available, provide the sophisticated programmer with a tool that can be applied to a variety of special situations." For example, the different NaN values could hold debugging information to track down errors. See "8087 Numeric Data Processor" page S-74: https…

> For example, the different NaN values could hold debugging information to track down errors.

Unfortunately IEEE didn't bother specifying NaN propagation semantics so it ended up pretty useless.

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

#104

Post by thaumasiotes »

shiandow wrote: post #95
nyeah wrote: post #43

Earlier quoted context omitted.

What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.

If you bring overflow into the mix things become a lot more complicated. You likely don't even need 32 bits, the numbers 2 and 3 might be enough (I don't know for sure or if there's a quick way to check).

Well, if you "bring overflow into the mix", what you get depends on your behavior when overflowing.

If you say that you want to be doing modular arithmetic instead of arithmetic, it doesn't look like 2 and 3 are enough. You're looking for a solution to

    2ᵃ * 3ᵇ ≡ n (mod 2⁶⁴)
If n is even, we can supply any number of 2 factors by fiddling with a. We can assume without loss of generality that n is odd and a = 0. Now we want

    3ᵇ ≡ n (mod 2⁶⁴)
for odd n.

If I'm reading wikipedia correctly, we know that this will fail for some n:

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

> In symbols, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gᵏ ≡ a (mod n).

This is what we want, with g = 3, k = b, a = n₁, and n₂ = 2⁶⁴. Our restriction that n₁ (our n) is odd satisfies the requirement that a be coprime to n₂ (wikipedia's n, the modulus).

The article continues:

> a primitive root exists modulo n if and only if n is 4, pᵏ or 2pᵏ for some odd prime number p and some k ≥ 0.

2⁶⁴ does not satisfy this requirement and therefore there is no primitive root modulo 2⁶⁴. As such, 3 is not a primitive root modulo 2⁶⁴.

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

#107

Post by antonvs »

order-matters wrote: post #30
jerf wrote: post #29

Earlier quoted context omitted.

Indeed, but justice requires that we recursively continue all the way to the base case, until all 32-bit integers are products of 16-bit integers, all 16-bit integers are products of 8-bit integers, all 8-bit integers are products of 4-bit integers, all 4-bit integers are products of 2-bit integers, and all 2-bit integers are products of 1-bit integers. Only when we have reach all the way down that list to the very,…

Enough of this divided binary world, we are all one

Did you just misdigit me

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

#108

Post by Dylan16807 »

svat wrote: post #100
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…

The word “most” is indeed not very surprising if taken to mean >50% (as you do), but the surprising fact (admittedly not relevant for 2^64 in the quoted sentence) is that “most” can be replaced with “almost all” in the technical sense meaning “tending to 1” i.e. “1 - o(1)”, i.e. “eventually greater than 1-epsilon for any epsilon”. Here's the multiplication table up to 9 (so for n=10 in place of n=2^64), and it alread…

It's an interesting fact, but it's weakened a lot by happening so slowly and not matching the everyday definition of "almost all".

And it's weakened even more by realizing that while you can get the raw fraction as low as you want, shrinking your list of products by n digits requires numbers with an exponential number of digits.

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

#110

Post by sebzim4500 »

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.

I'm not sure I understand your comment. Just because a number of of the form 2N with N > 2^32 doesn't mean it can't also be written as the product of two numbers below 2^32.

    E.g. 2^40 = 2^20 * 2^20
Post reply on HN