Parallel depth first search (DFS) to find prime juggling patterns. Prime siteswap patterns are those which cannot be expressed as compositions (concatenations) of shorter patterns.
jprime searches the juggling state graph for prime patterns, using efficiency tricks to speed up the search. The search is done in parallel using a work-stealing scheme to distribute the search across multiple execution threads. jprime can also run on a CUDA GPU, scaling to 50,000 or more concurrent workers.
The software can also analyze siteswap patterns provided by the user, and compute pattern inverses where they exist.
The following notes discuss the theory of prime juggling patterns, some details about algorithms used by jprime, and search results to date:
The CMake build tool is used to build the jprime executable on Linux, Windows, and macOS.
Prerequisites:
- Cloned repository
git clone https://github.com/jkboyce/jprime.git
- C++ build tools for your platform
- Linux:
gccorclangrecent enough to support C++20 - Windows:
Visual Studio 2022 Community Editionincludes everything needed, and is free; use Tools-->Command Line-->Developer Command Prompt to run CMake - macOS:
XcodeandXcode Command Line Toolsfrom Apple
- Linux:
CMakefor your platform- Version 3.21 or later
- For Linux and Windows this is included in the above build tools; for macOS it can be installed via Homebrew
- Optional: CUDA Toolkit from NVIDIA
- Enables the CUDA build option, which allows searches to be run on a GPU
- Linux and Windows installers are available from NVIDIA
How to build:
- See instructions in
CMakeLists.txtfor how to configure and build from the command line
How to run:
- After building, find the
jprimeexecutable in thebuildfolder of the repository - Execute
jprimewith no arguments to get a help message (it has no GUI and runs only from the command line) jprime -testruns a series of tests to confirm a successful build