Archive for the 'MarkCC’s Errors' category

Finger Tree Update: I forgot something

May 28 2009 Published by under Data Structures, MarkCC's Errors

As an alert commenter pointed out, I left out one really important thing in
my earlier post about finger trees. That's what I get for trying to write when
I'm sick :-). Seriously, this is a point that's implied by the post as it stands, but never explicitly stated - and since it's really important, it
should be stated explicitly.

The monoid-annotated tree structure doesn't replace the original
data structure: it's superimposed on it.

So, as I said: cons-cell style lists are ubiquitous and beloved by
functional and non-functional programmers. In finger trees, you're
not getting rid of them. The point of finger trees is to let
you keep the convenient data structure, with its basic operations
and properties intact, and to augment it with a tree that lets you search it efficiently.

To illustrate: here's the number list example from yesterdays post. The
original list is at the bottom, with green pointers representing the
original cons-list next-pointers. The monoid-annotated tree is on top,
with red pointers. The combination of the original list with the
monoid annotated tree is a finger tree.

counted-finger-tree-list.png

The point of this is that you've still got your cons list. All of the
beautiful recursive/iterative algorithms that walk the list continue to
work exactly the way that they would in the traditional cons-list: for code that walks the list, the fact that there are finger-tree pointers
sitting on top of the list is irrelevant - and, in fact, completely invisible. For algorithms that want to search the list, the tree structure is there,
and allows the searches to be performed much more quickly than they could be on
the traditional list. The superposition of those two structures is the
genius of the finger tree.

No responses yet

The Real Bozo Attempts to Atone: Why the DDWFTW Car Works

Dec 07 2008 Published by under MarkCC's Errors

Technorati Tags: , ,

So, as I said in the edit to my previous post about the wind-driven cart, I seriously blew it. The folks who pointed out the similarity of the cart to a tacking sailboat were absolutely correct. The guys who built this cart, and recorded the demo were absolutely right, and I was stupidly wrong, in multiple ways. First of all, I thought this was a really simple system. I couldn't possibly be more wrong about that - this is anything but simple; in fact, it's a remarkably interesting and elegant demonstration of how complicated and counterintuitive fluid dynamics can be. Second, I completely misunderstood the simple mechanics of the device; I originally thought that the propellor was spinning in the opposite direction - and I completely missed it when people repeatedly tried to explain that error to me. And third, I completely screwed up my own mathematical model of how something like this works.

So - to repeat: the guys who did the demo of this are clearly not bozos; the only bozo in this situation is me, for screwing it up so badly, on so many levels. I sincerely apologize for calling them bozos and mocking them. I made a whole series of really stupid errors, and took an unreasonably long time to recognize that fact.

It should be obvious that there's some way to go downwind faster than the wind, because as so many people pointed out, sailboats do it. It was frankly stupid of me to even argue about this - it's really pretty boneheadedly obvious. The question never should have been "can it be done?", but rather just "does this device do it?"

And the answer to that is "Yes". This thing does do it. It's not magic, it's not perpetual motion. In fact, it's really astonishingly simple, once you realize that the behavior of things moving through air is quite different from the simple rigid system that it appears to be equivalent to.

In this post, I'm going to try to do two things:

  1. Explain the faulty reasoning that led me to think it couldn't work, and why it's wrong.
  2. Explain why the thing really works.

In another post later this week, I'm going to try to explain why I think the mathematical element is so important. There's a ton of people who've got devices that really look convincing, and that have really convincing arguments for why they should work; only they don't, because they've missed something.

Continue Reading »

142 responses so far