kmill · HackerTrans

24 дня назадdiscuss

If someone says they'll pay $8.50 but then they round up and give you $9, you wouldn't say they didn't give you the $8.50 due, right? It's in the $9.

I think implicitly with the inheritance is the assumption that the father is promising at least 1/2, 1/3, and 1/9 of the flock to the respective sons, not the exact fraction. There's a solution where each son gets what's promised, and then a little more.

kmill

в прошлом месяцеdiscuss

Certainly check the assembly, but loop invariant code motion and strength reduction are basic optimizations. C compilers tend to be good at optimizing indexing patterns even at -O1.

Take a look, GCC and Clang go further than these suggestions by adding screenRect.w to the pointer each iteration to avoid the multiplication: https://godbolt.org/z/YfroqK7T6

Writing anything but pixels[y*screenRect.w + x] in an attempt to be faster, without checking the assembly first, is obfuscation.

(For what it's worth, you can beat the compiler by using *pixels++. I didn't profile the code to check it actually was faster in practice however.)

kmill

в прошлом месяцеdiscuss

I'd be surprised if the compiler didn't make that optimisation on its own.

kmill

5 месяцев назадdiscuss

Would you mind sharing your representation? :-)

kmill

5 месяцев назадdiscuss

1. Algebra: Let's say we have a linear operator T on a real vector space V. When trying to analyze a linear operator, a key technique is to determine the T-invariant subspaces (these are subspaces W such that TW is a subset of W). The smallest non-trivial T-invariant subspaces are always 1- or 2-dimensional(!). The first case corresponds to eigenvectors, and T acts by scaling by a real number. In the second case, there's always a basis where T acts by scaling and rotation. The set of all such 2D scaling/rotation transformations are closed under addition, multiplication, and the nonzero ones are invertible. This is the complex numbers! (Correspondence: use C with 1 and i as the basis vectors, then T:C->C is determined by the value of T(1).)

2. Topology: The fact the complex numbers are 2D is essential to their fundamentality. One way I think about it is that, from the perspective of the real numbers, multiplication by -1 is a reflection through 0. But, from an "outside" perspective, you can rotate the real line by 180 degrees, through some ambient space. Having a 2D ambient space is sufficient. (And rotating through an ambient space feels more physically "real" than reflecting through 0.) Adding or multiplying by nonzero complex numbers can always be performed as a continuous transformation inside the complex numbers. And, given a number system that's 2D, you get a key topological invariant of closed paths that avoid the origin: winding number. This gives a 2D version of the Intermediate Value Theorem: If you have a continuous path between two closed loops with different winding numbers, then one of the intermediate closed loops must pass through 0. A consequence to this is the fundamental theorem of algebra, since for a degree-n polynomial f, when r is large enough then f(r*e^(i*t)) traces out for 0<=t<=2*pi a loop with winding number n, and when r=0 either f(0)=0 or f(r*e^(i*t)) traces out a loop with winding number 0, so if n>0 there's some intermediate r for which there's some t such that f(r*e^(i*t))=0.

So, I think the point is that 2D rotations and going around things are natural concepts, and very physical. Going around things lets you ensnare them. A side effect is that (complex) polynomials have (complex) roots.

kmill

10 месяцев назадdiscuss

That second operator is the <|> operator, from the Alternative typeclass.

The first one has some arbitrariness (do you take the left or right value if both are Just). But, thankfully the Applicative typeclass gives both <* and *>, which lets you choose which value you want:

  Just A <* Just B = Just A
  Just A *> Just B = Just B

(There's the possibility to merge values too, with f <$> Just A <*> Just B, which evaluates to Just (f A B). I feel like this is a "don't try to understand it, just get used to it" sort of syntax. It can be pretty convenient though.)

kmill

10 месяцев назадdiscuss

An analogy might be how if you mix together water and alcohol, you get a solution with less volume than the sum of the volumes. That doesn't mean that there's "negative" volume, just that the volume turns out to be sub-additive due to an interaction of specific characteristics of the liquids. Somehow, some connect sums of particular knots enable possibilities that let it more easily be unknotted.

I spent the better part of the summer during grad school trying to prove additivity of unknotting numbers. (I'll mention that it's sort of a relief to know that the reason I failed to prove it wasn't because I wasn't trying hard enough, but that it was impossible!)

One approach I looked into was to come up with some different analogues of unknotting number, ones that were conceptually related but which might or might not be additive, to at least serve as some partial progress. The general idea is represent an unknotting using a certain kind of surface, which can be more restrictive than a general unknotting, and then maybe that version of unknotting can be proved to be additive. Maybe there's some classification of individual unknotting moves where when you have multiple of them in the same knotting surface, they can cancel out in certain ways (e.g. in the classification of surfaces, you can always transform two projective planes into a torus connect summand, in the presence of a third projective plane).

Connect summing mirror images of knots does have some interesting structure that other connect sums don't have — these are known as ribbon knots. It's possible that this structure is a good way to derive that the unknotting number is 5. I'm not sure that would explain any of the other examples they produced however — this is more speculation on how might someone have discovered this counterexample without a large-scale computer search.

kmill

6 лет назадdiscuss

It would have been nice if 4D only ever meant four spatial dimensions, and then we'd have (3+1)D for three spatial dimensions and a time dimension. (And (2+2)D for two spatial and two time dimensions :-))

comments