lomont.org

(Also lomonster.com and clomont.com)

Publications, talks, and other writing


Publications

Introduction to Intel AVX
Apr 2011
This article (1.5MB PDF) is an introduction to Intel's Advanced Vector Extensions (AVX), written for their developer network. It covers the new registers, feature detection, assembler and compiler support, and an example using C++ intrisics. The appendix is a brief listing of all the AVX functions. Here is the C++ project described in the article (10MB zipfile).

 

A Simple Fast Fourier Transform
Jan 2010
This article (600kb PDF) presents a free, simple, fast Fast Fourier Transform in C#. It derives the code and explains the FFT in detail. It also presents a real to complex FFT useful for many engineering tasks which has the advantage of being twice as fast and uses half the resources as a traditional FFT. Source code is available in C# or HTML view.

 

Introduction to x64 Assembly
Dec 2009
This article (364kb PDF) is a thorough introduction to x64 assembly programming. It covers the register set including a little about MMX and various SSE versions. A few assemblers are listed with details on MASM (ML64.exe). Instruction basics are then followed by examples for interfacing with Visual Studio C/C++. One particularly useful part is details for calling conventions for x64 .

This article appears on the Intel Software Network.

 

Secure Channel Communications
Dec 2009
This article (138kb PDF) covers the basics of secure communication for video game programming, and appears in Game Programming Gems 8 [amazon.com].

 

Excel 2007 bug analysis
Oct 2007
This article (500kb PDF) details the Excel 2007 formatting bug. On initial release, entering =850*77.1 in a cell results in 10000, instead of the correct 65535. This article shows this bug is the result of porting 16-bit code to 32-bit code, and shows why exactly 12 values of the possible 9*10^18 64-bit floating-point values are affected. See this page for more details.

 

Subdivision Surfaces
July 2007
Subdivision surfaces are a method of representing smooth surfaces using a coarser polygon mesh, often used for storing and generating high detail geometry (usually dynamically) from low detail meshes coupled with various scalar maps. They have become popular in modeling and animation tools due to their ease of use, support for multi-resolution editing, ability to model arbitrary topology, and numerical robustness. This article presents enough detail about a specific subdivision method for direct implementation. The main result is a complete set of subdivision rules for geometry, texture, and other attributes. A second result is an overview of methods for fast generation and rendering.
Paper (254 KB PDF)
Appears in Games Programming Gems 7 [amazon.com]

 

Random number generation
July 2007
This article is an introduction to random number generators (RNGs). The main goal is to
present a starting point for programmers needing to make decisions about RNG choice
and implementation. A second goal is to present better alternatives for the ubiquitous
Mersenne Twister (MT). A final goal is to cover various classes of random number
generators, providing strengths and weaknesses of each.
Paper (136 KB PDF)
Appears in Games Programming Gems 7 [amazon.com]

 

Floating Point Tricks
Aug 2005
This survey article on floating points tricks covers many speedups possible using IEEE 754 floating-point values. These are useful for high-performance needs, like video game programming, ray-tracing, sound processing, etc. Items covered include very fast inverse square roots, square roots, base 2 logarithms, accurate and fast comparisons, and more. In particular the article is designed to teach programmers the details of how to derive their own such tricks when needed. This article was selected to appear in the book Games Programming Gems 6, to be published early 2006. See my software page for the source code.
Coming in Games Programming Gems 6, 2006.

 

Taming the Floating Point Beast
May 2005
Comparing floating point numbers for near equality has been a well discussed topic. This note covers the relevant points, and then introduces a few new, robust, high performance ways to do these comparisons. Applications range from realtime raytracing to video games to CAD systems. In particular branchless comparisons are designed which are faster than previous methods with no loss of numerical quality.
Soon to be placed on arxiv.

 

The Hidden Subgroup Problem - Review and Open Problems
Oct 2004
An overview of quantum computing and in particular the Hidden Subgroup Problem (HSP) is presented from a mathematical viewpoint. Detailed proofs are supplied for many important results and notation is unified, making it easier to absorb the background necessary to begin research on the HSP. Some errors in previous proofs are corrected. Proofs are provided which give very concrete algorithms and bounds for the finite abelian case with little outside references, and future directions are provided for the nonabelian case. This summary is current as of October 2004. 83 pages.

 

Angelic and Evil Numbers
Oct 2004
This brief note answers a question posed on Ed Pegg's website www.mathpuzzle.com on Sept 20, 2004, regarding the likelihood that a randomly chosen irrational number has initial digits summing to a specified constant. In particular, different people noticed that when you add the digits of pi after the decimal, you eventually reach 666. Such numbers I termed "Evil." Those reaching 7 before 666 I termed "Angelic." I obtain a recurrence and a generating function that allows exact computation these such probabilities, and conjecture the probability converges to 20% of hitting a given large digit sum. The results were jointly written up with columnist Ed Pegg for the October 2004 MAA Online column "Math Games."
Published in Oct 2004 MAA Online column "Math Games." MAA Article

 

Using geometric algebra for computer graphics
Aug 2004
In this article I show how to use Clifford Algebras to simplify algorithm derivation. In particular, the elegant framework given using "geometric algebra" unites complex numbers, rotations in any dimension (including quaternions), and gives a nice way to view geometric entities like intersection and span. One useful application is it makes code much simpler. Related papers are on this website here.
Appears in the book Games Programming Gems V, ISBN 1584503521.

 

A Quantum Fourier Transform Algorithm
April 2004
An algorithm is presented showing how to do quantum Fourier transforms over a cyclic group, which can then be used to perform a QFT over any finite abelian group. This corrects results published in several places.
Submitted. Online at xxx.lanl.gov/quant-ph.

 

Robust String Matching in O(\sqrt{N}+M) Quantum Queries
Oct 2003
A quantum algorithm to match strings, supporting wildcards. However, there is a fatal error, and I have withdrawn the paper. It still has some value since it summarizes many theorems from other places, and presents a different view of complexity for some problems. In particular, it reiterates that Grover's algorithm has query complexity of O(sqrt(N)) but time complexity O(log N sqrt(N)), a point many authors confuse.

 

Quantum convolution and correlation are physically impossible
Sept 2003
In this paper I show that performing convolution or correlation of quantum states is physically impossible on a quantum computer. Since the Fourier transform is exponentially faster on quantum states, and the operations are related, it seems natural to ask if all three transforms can be performed efficiently. However the FT is unitary, a necessity, while convolution and correlation are not, making them impossible.

 

Quantum Circuit Identities
July 2003
Constructing a quantum computer out of basic gates is a challenge in quantum computation. Depending on the basic gate set allowed, other desired operations can be performed as combinations of these gates. In this paper I construct all simple (up to 4 gate) identities resulting from a common basic set.
PDF
DVI
PS
Source (19 KB)
Data  (1.43 MB)

 

Error Correcting Codes on Algebraic Surfaces
May 2003
This is my Purdue PhD math thesis which constructs families of codes on algebraic surfaces. In particular I analyze the codes resulting from vector bundles over ruled surfaces over curves of genus 0 and 1, using extensions of Atiyah's classification of vector bundles over elliptic curves.

 

Yet more Projective Curves over F2
Jan 2001
An exhaustive search is done over all plane curves of degree 6 or less with coefficients in F_2, and the number of rational points on the smooth model of each curve is counted over the finite fields of order 2^m for m=1,2,...11. This results in some new curves with more rational points than were previously known, giving data for better error correcting codes and for testing new bounds similar to Weil's formulas on the bounds for rational points on varieties.
Updated Apr 2002 - new version
Published in Experimental Mathematics http://www.expmath.org/

 


Talks

 

Space + Time = Spacetime
August 2011
These are notes on a talk I gave to a group of engineers showing a simple derivation of the Lorenz transform. The goal was to show that just by assuming the speed of light is constant for all observers that space and time must be intertwined in a manner similar to a rotation of the 2D plane. The resulting derivation is short, simple, and complete. Experimental evidence is listed to show how the theory matches experiment.

 

What is Math good for?
April 2011
These are slides for the the Don Buckeye talk I gave at Eastern Michigan University to a group of faculty and students. The topic was showing how a common device (I chose an iPhone for the concrete example) requires sophisticated mathematics to design and implement. I showed how each math class that an undergrad could take and even many graduate courses are required to cover the full breadth of technologies. Here is a link to the PPT slides (including many I did not have time to show).

 

An Exceptionally Simple Theory of Everything
April 2010
These are slides for a talk I originally gave at Cybernet in April 2010. The talk is motiviated by Garret Lisi's "An Exceptionally Simple Theory of Everything" and covers enough background to motivate the abstract to a non-physicist audience, as long as they are still somewhat mathematically sophisticated. The original presentation was to a group of engineers working in many fields from mechanical, electrical, and computer science, and was well received. The talk took three 1-hour sessions to cover the material.

 

C# for C++ Programmers
July 2008
This is a talk I gave to Cybernet Systems in May 2008, showing how C# compares to C++, with the slant of why C# will make them more productive with almost no loss in expressive power or performance for the tasks usually done in C++.

 

An Introduction to Special Relativity
Oct 2007
This is an introduction to special relativity, with a fair amount of historical and motivating material. Highlights include derivation from simple concepts of the following: time dilation, length contraction, relativistic mass, and the famous E=mc2.
Note: much of the material and images for the slides were shamelessly stolen from the web. If anything used violates any of your copyrights, let me know (fair use?).

 

Mathematics and Insanity
This is a light talk I have given at an IPFW Math Alumni meeting. It is a talk about different mathematicians who were "crazy" in various ways, not all of which were clinical. It was meant to give spouses of math people in the audience some insight to their loved ones minds.

 

Mathematics for Video Game Programming
Before my academic life I was a video game programmer, and am amazed how deep the required math is for modern video game programming. Ths talk, meant to inspire undergraduates in mathematics and computer science to study hard, covers most of an undergraduate cirriculum and the uses of each class in some area of game development. I have given this talk probably a dozen times to many universities.

 

Introduction to Quantum Computing
A talk designed for undergraduates to show a small sampling of quantum computing and how it came to be, and some future directions. I was invited to talk to a group of students on quantum computing, and this was the result.

 


Misc other writings

 

A Pandigital Approximation to e Explored
Sept 2011
Here is a detailed exposition of how to prove R. Sabey's 2004 pandigital approximation (1+9^-(6*7))^3^(2^85) to e is accurate to 18457734525360901453873570 digits (including the leading 2).

 

A Beginner Exploits a Security Advisory
April 2007
Here is a detailed explanation and associated files for how I developed (as a beginner) an exploit for the Microsoft ANI file vulnerability disclosed in Spring 2007.

 

C++ coding standards v1.0
Fall 2003
Here is a good set of C++ programming guidelines I developed from my own experience, that I wrote up for giving a talk at Cybernet to the developers.

 

Quantum computing lecture notes
Fall 2003
These lecture notes were made for a series of talks I gave at Purdue in the fall of 2003.

 

Fast Inverse Square Root
Feb 2003
Here a fast algorithm is explained for doing inverse square roots on IEEE floating point formats, which is slightly more accurate than the code found on the web. In particular, the techniques explaining the magic constant 0x5f3759df (search for this constant on Google) used by John Carmack in the Quake 3 code are explained and improved.
Postscript and DVI available on request

 

An Elementary Proof K3,3 is Non-Planar
Oct 2002
The common school kid puzzle of connecting three utilities (water, gas, electric) to three houses in the plane is shown to be impossible. After I wrote this I found out this proof is already known. Ah - that's what I get for playing outside my areas of expertise.

 

Solution to a hard integral problem.
April 2005
For a very challenging integration problem, solvable with 3rd semester calculus, look to the textbook, “Calculus and Analytic Geometry”, 6th edition, by
George B. Thomas and Ross L. Finney. The following problem appears in section 16.7 on multiple integration:

37. WARNING: Hard problem. Setting up the integral is straightforward, but integrating the result takes hours. (It took MACYSMA 20 minutes.)

A square hole of side length 2b is cut symmetrically through a sphere of radius a (a > b * sqrt(2)). Find the volume removed.

This is easy to set up - but try to integrate it using undergrad methods.... Very hard :)

 

Deriving Fast Nonlinear Gradient Fills
Oct 2002
This is a tutorial on several areas in code and algorithm optimization: namely polynomial approximation, Differential Digital Analysis (DDA), forward differencing, and a few more. The tutorial shows how I used these techniques to obtain a 20 fold performance increase in a simple nonlinear gradient fill routine.

 

Hartshorne Solutions version 1.0
2000-2001
While working through Hartshorne's book Algebraic Geometry I took the time to TeX some of the solutions. In an imaginary world I would write up nice solutions to all 400+ problems, but on planet Earth I have moved on and no longer have time. Solutions are presented for some problems in chapters I,II,III,IV.

 


Back to Math