strilanc

posted by twistedoak on March 7, 2014

Craig Gidney is continuing his blog in a new home: strilanc.com. You can be notified about posts there by following his rss feed, or following him on twitter. There are already two posts on the new site. Building your own Quantum Fourier Transform, and Ordering Cyclic Sequence Numbers. —

What Quantum Computers Do Faster, with Caveats

posted by Craig Gidney on February 19, 2014

I find reading media coverage of quantum computers frustrating. With rare exceptions, the explanations of what a quantum computer is or can do are totally unsatisfying. I remember being really confused about the whole thing. “You say a quantum computer can be in two states at the same time? Sounds cool, but how does that [...]

Naming Things: Fail-Useful

posted by Craig Gidney on February 9, 2014

Naming is a strange thing. You take reality, cut a chunk out, assign a sequence of syllables to that chunk, and suddenly you see it everywhere. Having the right chunks named literally changes how you think. In this series of posts, “naming things”, I take some shows-up-everywhere concept from programming (that doesn’t have a name, [...]

Detecting Simple Cycles Forming, Faster

posted by Craig Gidney on January 29, 2014

In this post: efficiently detecting when cycles appear, as edges are added to a graph, by taking advantage of a restriction on the type of graph. Motivation I worry a lot about little details. About ways people using my code might end up shooting themselves in the foot. Case in point: the collapsing futures library [...]

Third Party Bit Commitment

posted by Craig Gidney on January 22, 2014

In this post: using a trusted third party to make bit commitment perfectly secure. Motivation I wrote my master’s thesis on the subject of secret sharing, where a dealer splits some secret message into shares. Later on, players use some fraction of the shares to recover the secret. One of the tweaks to the problem [...]

Angular Velocity is Simple

posted by Craig Gidney on January 10, 2014

A few months ago, during the Halifax Game Jam, I realized that for a long time I’d thought angular velocities were more complicated than they actually are. Game Jam In October I attended the 2013 Halifax Game Jam. The theme was “discovery”. Actually, since the group I joined had an Occulus Rift, make that more [...]

Collection Equality is Hard

posted by Craig Gidney on December 31, 2013

In this post: dealing with the corner cases inherent in checking if collections are equivalent. Collection Equality One of Objective-C’s features that I really like, but forgot to mention in A Year’s Worth of Opinions about Objective-C, is the built-in support for equating collections by value. When I’m working in C#, and I want to [...]

Deadlocks in Practice: Don’t Hold Locks While Notifying

posted by Craig Gidney on December 22, 2013

In this post: a subtle way that reactive/event-based code can deadlock, how it affects ReactiveCocoa (obj-c) and Reactive Extensions (.Net), and ways to work around the problem. Realization Today I noticed that ReactiveCocoa, the Objective-C port of .Net’s Rx (Reactive Extensions), implements different semantics for its BehaviorSubject. This would be moderately interesting, except the change [...]

Brute Force Parallelization

posted by Craig Gidney on December 17, 2013

In this post: a technique for parallelizing accumulation, when the accumulator only takes on a small number of states. Trigger Today I watched the talk How to Think about Parallel Programming: Not! by Guy Steele. (It’s really good. The first third is off topic and still really good.) About an hour into the talk, Steele [...]

A Year’s Worth of Opinions about Objective-C

posted by Craig Gidney on December 11, 2013

About one year ago, I was placed on my first Objective-C project: porting RedPhone from Android to iOS. My part of RedPhone (the backend: audio, networking, crypto) has been done for about a month now. We’re waiting for an external security review, but internally no back-end bugs have been stumbled over while work continues on [...]

Older Posts


Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive