8 ms·
Only 17% of all 64-bit Integers are products of two 32-bit integers
- deleted 4mo ago[deleted]
- pants2 4mo agoI dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.
- kleiba2 4mo agoI upvoted you, not because I think your joke is particularly great, but I hate that HN has this tendency to downvote comments that are clearly meant as a humorous contribution. And I get it, no-one wants HN to turn into Reddit. I also understand that not every joke lands. But I just think it's unnecessary to downvote, you could simply ignore.
- zamadatix 4mo ago"Ignore" is one of those things that sounds like it's a neutral choice but really isn't in practice - it's still just saying "can only ever be positively pressured". IMO people shouldn't go as far as flag though, at the very least, and if it's already at the bottom of the sort there is no sense dumping on it further. My current comment itself, for instance, also doesn't really add anything to the discussion about the article and I'd have no expectation people leave it from going negative. Maybe the will, maybe they won't, but there is no reason to expect they should in principle of me loving tangents :D.
- jihadjihad 4mo agoWhy stop there? We can dream of a future where math is bent to our will [0] for the betterment of all mankind! 0: https://en.wikipedia.org/wiki/Indiana_pi_bill https://en.wikipedia.org/wiki/Indiana_pi_bill
- dvh 4mo ago1 + 1 = 3 (for sufficiently large values of 1)
- brookst 4mo agoThere should be a law!
- jerf 4mo agoIndeed, 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, very smallest of the numbers around us and brought justice to them will the future be able to arrive. I literally can not wait for that day.
- order-matters 4mo agoEnough of this divided binary world, we are all one
- antonvs 4mo agoDid you just misdigit me
- aidenn0 4mo agoThat would require multiplication to be non-commutative, right?
- AlienRobot 4mo agoMaybe we can reach there by using integers as fixed point decimals?
- basilikum 4mo agoCryptographers hate this trick
- Dylan16807 4mo ago> 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" already, and considering even a tiny amount of overlapping results gets you there. What gets interesting is actually trying to quantify the overlapping results.
- adgjlsfhk1 4mo agoA lot of the remaining is multiples of 4, which you can either get from having a 2 in both factors or a 4 in one (multiples of 9 are similar).
- PaulHoule 4mo ago... 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.
- topaz0 4mo agoIt'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)
- sebzim4500 4mo agoI'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
- danbruc 4mo agoAll the primes above 2^32 are out, but that accounts for only two point something percent.
- henry2023 4mo agoThere 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
- HWR_14 4mo agoThere are about 18.446 quintillion more 64-bit integers than 32-bit integers.
- deleted 4mo ago[deleted]
- moefh 4mo agoI think they meant to write "There are about 4 billion TIMES more 64 bit integers than 32 bit integers".
- henry2023 4mo agoIndeed, edited the mistake
- adrian_b 4mo agoTrue, but there are as many 64-bit integers as pairs of 32-bit integers. Therefore the fact that relatively few 64-bit numbers are products of 32-bit integers means that a lot of pairs of 32-bit integers give by multiplication the same product.
- aidenn0 4mo agoThat seems intuitively true given that most 32-bit numbers are composite, so if you have X = ab and aY < 2^32 and bY < 2^32: X × Y = X/a × aY = X/b × bY = Y × X = aY × X/a = bY × X/b Which is 6 pairs resulting in the same product. This will be reduced if e.g. aY = X, but still...
- bo1024 4mo ago
- MarkusQ 4mo agoIf 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.
- childintime 4mo agowhere is the graph and the theorem for integers of n bits, with n going to infinity?
- mswphd 4mo agoThe math was linked in the article https://arxiv.org/pdf/1908.04251 https://arxiv.org/pdf/1908.04251
- da_chicken 4mo agoThis feels like a underlying property that contributes to of Benford's Law[0]. That is, most numbers we measure and record are the results of various independent (addition) and dependent (multiplication) factors stacking together, and we observe this property in the distribution of them. [0]: https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law
- nicechianti 4mo ago[dead]
- crest 4mo agoSo you're better of using a 8x8->16 widening multiplication SIMD instruction or even just a multi register TBL/TBX instruction?
- deleted 4mo ago[deleted]
- kingstnap 4mo agoThis is something I had thought about some time back where I was thinking about the feasibility of somehow using the upper and lower registers inside a multiplier as general purpose storage for fun / seeing if you could make them more compact. Anyway here is a fun pattern you get when you multiply 8 bit unsigned integers. Not all pairs of (upper bits, lower bits) are reachable, and it has a lot of distinct patterns. https://i.imgur.com/Gb3HDR0.png https://i.imgur.com/Gb3HDR0.png (Should I host the image on GitHub Gists so it doesn't vanish?)
- tobz1000 4mo ago> the proportion of all 2n-bit values that can be generated by the product of two n-bit values goes to zero as n becomes large. This means that if you have, say, 10000000-bit integers multiplying 10000000-bit integers, you’d expect relatively few 100000000000000-bit integers to be produced. That should be "relatively few 20000000-bit integers", right?
- PunchyHamster 4mo agoWell, that is entirely not surprising. Pretty sure people writing not terrible hash functions figured it decades ago
- cobbzilla 4mo agoI must be missing something. Aren’t ~50% of 64-bit integers the product of the number 2 and another 32-bit integer?
- mplanchard 4mo agoI don’t think so, because that only gets you up to 2x2^32, which is nowhere near halfway to 2^64
- slazaro 4mo agoGoing from 32 bits to 64 bits doesn't double the range (that would be adding 1 bit), it squares the range.
- jlarocco 4mo agoNo. 50% of them are the product of 2 and a 63-bit integer.
- jandrese 4mo agoThis just seems like an expansion of prime numbers to includes factors in the 2^33+ range. Basically you're calculating if a number is prime but stopping the check when the factors go above 2^32.
- Taek 4mo agoWell, technically yes, but 'stopping the factors at 32 bits' is a plenty interesting constraint because it excludes all 64 bit composite numbers that have at least one factor above 2^32. You have to redo the math to make the constraint work.
- intuitionist 4mo agoHaving a prime factor greater than 2^32 accounts for about 80% of the 64-bit integers that can’t be expressed as a product of 32-bit integers. But it’s not the only way; you can also have three prime factors in the range (2^16, 2^32), for instance.
- bonzini 4mo agoMore precisely one in the range (a,2^32) and two in the range (2^32/a, 2^32). But if the latter have many duplicate prime factors it's worse.
- deleted 4mo ago[deleted]
- fogleman 4mo agoDoes it actually matter for hash uniformity, though?
- _alternator_ 4mo ago> You might be able to come up with a more efficient algorithm. Challenge accepted. Suppose we want to know the answer to 3 decimal places (so we'd match the headline). And suppose I allow my algorithm to be wrong one in a thousand times ("probably approximately correct"). Then sample some constant number C of random 64 bit integers. Run the following algorithm which separates each random sample into one of three classes: Y (has 32 but factors), N (does not have 32 bit factors), U (unknown). Check if prime using probabilistic miller rabin. (Error prob goes to zero exponentially fast). If prime, return N. If it's not a prime, then run T steps of pollard rho to determine whether the number has 32 but factors; return Y,N, or U depending of the factors found up to step T. The key observation is that T can be chosen to make the UNKNOWN class very small (with high probability), and so our estimate should rapidly converge to 17%Y, 83%N, ~0.001%U For fixed error tolerance, this would run in roughly a constant number of iterations, independent of N.
- bonzini 4mo agoEven if you have 32-bit factors the number may not be the product of two 32-bit numbers. For example 2^62*3 cannot be split as either (2^32, 2^30*3) or (2^31, 2^31*3). In both cases one factor does not fit in 32 bits.
- _alternator_ 4mo agoAh, yes, this is true, but it's not really a counterexample, since this would show up in the N or U bucket. But I think the issue is that my sketch algorithm is, well, pretty sketchy. Working on coding it up... it converges to 17±0.5%for N=64 bits in a javascript implementation relatively quickly, but for N=96, it really slows down as Pollard's Rho starts with large factors. This means my fast-and-loose assumption that "a constant number of iterations of Pollard Rho would work" isn't actually true!
- _alternator_ 4mo agoOk, chatting with Claude and I found a way to salvage the approach! (Also, it's apparently in the paper that's referenced in the post, kinda cool that my sketchy algorithm got halfway to the published result). Basically, replace the Pollard Rho partial factorization with a method of Kalai [1] for generating random numbers _together with their prime factors_. I'm able to run this at about 30 samples per second at 160bits, giving an estimate of ~14.1% of 160-bit numbers factoring into two 80-bit numbers. [1]: https://link.springer.com/article/10.1007/s00145-003-0051-5 https://link.springer.com/article/10.1007/s00145-003-0051-5
- kurlberg 4mo agoThere is a cute argument (I think it is due to Erdos) that, asymptotically, 0% of the integers in [0,n^2] appears in the "n by n multiplication table": By Erdos-Kac, almost all integers of size about n^2 have about log(log(n^2)) ~ log(log(n)) prime factors. However, almost all integers in the multiplication table have about 2*log(log(n)) prime factors. Kevin Ford gets much more precise asymptotic estimates.
- furyofantares 4mo agoI don't think I needed an AI-generated infographic of the headline. It looks like a product sales pitch. Extremely strange way to deliver the headline (right before delivering the headline).
- AnotherGoodName 4mo agoThe mathematical term for this is the probability of a number being b-smooth. Here ‘b’ is 2^32
- danbruc 4mo agoRelated but not strong enough. 17 x 17 x 17 = 4,913 is 2^8-smooth - no prime factors larger than 2^8 - and it is less than 2^16, but 17 x 17 = 289 does not fit into a byte. Smoothness is required but not sufficient for a product representation to exist.
- svat 4mo agoIt'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
- saghm 4mo agoThe way the headline is phrased doesn't really surprise me much. There aren't twice as many 64-bit integers than 32-bit ones; there are twice as many 33-bit integers as 32 bit ones, and there are 2^32 times as many 64-bit ones than 32-bit ones. It's like asking how many numbers between 1-64 you can get by multiplying numbers between 1-8; I think it's readily apparent that a pretty large portion are missed.
- andrewflnr 4mo agoBut you're using two 32-bit numbers, which have the same total bits as a 64-bit number. There are equally many 32-bit x 32-bit pairs as there are 64-bit numbers.
- saghm 4mo agoAnd there are as many pairs of numbers between 1-8 and numbers from 1-64, but it's still pretty apparent that most of them are not represented in the set of products.
- themafia 4mo agoSure. You're just experiencing aliasing though. Are you not? > There are 3,215,709,724,700,470,902 64-bit (unsigned) integers that can be written as a product of two 32-bit integers. That can be written as a product of one or more pairs of 32 bit integers. So this is just not a bijective map.
- Automator666 4mo ago[flagged]
- davesque 4mo agoHonestly, this is a larger portion than I would have expected.
- sam0x17 4mo agoI wonder what kind of result you'd get with floats
- avp210 4mo agoOnly 20% of 2 digit numbers are product of one digit numbers: 10 (1+9), 11, 12, 13 … 18 (9+9)