My whole legal name is James Pate Williams, Jr. I was born in LaGrange, Georgia approximately 70 years ago. I barely graduated from LaGrange High School with low marks in June 1971. Later in June 1979, I graduated from LaGrange College with a Bachelor of Arts in Chemistry with a little over a 3 out 4 Grade Point Average (GPA). In the Spring Quarter of 1978, I taught myself how to program a Texas Instruments desktop programmable calculator and in the Summer Quarter of 1978 I taught myself Dayton BASIC (Beginner's All-purpose Symbolic Instruction Code) on LaGrange College's Data General Eclipse minicomputer. I took courses in BASIC in the Fall Quarter of 1978 and FORTRAN IV (Formula Translator IV) in the Winter Quarter of 1979. Professor Kenneth Cooper, a genius poly-scientist taught me a course in the Intel 8085 microprocessor architecture and assembly and machine language. We would hand assemble our programs and insert the resulting machine code into our crude wooden box computer which was designed and built by Professor Cooper. From 1990 to 1994 I earned a Bachelor of Science in Computer Science from LaGrange College. I had a 4 out of 4 GPA in the period 1990 to 1994. I took courses in C, COBOL, and Pascal during my BS work. After graduating from LaGrange College a second time in May 1994, I taught myself C++. In December 1995, I started using the Internet and taught myself client-server programming. I created a website in 1997 which had C and C# implementations of algorithms from the "Handbook of Applied Cryptography" by Alfred J. Menezes, et. al., and some other cryptography and number theory textbooks and treatises.
#pragma once
#include <cinttypes>
#include <vector>
using namespace std;
// See "Introduction to Algorithms"
// Thomas H. Cormen Among Others
// Chapter 13 Binary Search Trees
// Translated from Pascal found in
// "Applied Data Structures Using
// Pascal" by Guy J. Hale and
// Richard J. Easton Chapter 6
// Introduction to Trees
typedef struct treeNode
{
uint32_t key;
treeNode* lt, * rt;
} TREENODE, * PTREENODE;
class BinaryTree
{
public:
static void InitTree(PTREENODE root, uint32_t key);
static void InsertInTree(PTREENODE& root, uint32_t key);
static void CreateTree(PTREENODE& root, vector<uint32_t> &data,
unsigned int seed, size_t number);
static void TravInOrder(PTREENODE node);
static void TravPreOrder(PTREENODE node);
static void TravPostOrder(PTREENODE node);
};
We calculate the ground state energies for Helium (Z = 2), Lithium (Z = 3), Beryllium (Z = 4), Boron (Z = 5), and Carbon (Z = 6). Currently, only three of the five atoms are implemented.
#pragma once
// Binary searches from the following website
// https://www.geeksforgeeks.org/binary-search/
typedef long long ll;
class Search
{
public:
int IterativeBinarySearch(
ll A[], ll x, int low, int high);
int RecursiveBinarySearch(
ll A[], ll x, int low, int high);
int IterativeLinearSearch(
ll A[], ll x, int low, int high);
};
#include "Search.h"
int Search::IterativeBinarySearch(
ll A[], ll x, int low, int high)
{
do
{
int middle = low + (high - low) / 2;
if (x == A[middle])
return middle;
else if (x > A[middle])
low = middle + 1;
else if (x < A[middle])
high = middle - 1;
} while (high >= low);
return -1;
}
int Search::RecursiveBinarySearch(
ll A[], ll x, int low, int high)
{
if (high >= low)
{
int middle = low + (high - low) / 2;
if (x == A[middle])
return middle;
else if (x > A[middle])
return RecursiveBinarySearch(
A, x, middle + 1, high);
else if (x < A[middle])
return RecursiveBinarySearch(
A, x, low, middle - 1);
}
return -1;
}
int Search::IterativeLinearSearch(
ll A[], ll x, int low, int high)
{
for (int i = low; i <= high; i++)
if (x == A[i])
return i;
return -1;
}
// Searching.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include "Search.h"
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using chrono::duration_cast;
using chrono::nanoseconds;
ll A[1000001];
ll RandomLongLong()
{
ll lo = rand();
ll hi = rand();
return (lo << 31) | hi;
}
void GenerateArray(ll A[], int n, int seed)
{
for (int i = 1; i <= n; i++)
A[i] = RandomLongLong();
}
void GenerateArrayMod(ll A[], int n, int mod, int seed)
{
Search search;
for (int i = 1; i <= n; i++)
{
while (true)
{
ll Ai = RandomLongLong() % mod;
if (search.IterativeLinearSearch(
A, Ai, 1, i) == -1)
{
A[i] = Ai;
break;
}
}
}
}
int Partition(ll* A, int p, int r)
{
int q = p;
ll t;
for (int u = p; u <= r - 1; u++)
{
if (A[u] <= A[r])
{
t = A[q];
A[q] = A[u];
A[u] = t;
q++;
}
}
t = A[q];
A[q] = A[r];
A[r] = t;
return q;
}
void RunQuickSort(ll* A, int p, int r)
{
if (p < r)
{
int q = Partition(A, p, r);
RunQuickSort(A, p, q - 1);
RunQuickSort(A, q + 1, r);
}
}
void RunSearches(
Search search,
ll A[],
int n, int seed)
{
int index[4];
ll x = RandomLongLong() % n;
GenerateArrayMod(A, n, 2LL * n, seed);
RunQuickSort(A, 1, n);
cout << "key = " << x << endl;
if (n <= 25)
{ for (int i = 1; i <= n; i++)
cout << A[i] << " ";
cout << endl;
}
cout << "Runtimes in nanoseconds" << endl;
cout << "n" << "\t" << "Iter" << "\t";
cout << "Recur" << "\t" << "Linear" << endl;
cout << setw(5) << n << "\t";
auto start1 = chrono::steady_clock::now();
index[0] = search.IterativeBinarySearch(A, x, 1, n);
auto final1 = chrono::steady_clock::now();
cout << setw(5) << duration_cast<nanoseconds>(final1 - start1).count();
cout << "\t";
auto start2 = chrono::steady_clock::now();
index[1] = search.RecursiveBinarySearch(A, x, 1, n);
auto final2 = chrono::steady_clock::now();
cout << setw(5) << duration_cast<nanoseconds>(final2 - start2).count();
cout << "\t";
auto start3 = chrono::steady_clock::now();
index[2] = search.IterativeLinearSearch(A, x, 1, n);
auto final3 = chrono::steady_clock::now();
cout << setw(5) << duration_cast<nanoseconds>(final3 - start3).count();
cout << endl;
cout << "Search indicies" << endl;
for (int i = 0; i < 3; i++)
cout << "index[" << i << "] = " << index[i] << endl;
}
int main()
{
cout << "Comparison of Iterative Binary Search," << endl;
cout << "Recursive Binary Search, and Linear Search" << endl;
while (true)
{
int n, seed;
Search search;
cout << "n = ";
cin >> n;
if (n == 0)
break;
cout << "seed = ";
cin >> seed;
srand(seed);
RunSearches(search, A, n, seed);
}
}
We compare selection sort, merge sort, quick sort, and std::sort. The runtime orders were quick sort < merge sort < std::sort < selection sort.
#pragma once
class Sort
{
public:
void RunSelectionSort(long long* A, int p, int r);
void RunMergeSort(
long long* A,
long long* B,
long long* C,
int p, int r);
void RunQuickSort(long long* A, int p, int r);
private:
void Merge(
long long* A,
long long* B,
long long* C,
int p, int q, int r);
int Partition(long long* A, int lo, int hi);
};
#include <limits.h>
#include "Sort.h"
void Sort::Merge(
long long* A,
long long* B,
long long* C,
int p, int q, int r)
{
int n1 = q - p + 1, n2 = r - q;
for (int i = p, j = 1; i <= q; i++, j++)
B[j] = A[i];
for (int i = q + 1, j = 1; i <= r; i++, j++)
C[j] = A[i];
B[n1 + 1] = C[n2 + 1] = LLONG_MAX;
int ii = 1, jj = 1;
for (int k = p; k <= r; k++)
{
if (B[ii] <= C[jj])
{
A[k] = B[ii];
ii++;
}
else
{
if (B[ii] > C[jj])
{
A[k] = C[jj];
jj++;
}
}
}
}
int Sort::Partition(long long* A, int p, int r)
{
int q = p;
long long t;
for (int u = p; u <= r - 1; u++)
{
if (A[u] <= A[r])
{
t = A[q];
A[q]= A[u];
A[u] = t;
q++;
}
}
t = A[q];
A[q] = A[r];
A[r] = t;
return q;
}
void Sort::RunMergeSort(
long long* A,
long long* B,
long long* C,
int p, int r)
{
int q = (p + r) / 2;
if (p < r)
{
RunMergeSort(A, B, C, p, q);
RunMergeSort(A, B, C, q + 1, r);
Merge(A, B, C, p, q, r);
}
}
void Sort::RunQuickSort(long long* A, int p, int r)
{
if (p < r)
{
int q = Partition(A, p, r);
RunQuickSort(A, p, q - 1);
RunQuickSort(A, q + 1, r);
}
}
void Sort::RunSelectionSort(long long* A, int p, int r)
{
for (int i = p; i <= r - 1; i++)
{
for (int j = i + 1; j <= r; j++)
{
if (A[i] > A[j])
{
long long t = A[i];
A[i] = A[j];
A[j] = t;
}
}
}
}
#include "Sort.h"
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using chrono::duration_cast;
using chrono::milliseconds;
long long A[16], B[18], C[18];
long long AA[100002], BB[100002], CC[100002];
long long RandomLongLong()
{
long long lo = rand();
long long hi = rand();
return (lo << 31) | hi;
}
void GenerateArray(long long A[], int n, int seed)
{
srand(seed);
for (int i = 1; i <= n; i++)
A[i] = RandomLongLong();
}
void GenerateArrayMod(long long A[], int n, int mod, int seed)
{
srand(seed);
for (int i = 1; i <= n; i++)
A[i] = RandomLongLong() % mod;
}
void RunSorts(
Sort sort,
long long A[],
long long B[],
long long C[],
int n, int seed)
{
cout << setw(5) << n << "\t";
auto start1 = chrono::steady_clock::now();
sort.RunSelectionSort(A, 1, n);
auto final1 = chrono::steady_clock::now();
cout << setw(5) << duration_cast<milliseconds>(final1 - start1).count();
cout << "\t";
GenerateArray(A, n, seed);
auto start2 = chrono::steady_clock::now();
sort.RunMergeSort(A, B, C, 1, n);
auto final2 = chrono::steady_clock::now();
cout << setw(5) << duration_cast<milliseconds>(final2 - start2).count();
cout << "\t";
GenerateArray(A, n, seed);
auto start3 = chrono::steady_clock::now();
sort.RunQuickSort(A, 1, n);
auto final3 = chrono::steady_clock::now();
cout << setw(5) << duration_cast<milliseconds>(final3 - start3).count();
cout << "\t";
GenerateArray(A, n, seed);
vector<long long> V;
for (int i = 0; i < n; i++)
V.push_back(A[i + 1]);
auto start4 = chrono::steady_clock::now();
std::sort(V.begin(), V.end());
auto final4 = chrono::steady_clock::now();
cout << setw(5) << duration_cast<milliseconds>(final4 - start4).count();
cout << endl;
}
void TestSorts(
Sort sort,
long long A[],
long long B[],
long long C[],
int n, int seed)
{
cout << "Testing Sorting Algorthms" << endl;
cout << "Selection Sort" << endl;
GenerateArrayMod(A, n, 100000, 1);
for (int i = 1; i <= n; i++)
cout << setw(5) << A[i] << " ";
cout << endl;
sort.RunSelectionSort(A, 1, n);
for (int i = 1; i <= n; i++)
cout << setw(5) << A[i] << " ";
cout << endl << endl;
cout << "Merge Sort" << endl;
GenerateArrayMod(A, n, 100000, 1);
for (int i = 1; i <= n; i++)
cout << setw(5) << A[i] << " ";
cout << endl;
sort.RunMergeSort(A, B, C, 1, n);
for (int i = 1; i <= n; i++)
cout << setw(5) << A[i] << " ";
cout << endl << endl;
cout << "Quick Sort" << endl;
GenerateArrayMod(A, n, 100000, 1);
for (int i = 1; i <= n; i++)
cout << setw(5) << A[i] << " ";
cout << endl;
sort.RunQuickSort(A, 1, n);
for (int i = 1; i <= n; i++)
cout << setw(5) << A[i] << " ";
cout << endl << endl;
cout << "std::sort" << endl;
GenerateArrayMod(A, n, 100000, 1);
vector<long long> V;
for (int i = 1; i <= n; i++)
{
cout << setw(5) << A[i] << " ";
V.push_back(A[i]);
}
cout << endl;
std::sort(V.begin(), V.end());
for (size_t i = 0; i < V.size(); i++)
cout << setw(5) << V[i] << " ";
cout << endl << endl;
}
int main(int argc, char** argv)
{
Sort sort;
TestSorts(sort, A, B, C, 15, 1);
cout << "Runtimes in Milliseconds" << endl;
cout << " n" << "\tSelect" << "\t Merge" << "\t Quick\tstd::sort" << endl;
for (int n = 10000; n <= 60000; n += 10000)
{
RunSorts(sort, AA, BB, CC, n, 1);
}
return 0;
}
Back in 2022 I reimplemented Henri Cohen’s Atkin’s Primality Test algorithm. This test makes use of an elliptic curve analog of Pocklington’s theorem. I restate the theorem utilized from Henri Cohen’s “A course in Computational Algebraic Number Theory” on pages 467 to 468: “Proposition 9.2.1. Let N be an integer coprime to 6 and different from 1, and E be an elliptic curve modulo N. Assume that we know an integer m a point P contained on the elliptic curve satisfying the following conditions. (1) There exists a prime divisor q of m such that q > (N^1/4 + 1) ^ 2 (2) m * P = O_E = (0 : 1 : ). (3) (m / q) * P = (x : y : t) with t contained in (Z/NZ)*. Then N is prime.” I used C# and Microsoft’s BigInteger class. I have not been able to prove numbers greater than 14 decimal digits to be prime. I am recoding the algorithm in C++ which limits me to 19 decimal digits since 2 ^ 63 – 1 = 9,223,372,036,854,775,807 (Int64).
I implemented the algorithm in C using unsigned 64-bit integers. This method is good for integers of around 18 decimal digits in length. For comparison I tested against my blazingly fast Shor’s classical factoring algorithm which works on arbitrarily large integers of around 50 to 60 or more decimal digits.
Numerical Explorations 