asboans (u/asboans) - Readit News

I keep seeing might and magic related content, despite never having played it, or even having heard of it until recently! But in the last few months I have been getting the odd YouTube recommendation, or see the occasional Reddit (and now HN) thread.

Why?

asboans commented on New sphere-packing record stems from an unexpected source quantamagazine.org/new-sp... · Posted by u/pseudolus

ivanbakel · 2 months ago

This looks to have been a conflation by the GP between the volume of the unit sphere itself and its ratio to the volume of its bounding cube (which is not the unit cube.) The volume of the sphere does top out at an unintuitive dimension, but indeed the ratio of the two is always decreasing - and intuitively, each additional dimension just adds more space between the corners of the cube and the face of the sphere.

asboans · a month ago

Urgh you’re right. I was being dumb and am now ashamed

asboans commented on New sphere-packing record stems from an unexpected source quantamagazine.org/new-sp... · Posted by u/pseudolus

Someone · 2 months ago

FTA: “in 100-dimensional space, his method packs roughly 100 times as many spheres; in a million-dimensional space, it packs roughly 1 million times as many“

Nice example of how weird large-dimensional space is. Apparently, when smart minds were asked to put as many 100-dimensional oranges in a 100-dimensional crate as they could, so far, the best they managed to do was fill less than 1% of its space with oranges, and decades of searching couldn’t find a spot to put another one.

asboans · 2 months ago

“Fill less than 1% of its space” becomes a very counter intuitive statement in any case when discussing high dimensions. If you consider a unit n-sphere bounded by a unit cube, the fraction occupied by the sphere vanishes for high n. (Aside: Strangely, the relationship is non monotonic and is actually maximal for n=6). For n=100 the volume of the unit 100-sphere is around 10^-40 (and you certainly cannot fit a second sphere in this cube…) so its not surprising that the gains to be made in improving packing can be so large.

asboans commented on Sequence and first differences together list all positive numbers exactly once oeis.org/A005228... · Posted by u/andersource

kleiba · 2 months ago

Coding exercise: write a function

    boolean isInSequence(n):

that decides whether the given integer is part of that sequence or not. However, pre-storing the sequence and only performing a lookup is not allowed.

asboans · 2 months ago

I don’t know but I think I could probably implement IsInSequenceOrFirstDifferences(n)

asboans commented on A curious case of O(N^2) behavior which should be O(N) (2023) gist.github.com/bssrdf/39... · Posted by u/bssrdf

consp · 8 months ago

Fun bonus: they can be interchangeable, e.g. increasing space to reduce time.

asboans · 8 months ago

And any operation that takes n bits as input can be trivially turned into an O(1) time and O(2^n) space algorithm through tabulation.