Patrick (patrickwonders) wrote,
Patrick
patrickwonders

  • Mood:

Fractal representation of binary operations

A few weeks back, I was playing with fractal representations of binary operations. For the math-phobic, Don't panic yet. General binary operations are pretty simple. Suppose you have a collection of things. A binary operation on those things is just a way of taking two of those things, putting them together (in order), and getting another one of those things.

For example, subtraction is a binary operation on numbers. If you take two numbers (in order) and subtract them, you end up with a number.

For a non-number example, suppose there is a club with four members: Larry, Moe, Curly, and Shemp. Suppose that the last two people to arrive at the monthly meeting must each pay $5 to some member of the club where the recipient is totally laid out in the by-laws based on who the second-to-last and last arrival were. For example, the by-laws might say that if Larry arrives second-to-last and Moe arrives last, they must each pay $5 to Shemp. The by-laws may say that if Shemp arrives second-to-last and Curly arrives last, they each must pay $5 to Curly. (Curly drafted the by-laws and then railroaded them past the other members.) If the by-laws cover all possible cases and only ever pay a single member of the club, then the by-laws define a binary operation on the members of the club.

As I mentioned, I wanted to try to find some fractal representation for binary operations in the hopes that isomorphisms might be easy to pick out with the pattern-matcher in your skull. I haven't made it there yet. But, I have made some interesting pictures with vecto.

For a set with n-elements, there are n separate trees in the fractal. Each tree represents one element in the group. The order of the trees is arbitrary, but consistent throughout the fractal.

The zero-th iterant of a tree is just a trapezoid of a color for the tree. The k+1-th iterant is the k-th iterant overlayed with a scaled down copy of the k-th iterant on its upper half and n trees in the lower half. The first tree in the lower half is a scaled down version of (the tree which represents) this element multiplied by the first element (in our arbitrary order). The second tree in the lower half is a scaled down version of this element multiplied by the second element. And, so on, through the n-th tree in the lower half is a scaled down version of this element multiplied by the n-th element.

Here is Z/4Z:

Here is the Z/2Z x Z/2Z:

Here is the Z/3Z x Z/2Z:

There is, of course, much to be desired. The arbitrary ordering really throws a wrench into the works. The only way that I can think to represent these which doesn't have that sort of bias is to make an n-dimensional (single-color) fractal. Each element has its own cardinal direction in which to grow. But, I haven't tried any of those pictures yet.

And, to keep with tradition, I am including the source code here. Starting with the multiplication tables for these groups:

(defvar *mult-z4* #2A((0 1 2 3)
                      (1 2 3 0)
                      (2 3 0 1)
                      (3 0 1 2)))

(defvar *mult-v4* #2A((0 1 2 3)
                      (1 0 3 2)
                      (2 3 0 1)
                      (3 2 1 0)))

(defvar *mult-z3-z2* #2A((0 1 2 3 4 5)
                         (1 2 0 4 5 3)
                         (2 0 1 5 3 4)
                         (3 4 5 0 1 2)
                         (4 5 3 1 2 0)
                         (5 3 4 2 0 1)))

On to a simple function for converting from HSV to RGB:

(defun hsv-to-rgb (hue sat val)
    (let* ((fractional-bucket (/ hue 60))
           (bucket (floor fractional-bucket))
           (part   (- fractional-bucket bucket))
           (pp     (* val (- 1 sat)))
           (qq     (* val (- 1 (* part sat))))
           (tt     (* val (- 1 (* (- 1 part) sat)))))
        (case bucket
            (0 (list val tt  pp))
            (1 (list qq  val pp))
            (2 (list pp  val tt))
            (3 (list pp  qq  val))
            (4 (list tt  pp  val))
            (5 (list val pp  qq)))))

A simple function to perform the binary operation. For simplicity later in the code, I allow one operand or the other to be null. This affords me an identity function to bootstrap my trees.

(defun monoid-multiply (mult-table aa bb)
    (cond
        ((null aa) bb)
        ((null bb) aa)
        (t (aref mult-table aa bb))))

The functions to actually draw the fractals:

(defun draw-monoid-part (current mult-table colors xx yy width height)
    (let ((n-elements (array-dimension mult-table 0)))
        (let ((bw (ceiling (/ width n-elements)))
              (bh (if current (round (/ height 2)) height)))
            (when current
                (apply #'vecto:set-rgb-fill (aref colors current))
                (let ((aa (+ xx (round (* width 1/3))))
                      (bb (+ xx (round (* width 2/3))))
                      (yh (+ yy height)))
                    (vecto:move-to aa yh)
                    (vecto:line-to xx yy)
                    (vecto:line-to (+ xx width) yy)
                    (vecto:line-to bb yh))
                (vecto:close-subpath)
                (vecto:fill-and-stroke))
            (when (and (> bw 1) (> bh 1))
                (dotimes (ii n-elements)
                    (let* ((no (* ii bw))
                           (nx (+ xx no))
                           (ny yy)
                           (nw (min bw (- width no)))
                           (nh bh)
                           (nc (monoid-multiply mult-table current ii)))
                        (draw-monoid-part nc mult-table colors
                                          nx ny nw nh)))
                (draw-monoid-part current mult-table colors
                                  (+ xx (round (* width 1/8)))
                                  (+ yy (round (* bh 9/8)))
                                  (round (* width 3/4))
                                  (round (* bh 3/4)))))))

(defun draw-monoid (mult-table filename &key (width 512) (height 288))
    (let* ((n-elements (array-dimension mult-table 0))
           (colors (make-array n-elements)))
        (dotimes (ii n-elements)
            (let ((hue (/ (* (- n-elements ii 1) 180) (1- n-elements)))
                  (sat 3/4)
                  (val 1))
                (setf (aref colors ii) (hsv-to-rgb hue sat val))))
        (vecto:with-canvas (:width width :height height)
            (vecto:set-rgb-stroke 0 0 0)
            (draw-monoid-part nil mult-table colors 0 0 width height)
            (vecto:save-png filename))))

Drawing these specific operations:

(draw-monoid *mult-v4*    "v4.png"    :width 800 :height 280)
(draw-monoid *mult-z4*    "z4.png"    :width 800 :height 280)
(draw-monoid *mult-z3-z2* "z3-z2.png" :width 800 :height 280)
Tags: lisp, math
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

  • 1 comment