In the Fall Semester of 2000 I took an industrial engineering course at Auburn University. The course was Industrial Systems 6700 and was taught by Professor and Chair Alice E. Smith. The course was entitled “Search Methods for Optimization”. The first two papers that Professor Smith handed out dealt with physical and computerized simulating annealing and were: “Equation of State Calculations by Fast Computing Machines” by Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, and Augusta H. Teller Los Alamos Scientific Laboratory, Los Alamos, New Mexico Edward Teller Notice that the inventor of the hydrogen bomb Edward Teller was involved with the paper and Optimization by Simulated Annealing | Science. The first paper dates from the year I was born namely 1953 and the second paper 1983, the latter year was the year that I flunked out of the Georgia Institute of Technology.
Our first assignment dealt with optimization via computerized simulating annealing (SA) and Professor Smith gave the class her implementation of the algorithm. By the way, over the last 22 years I have reused Smith’s algorithm in many of my own computer applications (C, C++, and C# computer languages).
SA gained the favor of Federal Express in 1983 and the Science paper mentioned above details the delivery service corporations use of the algorithm. The state of the art in solving the traveling salesperson problem (TSP) is the Concorde program written by scholars at the University of Waterloo in Canada: The traveling salesman problem | Mathematics | University of Waterloo (uwaterloo.ca). I believe Concorde uses linear programming.
With my software I am only able to solve small in size instances of the TSP. My implementations in a single computer application to solve toy random instances of the TSP for 3 to 25 number of locations are: brute force (3 to 9 cities), steepest descent local search (SDLS) from http://www.cs.bham.ac.uk/~wbl/biblio/gecco2007/docs/p1226.pdf, tabu search, evolutionary hill climber (EHC), genetic algorithm (GA), simulated annealing, some hybrid methods, minimum spanning tree, etc.
Steepest Descent Local SearchTabu (Taboo) SearchEvolutionary Hill ClimberGenetic AlgorithmSimulated Annealing (Probably Optimal)
I used Henri Cohen’s trial division algorithm from A Course in Computational Algebraic Number Theory. Trial division is the most primitive factoring method. I used a prime number sieve of Eratosthenes of all prime numbers less than or equal 100,000,000. There are 50,847,534 such primes. Also I used the C data type long long which yields a number of 64-bits. The vanilla C source is shown below as PDF file along with a run of the application. [Note: Somehow I lost this project, but fortunately I was working on an application that uses Brent’s modification of Pollard’s rho method. I have included the source code from that project below. The original code had a bug ridden Miller-Rabin probabilistic prime number test.]
Trial division is still a somewhat useful means of factoring large integers on modern massively parallel super computers. You can partition the factor base among the processors and run the algorithm in parallel.
I read the treatise Sorting and Sort Systems by Harold Lorin in the summer of 1979. That excellent intellectual work inspired me to implement the code and and algorithms from that book. Lorin used Algol, FORTRAN and IBM’s language PL/I. I used the Data General Eclipse minicomputer at LaGrange College from which I had graduated with a Bachelor of Arts degree in Chemistry. I utilized the computer language BASIC (Beginner’s All-purpose Symbolic Instruction Code) and Data General’s Advanced Operating System Macro-assembly language. Later in my academic life at Auburn University I learned about Heap Sort. I wrote about six sorting algorithms on Facebook that I implemented in the C# computer language back in 2015. It took me two days to create a similar application using the C++ computer language. Here are some results and the source code in PDF file format.
Using the chronological backtracking C++ code that I developed from the backtracking algorithm applied to the N-Queens constraint satisfaction problem, I developed an algorithm to solve the Knight’s Tour Problem. The general backtracking algorithm is from Foundations of Constraint Satisfaction by E. P. K. Tsang Chapter 2 page 37. I display some executions of the program in this blog.
Chronological Backtracking Closed Tour Solution for a 6×6 Chess BoardWarnsdorff Closed Tour Solution for a 6×6 Chess BoardWarnsdorff Open Tour Solution for an 8×8 Chess BoardKnight Move Count Matrix Used by Warnsdorff Heuristic
There are three classic theoretical tests of Albert Einstein’s Theory of General Relativity: the perihelion precession of Mercury, the other Solar System planets, and the planetoid Pluto, the bending of light by massive bodies, and the gravitational red shift. I recently wrote a C# program for displaying the exaggerated Rosette motion of theoretical planets (Schwarzschild’s solution to Einstein’s general relativity field equation that admit the existence of black holes). I also wrote a C++ program to calculate planetary precession values that agree with experimental results.
Precession.cpp (c) James Pate Williams, Jr. August 2022
This program calculates the planetary precessions of the planets in our solar system. Some of the equations and data are from “General Relativity” by Hans Stephani 1982 page 103 and the following websites. Also, two calculations of the mass of the Sun are exhibited, along with my weight on different planets:
Gibson EDS-1275 Double Neck Twelve String Over Six String Guitar May 2009 Post Production March 2022
Gibson EDS-1275 Double Neck Twelve String Over Six String Guitar May 2009 Post Production March 2022First Effect for First Video of this Blog EntrySecond Effect for First Video of this Blog EntryThird Effect for First Video of this Blog EntryFourth Effect for First Video of this Blog EntryFifth Effect for First Video of this Blog EntryEffects Used in the Second Video
Windows ’95 MIDI Sequencer Translated from Java in About 2005
An Early Attempt at Creating Computer Generated Music in May 1988 Using My Brand New Commodore Amiga 2000 and Microsoft’s Amiga Basic The Amiga’s Display Uses Colors but my 2015 Recreation Is in Black and White (Monochrome)