# On the Systematic Creation of Faithfully Rounded
Commutative Truncated Booth Multipliers

Theo Drane, Samuel Coward  Graphics Numerical Hardware Group
Intel Corporation
Email<EMAIL_ADDRESS>Mertcan Temel  Advanced
Architecture Design Group
Intel Corporation
Email<EMAIL_ADDRESS>Joe Leslie-Hurd  Design Engineering Group
Intel Corporation
Email<EMAIL_ADDRESS>
###### Abstract

In many instances of fixed-point multiplication, a full precision result is
not required. Instead it is sufficient to return a faithfully rounded result.
Faithful rounding permits the machine representable number either immediately
above or below the full precision result, if the latter is not exactly
representable. Multipliers which take full advantage of this freedom can be
implemented using less circuit area and consuming less power. The most common
implementations internally truncate the partial product array. However,
truncation applied to the most common of multiplier architectures, namely
Booth architectures, results in non-commutative implementations. The
industrial adoption of truncated multipliers is limited by the absence of
formal verification of such implementations, since exhaustive simulation is
typically infeasible. We present a commutative truncated Booth multiplier
architecture and derive closed form necessary and sufficient conditions for
faithful rounding. We also provide the bit-vectors giving rise to the worst-
case error. We present a formal verification methodology based on ACL2 which
scales up to 42 bit multipliers. We synthesize a range of commutative
faithfully rounded multipliers and show that truncated booth implementations
are up to 31% smaller than externally truncated multipliers.

##  1 Introduction

Of the most common arithmetic circuits, multiplication consumes the greatest
power and occupies the largest circuit area. As a result, binary
multiplication has been the subject of significant academic and industrial
research [1, 2, 3]. Amongst the most widely implemented multiplier
architectures is the Booth Radix-4 multiplier [4]. In many applications, the
requirement for exact multiplication can be dropped, and replaced with a
faithful rounding requirement. A faithful rounding returns the machine
representable number immediately above or below the infinitely precise result,
unless the infinitely precise result can in fact be represented at the machine
precision.

The additional freedom introduced by a faithful rounding, can be exploited, at
the register transfer level (RTL), to improve multiplier power consumption and
save circuit area. The standard approach to exploiting such freedom is to
truncate the partial product array, as shown in Figure 1. Unfortunately, the
partial product array arising from a Booth Radix-4 encoding is not symmetric,
as only one operand gets encoded. Applying truncation to a Booth Radix-4
multiplier, results in a non-commutative implementation [5, 6]. Compiler
optimizations routinely implicitly assume mathematical properties of
underlying hardware. Application level correctness may implicitly require
monotonicity of a complex function say, but may not have been considered
during the hardware design. But commutativity is a far greater pervasive
assumption, to the extent that compiler engineers could not conceive that non-
commutative multipliers could even be built. Preserving commutativity
significantly reduces compiler complexity for this most fundamental of
operations.

$\overbrace{\hskip 124.00012pt}^{16}$ | $\overbrace{\hskip 25.00003pt}^{4}$ | $\overbrace{\hskip 94.00008pt}^{12}$
---|---|---
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 1 |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 1 | 1 |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 1 | 1 | 1 |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Figure 1: A 16-bit $a\times b$, implemented as a traditional partial product
array, where each partial product bit is $a[i]\&b[j]$. From this array we
truncate 12 columns and insert the compensation constant, 11 (red). Summing
the truncated array (black) and discarding the light blue bits produces a
faithfully rounded 16-bit multiplication result.

In this work, we first demonstrate how, for minimal hardware overhead, the
commutativity property of a truncated Booth implementation can be recovered.
We then analytically derive tight error bounds on Booth array truncation and
describe necessary and sufficient conditions to implement a faithful rounding.
Lastly, we describe a procedure to construct efficient hardware
implementations. The result is a fully parameterizable faithfully rounded
multiplier design that exhibits better power and area than alternative
approaches.

The paper is organized as follows. In Section 2 we discuss prior work on
hardware efficient multiplier, with a particular focus on works that exploit
error freedom. In Section 3 we derive compensation terms to recover
commutativity and prove a set of mathematical bounds on truncation error. We
then demonstrate how we can use this information to design an efficient
faithfully rounded commutative Booth multiplier. In Section 4 we compare
synthesis results for a range of different implementations and discuss our
approach to verifying these multiplier designs.

The paper contains the following novel contributions:

  * •

a precise description of the compensation hardware required to recover the
commutativity property,

  * •

proven mathematical bounds on the maximal error due to truncation of Booth
partial product arrays,

  * •

a procedure to construct faithfully rounded commutative truncated Booth
multipliers with maximal truncation.

##  2 Background

###  2.1 Binary Multiplication

The most naive implementation of $n$-bit binary multiplication via primitive
logic gates [4] consists of first forming a partial product (PP) array of
$n^{2}$ PP bits, where each PP bit is the logical AND of two input bits. Next
that PP array is reduced from $n$ rows to two rows via compressor cells
arranged in a reduction tree. Once reduced to a summation of two rows, a full
parallel adder can be deployed, usually to produce a $2n$-bit result. Decades
of research has led to efficient implementations of all stages of this
approach. Array reduction was studied by Wallace and Dadda [1, 2] then more
recently improved with timing driven compressor-tree construction [7, 8].
Parallel addition in ASIC design is now most commonly implemented via parallel
prefix structures [8, 3]. In this work, we will be entirely focused upon the
first step, the construction of the PP array, and rely on existing techniques
for the efficient implementation of array reduction and parallel addition.

One of the most widely used PP array creation techniques, is to add a Booth
encoding step, which groups bits together to reduce the number of rows in the
PP array. As observed by Zimmerman [8], the overhead introduced by the
additional encoding step only offers a net benefit at larger bitwidths, beyond
16-bits. The two primary variants are the Booth Radix-4 and Radix-8 encoding
schemes. This paper modifies the Booth Radix-4 multiplication method, so we
will describe it in detail. We define the following encoding function taking
three single bit operands:

$B(x,y,z)=-2x+y+z$ (1)

For an $n$-bit signed multiplication, Booth Radix-4 encoding halves the PP
array height:

$\displaystyle a\times b$ $\displaystyle=\sum_{i=0}^{n-1}2^{i}a_{i}\times b$
(2) $\displaystyle=\sum_{i=0}^{(n/2)-1}4^{i}B(a_{2i+1},a_{2i},a_{2i-1})\times
b,$ (3)

where $a_{-1}=0$ and we assume an even $n$. Each PP row in (3) can be
efficiently implemented using primitive logic gates. Minor modifications are
required for odd $n$ and unsigned multiplication [4].

###  2.2 Faithfully Rounded Binary Multiplication

The implementation of binary multiplication where the full result is not
required is most commonly achieved via truncation schemes [9, 10, 11]. These
schemes follow a similar structure to compute $n$-bit $a\times b$. First,
truncate the partial product array, removing the $k$ least significant
columns, corresponding to an error value of $\Delta_{k}$. To the remaining
array add a compensation term, $f(a,b)$, to the $k^{th}$ column and then
perform standard array reduction. From this summation result a further $n-k$
columns can be truncated to recover a faithfully rounded multiplication. Early
work in this domain, described as Constant Correction Truncated schemes (CCT),
started from an AND array and considered constant $f(a,b)$ [12, 13]. An
example of CCT is shown in Figure 1. Later work introduced Variable Correction
Truncation, where $f(a,b)$ was considered to be a function of the inputs [14].
Other works considered linearization schemes [15] and approximate carry
predictions [16]. Booth array truncation has similarly seen CCT techniques
applied along with a range of statistical methods to approximate the expected
truncation error [5, 6, 9]. These previous Booth truncation schemes have
broken the commutativity property of multiplication, a property that, as we
show in this work, can be recovered for minimal hardware overhead.

Faithfully rounded truncated multipliers are most commonly applied in Digital
Signal Processing (DSP) but also can be found in floating point multipliers,
where a lower accuracy can be permitted [17]. For transcendental function
approximations, it is rarely necessary to compute full precision
multiplication, since we already have the approximation error to factor in
[18, 19].

##  3 Methodology

The cause of the non-commutativity of truncated Booth multiplier architectures
stems from the asymmetry of how the multiplier and multiplicand are treated;
namely that only one of the inputs is Booth encoded. Naturally to maintain the
hardware benefits of Booth architectures and remain commutative, the solution
is to Booth encode both inputs. For ease of exposition we will assume that
both inputs are signed two’s complement, have even bitwidth $n$. We focus on a
Booth Radix-4 architecture. It is simple to extend the analysis presented here
to odd $n$ and unsigned multiplication. Given these assumptions, double Booth
encoding results in the following:

$\displaystyle a\times b$
$\displaystyle=\sum_{i,j=0}^{(n/2)-1}4^{i+j}PP_{i,j}$ (4) $\displaystyle
PP_{i,j}$ $\displaystyle=B(a_{2i+1},a_{2i},a_{2i-1})\times
B(b_{2j+1},b_{2j},b_{2j-1}),$ (5)

where $a_{-1}=b_{-1}=0$. The key observation to achieving commutative
truncated Booth architectures is to truncate (4) directly. Ultimately we will
target creating a faithfully rounded result returning the most significant $n$
bits. By truncating $k$ columns, a portion of the summation, $\Delta$, will be
deleted and the remainder, $M$, will be implemented as a partial-product array
such that $a\times b=M+\Delta$.

$\displaystyle M$ $\displaystyle=\sum_{i,j=0,i+j\geq
k/2}^{(n/2)-1}4^{i+j}PP_{i,j}$ $\displaystyle\Delta$
$\displaystyle=\sum_{i,j=0,i+j<k/2}^{(k/2)-1}4^{i+j}PP_{i,j}$ (6)

Note that the proposed architecture and analysis assumes $k<n$ such that
$\Delta$ is strictly triangular in shape. (Hence the proposed architecture can
be extended to return a faithfully rounded result with $m$ bits as long as
$m>n$.) The first challenge is how $M$ is transformed into a binary array and
the second is analyzing the error of $\Delta$.

###  3.1 Commutative Truncated Booth Arrays

To begin reducing $M$ to a binary PP array, we can undo the Booth encoding to
one of the inputs:

$\displaystyle M$
$\displaystyle=\sum_{i=0}^{(n/2)-1}4^{i}B(a_{2i+1},a_{2i},a_{2i-1})\times
bb_{i}$ (7) $\displaystyle bb_{i}$
$\displaystyle=(-2^{n-k+2i-1}b_{n-1}+b_{n-2:k-2i}+b_{k-2i-1}),$

where $b_{j}=0$ if $j<0$ and $b_{n:m}$ denotes the bit slice of $b[n:m]$. Now
the terms in the summation only differ from a standard Booth Radix-4 summation
due to the presence of the $b_{k-2i-1}$ term. Let us consider a standard Booth
Radix-4 PP row $row_{i}$ and contrast this with one of the terms in (7),
$row_{i}^{\prime}$. Such rows are of the form (for some $c_{i}$):

$\displaystyle row_{i}$
$\displaystyle=B(a_{2i+1},a_{2i},a_{2i-1})(-2^{n-2}c_{n-1}+c_{n-2:1})$
$\displaystyle row_{i}^{\prime}$
$\displaystyle=B(a_{2i+1},a_{2i},a_{2i-1})(-2^{n-2}c_{n-1}+c_{n-2:1}+c_{0})$
(8)

Now the bit level construction of $row_{i}$ and $row_{i}^{\prime}$ can be
found in Table I (note that for two’s complement $c$ and bit $c_{0}$,
$-c-c_{0}=\overline{c}+1-c_{0}=\overline{c}+\overline{c_{0}}$).

TABLE I: PARTIAL PRODUCT CREATION FOR COMMUTATIVE TRUNCATED BOOTH RADIX-4 ARRAY $a_{2i+1}$ | $a_{2i}$ | $a_{2i-1}$ | $-2a_{2i+1}+a_{2i}+a_{2i-1}$ | $row_{i}=pp_{i}+s_{i}$ | $row_{i}^{\prime}=pp_{i}^{\prime}+s_{i}^{\prime}$
---|---|---|---|---|---
0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 1 | 1 | $\\{c_{n-1},c_{n-1}...c_{2},c_{1}\\}+0$ | $\\{c_{n-1},c_{n-1}...c_{2},c_{1}\\}+c_{0}$
0 | 1 | 0 | 1 | $\\{c_{n-1},c_{n-1}...c_{2},c_{1}\\}+0$ | $\\{c_{n-1},c_{n-1}...c_{2},c_{1}\\}+c_{0}$
0 | 1 | 1 | 2 | $\\{c_{n-1},c_{n-2}...c_{1},0\\}+0$ | $\\{c_{n-1},c_{n-2}...c_{1},c_{0}\\}+c_{0}$
1 | 0 | 0 | -2 | $\\{\overline{c_{n-1}},\overline{c_{n-2}}...\overline{c_{1}},1\\}+1$ | $\\{\overline{b_{n-1}},\overline{c_{n-2}}...\overline{c_{1}},\overline{c_{0}}\\}+\overline{c_{0}}$
1 | 0 | 1 | -1 | $\\{\overline{c_{n-1}},\overline{c_{n-1}}...\overline{c_{0}},\overline{c_{0}}\\}+1$ | $\\{\overline{b_{n-1}},\overline{c_{n-1}}...\overline{c_{2}},\overline{c_{1}}\\}+\overline{c_{0}}$
1 | 1 | 0 | -1 | $\\{\overline{c_{n-1}},\overline{c_{n-1}}...\overline{c_{0}},\overline{c_{0}}\\}+1$ | $\\{\overline{b_{n-1}},\overline{c_{n-1}}...\overline{c_{2}},\overline{c_{1}}\\}+\overline{c_{0}}$
1 | 1 | 1 | 0 | 0 | 0

Note that $row_{i}$ and $row_{i}^{\prime}$ can both be expressed in the form
integer $pp$ plus bit $s$. Moreover truncated $pp_{i}$ has identical values to
truncated $pp_{i}^{\prime}$, the key and only difference between a truncated
Booth Radix-4 array and commutative array are the $s_{i}^{\prime}$ bits. The
Boolean expressions for $s_{i}$ and $s_{i}^{\prime}$, derivable from Table I
are:

$\displaystyle s_{i}$ $\displaystyle=a_{2i+1}\&\overline{a_{2i}\&a_{2i-1}}$
$\displaystyle s_{i}^{\prime}$
$\displaystyle=a_{2i+1}\&\overline{a_{2i}\&a_{2i-1}}\&(c_{0}\oplus a_{2i+1})$
(9)

We can now present the steps in constructing a commutative truncated Booth
Radix-4 array:

  1. 1.

Construct standard Booth Radix-4 array

  2. 2.

Remove least significant $k$ columns, $k$ is even

  3. 3.

In column $k$, for $i\in[0,\frac{k}{2}-1]$, add additional bits

$s_{i}^{\prime}=a_{2i+1}\&\overline{a_{2i}\&a_{2i-1}}\&(b_{k-2i-1}\oplus
a_{2i+1}).$

The difference between a commutative and a non-commutative array is just the
inclusion of these $k/2$ bits.

$\overbrace{\hskip 124.00012pt}^{16}$ | $\overbrace{\hskip 25.00003pt}^{4}$ | $\overbrace{\hskip 94.00008pt}^{12}$
---|---|---
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | $C^{*}$ |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Figure 2: A 16-bit commutative truncated Booth multiplier, with 12 columns of
truncation. The six red bits are the additional compensation bits
$s_{i}^{\prime}$. The pink bits represent the typical Booth sign bits $s_{i}$.

Since these $s^{\prime}$ bits increase the array height of the least
significant column, it is natural to ask whether this will affect the critical
path.

Consider any array reduction that performs the summation of $m$ addends of
large length $k$. The greatest number of carries that the summation generates
will occur when the addends are maximal, evaluating
$m(2^{k}-1)=(m-1)2^{k}+(2^{k}-m)$. For sufficiently large $k$, $2^{k}-m>0$ and
hence such a summation will generate at most $m-1$ carries. This means the
implementations are capable of dealing with $m-1$ carries and hence accepting
$m-1$ additional carry-in bits in its least significant column without
significantly altering its delay characteristics.

The maximum array height in Figure 2 is $\approx n/2$, the number of
additional carry ins such an array can handle is $<n/2$, there are $k/2$
additional $s_{i}^{\prime}$ bits which is by assumption on $k$, $<n/2$. Hence
such commutative truncated Booth Radix-4 arrays are expected to exhibit
minimal delay differences when compared to untruncated arrays.

It is important to note that while there are but $k/2$ $s^{\prime}$ bits
additional bits required to make the truncated Booth Radix-4 array commutative
and such inclusion is expected to have limited delay impact; these bits are in
no way trivial. Omitting any one of them is likely to still produce a
faithfully rounded implementation, but it will not be commutative. These
$s^{\prime}$ bits are not present in the original Booth Radix-4 array and any
truncation or promotion of bits within the array will not result in a
commutative array. Such compensation bits would need to be rederived for every
Booth architecture variant. Moreover commutativity was achieved by truncating
(4), not standard Booth summation formulae.

###  3.2 The Truncation Error

In order to create optimal faithfully rounded multipliers, the value range of
$\Delta$ must be precisely known. This analysis will be facilitated by the
following helper functions, representing hexadecimal summations:

$X_{n}=$ | $Y_{n}=$ | $Z_{n}=$ | $W_{n}=$
---|---|---|---
$\overbrace{\texttt{222..222}}^{n}$ | $\overbrace{\texttt{222..222}}^{n}$ | $\overbrace{\texttt{000..000}}^{n}$ | $\overbrace{\texttt{444..444}}^{n}$
| +444..444 | +444..444 | +444..444
+444..440 | +444..440 | +444..440 | +444..440
+444..440 | +444..440 | +444..440 | +444..440
+444..400 | +444..400 | +444..400 | +444..400
+444..400 | +444..400 | +444..400 | +444..400
$\cdots$ | $\cdots$ | $\cdots$ | $\cdots$
+440..000 | +440..000 | +440..000 | +440..000
+440..000 | +440..000 | +440..000 | +440..000
+400..000 | +400..000 | +400..000 | +400..000
+400..000 | +400..000 | +400..000 | +400..000

These hexadecimal summations can be simplified. Consider reducing $X_{n}$:

$\overbrace{\texttt{222..222}}^{n}$ | $=\frac{2}{15}\texttt{FFF..FFF}$ | $=\hskip 15.00002pt\frac{2}{15}\overbrace{\texttt{0FFF..FFF}}^{n+1}$
---|---|---
+444..440 | $-\frac{8}{15}\texttt{111..110}$ | $-\hskip 15.00002pt\frac{8}{15^{2}}\texttt{0FFF..FF0}$
+444..440 | $+\frac{8}{15}\texttt{111..110}$ | $+\frac{8(n-1)}{15^{2}}\texttt{1000..000}$
+444..400 | $+\frac{8}{15}\texttt{FFF..FF0}$ |
+444..400 | $+\frac{8}{15}\texttt{FFF..F00}$ |
$\cdots$ | $\cdots$ |
+440..000 | $+\frac{8}{15}\texttt{FF0..000}$ |
+440..000 |  |
+400..000 | $+\frac{8}{15}\texttt{F00..000}$ |
+400..000 |  |

Therefore,

$\displaystyle X_{n}$
$\displaystyle=\frac{2}{15}(16^{n}-1)-\frac{8}{15^{2}}(16^{n}-16)+\frac{8}{15}(n-1)16^{n}$
$\displaystyle=\frac{2}{225}(16^{n}(60n-49)+49).$

Similarly the remaining helper functions can be reduced to:

$\displaystyle Y_{n}$ $\displaystyle=\frac{2}{225}(16^{n}(60n-19)+19)$
$\displaystyle Z_{n}$ $\displaystyle=\frac{4}{225}(16^{n}(30n-17)+17)$
$\displaystyle W_{n}$ $\displaystyle=\frac{8}{225}(16^{n}(15n-1)+1)$

######  Lemma 1.

Extremal values of $\Delta$ occur when $a_{i}\neq a_{i-2}$ and $b_{j}\neq
b_{j-2}$ for all $n>i,j>1$.

###### Proof.

Consider the contribution of $a_{0}$ and $a_{2}$ in $\Delta$:

$\displaystyle\Delta=$ $\displaystyle(-2^{k-1}b_{k-1}+b_{k-2:0})a_{0}$
$\displaystyle+4(-2^{k-3}b_{k-3}+b_{k-4:0})a_{2}+...$ $\displaystyle=$
$\displaystyle-2^{k-1}(b_{k-1}a_{0}+b_{k-3}a_{2})$
$\displaystyle+2^{k-2}(b_{k-2}a_{0}+b_{k-4}a_{2})+...$
$\displaystyle+4(b_{2}a_{0}+b_{0}a_{2})+...$

For $a_{0}=a_{2}=1$, extremal $\Delta$ occurs when $b_{k-1:2}=b_{k-3:0}$. If
$a_{0}=a_{2}=0$ made $\Delta$ extremal this would imply $b_{k-1:2}=b_{k-3:0}$.
But if $a_{0}=a_{2}$ implies $b_{k-1:2}=b_{k-3:0}$ and hence $b_{2}=b_{0}$
then by a symmetric argument this would imply $a_{k-1:2}=a_{k-3:0}$. Up to
input reordering, this implies the following extremal inputs:

TABLE II: $\Delta$ WORST CASE INPUTS $a_{i}=a_{i-2}$ AND $b_{j}=b_{j-2}$

$a$ | $b$ | $\Delta$
---|---|---
111…111 | 111...111 | $1$
111...111 | 101...010 | $\frac{2^{k}+2}{3}$
111...111 | 010...101 | $-\frac{2^{k}-1}{3}$
101...010 | 101...010 | $\frac{1}{18}((3k+16)2^{k}+16)$
101...010 | 010...101 | $-k2^{k-2}-\frac{1}{3}(2^{k}-1)$
010...101 | 010...101 | $\frac{1}{18}((3k-2)2^{k}+2)$
000...000 | 000...000 | $0$

Alternatively if $a_{0}\neq a_{2}$, swapping the value of $a_{0}$ with $a_{2}$
will produce the largest change to $\Delta$ if $b_{k-1:2}\neq b_{k-3:0}$. But
if $a_{0}\neq a_{2}$ implies $b_{k-1:2}\neq b_{k-3:0}$ and hence $b_{2}\neq
b_{0}$ then by a symmetric argument this would imply $a_{k-1:2}\neq
a_{k-3:0}$.

As an example, consider $k/2$ is odd and $a=b=10011001...100110$:

$\displaystyle\Delta$
$\displaystyle=\sum_{i,j=0,i+j<k/2}^{(k/2)-1}4^{i+j}PP_{i,j}$
$\displaystyle=-\sum_{i,j=0,i+j<k/2}^{(k/2)-1}(-4)^{i+j+1}$
$\displaystyle=Z_{(k+2)/4}-4W_{(k-2)/4}$
$\displaystyle=\frac{2}{25}(2^{k}(5k+2)+2)$

Similarly, the helper functions can be used to simplify $\Delta$ for all the
cases where $a_{i}\neq a_{i-2}$ and $b_{j}\neq b_{j-2}$ for all $n>i,j>1$,
four of these cases are:

TABLE III: $\Delta$ WORST CASE INPUTS $a_{i}\neq a_{i-2}$ AND $b_{j}\neq
b_{j-2}$

$k/2$ | $a$ | $b$ | $\Delta$
---|---|---|---
even | 10011001...1001 | 01100110...0110 | $4Y_{\frac{k}{4}}-X_{\frac{k}{4}}$
odd | 10011001...10 | 10011001...10 | $Z_{\frac{k+2}{4}}-4W_{\frac{k-2}{4}}$
even | 01100110...0110 | 01100110...0110 | $Z_{\frac{k}{4}}-4W_{\frac{k}{4}}$
odd | 10011001...10 | 01100110...01 | $-X_{\frac{k+2}{4}}+4Y_{\frac{k-2}{4}}$

The remaining cases produce less extremal $\Delta$ values. These four cases
can be combined and simplified using the helper function to conclude:

$\displaystyle-\frac{1}{25}(2^{k}(10k+5(-1)^{k/2}$
$\displaystyle-1)-5+(-1)^{k/2}$ $\displaystyle\leq\Delta$ $\displaystyle\leq$
$\displaystyle\frac{1}{25}(2^{k}(10k-5(-1)^{k/2}$
$\displaystyle-1)+5+(-1)^{k/2}$ (10)

Note that the leading coefficient of $k2^{k}$ in these bounds are $2/5$ versus
$1/6$ and $1/4$ in Table II . Conclude that the extremal values of $\Delta$
occur when $a_{i}\neq a_{i-2}$ and $b_{j}\neq b_{j-2}$ for all $n>i,j>1$. The
worst case input vectors can be found in Table III and (3.2) contains tight
bounds on $\Delta$. ∎

###  3.3 Faithfully Rounded Commutative Truncated Booth Arrays

The optimal truncation scheme will truncate the most number of columns while
maintaining the faithful rounding condition. The truncated array $M$ will have
an additional constant $C$ added to compensate for the loss of $\Delta$. Once
summed, the least significant bits (value $D$) will be truncated before
returning the approximation.

$\displaystyle y=a\times b=M+\Delta\quad\text{Unrounded Result}$
$\displaystyle y^{\prime}=M+C-D\quad\text{Rounded Result}$
$\displaystyle|y-y^{\prime}|<2^{n}\quad\text{Faithful Rounding Condition}$
$\displaystyle\Rightarrow C-D-2^{n}<\Delta<C-D+2^{n}$

$D$ can take any value between $0$ and $2^{n}-2^{k}$, hence necessary and
sufficient condition for faithful rounding is:

$\displaystyle C-2^{n}<$ $\displaystyle\Delta<C+2^{k}$
$\displaystyle\max(\Delta)-2^{k}<$ $\displaystyle C<\min(\Delta)+2^{n}$

Now $C$ is a multiple of $2^{k}$, hence:

$\displaystyle\left\lfloor\frac{\max(\Delta)}{2^{k}}\right\rfloor\leq\left\lfloor\frac{\min(\Delta)}{2^{k}}\right\rfloor+2^{n-k}$

Substituting the extremal found in (3.2) and simplifying results in:

$\displaystyle\left\lfloor\frac{2k-(-1)^{k/2}}{5}\right\rfloor+\left\lceil\frac{2k+(-1)^{k/2}}{5}\right\rceil<2^{n-k}$
(11)

Maximising $k$ in (11) generates the optimal truncation value. The optimal
truncation scheme values can now be presented:

$\displaystyle k^{*}=\max_{\text{even }k}\left(k\leq 5\times 2^{n-k-2}\right)$
(12) $\displaystyle\frac{2k^{*}-5-(-1)^{\frac{k^{*}}{2}}}{5}\leq
C^{*}\leq\frac{5\times 2^{n-k^{*}}-2k^{*}-(-1)^{\frac{k^{*}}{2}}}{5}$ (13)

Example values of $k^{*}$ and $C^{*}$:

$n$ | $k^{*}$ | $\min C^{*}$ | $\max C^{*}$
---|---|---|---
8 | 4 | 1 | 14
16 | 12 | 4 | 11
24 | 20 | 7 | 7
32 | 26 | 10 | 53
53 | 46 | 18 | 109
64 | 58 | 23 | 41

We can now present the steps in constructing a commutative truncated Booth
Radix-4 array for an $n$ multiplication returning a faithful rounding of the
$n$ most significant bits:

  1. 1.

Construct standard Booth Radix-4 array, Booth encoding $a$

  2. 2.

Calculate $k^{*}=\max_{\text{even }k}(k\leq 5\times 2^{n-k-2})$

  3. 3.

Remove least significant $k^{*}$ columns

  4. 4.

In column $k^{*}$, for $i\in[0,\frac{k^{*}}{2}-1]$, add additional bits

$s_{i}^{\prime}=a_{2i+1}\&\overline{a_{2i}\&a_{2i-1}}\&(b_{k^{*}-2i-1}\oplus
a_{2i+1}).$

  5. 5.

In column $k^{*}$, include constant $C^{*}$ which can be any value in the
range:

$\left[\frac{2k^{*}-5-(-1)^{\frac{k^{*}}{2}}}{5},\frac{5\times
2^{n-k^{*}}-2k^{*}-(-1)^{\frac{k^{*}}{2}}}{5}\right]$

  6. 6.

Sum the array

  7. 7.

Remove the least significant $n$ columns

TABLE IV: Synthesis results for three competing architectures at several delay targets, across four different bitwidths, $n$. The percentage improvements are with respect to the baseline implementation. We highlight the best result in each row in bold. |  | Baseline | Truncated AND [9] | Commutative Truncated Booth
---|---|---|---|---
$n$ | Delay (ns) | Area ($\mu m^{2}$) | Power ($\mu W$) | Area ($\mu m^{2}$) | Power ($\mu W$) | Area ($\mu m^{2}$) | Power ($\mu W$)
16 | 0.175 | 74.0 | 450 |  64.4 (-13.0%) |  319 (-29.2%) | 69.3 (\- 6.4%) | 389 (-13.7%)
0.2 | 56.1 | 346 |  46.4 (-17.4%) |  252 (-27.3%) | 48.3 (-13.9%) | 286 (-17.5%)
0.225 | 51.7 | 309 |  40.9 (-20.8%) |  215 (-30.4%) | 43.6 (-15.8%) | 252 (-18.5%)
0.25 | 47.5 | 283 |  37.1 (-21.9%) |  198 (-30.1%) | 39.7 (-16.3%) | 226 (-20.1%)
24 | 0.225 | 127.7 | 815 | 108.6 (-14.9%) | 622 (-23.7%) |  99.9 (-21.8%) |  600 (-26.4%)
0.25 | 113.4 | 705 | 101.5 (-10.4%) | 575 (-18.4%) |  88.7 (-21.8%) |  516 (-26.8%)
0.275 | 108.0 | 653 | 93.5 (-13.4%) | 502 (-23.2%) |  84.9 (-21.3%) |  498 (-23.8%)
0.3 | 99.2 | 595 | 83.8 (-15.6%) | 466 (-21.8%) |  77.3 (-22.1%) |  447 (-25.0%)
32 | 0.275 | 193.7 | 1225 | 161.3 (-16.7%) | 897 (-26.7%) |  156.2 (-19.4%) |  914 (-25.4%)
0.3 | 171.5 | 1097 | 156.3 (\- 8.8%) | 861 (-21.5%) |  148.0 (-13.7%) |  862 (-21.4%)
0.325 | 164.3 | 1024 | 139.7 (-15.0%) | 787 (-23.1%) |  134.2 (-18.3%) |  768 (-25.0%)
0.35 | 152.9 | 945 | 137.2 (-10.3%) | 772 (-18.3%) |  130.7 (-14.5%) |  748 (-20.8%)
64 | 0.3 | 823.0 | 5548 | 647.6 (-21.3%) | 3808 (-31.4%) |  566.8 (-31.1%) |  3527 (-36.4%)
0.325 | 745.5 | 4886 | 593.3 (-20.4%) | 3403 (-30.4%) |  515.6 (-30.8%) |  3073 (-37.1%)
0.35 | 709.2 | 4558 | 565.1 (-20.3%) | 3165 (-30.6%) |  491.7 (-30.7%) |  2846 (-37.6%)
0.375 | 638.6 | 4187 | 513.1 (-19.7%) | 2936 (-29.9%) |  446.9 (-30.0%) |  2593 (-38.1%)

##  4 Results

We compare three implementations of faithfully rounded commutative $n$-bit
multipliers returning an $n$-bit result. The baseline is a round to zero
multiplier, implemented by computing the full precision $n$-bit
multiplication, generating a 2$n$-bit result, from which we return the $n$
most significant bits. The second implementation is a truncated AND array,
where we follow the approach in [9] to compute the maximum possible truncation
and an efficient constant compensation term. We do not compare against
alternative truncated Booth implementations since these designs do not retain
commutativity.

###  4.1 Synthesis

We synthesize each design using a commercial logic synthesis tool, targeting a
standard TSMC 5nm library. We present results for a range of bitwidths and at
a number of delay targets for each parameterization. The combinational area
and total power consumption results reported by the logic synthesis tool are
shown in Table IV. We also present the percentage improvement in each metric
with respect to the baseline. We synthesize multipliers at relevant bitwidths
between 16 and 64 bits. At lower bitwidths the overhead of Booth encoding is
detrimental [8] and at higher bitwidths multiplier decomposition techniques,
such as Karatsuba [20], dominate [21].

In Table IV we can see that the truncated Booth array is up to 31% smaller
than the baseline implementation and consumes up to 38% less power.
Furthermore, the truncated Booth array is up to 13% smaller than the truncated
AND array and consumes up to 12% less power. For 16-bit multiplication, we see
that the truncated AND array is both smaller and more power efficient across
all delay targets. For 24-bit multiplication, the truncated Booth multiplier
is superior. Prior work on exact multiplier implementations also observed an
architectural crossover point around 16-bits [8], at which the overhead of
Booth encoding is offset by the gains in array reduction. As we increase the
bitwidth, the benefit offered by the truncated Booth array over the
alternatives increases.

$0.3$$0.35$$0.4$$0.45$$400$$500$$600$$700$$800$Delay (ns)Area ($\mu
m^{2}$)BaselineCom AND [9]Com BoothNon Com Booth Figure 3: Area-delay profiles
for the three competing commutative designs for n=64. We also plot the
truncated Booth architecture without the compensation bits to recover
commutativity.

In Figure 3 we present complete area-delay profiles for the competing 64-bit
multiplier implementations. Across the complete delay spectrum the truncated
Booth multiplier demonstrates roughly constant area reduction when compared
against the truncated AND array.

To understand the penalty we must incur to recover commutativity, we also
synthesize the 64-bit truncated Booth array without the additional
compensation bits described in Section 3.1. As we can see in Figure 3, the
area difference between the commutative and non-commutative truncated Booth
implementations is minimal across the delay spectrum. At worst we pay a 2.5%
area penalty.

###  4.2 Formal Verification

For multiplier implementations beyond 16-bit, formal verification becomes
challenging as the number of inputs exceeds what can be simulated.
Furthermore, the verification of custom multiplier implementations is
particularly challenging due to the circuit complexity, leading to bespoke
tools [22, 23] and methods [24, 25].

In this work, we deploy the S-C-Rewriting method [26, 27] built on the ACL2
theorem prover [28], supported by the Glucose SAT solver. We use the tool to
prove that the output, out, of the Verilog code implementing a truncated Booth
multiplier satisfies the following lemma:

⬇

mult = a[n-1:0]*b[n-1:0]

lsbs = mult[ n-1:0]

msbs = mult[2*n-1:n]

lemma (lsbs==0) ? out==msbs

: 0<=out-msbs<=1

Where a and b are $n$-bit, and mult is $2n$-bit wide unsigned bit-vectors
representing integer values. This lemma guarantees that out is a faithful
rounding. We also use the same tool to prove commutativity of the truncated
Booth multiplier.

TABLE V: ACL2 runtimes for proving that the truncated booth multiplier implements a faithful rounding and is commutative. The dash indicates a proof which did not converge. $n$ | Faithful (sec) | Commutative (sec)
---|---|---
4 | 3 | 0.6
6 | 4 | 0.6
16 | 7 | 0.7
24 | 44 | 0.7
32 | 63 | 0.9
36 | 117 | 1.0
42 | 835 | 1.1
64 | – | 2.0

We prove the two properties for a range of bitwidths $n$ and present the proof
runtimes in Table V. Unfortunately, as the bitwidth $n$ increases, the proof
of faithful rounding runtimes grow exponentially, meaning we are unable to
prove the correctness of the 64-bit truncated Booth multiplier.

##  5 Conclusion

This paper provides the first implementation of a commutative truncated Booth
multiplier, that produces a faithfully rounded result. We first described how,
for minimal circuit area overhead, we can recover commutativity, via the
introduction of a small number of compensation bits. We then proved exact
bounds on the maximal error due to Booth array truncation and used these
bounds to calculate the maximum number of columns which can be truncated.
Lastly, we described how the addition of a constant can compensate for the
error induced by truncation. We synthesized a number of faithfully rounded
multiplier implementations and were able to reduce circuit area by up to 13%
and reduce power consumption by up to 12% when compared to the state of the
art. Using an ACL2 based verification tool, we were able to prove the
correctness of the commutative truncated Booth multipliers up to 42 bits.

Future work will look to generalize the results here to arbitrary Booth
encoding radices, e.g. Booth Radix-8. A further generalization will consider
different error thresholds, as opposed to the faithful rounding considered
here. We will also address the limitations of our verification, exploring
proof decomposition techniques. Lastly, an approach in [9] can be used to
incorporate these multiplier components into larger hardware designs, for
example a floating-point multiplier.

## References

  * [1] C. S. Wallace, “A Suggestion for a Fast Multiplier,” _IEEE Transactions on Electronic Computers_ , vol. EC-13, no. 1, 1964.
  * [2] L. Dadda, “Some schemes for parallel multipliers,” _Alta frequenza_ , vol. 34, pp. 349–356, 1965.
  * [3] R. Zimmermann and D. Q. Tran, “Optimized synthesis of sum-of-products,” in _Conference Record of the Asilomar Conference on Signals, Systems and Computers_ , vol. 1, 2003.
  * [4] M. D. Ercegovac and T. Lang, _Digital arithmetic_. Elsevier, 2004.
  * [5] H. A. Huang, Y. C. Liao, and H. C. Chang, “A self-compensation fixed-width booth multiplier and Its 128-point FFT applications,” in _Proceedings - IEEE International Symposium on Circuits and Systems_ , 2006.
  * [6] Y. H. Chen, T. Y. Chang, and R. Y. Jou, “A statistical error-compensated Booth multipliers and its DCT applications,” in _IEEE Region 10 Annual International Conference, Proceedings/TENCON_ , 2010.
  * [7] V. G. Oklobdzija, D. Villeger, and S. S. Liu, “A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach,” _IEEE Transactions on Computers_ , vol. 45, no. 3, 1996.
  * [8] R. Zimmermann, “Datapath synthesis for standard-cell design,” in _Proceedings - Symposium on Computer Arithmetic_ , 2009.
  * [9] T. A. Drane, T. M. Rose, and G. A. Constantinides, “On the systematic creation of faithfully rounded truncated multipliers and arrays,” _IEEE Transactions on Computers_ , vol. 63, no. 10, 2014.
  * [10] K. J. Cho, S. M. Lee, S. H. Park, and J. G. Chung, “Error bound reduction for fixed-width modified booth multiplier,” in _Conference Record - Asilomar Conference on Signals, Systems and Computers_ , vol. 1, 2004.
  * [11] H. J. Ko and S. F. Hsiao, “Design and application of faithfully rounded and truncated multipliers with combined deletion, reduction, truncation, and rounding,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 58, no. 5, 2011.
  * [12] M. J. Schulte and E. E. Swartzlander, “Truncated multiplication with correction constant [for DSP],” in _Proceedings of IEEE Workshop on VLSI Signal Processing VI, VLSISP 1993_ , 1993.
  * [13] S. S. Kidambi and P. El-Guibaly, “Area-efficient multipliers for digital signal processing applications,” _IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing_ , vol. 43, no. 2, 1996.
  * [14] E. J. King and E. E. Swartzlander, “Data-dependent truncation scheme for parallel multipliers,” in _Conference Record of the Asilomar Conference on Signals, Systems and Computers_ , vol. 2, 1998.
  * [15] N. Petra, D. De Caro, V. Garofalo, E. Napoli, and A. G. M. Strollo, “Designof fixed-width multipliers with linear compensation function,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 58, no. 5, 2011.
  * [16] R. Michard, A. Tisserand, and N. Veyrat-Charvillon, “Carry prediction and selection for truncated multiplication,” in _2006 IEEE Workshop on Signal Processing Systems Design and Implementation, SIPS_ , 2006.
  * [17] K. E. Wires, M. J. Schulte, and J. E. Stine, “Variable-correction truncated floating point multipliers,” in _Conference Record of the Asilomar Conference on Signals, Systems and Computers_ , vol. 2, 2000.
  * [18] B. Orloski, S. Coward, and T. Drane, “Automatic Generation of Complete Polynomial Interpolation Design Space for Hardware Architectures,” in _Proceedings of the 28th Asia and South Pacific Design Automation Conference_. Tokyo: Association for Computing Machinery, 2023, pp. 573–578.
  * [19] D. De Caro, E. Napoli, D. Esposito, G. Castellano, N. Petra, and A. G. Strollo, “Minimizing Coefficients Wordlength for Piecewise-Polynomial Hardware Function Evaluation With Exact or Faithful Rounding,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 64, no. 5, 2017.
  * [20] A. A. Karatsuba and Y. P. Ofman, “Multiplication of many-digital numbers by automatic computers,” in _Doklady Akademii Nauk_ , vol. 145, no. 2, 1962, pp. 293–294.
  * [21] E. Ustun, I. San, J. Yin, C. Yu, and Z. Zhang, “IMpress: Large Integer Multiplication Expression Rewriting for FPGA HLS,” in _2022 IEEE 30th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , 2022, pp. 1–10.
  * [22] A. Koelbl, R. Jacoby, H. Jain, and C. Pixley, “Solver technology for system-level to RTL equivalence checking,” in _Proceedings -Design, Automation and Test in Europe, DATE_ , 2009.
  * [23] J. R. Burch, “Using BDDs to verify multipliers,” in _Proceedings - Design Automation Conference_ , 1991.
  * [24] R. Kaivola and N. Narasimhan, “Formal verification of the Pentium®4 floating-point multiplier,” in _Proceedings -Design, Automation and Test in Europe, DATE_ , 2002.
  * [25] D. Kaufmann, A. Biere, and M. Kauers, “Verifying large multipliers by combining SAT and computer algebra,” in _Proceedings of the 19th Conference on Formal Methods in Computer-Aided Design, FMCAD 2019_ , 2019.
  * [26] M. Temel, A. Slobodova, and W. A. Hunt, “Automated and Scalable Verification of Integer Multipliers,” in _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 12224 LNCS, 2020.
  * [27] M. Temel and W. A. Hunt, “Sound and Automated Verification of Real-World RTL Multipliers,” in _Proceedings of the 21st Formal Methods in Computer-Aided Design, FMCAD 2021_ , 2021.
  * [28] M. Kaufmann and J. S. Moore, “ACL2: An industrial strength version of Nqthm,” in _COMPASS - Proceedings of the Annual Conference on Computer Assurance_ , 1996.


# An explorative study on how human-robot interaction is taken into account by
robot developers in praxis

Doris Aschenbrenner<EMAIL_ADDRESS>0000-0002-3381-1673 TU Delft
IDELandbergstraat 15DelftNetherlands2628 CE ,  Danielle van Tol  TU Delft
IDEDelftNetherlands<EMAIL_ADDRESS>,  Pak Long Cheung  TU Delft
IDEDelftNetherlands<EMAIL_ADDRESS>and  Zoltan Rusak  TU Delft
IDEDelftNetherlands<EMAIL_ADDRESS>
(2021)

###### Abstract.

How is human-robot interaction considered within the development of new
robotic systems by practitioners? This study sets out to inquire, whether the
development teams of robotic products have been considering human factor
methods in their design and implementation process. We were specifically
interested in the non-verbal communication methods they were aiming to
implement, and how they have approached the design process for these. Although
valuable insights on tasks and communication needs during the different phases
of robot operation could be gathered, the results of this study indicate, that
the perspective of the human user or bystander is very often neglected and
that knowledge on methods for engineering human-robot interaction is missing.
The study was conducted with eleven development teams consisting of robot
manufacturers and students within a robot building course representing overall
68 individual participants.

human-robot interaction, human factor methods, design process, end-user study

††copyright: acmcopyright††journalyear: 2021††doi: no doi††conference: HRI
’21: Exploring Applications for Autonomous Non-Verbal Human-Robot Interactions
at the ACM/IEEE International Conference on Human Robot Interactions; March
08–12, 2021; Virtual Conference††booktitle: HRI ’21: ACM/IEEE International
Conference on Human Robot Interactions††ccs: Human-centered computing
Interaction design process and methods††ccs: Social and professional topics
Systems planning††ccs: Computer systems organization Robotics

##  1\. Introduction

Robotics research was for a long time majorly performed in the narrow domains
that could afford the high investments necessary to build capable robotic
systems (Goodrich et al., 2008). Thus, robots have been mainly applied for
areas like space exploration or within other hazardous environments, for
example, search and rescue applications. Here it was clear, that humans cannot
operate on their own and need some kind of mechanic assistant. Furthermore,
industrial robots have been developed for the production environment, in which
they take over automation tasks and were kept separate from the workers behind
safety fences. As robotics research has advanced, the field of “social robots”
for hospital or home environments has been opened. Here, the necessity to take
human safety and interaction into account is logical and have immersed into an
own field of study. Within the increasing amount of discussions on the “future
of work” (Lorenz et al., 2015), it becomes clear that there is a possible
future in which humans might work alongside intelligent machines and robots in
their daily work routine in a “hybrid intelligence” (Dellermann et al., 2019)
setting. But are the current systems designed so that they can meet this goal?
If they are not (yet), are at least the development teams aware of the
implications of human-centered approaches within robotic system development,
so this goal can be achieved? As already pointed out by Sheridan (Sheridan,
2016), there is still a principle gap between the human factors professionals
and the robotics engineers. Specifically in one of the “origin” fields of
robotics research, the production industry, there are many studies (Ludwig et
al., 2018) (Romero et al., 2016) that advocate for looking at the entire
socio-technical system and thus strengthening human factor aspects. The
consideration of human-robot interaction principles within the design of
robotic systems is highly relevant for guaranteeing i) high performance and
ii) high well-being of the involved humans. Thus, the explorative study
presented in this publication aims at finding out the following research
questions:

  * •

How do current robotics development teams approach the design challenge in
general?

  * •

Is there interaction with the target user group during development?

  * •

What do members of robotic development teams think of the user of their
system?

  * •

Which methods from human factor research are used?

  * •

Which kind of (verbal and non-verbal) interaction do they envision for their
product?

##  2\. Approach based on existing taxonomies

The research was conducted in two steps, which is displayed in Figure 1:
First, a questionnaire has been developed and sent out to companies and
students of a robotic development university course. Then, a round of
interviews was performed on the same target group.

Figure 1. Approach of this research

The first aspect was used to inquire on how and if the investigated methods
fit into the existing taxonomies discussed in the literature. We decided to
inquire basically into the theoretical models displayed in Figure 2, the
revised taxonomy of human-robot interaction from Yanco and Drury (Yanco and
Drury, 2004), and a self-developed phase model in Figure 3 which describes a
generic robot lifecycle.

Figure 2. Human robot interaction classification according to task model from
Sheridan (Sheridan, 1992)

Human tasks Plan, Teach, Monitor, Intervene, Learn

Figure 3. Lifecycle phase model for robot development

Lifecycle Phase 1: Design & Development, Phase 2: Initial installation, Phase
3,: Normal robot operation, Phase 4. Adjustment of robot, Phase 5: Failure
handling)

Concerning non-verbal communication, we used the questions displayed in Figure
4 to investigate the “means of interaction” that have been used within the
participant teams.

Figure 4. Communication input and output

##  3\. Questionnaire study

###  3.1. Experimental Design

The experiment was designed as a questionnaire with subjective reporting and
can yield both qualitative and quantitative results. The questionnaire has
been sent over a mailing list with robotic developers (small and medium-sized
companies, SMEs) that have received funding through a European cascade funding
and was distributed to an interdisciplinary course within TU Delft, the
“Robotics minor”, in which groups of students from four to five faculties
build a robot system from scratch together following an assignment of a paying
client from outside the university. The initial idea was to compare the
students with professional teams, as the student has gained basic training on
human factor methods, and with the professional teams, the status of existing
knowledge is unknown. Due to the low reply rate, a statistically significant
comparison was not feasible.

###  3.2. Experimental Procedure

The participants have been asked to fill out the questionnaire which will be
made available under http://smartfactoryresearch.com. The questionnaire
consists of four parts:

  1. (1)

Your project and team – statistical data on team composition and project
description

  2. (2)

The target user in your project – in order to identify and characterize user
groups following a self-developed phase model, combined with the task model
from Sheridan and the revised level of interaction taxonomy (all discussed
above)

  3. (3)

Human-Robot Interaction in your project – based on the identified user groups,
this part of the questionnaire aims at inquiring on the existing knowledge of
the user and their interaction and communication methods

  4. (4)

User interaction research/ design in your project – this part inquires further
on the applied human factor methods and the existing knowledge of these
approaches

###  3.3. Results

####  3.3.1. Participants

It was very complicated to receive feedback from companies, after numerous
attempts we merely were able to get four filled-out questionnaires. Together
with the student groups, we were able to analyze eleven feedback
questionnaires. In total, there are 68 people involved in the development
teams, the mean amount of people involved per group is 6.2 where the smallest
groups reported three team members and the largest group consists of sixteen
members. Gender balance: In the SME group we found two teams with equally
distributed gender and two male-dominated teams. In the student group, there
were two teams with only men, the others were male-dominated. Discipline
balance: Both groups consist mainly of software-engineers (19 team members
from 68) and the user experience designer underrepresented (1 from 68 team
members). Age balance: Both groups were constituted by young teams (age under
30), which also was the case for the answering company teams.

####  3.3.2. Main user

Based on the lifecycle phase model from Figure 3, we will present a list of
user groups that have been mentioned the most. Phase 1 (Design & Development):
“development team”, “software engineers”, “us”, or “$companyname staff”,
whereas $companyname is used here as a placeholder for the different mentioned
company names. Phase 2 (Initial installation): “development team”, “software
engineers”, “us”, or “$companyname staff”. Phase 3 (Normal robot operation):
The main user mentioned were unspecific like “client”, “robot operator”, or
“$companyname employees”, but some were more specific like “medical patients”
or “assembly line workers”. Phase 4 (Adjustment of robot): “software
engineers”, “robotics development staff”, “tech support worker”, “development
team client”. Phase 5 (Failure handling): “tech support workers”, “Mechanical
engineers at $company”, or / “$company maintenance technicians”.

####  3.3.3. Identified human tasks

In Figure 5 the summary of the identified tasks of the human (Sheridan) are
combined with the reported interaction role of human and robot (Yanco and
Drury). Interesting is, that the human seems to be active in all phases, but
least in the third phase (normal operation). Only in this phase, the human has
been considered “inactive” by some participants. The robot is mainly active in
the third phase, which is logical, but interesting enough the robot also
should take a role in the other phases. The user appears to mainly “Plan” in
phase 1, mainly “Teach” in Phase 2, “Monitor” in Phase 3, and “Intervene” in
Phase 5.

Figure 5. Analysis results on task type (Sheridan) and interaction type (Yanco
and Drury) with respect to the different phases of the robot lifecycle. $y$ is
the absolute number of mentions

####  3.3.4. Means of interaction

Figure 6 provides an overview of the mentioned input variants and Figure 7
presents the output means. The main mentioned interaction for the Input were
physical buttons (6) and controller (6), and as the main output means the
robot’s movement (9) and the screen (7) has been mentioned.

Figure 6. Means of interaction mentioned by project feedback (multiple answers
have been possible) for input. $y$ is the absolute number of mentions Figure
7. Means of interaction mentioned by project feedback (multiple answers have
been possible) for output. $y$ is the absolute number of mentions

####  3.3.5. Communication needs

As mentioned above, the questionnaire asks the participant to mention their
most important user per phase and then extract their three main important user
groups. We wanted to find out the communication needs and the required human
skills by asking a question on the tasks that the target user groups are
performing with the robotic system. We decided to group the response options
according to situation awareness / legibility, add failure identification, and
leave an open field for free annotations (other). The results are displayed in
Figure 8. Interestingly enough (but maybe motivated by the questionnaire
design), the own development team was mentioned six times as being part of the
three main important user groups, this is omitted in Figure 8. Furthermore,
empty entries have been removed. Only one group mentioned themselves as the
user with the highest priority, which appears a strange thing as they have
been clearly developing a robot that was to be used not by themselves. The
most relevant information need seems to be to identify the current state. The
feedback to the “other” category was partially quite verbose, mentioning
various different tasks that the users should be able to fulfill. Some
examples on the replies for the “other” tasks are: “Benefit from the assistive
applications of the robot”, “Teach the task to the robot”, “Robot does medical
procedures on this group”, ”Manually control the robot to move around a
beach.”, “Identify the current state of the robot (location,
active/inactive)”, “Create a map that contains the locations of cigarette
butts in the beach.”. Furthermore, we asked an additional question
specifically about the skills that the operators need to have. It is
interesting that, according to the responses, the end-users mainly need to
have “no” skills within phase 3, and already, for phase 4, possess relatively
high knowledge (like “robotic development”), although minor adjustments will
be part of every robot routine.

Figure 8. Communication needs from the human side

####  3.3.6. Applied human factor methods

Next to this, we inquired upon the responsibilities of the highest important
user group and the goal of the human-robot interaction and displayed the
results in Figure 9. We wanted to know, which human factor methods have
already been applied within the interaction with the identified most important
target user groups (Figure 10). Five teams answered the questions on whether
there are any bystanders with “yes, but we do not take them into account”,
four groups answered with “Yes, we take them into account”, and two groups
answered with “No, there are no bystanders”. Furthermore, we asked, whether
there already have been any interaction problems identified. Here, six groups
answered “No”, which, from an HRI research perspective, might be due to the
fact that there has not been enough interaction with the target user group
yet. Additionally, we asked whether they think they need to know more about
their users. Here, four groups answered with “No”, and seven groups answered
with “Yes”. We also asked whether the group, after finishing the
questionnaire, would like to know more about their users. Here, only one group
answered with “No” and the other ten answered with “Yes”.

Figure 9. Goal of human robot interaction Figure 10. Human factor methods
applied so far (please note, that the six times mentioned own team as a target
user group is part of the presented data)

##  4\. Interviews study

###  4.1. Experimental Design

We prepared a semi-structured interview, the leading questions can be found in
Figure 11. They consist of four blocks: First, we wanted to know more about
their target users, after which we discussed how they approached the target
users, then we asked about the design of the interaction, and finally on the
skills that the human needs to operate the system.

Figure 11. Structured interview guideline

###  4.2. Experimental Procedure

Unfortunately, none of the SME participants were interested in an interview,
so this study is limited to the seven student teams. Within the education
program, there have been interviews with the entire team of each of the seven
student groups. The interviews took between 15 and 25 minutes and were
conducted via Zoom and recorded. Afterward, the discussion was summarized in
writing. The measured data were qualitative self-reporting on estimations and
beliefs. It was tested how much the developer teams know about their user
group and which methodology they applied.

###  4.3. Results

We present a summary of the findings in the following list:

  * •

Not every client puts importance on the user of the robot. When the client
does not specifically request good usability, an engineering team does not
automatically think about that themselves. Also, the client is in some
projects seen as the end-user with a strong opinion on the usage without
actually being the person who is going to use it.

  * •

All groups want the robot to be intuitive and think that the user does not
need any specific skills, but when delving deeper into it, there are always
ways of interaction and communication that the user has to understand or
learn.

  * •

In the view of the some developers, the projects primarily had the goal of a
proof of concept on the technological aspect. These types of projects tend not
to take the user into account, but the user aspect might still have a large
impact on the feasibility of the system (if it works but no one wants to use
it, then it cannot be successful).

  * •

It is important to have some sort of illustration or storyboard that
illustrates the envisioned usage so that everyone sees it the same way and
that all points of interaction are taken into account.

Specifically asking on communication and skills for the humans, the following
quotes have been gathered:

  * •

“They don’t need any additional skills, although some training or ‘play time’
will help the delivery workers to better grasp the movement of the robot and
how it steers.”

  * •

“The operator of the robot does not need additional skills. Although a little
bit of understanding of how the robot moves can be beneficial for extra
safety.”

  * •

“For the people that services the robot, there should be a guide so they know
which panels to remove so you can reach the needed parts. We also want to
incorporate error codes and intuitive language (if the robot flashes red
light, something is wrong)”

  * •

“Not much. Some basic controller skills should be enough. (it’s as simple as
getting it out, putting two poles in the ground, drive it to the general
direction and let it do its thing).”

  * •

“When something goes wrong, an error will be displayed on the screen and the
robot will shut down along with a description of how to solve it on the UI
(e.g. ‘we detect an extreme angle, please put the robot on a flat surface). If
the error persists after restarting, the UI will display ‘Contact engineers’.”

  * •

“Apart from the specific setup (put in empty capsules and take out full
capsules) and some instructions on how the robot is supposed to function, what
you should do to prepare it, and what tasks need to be performed to make it
ready for the next use.”

##  5\. Summary and discussion

###  5.1. Research questions

First of all, the initially mentioned research questions should be answered
based on the knowledge acquired from the questionnaire and interviews:

####  5.1.1. How do current robotics development teams approach the design
challenge in general?

Based on the received feedback, it can be found, that most teams consider
their robot as fully autonomous because it does not rely on (permanent) human
input. Although they might succeed in the more technical aspects of the design
challenge, they do not consider that human-robot interaction is a necessary
field that needs to be regarded. This can be supported by the fact, according
to the feedback, the robot should be “active” during ”normal operation” of the
robot (Phase 3), whereas the human should mainly be ”supportive” or ”inactive”
(Figure 19). It can also be supported by the written feedback we got from
people who were directly asked by the research team to fill out the
questionnaire – either they considered themselves to be merely component
developers, did not have time, stated that their robotic system is “too
autonomous” and thus the questions would not apply, or did not respond at all.
Interestingly, the results from the questionnaires but also the interviews
show, that it is possible for all groups to identify a relevant user after
asking several consequent questions, as the adjustment phase (Phase 4)
requires attention from a human team which appears to be different from the
maintenance and troubleshooting state (Phase 5), who are no experts in
robotics. For these target groups the interaction with the robot should be
“easy” and “intuitive”, as it can be derived from the interviews, so this is a
relevant design challenge.

####  5.1.2. Is there interaction with the target user group during
development?

Only three groups spoke with one or more representatives of the target user
group with the highest priority (which includes the group which had positioned
themselves as the most important user group). Thus it can be concluded, that
it is very little or no interaction between the development team and the
target user group. Especially, as after filling out the questionnaire, seven
out of eleven groups had the feeling that they need to know more about their
target user and ten out of eleven groups said, that it would improve the
result of their project if they knew more about the target user.

####  5.1.3. What do members of robotic development teams think of the user of
their system?

From the results of the research, it can be concluded that the development
teams as a majority, do not care about the end-user. The most representative
quote for this mindset was the feedback from a company team, which stated that
the user’s responsibilities were “To not disturb the robot during operation”
(Figure 9). As the specific application is the performance of medical
procedures without another human person present, the interaction design is way
more important than this specific answer implies.

####  5.1.4. Which methods from human factor research are used?

This is answered in the findings of Figure 10: There have been no advanced
methods used, like a questionnaire or quantitative user studies, in order to
investigate further into the human factors components of the highest priority
user. Two groups used a walkthrough method, but the majority did not.
Additional methods have been mentioned which are rather applied in the
contextual inquiry phase of a project but not during development. This might
also explain the finding that the majority of the teams did not encounter
interaction problems.

####  5.1.5. Which kind of (verbal and non-verbal) interaction do they
envision for their product?

The participants in the above-mentioned user research have been asked several
times to mention the skills that the user needs to perform during the usage of
the robot. The skills necessary for interaction with the user in Phase 3 are
five times “None” and then “Monitoring”, “Communication”, “human interaction
task”, “use interface”, “Assessing outcomes of tasks”, and “Transport the
robot”. The task model from Sheridan is applied, which showed that the human
is in nearly all phases quite active (least in phase 3) and that “Plan” tasks
are dominant in phase 1 and phase 4, “Teach” tasks are dominant in Phase 2,
“Monitor/Perform” is dominant in Phase 4, “Intervene” in Phase 5, and “Learn”
is underrepresented. Within the analysis of the most important user groups,
the question is asked again in a different way, the most important information
appears to be “identify current state” (23 mentions in Figure 8), followed by
“identify past state” (9 mentions) and “others” (9 mentions). These findings
are summarized in Figure 12, which displays the most relevant tasks for each
phase and the interaction types.

Figure 12. Model on which tasks are mostly relevant in which phase

###  5.2. Limitations

Due to the low response rate of the questionnaires from the side of companies,
these results can only be considered preliminary. The student groups that have
been interviewed as well were very informative, but it could be argued that
older participants would have already had more project experience and thus
would not neglect the needs of the users. What is indeed hard to measure is
the high amount of people that did not want to fill out a questionnaire
because they did not feel that their robotic project involved human-robot
interaction (although the researcher did not share this impression based on
their project presentations).

###  5.3. Conclusion

In general, it can be said and proved by the results from this investigation,
that the human-robot interaction design is neglected by the development teams,
who are majority male and computer-scientists. It is important to waken this
sensibility in order to be able to develop robot systems that can be
successful on the market instead of having systems that can only be used by
people with a rare special background.

Neglecting the end-user within the design process is especially problematic as
the identified highest priority user groups do not have a high technology
affinity and are partly conservative. There have been two direct quotes in
which groups mentioned that their robotic system is causing the users to be
afraid of losing their jobs because they think that they are replaced by
robots. Designing a highly complex system for this kind of user group will be
very challenging without the proper interaction design knowledge.

###### Acknowledgements.

The research presented here has received funding within the RobMoSys project
H2020-EU.2.1.1. and ID 732410.

## References

  * (1)
  * Dellermann et al. (2019) Dominik Dellermann, Philipp Ebel, Matthias Söllner, and Jan Marco Leimeister. 2019.  Hybrid intelligence.  _Business & Information Systems Engineering_ 61, 5 (2019), 637–643.
  * Goodrich et al. (2008) Michael A Goodrich, Alan C Schultz, et al. 2008\.  Human–Robot Interaction: A Survey.  _Foundations and Trends in Human–Computer Interaction_ 1, 3 (2008), 203–275.
  * Lorenz et al. (2015) Markus Lorenz, Michael Rüßmann, Rainer Strack, Knud Lasse Lueth, and Moritz Bolle. 2015\.  Man and machine in industry 4.0: How will technology transform the industrial workforce through 2025.  _The Boston Consulting Group_ 2 (2015).
  * Ludwig et al. (2018) Thomas Ludwig, Christoph Kotthaus, Martin Stein, Volkmar Pipek, and Volker Wulf. 2018.  Revive old discussions! Socio-technical challenges for small and medium enterprises within industry 4.0. In _Proceedings of 16th European Conference on Computer-Supported Cooperative Work-Exploratory Papers_. European Society for Socially Embedded Technologies (EUSSET).
  * Romero et al. (2016) David Romero, Peter Bernus, Ovidiu Noran, Johan Stahre, and Åsa Fast-Berglund. 2016\.  The operator 4.0: human cyber-physical systems & adaptive automation towards human-automation symbiosis work systems. In _IFIP international conference on advances in production management systems_. Springer, 677–686.
  * Sheridan (1992) Thomas B Sheridan. 1992\.  _Telerobotics, automation, and human supervisory control_.  MIT press.
  * Sheridan (2016) Thomas B Sheridan. 2016\.  Human–robot interaction: status and challenges.  _Human factors_ 58, 4 (2016), 525–532.
  * Yanco and Drury (2004) Holly A Yanco and Jill Drury. 2004.  Classifying human-robot interaction: an updated taxonomy. In _2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No. 04CH37583)_ , Vol. 3. IEEE, 2841–2846.


# Joseph Wolstenholme and the Trigonometry of Tetrahedra

Daniil Rudenko

###### Abstract.

“Mr Wolstenholme was a very old gentleman who came every summer to stay with
us. He was brown; he had a beard and very small eyes in fat cheeks; and he
fitted into a brown wicker beehive chair as if it had been his nest. He used
to sit in this beehive chair smoking and reading. He had only one
characteristic – that when he ate plum tart he spurted the juice through his
nose so that it made a purple stain on his grey moustache. This seemed enough
to cause us perpetual delight. We called him “The Woolly One”. By way of
shading him a little I remember that we had to be kind to him because he was
not happy at home; that he was very poor, yet once gave Thoby half a crown;
that he had a son who was drowned in Australia; and I know too that he was a
great mathematician. He never said a word all the time I knew him. But he
still seems to me a complete character; and whenever I think of him I begin to
laugh.” – Virginia Woolf, Moments of Being.

The trigonometry of tetrahedra remains a relatively unexplored and complex
area compared to the well-established and extensively studied trigonometry of
triangles. While working on Hilbert’s third problem, I discovered a new fact
in the trigonometry of a tetrahedron: the identity

(1)
$\displaystyle\bigl{[}e^{i\Omega_{1}},e^{i\Omega_{2}},e^{i\Omega_{3}},e^{i\Omega_{4}}\bigr{]}=[P_{1},P_{2},P_{3},P_{4}],$

where $[a,b,c,d]=\frac{(a-b)(c-d)}{(a-c)(d-b)}$ is the cross-ratio, $P_{i}$
are the perimeters of faces, and $\Omega_{i}$ are the spherical angles of a
Euclidean tetrahedron ([3, Corollary 1.2]). This statement has such a
“classical” flavor that I kept wondering if it had been discovered long before
my work, see https://mathoverflow.net/q/336464 for the discussion. The
literature related to the trigonometry of tetrahedra is extensive, yet I was
unable to find anything resembling my result anywhere in the published texts.
I was at the point of giving up when I came across the name Joseph
Wolstenholme in [2]. Wolstenholme worked on the trigonometry of tetrahedra in
the late 19th century. The mathematical community failed to react to his
results, likely because they were never published in a peer-reviewed journal
and appeared only as problems in the British periodical The Educational Times.
I am going to resist the temptation to state Wolstenholme’s theorem at the
onset, and will begin instead with some historical context. In doing so, I
hope to put this mesmerizing story in perspective.

##  1\. Joseph Wolstenholme and the trigonometry of tetrahedra

Joseph Wolstenholme was born in 1829 in Eccles near Salford, Lancashire,
England. He graduated from Cambridge in 1850 and was elected a fellow of
Christ’s College in 1852. For the next twenty years he served as an examiner
for the Mathematical Tripos and became rather well-known as a creator of
ingenious mathematical problems. At the age of 40, Wolstenholme had to resign
the fellowship because he wished to get married, and fellows at Cambridge
University were historically not allowed to marry due to the institution’s
medieval clerical origins, where celibacy was required. After a few years of
poverty, he settled as the first professor of mathematics at the newly created
Royal Indian Engineering College. Shortly after turning 60, he was forced to
retire because of a disagreement about the level of abstraction appropriate
for a mathematics course aimed at engineers. Joseph Wolstenholme passed away
in 1891, leaving a widow and four sons.

In the last decade of his life, Wolstenholme became increasingly interested in
the trigonometry of tetrahedra. He published his observations as problems in
the mathematical section of the monthly journal The Educational Times, see the
database woollymathematics.com.

Figure 1. Problem 7425. Educational Times, Vol. 36, August 1883.

Since his years in Cambridge, Wolstenholme had been one of the most active
contributors to the journal. The sequence of problems relevant to us begins at
Problem 7425, see Fig. 1 (for some reason, the same notation is used for the
lengths of edges and dihedral angles). This problem caught my attention,
because it can be interpreted and solved using the connection with rational
elliptic surfaces from [3] as both conditions $AB+AC=DB+DC$ correspond to the
existence of an extra reducible fiber, resulting in the vanishing of both
period maps on a root of the $D_{6}$-lattice.

A few months later, Problem 7509 was published (Fig. 2), which can be viewed
as a ‘soft’ version of $(\ref{FormulaCrossRatios})$.

Figure 2. Problem 7509. Educational Times, Vol. 36, November 1883.

Figure 3. Examples for Practice in the Use of Seven-figure Logarithms, p. 41.

In the course of the next decade, 16 more problems appeared in the journal,
all of which were related to the trigonometry of tetrahedra. In 1888, shortly
before retiring, Wolstenholme published a book called Examples for Practice in
the Use of Seven-figure Logarithms [5]. Traditionally, students were taught to
use logarithms in computations on examples from the trigonometry triangles.
Wolstenholme discusses 225 similar examples based on tetrahedra! To these
examples, he adds “remarks,” often special cases of the theorems he had
discovered. For example, on p. 40 (Fig. 3) Wolstenholme presents ten
tetrahedra, their lengths of edges, plain and dihedral angles, and volumes.

In November 1888, Wolstenholme sought to publish a note “Certain Algebraic
Results Deduced from the Geometry of the Quadrangle and Tetrahedron” but it
was rejected by the referees. In the next three years, another three
‘tetrahedral’ problems appeared in the journal. Wolstenholme passed away in
November 1891.

##  2\. Wolstenholme’s Theorem

In June 1897 the following problem (Fig. 4) appeared in The Educational Times
authored by George Richardson, a friend of Wolstenholme.

Figure 4. Problem 13521. Educational Times, Vol. 50, June 1897.

Here is the statement of the theorem in more standard notation.

######  Theorem 1 (J. Wolstenholme, 1889).

Let $T$ be a Euclidean tetrahedron with lengths of edges $l_{ij}$ and dihedral
angles $\alpha_{ij}.$ Then there exist number $\lambda\in\mathbb{R}$ such that

$\displaystyle\frac{\cos(\alpha_{12}+\alpha_{34})}{(l_{12}+l_{34})^{2}+\lambda}=\frac{\cos(\alpha_{12}-\alpha_{34})}{(l_{12}-l_{34})^{2}+\lambda}=\frac{\cos(\alpha_{13}+\alpha_{24})}{(l_{13}+l_{34})^{2}+\lambda}$
$\displaystyle=$
$\displaystyle\frac{\cos(\alpha_{13}-\alpha_{24})}{(l_{13}-l_{24})^{2}+\lambda}=\frac{\cos(\alpha_{14}+\alpha_{23})}{(l_{14}+l_{23})^{2}+\lambda}=\frac{\cos(\alpha_{14}-\alpha_{23})}{(l_{14}-l_{23})^{2}+\lambda}.$

It took me some time to notice that Theorem 1 is equivalent to (1). Indeed,
Theorem 1 is equivalent to the identity

(2)
$\displaystyle[\cos(\alpha_{14}-\alpha_{23}),\cos(\alpha_{13}-\alpha_{24}),\cos(\alpha_{12}-\alpha_{34}),\infty]=[(l_{14}-l_{23})^{2},(l_{13}-l_{24})^{2},(l_{12}-l_{34})^{2},\infty].$

Notice that

$\Bigl{[}\frac{a+a^{-1}}{2},\frac{b+b^{-1}}{2},\frac{c+c^{-1}}{2},\infty\Bigr{]}=[1,ab,ac,bc],$

so

$[\cos(\alpha_{14}-\alpha_{23}),\cos(\alpha_{13}-\alpha_{24}),\cos(\alpha_{12}-\alpha_{34}),\infty]=\bigl{[}e^{i\Omega_{1}},e^{i\Omega_{2}},e^{i\Omega_{3}},e^{i\Omega_{4}}\bigr{]}.$

Similarly,

$\bigl{[}a^{2},b^{2},c^{2},\infty]=[0,a+b,a+c,b+c],$

so

$[(l_{14}-l_{23})^{2},(l_{13}-l_{24})^{2},(l_{12}-l_{34})^{2},\infty]=[P_{1},P_{2},P_{3},P_{4}].$

We conclude that (2) coincides with (1).

Theorem 1.1 from [3] implies other identities of cross-ratios, for instance,

$\bigl{[}e^{i\Omega_{1}},e^{i\Omega_{2}},e^{i\Omega_{3}},1\bigr{]}=[P_{1},P_{2},P_{3},0].$

It is not hard to see that the full set of cross-ratio invariants obtained
from [3, Theorem 1.1] defines the tetrahedron up to an isometry, so [3,
Theorem 1.1] is stronger than Theorem 1.

I recently obtained a copy of Wolstenholme’s note for the LMS, from which it
is clear that in 1888 he had already discovered a special case of Theorem 1
for a tetrahedron with the sum of areas of faces $123$ and $234$ equal to the
sum of areas of faces $134$ and $124.$ For such tetrahedra the statement of
the theorem simplifies since $u^{\prime}=0.$

A few months after Problem 13521 another problem appears in The Educational
Times with the same theorem. Here, the statement is followed by a comment by
Joseph Wolstenholme, see Fig. 5.

Figure 5. Problem 13605. Educational Times, Vol. 50, October 1897.

I remain curious about the specific connection to the theory of elliptic
functions that Wolstenholme had in mind. My best guess is that he proposed
using elliptic functions to make the statement of Theorem 1 look similar to
the Law of Sines by getting rid of the constant $k.$ I cannot find any
connection between that and an elliptic surface corresponding to the
tetrahedron, so it seems to be “one of those dazzling coincidences that
logicians loathe and poets love.”

##  3\. The ‘Woolly One’

We have another perspective on the years Wolstenholme spent working on
tetrahedral trigonometry. Leslie Stephen, his close friend from Cambridge,
used to invite him to spend summers with his family at St. Ives. In 1895
Leslie Stephen wrote in his autobiographical Mausoleum Book, [4, p.79]:“I
think especially of poor old Wolstenholme, called ’the woolly’ by you
irreverent children, a man whom I had first known as a brilliant mathematician
at Cambridge, whose Bohemian tastes and heterodox opinions had made a
Cambridge career inadvisable, who tried to become a hermit at Wastdale. He had
emerged, married an uncongenial and rather vulgar Swiss girl, and obtained a
professorship at Cooper’s Hill. His four sons were badly brought up: he was
despondent and dissatisfied and consoled himself with mathematics and opium. I
liked him or rather was very fond of him, partly from old association and
partly because feeble and faulty as he was, he was thoroughly amiable and
clung to my friendship pathetically. His friends were few and his home life
wretched. … [We] had him stay every summer with us in the country. There at
least he could be without his wife.”

Figure 6. Back row left: Joseph Wolstenholme; middle row right: Virginia
Stephen (Woolf). St. Ives, ca. 1889.

Leslie Stephen’s daughter Virginia Woolf was born in 1882, and Wolstenholme
was her father’s summer guest during her childhood. He made an impression on
her, and she left a compelling child’s eye view of him in the autobiographical
essay A Sketch of the Past, [6]: “I name these three people because they all
died when I was a child. Therefore they have never been altered. I see them
exactly as I saw them then. Mr Wolstenholme was a very old gentleman who came
every summer to stay with us. He was brown; he had a beard and very small eyes
in fat cheeks; and he fitted into a brown wicker beehive chair as if it had
been his nest. He used to sit in this beehive chair smoking and reading. He
had only one characteristic – that when he ate plum tart he spurted the juice
through his nose so that it made a purple stain on his grey moustache. This
seemed enough to cause us perpetual delight. We called him “The Woolly One”.
By way of shading him a little I remember that we had to be kind to him
because he was not happy at home; that he was very poor, yet once gave Thoby
half a crown; that he had a son who was drowned in Australia; and I know too
that he was a great mathematician. He never said a word all the time I knew
him. But he still seems to me a complete character; and whenever I think of
him I begin to laugh.”

Joseph Wolstenholme became the prototype of Augustus Carmichael, [1, I, p.32],
the only character in To The Lighthouse whose talent is not questioned in the
novel. I find it astonishing that the powerful image of Carmichael was
inspired by Wolstenholme whom the writer observed throughout the entire
process of his discovery of the trigonometry of tetrahedra.

## References

  * [1] Q. Bell.  Virginia Woolf: a Biography. New York: Harcourt Brace Jovanovich, 1972.
  * [2] G. Richardson.  The Trigonometry of the Tetrahedron.  The Mathematical Gazette, 2(32):149–158, 1902.
  * [3] D. Rudenko.  Rational elliptic surfaces and the trigonometry of tetrahedra.  Invent. Math., 227(1):211–246, 2022.
  * [4] L. Stephen.  Sir Leslie Stephen’s Mausoleum Book.  Clarendon Press, 1977.
  * [5] J. Wolstenholme.  Examples for Practice in the Use of Seven-figure Logarithms.  Macmillan and Co., 1888.
  * [6] V. Woolf.  Moments of Being: Unpublished Autobiographical Writings. New York: Harcourt Brace Jovanovich, 1976.