To preface my algorithms page I decided to write down some of my rules for getting along in this life .
I plan to put up a number of interesting algorithms on this site, the first of which is the correct way to do mortgage calculations.
I have written two Ruby programs that carry out Shor's factoring algorithm. One is an inefficient implementation, useful mostly for illustration. For a more efficient program, this a complete implementation of Shor's algorithm, the best that can be done on a classical computer, i.e., I had to fake the "quantum entanglement".
After the 2012 presidential election I got interested in combining polls to predict the elections. My Predicting Elections page lets the user combine any number of polls to make election predictions.
My son, David, and I published an encryption algorithm which allows multiple messages to be encrypted in one transmission, each message having its own passphrase. Our algorithm is based on Ron Rivest's Chaffing and Winnowing scheme and also Rivest's package algorithm. Our method, called MMPC for Multi-Message Package Chaffing, has some unusual applications. One could, for example, send the same file to several recipients but with different passphrases for each so that each recipient would not only see a different message, but no one but the sender would know that there was more than one message contained in the file. Or the sender could put two messages in one file, the intended message and a fake one, so that if the "password" was demanded, the sender could reveal the password paired with the fake message to satisfy the person or authority demanding to see the contents of the message.
I took an online course on Bitcoins, only because I was interested in the technology of decentralization. The block-chain used by Bitcoin has a couple of nice schemes for ensuring that the chain has not been modified, and that may lead to other uses of the chain technology, besides as a crypto-currency. With the "other uses" in mind, I wrote a program that uses Bitcoin's Merkle tree scheme and the combining of each block's hash with its successor's head to keep a running hash. The chain's head hash, typically 256 bits, can serve as a sentinel that the chain has not been modified. Here is my Ruby implementation of a Bitcoin-like block chain and here it is in Python.
I added mining to the Python code. If you run this code you will likely want to decrease the value of the difficulty integer in the mining search to increase the search time, as I do my development on a Raspberry Pi 3.
I like to dabble in number theory and encryption. If you do, too, or even if you are only interested in seeing how things like testing a number to see if it is prime, or perhaps finding the multiplicative inverse of a number work, take a look at my number theory library in Ruby or number theory module in Haskell or number theory module in Python code.
I have started a statistical applications module in Haskell with the well-known "birthday" problem. And here it is in Python. Here is a graph that shows how the probability of a match on any birthday in a group of n people varies with n. The probability exceeds 1/2 when n = 23. Matching on a specific birthday, say yours, in a group of n other people varies with n like this and exceeds 1/2 when n = 253.
Quadrature using Simpson's rule is well known, but there is a way to improve the accuracy. The trick is to vary the interval size with the function. When the function is smooth, longer intervals will suffice and when the function is changing rapidly, shorter intervals will be needed. Here is Python code for adaptive Simpson integration. The test code integrates the normal curve and uses the result to approximate pi, approximates 5! by integrating the gamma function, and integrates cosine from 0 to pi / 2 which should yield an area of 1.
The gamma function is usually presented in advanced calculus courses as an extension of factorials to non-integers when in fact it should be the other way around. That is, factorials are a restriction of the much more general gamma function. The give-away is that 0! is defined to be 1, which makes no sense at all. This comes about because 0! ≡ Γ(1) = 1. There is a wonderful book by Emil Artin, The Gamma Function, which describes the gamma function as the solution of Γ(n + 1) = n * Γ(n) plus some other requirements. Artin extends Stirling's formulas to allow accurate calculations of Γ. Here is a Python program which calculates Γ(1.75) two different ways, from Artin's extension of Stirling's formulas and by evaluating the integral for Γ(x). (By the way, Artin's extension of Stirling's formulas is anything but obvious. It involves evaluating a divergent series each coefficient of which itself results from summing an infinite series. Fortunately, you only need three or four terms in the divergent series.)
Is it possible to flip a coin electronically? You might think it would not be possible to do a trusted random coin flip between two parties in different locations. There is an ingenious mathematical algorithm that is titled "Coin Flipping by Telephone" and dates to 1982, i.e. before we were all using the internet. Here is an explanation of this algorithm, followed by an implementation in Ruby and some examples. And here is the same thing written in Python.
But, there is an even simpler way to flip a coin fairly using cryptographic hash functions. The trick is for one party to make a random heads/tails choice and to send, i.e., commit that choice hashed with a random string to the other party. The second party then guesses the choice the first party made. It's easy to confirm the first party's choice to the second in the event of a mismatch. Here is Ruby and Python code for coin flipping using a cryptographic hash.
Solving linear equations is old stuff in the computer world. Everyone has at least heard of Gauss row-reduction and if you have ever gotten serious about solving linear systems of equations, you certainly have bumped into lower-upper decomposition. But there is another method for handling linear systems due to Cornelius Lanczos. The so-called Lanczos iterative algorithm is particularly efficient for large systems of equations and when the right hand side consists of real-world measurements which are accompanied by well-controlled errors.
This iterative scheme is based on Chebyshev polynomials, although these polynomials never enter into the code for the algorithm. You do have to rescale the matrix's columns (and rows for symmetric matrices) and divide the system by an upper limit on the largest eigenvalue, but after that each iteration is just one matrix multiplication followed by a matrix subtraction. Here is code for the Lanczos iterative algorithm for solving positive-definite systems of linear equations, including an application to a simple 3x3 least squares problem. And here is code for iteratively improving on the initial solution by solving the problem again, but on the residual from the first solution.
Getting the cart ahead of the horse, it turns out that you need a technique called automatic differentiation (AD) later to develop neural networks. AD is not numerical differentiation and is also not symbolic differentiation. The idea is to use the chain rule and to carry the derivative along with the value of each variable, when needed. This gives derivatives to machine-level accuracy, albeit with some overhead. Here is an AD class Val_der (for value and derivative) that includes all the basic arithmetic functions, logarithms, exponentials, and the basic trigonometric functions.
As I write this (2018-07-12) I have just completed Dr. Andrew Ng's Coursera course Machine Learning. I got interested in the course's algorithms enough that I coded some of them in Python. This page describes and has links to these algorithms.
I have a great interest in electric vehicles and owned a 2015 Nissan Leaf for three years.. It's possible, but perhaps not obvious, to track the Leaf's efficiency. There are two ways using the car's instrumentation and I initially used one of those methods. More recently I set up an integrating power meter to accurately measure the energy supplied with each charge. My Leaf spreadsheets, before and after incorporating the 240 VAC kWh meter, are here. If you click on the cells you can see the formulas I use. (There is even a worksheet for my gas-powered 2000 Toyota MR2.)
Ever wonder where you spend your time and money? Me too, so I wrote Ruby and Python programs to keep track of things. Each requires a data file, which takes some time to construct, but little effort to maintain. There is a Driver file, a Class file, a Partial data file, and a Partial output file. And here is a combined driver and class file in Python. I call this program 'lv' for Life Value.
My books, How Things Mathematical Work and In Your Head, are available from Amazon.
To comment or report errors in my code, you can reach me here.