#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.
