EOP Exercise Round-Up: Chapter 2

This entry is part of a series, Elements of Programming»

A big thanks to Mark Ruzon and Piotr Jachowcz who submitted homework [and a thanks to Dave for painstakingly formatting the math without LaTeX -- Sean]. Chapter 2 gave us a detailed look at the structures obtained from just a single unary operation.

With a few exceptions—Mark Ruzon concentrated on the exercises and Piotr Jachowicz focused on proving lemmas. With that, let’s get started:

Lemmas

We’ll start with an exception: Mark proved this one.

Lemma 2.1: euclidean_norm(x,y,z) = euclidean_norm(euclidean_norm(x,y),z)

euclidean_norm(x,y,z) = sqrt(x²+y²+z²) = sqrt(sqrt(x²+y²)²+z²) = sqrt(euclidean_norm(x,y)²+z²) = euclidean_norm(euclidean_norm(x,y),z).

To prove the rest, Piotr introduced “lemma 2.pj”:

Lemma 2.pj: f^a( f^b(x) ) = f^a+b(x)

We’ll prove it by recursion with respect to a.

f⁰( f^b(x) ) = f^b(x) (by definition)

Let us assume that f^a( f^b(x) ) = f^a+b(x). Then we have
f^a+1( f^b(x))
= f( f^a( f^b(x) ) )
= f( f^a+b(x) )
= f^a+b+1(x).

Recursion concludes the proof.

Lemma 2.2: An orbit does not contain both cyclic and a terminal element.

Let us assume that it contains both cyclic and terminal element. Let

x_c = f^c(x)

and

x_t = f^t(x)

be the cyclic and terminal elements, respectively.

The case t < c is impossible because x_t is terminal, which implies t is the maximim index for which we can calculate f^t(x). Therefore t >= c.

If x_c is a cyclic element, then there exists N > 0 such that

f^c+N = f^c(x) = x_c.

Let k = t – c + 1. Then

c + kN = c + (t-c)N + N > c + (t-c) = t,

and

f^c+kN(x) = f^c(x) = x_c.

which shows that x_t is not terminating. QED

Lemma 2.3: An orbit contains at most one terminal element.

Let x_t₁ = f^t₁(x) and x_t₂ = f^t₂(x) be two terminating elements.

If t₁ > t₂ then x_t₁ is not terminating because

x_t₂
= f^t₂(x)
= f^{t₁ + (t₂ – t₁)}(x)
= f^{t₂ – t₁}( f^t₁(x) ) (by Lemma 2.pj).

which shows that x_t₁ is not terminating.

Similarly, it is false that t₁ < t₂. Therefore t₁ = t₂ that proves that there is only one terminating element. QED

Lemma 2.5: The distance fron any point in the orbit to a point in a cycle of that orbit is always defined.

Let x_a = f^a(x) belong to the orbit and x_b = f^b(x) belong to the cycle.

If a <= b then f^b-a( f^a(x) ) = f^b(x) = x_b.

If b < a and cycle size is c, then

b + c(a – b + 1) >= b + (a – b + 1) > a,

and

x_b = f^b(x) = f^{b + c(a – b + 1)}(x).

and

b + c(a – b + 1) > a

so by Lemma 2.pj,

f^{b + c(a – b. + 1) – a}( f^a(x) ) = f^b(x) = x_b

which proves x_b is reachable from x_a. QED

Lemma 2.6: If x and y are distinct points in a cycle of size c, c = distance(x, y, f) + distance(y, x, f)

Let distance(x, y, f) = n. Then,

fⁿ(x) = y

f^c-n( fⁿ(x) ) = f^c(x) = x.

From the other side, f^c-n( fⁿ(x) ) = f^c-n(y).

It sufficies to prove that there is no m < c – n such that f^m(y) = x.

Let us assume that such m exists. Then

x = f^m(y) = f^m( fⁿ(x) ) = f^m+n(x).

But cycle size is c, so c <= m + n. We have m < c – n ∧ c <= m + n that implies m < c – n ∧ m >= c – n, which is impossible. That proves that distance(y, x, f) = c – n. QED

Lemma 2. 7 If x and y are points in a cycle of size c, then 0 <= dist(x, y, f) < c

Because y belongs to a cycle, then due to Lemma 2.5, distance(x, y, f) is defined

If x = y then distance(x, y, f) = 0 which satisfies thesis

If x != y, then due to Lemma 2.6, distance(x, y, f) = c – distance(y, x, f). Because distance(y, x, f) > 0, then distance(x, y, f) < c. QED

Exercises

Exercise 2.1: Implement a definition-space predicate for addition on 32-bit signed integers.

bool is_defined(std::plus<int32>, int32 x, int32 y)
  {
     return x >= 0 ? std::numeric_limits<int32>::max() - x >= y :
                     std::numeric_limits<int32>::min() - x <= y;
  }
This function can be templatized for any integral type. Only the max() comparision is necessary for unsigned types. Because of the strange behavior of numeric_limits<T>::min when T is a floating type, a different implementation would be needed for that case.

Exercise 2.2: Design an algorithm that determines, given a transformation and its definition-space predicate, whether the orbits of two elements intersect.

template <typename F, typename P>
     requires(Transformation(F) && UnaryPredicate(P) && Domain(F)==Domain(P))
  bool orbits_intersect(const Domain(F)& x0, const Domain(F)& x1, F f, P p)
  {
     // Precondition: p(x) iff f(x) is defined
     Domain(F) y0 = collision_point(x0, f, p);
     Domain(F) y1 = collision_point(x1, f, p);
     if (y0 == y1)
       return true;
     if (!p(y0) || !p(y1)) // At least one orbit terminates
       return false;
     Domain(F) z = f(y0);
     while (z != y0 && z != y1)
       z = f(z);
     return z == y1; // if z == y0 && z != y1, the cycles are disjoint
  }

Exercise 2.3: For convergent_point to work, it must be called with elements whose distances to the convergent point are equal. Implement an algorithm convergent_point_guarded for use when that is not known to be the case, but there is an element in common to the orbits of both.

template <typename F>
     requires(Transformation(F))
  pair <Domain(F),Domain(F)> convergent_point_guarded(Domain(F) x0,
     Domain(F) x1, Domain(F) g, F f)
  {
     // Precondition: there exist m,n s.t. f^m(x0) == g && f^n(x1) == g
     bool found_x0 = false;
     bool found_x1 = false;
     while (x0 != x1 && !(found_x0 && found_x1)) {
       x0 = f(x0);
       x1 = f(x1);
       if (x0 == g)
         found_x0 = true;
       if (x1 == g)
         found_x1 = true;
     }
     // Postcondition: x0 == x1 or the loop executed max(m,n) times
     return pair<Domain(F),Domain(F)>(x0, x1);
  }

Exercise 2.4: Derive formulas for the count of different operations (f, p, equality) for the algorithms in this chapter.

But Mark wrote:

Compute AVERAGE count of operations in Ch. 2 algorithms (if I’m off anywhere the errors will cascade)

abs: <: 1, Unary -: 0.5

euclidean_norm (binary): *: 2, +: 1, sqrt: 1

euclidean_norm (ternary): *: 3, +: 2, sqrt: 1

power_unary: !=: n+1, -: n, f: n

distance: !=: n+1, f: n, +: n

collision_point:

terminating orbit: !=: n, f: 3n-0.5, !p: 2n-0.5

non-terminating orbit: !=: n+1, f: 3n+1, !p: 2n+1

terminating:

terminating orbit: !=: n, f: 3n-0.5 !p: 2n-0.5, p: 1

non-terminating orbit: !=: n+1, f: 3n+1, !p: 2n+2

collision_point_nonterminating_orbit: !=: n+1, f: 3n+1

circular_nonterminating_orbit: !=: n+1, ==: 1, f: 3n+2

circular:

terminating orbit: !=: n, f: 3n-0.5, !p: 2n-0.5, p: 1

non-terminating orbit: !=: n+1, ==: 1, f: 3n+0.5, !p: 2n-0.5, p: 1

For the rest, n is the convergent distance and h and c are as in the text.

convergent_point: !=: n+1, f: 2n

connection_point_nonterminating_orbit: !=: n+h+2, f: 3n+2h+2

connection_point:

terminating orbit: !=: n, f: 3n-0.5, !p: 2n+0.5

non-terminating orbit: !=: n+h+2 f: 3n+2h+0.5, !p: 2n+0.5

orbit_structure_nonterminating_orbit: !=: n+2h+c f: 3n+3h+c+1 +: h+c-2

orbit_structure:

terminating orbit: !=: n+h f: 3n+h-0.5, !p: 2n+0.5

non-terminating orbit: !=: n+h+c, f: 3n+h+c-0.5, !p: 2n+1.5

Exercise 2.5: Use orbit_structure_nonterminating_orbit to determine the average handle size and cycle size of the pseudorandom number generators on your platform for various seeds.

Microsoft/Vista/VS2008: Handle: 109, Cycle: 115 (1000 seeds)

Linux/gcc 4.1.2: Handle: 32033, Cycle: 21573 (20 seeds)

Linear Congruential Method (TAOCP): Handle: 552,493,925 Cycle: 421,412,441 (30 seeds)

Exercise 2.6: Rewrite all the algorithms in this chapter in terms of actions.

// Exercise 2.6: Rewrite all transformation algorithms in terms of actions
   
  template <typename A, // A models Action
            typename N> // N models Integer
  typename void power_unary(typename A::domain_type& x, N n, A a)
  {
    // Precondition: n >=0 and for all 0<i<=n, a^i(x) is defined
    while (n != N(0)) {
      n = n - N(1);
      a(x);
    }
  }
   
  template <typename A> // A models Action
  typename A::distance_type distance(typename A::domain_type x, typename A::domain_type y, A a)
  {
    // Precondition: y is reachable from x under a
    typedef typename A::distance_type N;
    N n(0);
    while (x != y) {
      a(x);
      n = n + N(1);
    }
    return n;
  }
   
  template <typename A, // A models Action
            typename P> // P models UnaryPredicate with P::domain_type == A::domain_type
  typename A::domain_type collision_point(const typename A::domain_type& x, A a, P p)
  {
    // Precondition: p(x) iff a(x) is defined
    if (!p(x)) return;
    typename A::domain_type slow = x;
    typename A::domain_type fast = x;
    a(fast);
   
    while (fast != slow) {
      a(slow);
      if (!p(fast)) return fast;
      a(fast);
      if (!p(fast)) return fast;
      a(fast);
    }
    return fast;
  }
   
  template <typename A, // A models Action
            typename P> // P models UnaryPredicate with P::domain_type == A::domain_type
  bool terminating(const typename A::domain_type& x, A a, P p)
  {
    // Precondition: p(x) iff a(x) is defined
    return !p(collision_point(x, a, p));
  }
   
  template <typename A> // A models Action
  typename A::domain_type collision_point_nonterminating_orbit(const typename A::domain_type& x, A a)
  {
    typename A::domain_type slow = x;
    typename A::domain_type fast = x;
    a(fast);
   
    while (fast != slow) {
      a(slow);
      a(fast);
      a(fast);
    }
    return fast;
  }
   
  template <typename A> // A models Action
  bool circular_nonterminating_orbit(const typename A::domain_type& x, A a)
  {
    typename A::domain_type y = collision_point_nonterminating_orbit(x, a);
    a(y);
    return x == y;
  }
   
  template <typename A, // A models Action
            typename P> // P models UnaryPredicate with P::domain_type == A::domain_type
  bool circular(const typename A::domain_type& x, A a, P p)
  {
    // Precondition: p(x) iff a(x) is defined
    typename A::domain_type y = collision_point(x, a, p);
    if (!p(y))
      return false;
    a(y);
    return x == y; 
  }
   
  template <typename A> // A models Action
  typename A::domain_type convergent_point(typename A::domain_type x0, typename A::domain_type x1, A a)
  {
    while (x0 != x1) {
      a(x0);
      a(x1);
    }
    return x0;
  }
   
  template <typename A> // A models Action
  typename A::domain_type connection_point_nonterminating_orbit(const typename A::domain_type& x, A a)
  {
    typename A::domain_type y = collision_point_nonterminating_orbit(x, a);
    a(y);
    return convergent_point(x, y, a);
  }
   
  template <typename A, // A models Action
            typename P> // P models UnaryPredicate with P::domain_type == A::domain_type
  typename A::domain_type connection_point(const typename A::domain_type& x, A a, P p)
  {
    // precondition: p(x) iff a(x) is defined
    typename A::domain_type y = collision_point(x, a, p);
    if (!p(y))
      return y;
    a(y);
    return convergent_point(x, y, a);
  }
   
  template <typename A> // A models Action
  triple<typename A::distance_type, typename A::distance_type, typename A::domain_type>
  orbit_structure_nonterminating_orbit(const typename A::domain_type& x, A a)
  {
    typedef typename A::distance_type N;
    typedef typename A::domain_type D;
    D y = connection_point_nonterminating_orbit(x, a);
    D z = y;
    a(z);
    return triple<N, N, D>(distance(x, y, a), distance(z, y, a), y);
  }
   
  template <typename A, // A models Action
            typename P> // P models UnaryPredicate with P::domain_type == A::domain_type
  triple<typename A::distance_type, typename A::distance_type, typename A::domain_type>
  orbit_structure_nonterminating_orbit(const typename A::domain_type& x, A a)
  {
    // precondition: p(x) iff a(x) is defined
    typedef typename A::distance_type N;
    typedef typename A::domain_type D;
    D y = connection_point(x, a, p);
    N m = distance(x, y, f);
    N n(0);
    if (p(y)) {
      D z = y;
      a(z);
      n = distance(z, y, a);
    }
    return triple<N, N, D>(m, n, y);
  }

Entries in this series:

Posted Wednesday, March 31st, 2010 under EoP Study Group, Exercises.

Phuc Nguyen says:

November 18, 2010 at 12:16 am

I don’t understand 2.3 here. Isn’t it a little pointless? You have convergent_point(x0, x1, g, f), where g is the convergent point. In the end, what you return is (g, g), right? So what’s the point of doing this?

Quote

Paul McJones says:

November 19, 2010 at 7:58 pm

Good point. Here’s the solution we provide in the code accompanying Elements of Programming (http://www.elementsofprogramming.com/code/eop.h):

// Exercise 2.3:

template
    requires(Transformation(F))
Domain(F) convergent_point_guarded(Domain(F) x0,
                                   Domain(F) x1,
                                   Domain(F) y, F f)
{
    // Precondition: $\func{reachable}(x0, y, f) \wedge \func{reachable}(x1, y, f)$
    typedef DistanceType(F) N;
    N d0 = distance(x0, y, f);
    N d1 = distance(x1, y, f);
    if      (d0 < d1) x1 = power_unary(x1, d1 - d0, f);
    else if (d1 < d0) x0 = power_unary(x0, d0 - d1, f);
    return convergent_point(x0, x1, f);
}

Petar Marendic says:

July 6, 2010 at 9:09 am

Regarding exercise 2.5, and the test done with Microsoft/Vista/VS2008…

I’ve noticed that using the random function simulator of the form: int random(int x) { srand(x); return rand(); }

results with very short orbit sizes, as is evident from the solution posted above, so I decided to use the following functor that does away with continuous reseeding:

struct Slucajan { Slucajan() { srand(unsigned(time(NULL)));} Slucajan(unsigned x) { srand(x);} unsigned operator ()(unsigned x) { return rand(); } };

Compiling this on VS2008 produced an average orbit size of ~64000 for 1000 seeds.

Sean Parent says:

July 6, 2010 at 1:13 pm

Continually reseeding doesn’t give you an accurate analysis of the quality of the random number generator – it simply provides a source of cycles for the exercise. To properly analyze the random number generate you need to be looking for cycles in the internal state of the generator – and that requires sources to your random number generator. The problem with your solution is that it isn’t guaranteed to give you strict cycles – you might get a sequence like “1, 3, 5, 3, 27, 3, 48″. The function is no longer regular – and so the “orbit size” you are measuring is something else entirely.

Sean ParentQuote
- Petar Marendic says:
  
  July 6, 2010 at 6:08 pm
  
  Yeah, you’re absolutely right. Thanks for pointing it out.
  
  Petar MarendicQuote

Jason McCarrell says:

May 7, 2010 at 7:44 pm

Just a general comment. Someone should really add a favicon to this website, so I can take the label off it in my bookmark bar. That is all.

Mark Ruzon says:

April 13, 2010 at 6:58 pm

Hmm. I proved all the lemmas, too. I must have missed that page when transcribing. But why am I the only person doing the exercises?

Dave Abrahams says:

April 10, 2010 at 2:41 pm

…thanks to Dave for painstakingly formatting the math without LaTeX — Sean

And since this was such a pain, I found and installed this plugin, which enables LaTeX math mode support (see the plugin’s FAQ for information on how to use it.

I would appreciate it if you’d try to use it when submitting answers to the homework or chapter write-ups. It will save a huge number of headaches.

Thanks!

C++Next