Trigonometry Problem without Trigonometry: Clarification/Correction

In the previous post I was exulting about the coolness of solving a trigonometry problem without trigonometry, using complex numbers. Well, that isn’t quite the full truth. You can certainly do the problem described easily and elegantly with a complex number capable calculator. However, there is some hidden trigonometry in the initial rotation operation:

The complex number ei has to be raised to a power. If you raise to an integer power, you could simply multiply out the rectangular values algebraically. But how do you raise a complex number to a fractional power, like 2.5? The standard approach, near as I can tell, is to convert the complex number to polar format, with a magnitude r and an angle ϕ. Assuming complex number a+bi, pulling out the magnitude requires only the sqrt function (pythagorean theorem) but pulling out the angle requires the arctangent of b/a. Then, use the formula Zn = rn (cos nϕ + i sin nϕ). I really don’t know if this is how all calculators do it, but here is the code behind the operations in the racket interpreter:

  Scheme_Complex *cb = (Scheme_Complex *)base;
  Scheme_Complex *ce = (Scheme_Complex *)exponent;
  double a, b, c, d, bm, ba, nm, na, r1, r2;
  int d_is_zero;

  if ((ce->i == zero) && !SCHEME_FLOATP(ce->r)) {
    if (SCHEME_INTP(ce->r) || SCHEME_BIGNUMP(ce->r))
      return scheme_generic_integer_power(base, ce->r);
  }

  a = scheme_get_val_as_double(cb->r);
  b = scheme_get_val_as_double(cb->i);
  c = scheme_get_val_as_double(ce->r);
  d = scheme_get_val_as_double(ce->i);
  d_is_zero = (ce->i == zero);

  bm = sqrt(a * a + b * b);
  ba = atan2(b, a);

  /* New mag & angle */
  nm = scheme_double_expt(bm, c) * exp(-(ba * d));
  if (d_is_zero) /* precision here can avoid NaNs */
    na = ba * c;
  else
    na = log(bm) * d + ba * c;

  r1 = nm * cos(na);
  r2 = nm * sin(na);

The code there is just slightly more complicated, as it has separate angle finding conditional branches for real number and complex number exponents.

Of course, you don’t need to deal with any of that if you are just manipulating complex numbers in the interpreter or calculator.

I feel this would be a great place to dive into the interesting subject of complex roots, but that I should hold off until I have a more thorough grasp of the subject.

Advertisements

Trigonometry Problem without Trigonometry

Here is a classic trigonometry problem:

With the satellite dish pointed up 13 degrees above the ground, how far up will the Line of Sight (LOS) be after passing over 100 meters of ground? (To save a few sentences in our post, we will ignore the fact that the satellite dish will usually start a few meters above the ground.)

This is simple using any calculator with the trigonometry function tangent:

tan(ϕ) = opp/adj, so height = 100 * tan 13° (after 13° is converted to radians).

If you didn’t want to use a trigonometric function, however, what could you do? Another approach is complex numbers, and it is pretty simple. You simply need to rotate ϕ degrees up the unit circle (a basic operation with complex numbers), get the real and imaginary parts of that complex number, and use that proportion to figure out the opposite side of your problem triangle.

So, after raising e^i by 13 degrees (converted to radians) multiply 100 x (imag Z / real Z). In programming code, it looks like this:

#lang racket

(define tau (* 2 pi))

(define rfact (/ tau 360))

(define (rise gnd deg)
  (let* ([rad (* deg rfact)]
         [Z (exp (* 0+1i rad))])
    (/ (* gnd (imag-part Z)) (real-part Z))))

> (rise 100 13)
23.08681911255631

It gives geometrically sane results also if you use negative degrees or negative distances:

> (rise 100 -13)
-23.08681911255631
> (rise -100 -13)
23.08681911255631
> (rise -100 13)
-23.08681911255631

What if you don’t have or want to use the exp function (to raise e to some value). You instead start with an approximation of e^i, which happens to be

0.5403023058681398+0.8414709848078965i

and then just raise that to ϕ.

Now, why would you want to use the complex number approach rather than the trig function? Well, to be honest I couldn’t think of a really compelling reason off the top of my head. An easy one would be if you were already using complex numbers for other reasons. Another would be if you wanted to use purely algebraic operations in your programming, say, on a computer board that did not have trigonometric functions built in. I suspect that the complex number approach is ultimately simpler and more efficient on the computational level, but since trigonometric functions are usually approximated with tables and with an algebraic exponential function, I couldn’t really say for sure off the top of my head.

In any case, it seems cool that complex numbers allow you to do an angle and distance trigonometry problem without trigonometry.

Harmongrams on Arduino Via Serial Commands

Previously I was experimenting with trying to write advanced programs in uLisp, embedded on an Arduino with a TFT display/touchscreen. Ultimately this proves not the best approach due to limitations in the memory and also the uLisp interpreter. A different approach is to keep the uLisp interpreter on the Arduino, but limit the on-board programming to a set of core interface commands, e.g., (drawline) and (fillscr). Then have the desktop computer or server sending uLisp commands over the serial connection. Of course, the uLisp commands can be constructed in Racket Scheme, allowing the power of the Racket syntax and libraries, and the great CPU and memory access, in controlling the arduino. I.e., remote control by the Mother Brain.

The demo I’ve programmed here is drawing the harmonograms slow enough to watch, so as to simulate the harmonograph experience. I do not have a camera setup suitable to show this in live video, but here are some snapshots:

The Racket code for the demo is available here:

ftp://lavender.qlfiles.net/Racket/arduino-harmon-demo.7z (md5sum 7e2bc9bc2ea25d048577b28c95c4fca5)

The project to adapt uLisp with TFT control primitives is here:

http://savannah.nongnu.org/projects/ulisp-tft

Though control over serial cables is doable for some applications, the longer-term goal would be to have them transmitted over Wi-Fi.

Complex Numbers in Emacs Calc Tutorial Video (Part I)

After learning the basics of how to use complex numbers, I find myself suddenly more interested in buttons on scientific calculators, and the built-in functions of calculator and programming software. Something which I thought might be of interest to my small (but distinguished!) audience would be a tutorial on using complex numbers in the Gnu/Emacs Calc program.

Please forgive the quiet audio — you’ll need to turn up the volume a lot. I’m dealing with a not-ideal microphone set-up at the moment, but I hope to have access to a better microphone set-up next week.

I have been advised by well-meaning relatives that, by continuing to upload boring tutorials and technical articles, it is likely that my readership will never expand beyond two dozen people. There is hope, they say, if I were instead to upload cute bunny rabbit photos. Consequently, I am going to start the practice of randomly attaching bunny photos taken from my mother’s Web site about rabbit farming.

I am hoping that, since we are related, my Mom will overlook this blatant act of copyright violation. This image is reproduced for scholarship purposes only under the “fair use” doctrine.

Lossless Compression

A subject I’ve recently taken some interest in is data compression. As far as compression algorithms themselves, you’ll learn nothing in this post that you can’t find out in a few minutes on Wikipedia. Nevertheless, I think there are two things worth pointing out, which are perhaps not known to even many I.T. professionals:

  1. There is no lossless compression algorithm which is optimal for all types of data.
  2. With Free Software programs at least, you have considerable freedom in choosing your compression algorithm and related parameters.

For those not in the know, lossless compression is compression that allows you to compress without losing any information. In contrast, the lossy compression algorithm used in JPEG basically discards some of the image data, sacrificing some fine resolution in such a way that hopefully you won’t notice the difference. PNG compression, on the other hand, is lossless, allowing you to view the image exactly the way you got it originally.

Point (1) above is true because of the mathematical Pidgeon Hole principle. Applied to compression algorithms, this basically means that any algorithm that is good at compressing one type of data, will be bad at compressing at least one other type of data.

Regarding point (2): On a Gnu/Linux system, it is likely that without even having to install anything, you will have at least three compression tools installed: gzip, bzip2, and 7z.

My version of gzip uses LZ77 (Lempel-Ziv) coding.

LZ77 algorithms achieve compression by replacing repeated occurrences of data with references to a single copy of that data existing earlier in the uncompressed data stream.

https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ7
christopher@nightshade:~/Scratch$ gzip --version | head -n1
gzip 1.6

This is a simple idea that works decently applied to some text data:

christopher@nightshade:~/Scratch$ wget https://www.gnu.org/licenses/gpl-3.0.txt
--2019-03-07 16:34:50-- https://www.gnu.org/licenses/gpl-3.0.txt
Resolving www.gnu.org (www.gnu.org)… 2001:470:142:3::a, 209.51.188.148
Connecting to www.gnu.org (www.gnu.org)|2001:470:142:3::a|:443… connected.
HTTP request sent, awaiting response… 200 OK
Length: 35149 (34K) [text/plain]
Saving to: ‘gpl-3.0.txt’
gpl-3.0.txt 100%[================================================================>] 34.33K --.-KB/s in 0.1s 
2019-03-07 16:34:51 (280 KB/s) - ‘gpl-3.0.txt’ saved [35149/35149]
christopher@nightshade:~/Scratch$ gzip -vc gpl-3.0.txt > gpl-3.0.txt.default.gz
gpl-3.0.txt: 65.5%

Now you can (in principle) increase your compression amount by looking over a larger data window, which is to say, spending more cpu cycles looking for repeats. With gzip you can specify this by specifying a compression level. The default is 6, and you can go up to 9. In this particular case though, it doesn’t make a difference:

christopher@nightshade:~/Scratch$ gzip -v9c gpl-3.0.txt > gpl-3.0.txt.9.gz
gpl-3.0.txt: 65.6%

I haven’t had a chance to spend any quality time with bzip2 yet, but 7z (which technically does both archiving and compressing) by default uses LZMA2 algorithm. In this case (text data) we get only slightly better results, even with the compress level set high:

christopher@nightshade:~/Scratch$ 7z a gpl-3.0.txt.default.7z gpl-3.0.txt

7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21
p7zip Version 16.02 (locale=en_US.utf8,Utf16=on,HugeFiles=on,64 bits,3 CPUs AMD Athlon(tm) II X3 455 Processor (100F53),ASM)

Scanning the drive:
1 file, 35149 bytes (35 KiB)

Creating archive: gpl-3.0.txt.default.7z

Items to compress: 1

    
Files read from disk: 1
Archive size: 11487 bytes (12 KiB)
Everything is Ok
christopher@nightshade:~/Scratch$ 7z a gpl-3.0.txt.9.7z gpl-3.0.txt -mx=9

7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21
p7zip Version 16.02 (locale=en_US.utf8,Utf16=on,HugeFiles=on,64 bits,3 CPUs AMD Athlon(tm) II X3 455 Processor (100F53),ASM)

Scanning the drive:
1 file, 35149 bytes (35 KiB)

Creating archive: gpl-3.0.txt.9.7z

Items to compress: 1

    
Files read from disk: 1
Archive size: 11495 bytes (12 KiB)
Everything is Ok

However, 7z allows us to choose from several different compression algorithms. One is PPMd:

Predictions are usually reduced to symbol rankings[clarification needed]. Each symbol (a letter, bit or any other amount of data) is ranked before it is compressed and, the ranking system determines the corresponding codeword (and therefore the compression rate). In many compression algorithms, the ranking is equivalent to probability mass function estimation. Given the previous letters (or given a context), each symbol is assigned with a probability. For instance, in arithmetic coding the symbols are ranked by their probabilities to appear after previous symbols and the whole sequence is compressed into a single fraction that is computed according to these probabilities.

https://en.wikipedia.org/wiki/Prediction_by_partial_matching#Theory

This algorithm is especially good with text data, and gives us much compression in this case:

christopher@nightshade:~/Scratch$ 7z a gpl-3.0.txt.ppm.7z gpl-3.0.txt -m0=PPMd

7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21
p7zip Version 16.02 (locale=en_US.utf8,Utf16=on,HugeFiles=on,64 bits,3 CPUs AMD Athlon(tm) II X3 455 Processor (100F53),ASM)

Scanning the drive:
1 file, 35149 bytes (35 KiB)

Creating archive: gpl-3.0.txt.ppm.7z

Items to compress: 1

    
Files read from disk: 1
Archive size: 9617 bytes (10 KiB)
Everything is Ok

On a Debian Gnu/Linux system, you can see the algorithms supported by 7z at file:///usr/share/doc/p7zip/DOC/MANUAL/cmdline/switches/method.htm using your Web browser. Our results so far:

christopher@nightshade:~/Scratch$ ls -l
total 96
-rw-r--r-- 1 christopher parents 35149 Sep 29  2017 gpl-3.0.txt
-rw-r--r-- 1 christopher parents 11495 Mar  7 16:41 gpl-3.0.txt.9.7z
-rw-r--r-- 1 christopher parents 12136 Mar  7 16:36 gpl-3.0.txt.9.gz
-rw-r--r-- 1 christopher parents 11487 Mar  7 16:37 gpl-3.0.txt.default.7z
-rw-r--r-- 1 christopher parents 12142 Mar  7 16:35 gpl-3.0.txt.default.gz
-rw-r--r-- 1 christopher parents  9617 Mar  7 16:37 gpl-3.0.txt.ppm.7z

Compression of images and audio is a different animal, for one because the storage format itself usually includes the compression. Perhaps that will be the subject of another post.

Rotary Harmonograph with Dampening

To get some more artistic variety in the simulated rotary harmonograph output, we introduce a dampening, i.e., causing the pen and table to run down as though from friction. Also, we can nudge our simple ratio slightly, to add a small element of discord or imperfection.

Here is the adjusted function:

(define (rot ang/tunit t phase dampfact)
  (* (make-rectangular (expt dampfact t) 0)
   (expt ei
         (+ phase (* ang/tunit t)))))

With very fine control of the ratios, dampening factor, and number of samples, we can produce a variety of effects. (I’m guessing this would be much more difficult with a physical harmonograph.)

Rotary Harmonographs

Reading about rotary harmonographs in the Quadrivium, it was of course necessary for me to write scheme code to simulate one. This simulates a pen moving circularly in one direction, on a piece of paper moving circularly in the other direction. This, in turn, provides an interesting way to visualize harmonic ratios.

Formulas on the Internet focus on trigonometric functions for x and y axes. But it seems more appealing to deal with this using rotations of complex numbers. This is the basic math:

#lang racket
(require plot)
(define ei (exp 0+1i))
(define (rot ang/tunit t phase)
(expt ei (+ phase (* ang/tunit t))))
(define tau (* 2 pi))
(define (compnums ti samples f1 f2)
(let ([ang0 (/ tau f1)]
[ang1 (/ tau f2)])
(map (lambda (n)
(let ([t (* n ti)])
(+
(rot ang0 t 0)
(rot ang1 t 0))))
(range 0 (- samples 1))))

And we need some interface code to generate the plot:

(define (complex2vec c) (vector (real-part c) (imag-part c)))
(define (rotaryplot ti samples f1 f2)
(plot
(lines
(map
complex2vec
(compnums ti samples f1 f2)))))

Here, we have the basic circle generated by matching frequencies:

Next we do the octave (2:1):

We get quite a different plot if we have the pen turning in the opposite direction of the paper:

And the 4:3 ratio (known as a “Fourth” in music):

This would be more artistic if we introduced some dampening (friction) like in a physical harmonograph, and a small amount of discord. But, it is getting late, and I have to face that day job tomorrow, so that will have to wait for some other evening.