Re: Typo in http://arxiv.org/.../0402051.pdf?

From: Vadim Tropashko <vadimtro_at_yho.cm>
Date: Tue, 22 Jun 2004 16:21:37 -0700
Message-ID: <40D8BF01.7010908_at_yho.cm>


Jim Kraai wrote:
>Vadim Tropashko said:
>
>>Jim,
>>
>>I edited my reply to make it more readable, and posted it to
>>comp.databases.theory.
>>
>>
>
>I have read access to c.l.d, but not write at the moment.
>
>
>Here's what I'm hearing--hopefully I'm stating this correctly. and have
>my particulars straight.
>
>Stating the insignificant flaw a little more formally, given a function,
>path2moebius(path) -> rational number via moebius encoding,
>path2moebius(a_0,a_1,...a_m,1) = path2moebius(a_0,a_1,...a_m+1)
>
>for example,
>path2moebius(5,4,2,1) => Matrix[[68,13],[47,9]] => 68/13
>path2moebius(5,4,3) => Matrix[[68,13],[21,4]] => 68/13
>
>So, storing just the resulting rational isn't sufficient, but storing
>either of the following would:
>1. A boolean indicating the depth modulo 2 or
>2. The rational for the parent node

Excellent summary so far.

>Here are the tradeoffs I see:
>1. If we choose to store the boolean,
>
>1.1 To calculate an n'th child's rational, we must first calculate the
>parent's rational (left interval value), a (depth-1) calculation via
>extended euclid, then given the calculated parent rational, calculate
>the n'th child's rational value.
>
>1.2. To calculate a node's interval, we again need to calculate the
>full path via extended euclid because the right-end of the interval is
>determined by the node's rational value and the node's parent's rational
>value.

I don't give much thought to "rational+boolean" coding. Perhaps it's not elegant enough?

Interestingly, in Farey encoding I somehow avoided this problem. Semiopen intervals, however, were changing orientation at each level: from [a,b) at level n to (c,d] on level n+1. This is, I guess, just a manifestation of alternating determinant sign.

>2. If we choose to store the parent's rational,
>
>2.1. An n'th child's rational, given what's stored for the parent
>[[a,b],[c,d]], is calculable directly by [[a*n+b,c*n+d],[a,c]].
>
>2.2. A node's interval is also calculable directly as given previously
>by Tropashko as [a/b,(a+c)/(b+d)] (note interval notation, rather than
>matrix notation).
>
>From an implementation standpoint, coding the wall, while
>straightforward at first glance, appears to be much more effort than
>coding the moebius encoding.

No, the wall is just for visualization. All algorithms traverse a small part of it really.

>All other calculations appear to remain essentially the same, including
>a node's materialized path, depth, finding the next available child
>node interval, etc.
>
>
>Let's look at the calculation cost for using the wall approach vs. the
>moebius encoding approach to calculate a rational from a path for path
>length n,
>
>Calculating via 'the wall' takes 3*(n(n-1))/2 simple calculations,
>therefore is O(n**2). Additionally, we are required to store
>3*((n-1)((n-1)-1))/2 intermediate integer results which are later
>discarded.

One's again, wall is cool theoretical abstraction, but in all practical algorithms we take shortcuts. For example, in order to calculate materialized path from matrix/moebius encoding we just descend horizontally while filling in the 2 top rows with numbers

7187 0547 0076 0015 0001
0473 0036 0005 0001 0000
---- applying pty#2 --->

(together with the path numbers in the diagonal, of course).

We stop when we hit 0 in the second row.

>Calculating via moebius encoding takes 3*(n-1) simple calculations,
>therefore is O(n). Additionally, only requires that we store 4
>intermediate integer results which ultimately become the sought result.
Received on Wed Jun 23 2004 - 01:21:37 CEST

Original text of this message