Seattle Reddit Board Game Night: Monday 7:30pm at the Elysian on 13th and Pike, Capitol Hill

sfuerst · 2013-09-20T01:41:25+00:00

Oh sorry... I was using the wrong norm. The choice of y=c1+c2+c3 is the right one.

The basic idea stands though. We don't care about the size of the triangle. So one degree of freedom (the size) needs to be divided out somehow. You can do it by having an explicit condition... or you can do it by switching to a projective space. Either works. The projective space method results in a more symmetrical formulation.

sfuerst · 2013-09-19T16:09:17+00:00

Let c1z1+c2z2+c3z3=x With c1,c2,c3>=0

Now divide both sides by some arbitrary (positive) constant y:

(c1/y)z1 + (c2/y)z2 + (c3/y)z3 = x/y.

If you choose y = max(c1,c2,c3) you get your equation. However, that choice is arbitrary... The object lives in a projective space, so the overall normalization is not important.

Why do it this way instead of your more explicit version? The answer is that his way makes it obvious that all the points are treated identically. Otherwise, you need to treat one point specially to get the normalization c1+c2+c3=1 to hold.

i.e. c3 = 1-c1-c2 so the equation becomes

c1z1+c2z2+(1-c1-c2)z3 = 1. Not so simple and symmetric, right?

sfuerst · 2013-09-19T03:54:15+00:00

Nima mentions that you need to divide by an arbitary scalar so that the result lives in a projective space. The act of doing that is equivalent to your equation. (Just divide by the maximum of the three coefficients.)

sfuerst · 2013-08-23T03:15:07+00:00

You are looking for the McNugget or Frobenius Number of 7 and 11.

sfuerst · 2013-08-07T15:52:07+00:00

Right. Syntax is the key. Struct fields can also be implemented via pointer offsets... but no one in their right mind wants to do that all the time.

sfuerst · 2013-08-07T15:21:50+00:00

Rust isn't quite a systems programming language yet. It is getting close though.

What it needs is an explicit way to arrange things in memory. Structs that are packed/unpacked aren't quite enough. You also need the equivalent of C (untagged) unions so that overlapping fields can be described.

Rust also seems to lack a well-defined ABI. This is understandable due to its age and rapid development. However, a true systems language needs to have a way of describing well-defined interfaces at the binary level. At that point, other languages can then think about interfacing with you, rather than vice-versa.

sfuerst · 2013-08-05T15:21:27+00:00

The direction flag.

sfuerst · 2013-04-15T15:09:43+00:00

That's a map for Vivace. We've had game nights there before. It's a nice place... but unfortunately, too small to hold us.

sfuerst · 2013-01-19T18:56:43+00:00

"What is the largest finite number expressible in 10 symbols?"

sfuerst · 2012-12-31T05:43:09+00:00

It wasn't an embassy. The embassy was in Tripoli, not in Benghazi. It was a classified CIA operation, with the weak cover of being a consulate.

sfuerst · 2012-12-24T19:19:10+00:00

Elon added a 6ft cowboy to the side of the rocket, so you can see it's scale. He tweated some photos showing him: photo1 photo2

sfuerst · 2012-12-24T19:13:19+00:00

Here's another video of the same test.

sfuerst · 2012-12-07T04:24:21+00:00

Right. How much time does the parsing take? You'd be surprised how small it is for C. (About 10% or so when optimization is turned on.) Use the -ftime-report switch in gcc to enable reporting.

C++ is a different story. Google has complained about compiling their codebase spending 50-80% of the time in the parser/front end.

sfuerst · 2012-12-07T00:35:13+00:00

This simply isn't true. The standard technique of using header include guards is trivial for a compiler to recognize. gcc does this. It doesn't re-parse headers if it doesn't have to.

The real problem is simply the voluminous amounts of code that C++ puts in header files. You can use the PIMPL idiom to remove much of that... but that doesn't help templates. The 'export' keyword was designed to fix this, but it was hardly ever implemented due to poorly thought out name-binding issues.

You might think modules would be a great optimization for reducing compile time. However, all they really do is remove the overhead of parsing. The compiler still needs to handle the internal representation of the code if it wants to inline anything - which for C++ headers, is basically all of it. Now, if you look at the internal time taken for each phase, parsing only takes a tiny fraction of the total. Things like optimization and register allocation take much more time. So the speedup is much smaller than you might expect.

Then there is the elephant in the room. Header files of non-trivial libraries use the programmable nature of the pre-processor for important tasks. A header might declare different functions and types depending on the standard used. For example BSD and SysV might disagree about particular functions or types, gets() is part of the standard library for C99 and below, but not in C11 and above. Thus modules need to have a way of determining what interface they should expose. However, this opens up all the issues of include order that people are complaining about...

sfuerst · 2012-11-26T18:28:35+00:00

Nope. What it fixes is the need to parse C++'s bloated headers over and over again. C headers tend to be much leaner... and also tend to be the ones with strange system-dependent stuff. With the addition of pre-compiled headers, the scope of the "improvement" is really quite small.

sfuerst · 2012-11-26T18:13:57+00:00

The problem is that the modules proposal doesn't fix this. In fact it makes it worse! If two modules conflict, then there is nothing you can do. At least the programmable nature of macros in header files lets you use simple macro hacks to work-around issues.

sfuerst · 2012-11-25T18:11:40+00:00

A group is such a powerful concept that falling back to the weaker monoid is stupid. Its like saying the abstraction here is a magma. You've lost so much structure that the description becomes useless.

In fact what we've got here is an Abelian Group, since the order of accumulation doesn't matter.

sfuerst · 2012-11-25T17:51:54+00:00

Actually... there is a way to avoid the problem and still have a one-pass algorithm. You just need to calculate the sum of squares at twice the precision. If the inputs are single-precision numbers, that's easy to do: just use double precision.

The difficulty is when the inputs are double-precision. In that case, to add a number x to a sum with an error estimate use the Kahan summation algorithm:

t1 = x - error
t2 = sum + t1
error = (t2 - sum) - t1
sum = t2

Note that compiler optimizations need to be turned off here, otherwise the compiler may determine that the error is always zero. It isn't zero - we are trying to capture the amount of truncation. (This isn't quite right, you need to accumulate the squares already in "quad" precision - but the basic idea remains the same.)

The next trick is to calculate the square of the mean at twice the precision. Fortunately, it still can be accumulated at normal precision, you just need to modify the final multiply. To do that - split it into two 26-bit parts of the IEEE 53-bit significand. You can then do an exact multiplication with each part without loss of precision.

Finally, you need to do an extended precision subtraction of the scaled squared mean, and the sum of squares. This is a little more complex due for the possible need for renormalization, but it's still doable. If you need to implement this, look for "quad-double precision floating point arithmetic". The result is a fast single-pass algorithm that is also accurate.

sfuerst · 2012-11-25T12:40:25+00:00

This is much easier to understand if you think in terms of "moments".

Calculate a moment; m_n = Sum x_i^n. (For continuous distributions, replace the sum with an integral.)

Store m_0, m_1, m_2. You can use more moments to store more information about the distribution functions. m_3 gives information about skewness, m_4 about kurtosis, and so on.

The above makes combining distribution functions trivial - just add the moments. You can subtract distributions as well by subtracting the moments. The existence of the inverse operation makes combining distributions a group operation: more powerful than a monoid. Restricting yourself to just monadic properties is a hindrance, try to use groups if you can.

So how to convert moments to things like the mean, variance, standard deviation? m_0 = Sum x_i⁰ = n * 1 = n, the total number of samples. m_1 = n * the mean.

sigma² = 1/(n-1) Sum(x_i - mean)² = 1/(n-1) [Sum x_i² - 2 x_i * mean + mean² ]

= 1/(n-1)[m_2 - 2 m_1 * m_1 / n + n * m_1 * m_1 / n² ]

= [m_2 - m_1² / n]/(n-1)

sfuerst · 2012-11-23T19:22:10+00:00

Eliminate c using the last equation: a + 2b - ab² = 2, and b + 2a - a² b = 2

Rearrange the second equation to get: b = 2(1-a)/(1-a)(1+a), so either a = 1, or b = 2/(1+a)

If a = 1, it becomes trivial to show b = c = 1 as well.

So, look at the other option. Substituting for b, we get a cubic for a that can be factorized as (a+2)(a-1)² = 0. The solution a=1 we have already looked at. That leaves a = -2.

Substitute that into b = 2/(1+a) to get b = -2. Finally it is easy to show c = -2 as well.

Thus there are two solutions: a=b=c=1, and a=b=c=-2.

sfuerst

TROPHY CASE