We give 12 mathematical puzzles (and their solutions) that were presented at a special session in honor of Sol Golomb at the 2017 ITA meeting in San Diego. Some are “well known,” and the very first one is a famous result due to Golomb.

Many applications of fast Fourier transforms (FFTs), such as computer tomography, geophysical signal processing, high-resolution imaging radars, and prediction filters, require high-precision output. An error analysis reveals that the usual method of fixed-point computation of FFTs of vectors of length 2/sup l/ leads to an average loss of l/2 bits of precision. This phenomenon, often referred to as computational noise, causes major problems for arithmetic units with limited precision which are often used for real-time applications. Several researchers have noted that calculation of FFTs with algebraic integers avoids computational noise entirely. We combine a new algorithm for approximating complex numbers by cyclotomic integers with Chinese remaindering strategies to give an efficient algorithm to compute b-bit precision FFTs of length L. More precisely, we approximate complex numbers by cyclotomic integers in Z[e(2/spl pi/i/2/sup n/)] whose coefficients, when expressed as polynomials in e(2/spl pi/i/2/sup n/), are bounded in absolute value by some integer M. For fixed n our algorithm runs in time O(log(M)), and produces an approximation with worst case error of O(1/M(2/sup n-2/-1)). We prove that this algorithm has optimal worst case error by proving a corresponding lower bound on the worst case error of any approximation algorithm for this task. The main tool for designing the algorithms is the use of the cyclotomic units, a subgroup of finite index in the unit group of the cyclotomic field. First implementations of our algorithms indicate that they are fast enough to be used for the design of low-cost high-speed/high-precision FFT chips.

Many applications of fast fourier transforms (FITs), such as computer-tomography, geophysical signal processing, high resohstion imaging radars, and prediction filters, require high precision output.The usual method of fixed point computation of FIT's of vectors of length 21 leads to an average loss of f/2 bits of precision.This phenomenon, often referredto as computationalnoise, causes major problems for arithmeticunits with limited precision which areoften used for real time applications.Severalresearchers have noted thatcalculation of ITT's with algebraic integersavoids computationalnoise entirely,see, e.g., [3].We will show thatcomplex numbers can be approximated accurately by cyclotomic integers, andcombine this idea with Chinese remainderingstmtegiesin the cyclotomic integersto, rotsgbly,give a O(b'" L log( L) ) algorithm to compute b-bit precision FIT's of length L. The firstpart of the paperwill describe the ~strategy,assuminggood approximationalgorithms;the second partpresentsanew, general,andefticient algorithmfor a~proximatingcomplex numbersby cyclotomic integersin Z[e2*'\2 ] whose coefficients, when expressedas polynomials in e'~ii'", are bounded in absolute value by some integer M. For fixed n our algorithm runs in time 0(log(A4)), and produces an approximation with worst case errorof 0(1/A42"-2'1).We will prove that this algorithm has optimal worst case emor by proving a correspondinglower bound on the worstcase errorof any approximationalgorithm for this task.Firstimplementationsof our algorithmsindicate thatthey are fast enough to be used for the design of low cost high speecfhigh precision FIT-chips.