fivemack: (Default)
I have just emerged from a five-hour optimisation trance, fuelled by sushi and plum wine.

Here is the code; it looks for numbers which can be written as the sum of three sixth powers in two different ways. It's multi-threaded (by constants in the code assuming you have four cores spare) and uses a cache-friendly blocked linked-list structure; it slices up the problem into chunks by sum-modulo-P and then into buckets by sum-modulo-Q, then sorts the bucket contents. It uses moderately prodigious amounts of memory - about 20N^2 bytes. It takes 1m15s wall-time on my machine (2.4GHz quad-core) to run 'sumsix_t4 2003', 10m35s wall-time for 'sumsix_t4 4007'. I'm surprised that the output from 'time' indicates that it spends non-trivial time in the OS: how? The only bits that look like OS calls are print statements and memory allocation, and it only does O(N) of those.

real 10m35.586s
user 31m20.462s
sys 5m20.408s

I'm sure it could be significantly faster - it's trivially parallel and I'm only getting x3 speedup on four CPUs - but I am not quite sure how. I've looked at profiles, I suspect I may have been foiled by out-of-order execution, where quick-op ( result of slow-op ) has to wait for slow-op to complete and so appears as a hotspot when the real hotspot is elsewhere. Hard-wiring the values of 'N' and 'bucket' so that the compiler can replace the modulo operations with multiplies by magic constants doesn't make a difference.

If there are people out there who like this sort of challenge, I'd like some input.
fivemack: (balls)
As far as I've bothered to run the exhaustive search, the number of ways of making a tetrahedron out of N colours of perspex rods such that you never have two rods of the same colour coming out of a single vertex, but not requiring you to use all N colours, is N (N-1) (N-2) (N^3-9N^2+29N-32).

This doesn't seem a very natural polynomial to me.

There seems to be a unique-up-to-A5 three-colouring of the edges of a dodecahedron and a unique-up-to-S4 three-colouring of the edges of a cube; there's an obvious unique-up-to-S3 three-colouring of the edges of a tetrahedron. Obviously you can't three-colour the edges of an octahedron or an icosahedron, since four or five edges meet at a vertex; it looks as if there are maybe two group-theoretically-distinct four-colourings of the octahedron, and roughly 1560 five-colourings of the icosahedron.

As an obviously related question, where can I get some (fifty would be a good number) two-inch solid black rubber balls? I have already found a supplier of six-foot lengths of half-inch perspex rod in three distinct fluorescent colours ...

What's a material that can both be cast and machined? To get the holes in the balls in the right places I'd need the use of a drill-press and a couple of oddly-shaped jigs, and the easy way to make the jigs seems to be to use a ball as a mould to cast a hemispherical hole in something castable, then orient the casting properly (this is the tough part, I don't know what the name for the kind of contraption of adjustable vices I'm thinking of would be), drill a hole in the correct place with the drill-press, and insert a spare bit of half-inch dowelling to fit into the first hole drilled so that the second and third (and fourth and fifth for the icosahedron) end up in the right places. Or is drilling holes in rubber balls likely to be a source of frustration, horrible stench, and an unreasonable amount of time spent cleaning melted rubber off drill-bits?

July 2017

161718 19202122


RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 21st, 2017 03:16 am
Powered by Dreamwidth Studios