Branch Cuts and Complex Functions in Common Lisp
There are a lot of functions that we take for granted that have some surprisingly interesting backstories.
Join the DZone community and get the full member experience.
Join For Free“Nearly everything is really interesting if you go into it deeply enough.” — Richard Feynman
If you thumb through Guy Steele’s book Common Lisp: The Language, 2nd Edition, you might be surprised how much space is devoted to defining familiar functions: square root, log, arcsine, etc. He gives some history of how these functions were first defined in Lisp and then refined by the ANSI (X3JI3) standardization committee in 1989.
There are three sources of complexity:
 Complex number arguments.
 Multivalued functions.
 +0 and 0.
Complex Arguments
The functions under discussion are defined for either real or complex inputs. This does not complicate things much in itself. Defining some functions for complex arguments, such as the exp
function, is simple. The complication comes from the interaction of complex arguments with multivalued functions and floatingpoint representations of zero.
Multivalued Functions
The tricky functions to define are inverse functions, or functions where we have to make a choice of range.
Real Multivalued Functions
Let’s restrict our attention to real numbers for a moment. How do you define the square root of a positive number x? There are two solutions to the equation y^{2} = x, and √x is defined to be the positive solution.
What about the arcsine of x? This is the number whose sine is x. Except there is a “the” number. There are infinitely many numbers whose sine is x, so we have to make a choice. It seems natural to choose values in an interval symmetric about 0, so we take arcsine of x to be the number between π/2 and π/2 whose sine is x.
Now, what about arctangent? As with arcsine, we have to make a choice because for any x there are infinitely many numbers y whose tangent is x. Again, it’s convenient to define the range to be in an interval symmetric about zero, so we define the arctangent of x to be the number y between π/2 and π/2 whose tangent is x. However, now we have a subtle complication with tangent that we didn’t have with sine because tangent is unbounded. How do we want to define the tangent of a vertical angle? Should we call it ∞ or ∞? What do we want to return if someone asks for the arctangent of ±∞? Should we return π/2 or π/2?
Complex Multivalued Functions
The discussion shows there are some minor complications in defining inverse functions on the real line. Things get more complicated when working in the complex plane. To take the square root example, it’s easy to say we’re going to define square root so that the square root of a positive number is another positive number. Fine. But which solution to z^{2} = w should we take to be the square root of a complex number w, such as 2 + 3i or 5 + 17i?
Or consider logarithms. For positive numbers x there is only one real number y such at exp(y) = x. But what if we take a negative value of x such as 1? There’s no real number whose exponential is 1, but there is a complex number. In fact, there are infinitely many complex numbers whose exponential is 1. Which one should we choose?
FloatingPoint Representations of Zero
A littleknown feature of floating point arithmetic (specified by the IEEE 754 standard) is that there are two kinds of zero: +0 and 0. This sounds bizarre at first, but there are good reasons for this, which I explain here. But defining functions to work properly with two kinds of zero takes a lot of work. This was the main reason the ANSI Common Lisp committee had to revise their definitions of several transcendental functions. If a function has a branch cut discontinuity along the real axis, for example, you want your definition to be continuous as you approach x + 0i from above and as you approach x 0i from below.
The Common Lisp Solution
I’ll cut to the chase and present the solution the X3J13 came up with. For a discussion of the changes this required and the detailed justifications, see Guy Steele’s book.
The first step is to carefully define the twoargument arctangent function (atan y x)
for all 16 combinations of y and x being positive, negative, +0, or 0. Then other functions are defined as follows.
 Define
phase
in terms ofatan
.  Define complex
abs
in terms of realsqrt
.  Define complex
log
in terms ofphase
, complexabs
, and reallog
.  Define complex
sqrt
in terms of complexlog
.  Define everything else in terms of the functions above.
The actual implementations may not follow this sequence, but they have to produce results consistent with this sequence.
The phase of z is defined as the arctangent with arguments the imaginary and real parts of z.
The complex log of z is defined as log z + i phase(z).
Square root of z is defined as exp( log(z) / 2 ).
The inverses of circular and hyperbolic functions are defined as follows.
Note that there are many ways to define these functions that seem to be equivalent, and are equivalent in some region. Getting the branch cuts right is what makes this complicated.
Published at DZone with permission of John Cook, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Trending

Auditing Tools for Kubernetes

The SPACE Framework for Developer Productivity

Effortlessly Streamlining TestDriven Development and CI Testing for Kafka Developers

What Is Test Pyramid: Getting Started With Test Automation Pyramid
Comments