Fly Straight, Dammit!
Tags: j, numberphile, math
Published: 2019-09-13 18:05:58

---
title: Fly Straight, Dammit!
published: true
tags: J,Numberphile,Math
canonical_url: http://www.petecorey.com/blog/2019/08/12/fly-straight-dammit/
---

[Numberphile](https://www.numberphile.com/) recently posted a video about [an interesting recursive function](https://www.youtube.com/watch?v=pAMgUB51XZA) called “Fly Straight, Dammit!” which, when plotted, initially seems chaotic, but after six hundred thirty eight iterations, instantly stabilizes.

This sounds like a perfect opportunity to flex our J muscles and plot this function ourselves!

## An Imperative Solution

The simplest approach to plotting our “Fly Straight, Dammit!” graph using [the J programming language](https://www.jsoftware.com/#/) is to approach things imperatively:

```
a =: monad define
  if. y < 2 do.
    1
  else.
    py =. a y - 1
    gcd =. y +. py
    if. 1 = gcd do.
      1 + y + py
    else.
      py % gcd
    end.
  end.
)
```

We’ve defined our `a` monadic verb to return `1` if we pass in a “base case” value of `0` or `1`. Otherwise, we recursively execute `a` on `y - 1` to get our `py`, or “previous `y`”. Next, we check if the `gcd` of `y` and `py` equals `1`. If it does, we return `1 + y + py`. Otherwise, we return `py` divided by `gcd`.

This kind of solution shouldn’t look too foreign to anyone.

Let’s plot values of `a` to verify our solution:

```
require 'plot'
'type dot' plot a"0 i. 1000
```

 ![](http://www.petecorey.com/img/2019-08-12-fly-straight-dammit/plot.png)

This works, but it’s very slow. We know that our recursive calls are doing a lot of duplicated work. If we could memoize the results of our calls to `a`, we could save quite a bit of time. Thankfully, memoizing a verb in J is as simple as adding `M.` to the verb’s declaration:

```
a =: monad define M.
  ...
)
```

Now our imperative solution is much faster.

## Using Forks and Hooks

While our initial solution works and is fast, it’s not taking advantage of what makes J a unique and interesting language. Let’s try to change that.

The meat of our solution is computing values in two cases. In the case when `y` and `py` have a greatest common divisor equal to `1`, we’re computing `1` plus `y` plus `py`. Our imperative, right to left implementation of this computation looks like this:

```
1 + y + py
```

We could also write this as a [“monadic noun fork”](https://www.jsoftware.com/help/jforc/forks_hooks_and_compound_adv.htm) that basically reads as “`1` plus the result of `x` plus `y`:

```
a_a =: 1 + +
```

Similarly, when we encounter the case where the greatest common divisor between `y` and `py` is greater than `1`, we want to compute `py` divided by that `gcd`. This can be written as a [“dyadic fork”](https://www.jsoftware.com/help/jforc/forks_hooks_and_compound_adv.htm):

```
a_b =: [ % +.
```

We can read this fork as “`x` divided by the greatest common divisor of `x` and `y`.”

Now that we’ve written our two computations as tacit verbs, we can use the [“agenda” verb](https://www.jsoftware.com/help/dictionary/d621.htm) (`@.`) to decide which one to use based on the current situation:

```
a_a =: 1 + +
a_b =: [ % +.

a =: monad define M.
  if. y < 2 do.
    1
  else.
    py =. a y - 1
    has_gcd =. 1 = y +. py
    py (a_b ` a_a @. has_gcd) y
  end.
)
```

If `has_gcd` is `0`, or “false”, we’ll return the result of `py a_b y`. Otherwise, if `has_gcd` is `1`, we’ll return the result of `py a_a y`.

## More Agenda

We can elaborate on the idea of [using agenda to conditionally pick the verb](https://www.jsoftware.com/help/learning/10.htm) we want to apply to help simplify out base case check.

<form action="//east5th.us11.list-manage.com/subscribe/post?u=f8833fd40e2b1b28545d9f382&amp;id=c56ceba687" method="post" id="mc-embedded-subscribe-form" name="mc-embedded-subscribe-form" target="_blank">
            <p>I find myself producing lots of ranging content from books and articles, like the one you're reading now, to open source software projects. If you like what I'm doing, <strong>nothing shows your support more than signing up for <a href="#newsletter">my mailing list</a></strong>.</p>
            <div>
<input placeholder="Email address" type="email" value="" name="EMAIL" id="mce-EMAIL"><!--
                                                                                                                                                                                                    --><input type="submit" value="Sign me up!" name="subscribe" id="mc-embedded-subscribe">
            </div>
            <div style="position: absolute; left: -5000px;"><input type="text" name="b_f8833fd40e2b1b28545d9f382_c56ceba687" tabindex="-1" value=""></div>
        </form>

First, let’s define our base case and recursive case as verbs that we can combine into a gerund. Our base case is simple. We just want to return `1`:

```
base_case =: 1:
```

Our recursive case is just the (memoized) `else` block from our previous example:

```
recursive_case =: monad define M.
  py =. a y - 1
  has_gcd =. 1 = y +. py
  py (a_b ` a_a @. has_gcd) y
)
```

Our function, `a` wants to conditionally apply either `base_case` or `recursive_case`, depending on whether `y` is greater or less than one. We can write that using agenda like so:

```
a =: base_case ` recursive_case @. (1&<)
```

And because our `base_case` verb is so simple, we can just inline it to clean things up:

```
a_a =: 1 + +
a_b =: [ % +.

recursive_case =: monad define M.
  py =. a y - 1
  has_gcd =. 1 = y +. py
  py (a_b ` a_a @. has_gcd) y
)

a =: 1: ` recursive_case @. (1&<)
```

Using agenda to build conditionals and pseudo-“case statements” can be a powerful tool for incorporating conditionals into J programs.

## Going Further

It’s conceivable that you might want to implement a tacit version of our `recursive_case`. Unfortunately, my J-fu isn’t strong enough to tackle that and come up with a sane solution.

That said, Raul Miller came up with a one-line solution (on his phone) and [posted it on Twitter](https://twitter.com/raudelmil/status/1159575084757135361). Raul’s J-fu is strong.

 ![](http://www.petecorey.com/img/2019-08-12-fly-straight-dammit/tweet.png)