20140102

The Mandelbrot set in one line of APL

Is this line noise?
⍉' *'[⍎'1+0<|z',(∊150⍴⊂'←c+m×m'),'←c←(¯2.1J¯1.3+(((2.6÷b-1)×(¯1+⍳b))∘.+(0J1×(2.6÷b-1)×(¯1+⍳b←51))))']

NOTE: if you are not seeing several Greek looking letters and arrows in the line above, some UTF8 stuff got wrong. Sorry, I'll try to fix it, drop me a tweet!

Nope. This is not line noise, but a complete APL program to display the Mandelbrot set in glorious ASCII, with asterisks and spaces just like Brooks and Matelski did a long time ago while studying Kleinian groups (it's a short paper, read it someday). I'll explain in (a lot, I hope) detail this line in a few moments. So, what's APL first?



APL is literally A Programming Language. Funny, isn't it? Its origins can be traced back to a way to formalise algorithms created by Kenneth Iverson while at Harvard. It is famed as a very cryptic language, for a reason. Its fundamental functions are unicode chars, and at first it feels extremely weird.

I got interested in it after finding an iOS interpreter for J, a programming language developed as a successor to APL, also by K.I. It just got away without Unicode, leaving only cryptic dygraphs, like <.@o. (from a Wikipedia example of high precision computing.) J is very cool, in that it offers a terse syntax to operate with matrices and vectors, very much like Matlab (Octave in my case) or R. But I felt I'd rather check the first idea, before diving into the even weirder syntax of J. So, it was APL.

The first problem was finding a good APL interpreter. Most were paid (and extremely expensive) and I could only find 2 APL interpreters working in Mac OS. One is NGN APL an implementation focused on node.js Also usable on a browser, so it is cool. But I'd rather get a little closer to the system... And decided to use Gnu APL instead. Of course, using an emacs mode for gnu-apl. Caveat: make sure to add

export LC_ALL=es_ES.UTF-8
export LANG=es_ES.UTF-8


to your .zshrc or similar, without it you'll need to add a hook to gnu-apl mode reading

(set-buffer-process-coding-system 'utf-8 'utf-8)

to make sure emacs and apl talk in utf-8. Without it, there are no commands to send to the interpreter!

Since I'm also a heavy acme user, and acme is well-known in its unicode support, I used it instead to develop that line above. But emacs works correctly, I just like having things to tinker with acme.

Getting back to the line-noisiness of APL, first you need to know that precedence is right-to-left, so

3×3+1

in APL yields 12 instead of the expected 10. You can change this with parentheses. Now that I have taken this out, we can analyse the line above. Instead of explaining it from right to left, I'll explain how I proceeded to develop it.

Iterating the quadratic polynomial

(∊150⍴⊂'←c+m×m')

Put it succintly (I could explain a lot of the mathematics behind, but I just want to do a picture today) to draw the Mandelbrot set we need to find complex points c=x+iy (remember: you can think of a complex point as a point in a plane, like a screen: it has an x coordinate and a y coordinate) such that computing

f(z)=z^2+c

a lot of times with z=c is eventually a point outside a circle of radius 2. For instance, if c=1 this would be:
  1. f(1)=1^2+1=2
  2. f(f(1))=f(2)=2^2+1=5
  3. f(f(f(1)))=f(5)=25+1=26
And so on. In this particular case, after the first iterate we could stop. Remember that to do so, the product c·c is the product of complex numbers.

So the first part I wanted to get out of my way was generating this iteration. There are several ways to do it in APL, but a very cool way I found was to first generate the required computation like above. How?

'c+m×m'

computes exactly this, if m=c or if m is any other iterate, like m=f(f(f(c))). In APL speak, making m hold the same as c would be

m←c

and since right-to-left priority,

c+m×m←c

means "assign to m the value of c, multiply m by m (remember: it's the same as c) and add c." Likewise,

c+m×m←c+m×m←c

ends is computing the 2nd term in the list above, if c 1. So we have a pretty clear idea of how it should look like:

something←c+m×m←c+m×m←c+m×m←c+m×m←c+m×m←c+m×m←c+m×m←c

This is essentially "many times" the string " c+m×m" There's a very very easy way to repeat stuff in APL. For instance, 3 ⍴ 1 (read 3 reshape 1) creates a vector with three ones, 1 1 1. Reshape essentially multiplies or trims vectors. But... 3 ⍴ 'tomato' is 'tom'. The reshaping also cuts, of course! What we need is to make APL treat the string ' c+m×m' as one element. This is done with the next instruction in the Mandelbrot line, as you may guess: encapsulate.

⊂'←c+m×m'

ensures APL treats it as one element, so

20⍴⊂'←c+m×m'

generates a neat and long string of what the iterates should look like. To make sure the final string makes APL-sense, first we "enlist" with ∊. Turn the vector of repeated iterates into just one iterated element, like a long string all together. This could actually be removed, but it allowed me to learn a new function and I think it's pretty interesting. To end in a proper way, we add to the string a receiver variable 'z' and fuse the strings with comma.

I know this was long, but the iteration was the trickiest part!

Generating the grid of points

'←c←(¯2.1J¯1.3+(((2.6÷b-1)×(¯1+⍳b))∘.+(0J1×(2.6÷b-1)×(¯1+⍳b←51))))'

Since APL is cool with matrices (and complex numbers!) we can assign to the initial c a whole matrix of complex points (our screen pixels) and then we'll have all the stuff required for the picture.

This weird piece is just a compact way of generating a grid. To make it easier to understand, ⍳5 (that's iota 10) generates the sequence 1 2 3 4 5. To create a matrix we need two sequences (one for the x coordinates and another for the y coordinates.) For the complex numbers we can do 0J1 ⍳× 5 which yields 0J1 0J2 0J3 0J4 0J5. As you may guess, 0J1 is just the complex number i. For some weird reason APL uses the j letter instead of i. No big issue. Now we have the x's which go from 1 to 5 and the y's which go from i to 5i Now we need to find all the complex points in the plane. This means adding one of each x to each y, to get a grid. Similar to a multiplication table, but with sums instead of products. APL magic to the rescue!

(⍳5) .+ (0J1×(⍳5))

yields

1J1 1J2 1J3 1J4 1J5
2J1 2J2 2J3 2J4 2J5
3J1 3J2 3J3 3J4 3J5
4J1 4J2 4J3 4J4 4J5
5J1 5J2 5J3 5J4 5J5


which is pretty close to what we need. To plot the Mandelbrot set we are only interested (mostly, and in this particular instance) in points with real coordinate x between -2.1 and 0.5 and complex coordinate between -1.3 and 1.3 (just to make it square which is easier.) This long blurb just adds a matrix similar to the one above to a complex point, generating the grid of points we want, and assigns it to c. Almost done!

Computing and plotting

⍉' *'[⍎'1+0<|z',

After we have the set of points in c, we merge this string (with comma) to the iteration we developed above. At the far right of the iteration we find this piece
'1+0<|z',

As you may guess, this adds to the string 1+0<|z which from right to left does:

  1. Compute the norm (distance to the origin) of the final iterate, which was assigned to z at the end of the iteration with |
  2. Check if this is larger than 4. This generates a matrix of 1s and 0s
  3. Add 1 to all entries of this matrix (so we have a matrix full of 1s and 2s

NOTE: The first version of this code had 0<|z, which works well for rough images of the Mandelbrot set, since most iterates are eventually INFNAN, which is a funny number in programming, since it is positive, smaller than 0, different from itself... Almost anything :D

We have a neat string which can generate a matrix of 1s and 2s and represent the Mandelbrot set. How do we make this string compute something? Magic!

⍎ (known as execute) takes a string and computes it as an APL function. Magic! (just like eval in Lisp or Javascript, actually)

Represent it neatly

⍉' *'[stuff]

Since a matrix can be used to index a vector, we use this newly computed matrix as indexes (i.e. between square bracket) with the vector ' *' so we get almost a Mandelbrot set. But since I was slightly lazy when generating the grid of points, it is transposed. ⍉ (transpose) fixes it and finishes the program.

Conclusion

Writing this line of code took me quite a long time, mostly because I was getting used to APL and I didn't know my way around the language. Now that I'm done I'm quite impressed, and I'm looking forward to doing some more fun stuff with it. And if possible, some useful stuff.
Written by Ruben Berenguel

20131102

My Russian KL-1 Circular Slide Rule (and a small intro to slide rules)

A few months ago (woah, so long already!) I had an impulse buy: I purchased a circular slide rule from Etsy. It was cheap, and I had always wanted one, so... I just bought it (a neat addition to my Addiator.)

I guess if you are geeky enough to read mostlymaths.net, you know how a slide rule works. Although I knew how to use it, getting to grips with it took a little while. Just to make sure you follow along here's a brief explanation.

In a normal rule (as pictured below) you can measure a distance, add the distance to another one and get a new distance. 4 and 4 are 8, see?


A slide rule works exactly the same, but the scale on the rule is logarithmic. This means that if you measure the distance between 1 and 3, and add it to the point 3, you get 9 (which is 3 times 3.) This is because in a linear scale distance measures the difference (b-a) and in a logarithmic scale it measure ratios (b/a)

Usually you will do this using a piece labeled the same as the slide rule:


In a normal slide rule (the long wooden or aluminium thing) you have several scales, all placed together with an indicator to know where to measure. In the simplest setting a slide rule is basically what is shown above: a way to fix a distance and displace it along. You could do it with your fingers, even!

In a basic model of circular slide rule (like the KL-1) you have something that works much like this. See the picture below:


If you look carefully you'll see a marker (which is place just below a knob, and fixed in the glass cover) and a red marking needle (it's hard to see, but it's red.) In this picture you'll also see the logarithmic scale (below, from 1 to 9) and a square scale just on top (from 1 to 90.)

The black knob (on top of the fixed marker) displaces the scale, leaving the red marking needle wherever it is (it moves the paper where the scale is written!) and the red knob (the other one) moves just the needle, hovering above the paper.


If you set the black marker on 1 by moving the black knob and then the red marker on (for example) sqrt(2) (which is the number just below 2 in the square scale!) you are fixing the ratio 1-sqrt(2) (roughly 1-1.4)


If you now twist the black knob, you are moving the scale while the distance black-red remains perfectly fixed. So if you place the black marker above 2, you are "adding" the ratio of sqrt(2) and 2, which means 2 times sqrt(2) (roughly 2.8):


So, no mysteries in how this works! In the back there are a few trigonometric scales (known in the slide rule lingo as the S and T scales, for sin and tan):


For the sin and tan scales, you place the cursor (the red marker) in the degrees scale (the one from 10 to 90) and you read the sin of it on top. For the tan, you need to check the degrees in the spiraling scale in the center, and read the tan of the angle also on top.

What's it good for?

Such a small circular slide rule has a very low precision (2 digits more or less.) This essentially makes it pretty much useless for me, since I have more or less the same precision in mental division or multiplication. 

Anyway, I have used it several times when checking traffic numbers for websites, when estimating daily visits from monthly or bimonthly numbers. Once you set the number of days as ratio, it's pretty fast.

An interesting use would be for quick currency conversions while abroad (you fix the ratio and can easily convert from currencies) but since I travel mostly in Europe, I can't use it for this (Norway, Iceland, Great Britain and Denmark are good targets still.)

People still use slide rules though: nomographs (what the sin and tan scales are, actually) are a quick way to compute things, and are used in aviation, electric engineering and other fields where speed is interesting and 5 digit precision is not as important.
Written by Ruben Berenguel

20130919

A Slightly Better reddit Upvote/Downvote Widget (button)

A few days ago I found myself with a problem. I wanted a reddit button in one of our websites, and our technical guy wanted it to be asynchronous. After a little poking around and deciding that reddit doesn't offer asynchronous buttons, I rolled my poor man's version: wrap it in a $(document).ready() It's not asynchronous, but at least it won't block page loading.

Both happy, we deployed and I tested. Worked well, no problem. Well, actually, yes. A problem shared by all reddit buttons, one that was very troublesome here in mostlymaths (back when I had a share on reddit button just beside the post title.)

When setting up the button you select the target reddit you'd rather have your users send your content. In a page about Apple stuff, it would be r/apple. The problem is though that your users are free and can do whatever they want. So they go and submit to r/technology. Fine, r/technology is cool enough, lots of readers. Trouble is, when a user arrives from r/technology to your blog, after clicking on the link... He will see your widget with an ugly submit text, and no upvotes or downvotes:


even though your post has quite a few votes already in r/technology. The trouble comes from setting the target subreddit beforehand: if the url is not in this subreddit, reddit looks nowhere else. Of course, you'd rather have:


with the real counter. After all, this means making the experience completely seamless:
  1. Reddit user sees a cool link to your content in r/whatever. Clicks
  2. Lands on your page
  3. Upvotes (or downvotes)
instead of
  1. Reddit user sees a cool link to your content in r/whatever. Clicks
  2. Lands on the page
  3. Tries to upvote, needs to submit instead
  4. Is forced to submit to r/whatever, gives up (or not)
An easy way to solve this problem is to check the referring URL. If it matches a subreddit, we can set the target of our widget to that subreddit instead of the default one. All reddit readers happy!

There's another issue, though: users not arriving from reddit.

A random user landing in your awesome post, which has a bazillion points in r/whatever likes your content, and wants to upvote it. But, alas! He sees the dreaded submit button, because our default is r/apple. Or worse, sees 0 (or even a negative number!) because it has been downvoted in our target subreddit.

This can also be solved. Reddit offers a clear-cut json API, allowing jsonp callbacks. This means that we can write a small piece of javascript that will check whether our post has been submitted to another reddit AND change the target to that one! All reddit users happy!

Below you can find the code. Fork it, use it, whatever. Be happy. If something breaks or doesn't work as expected it's not my fault: use cases may vary.

Written by Ruben Berenguel