Factor Guessing

A high-performance C++ implementation of parallel divisor function algorithms with Huffman tree-based optimal binary decision strategies.

Overview

This project implements and benchmarks multiple algorithms for computing divisor functions (the number of positive divisors for each integer in a range [1, n]). It explores both sequential and parallel approaches, including:

• Parallel Sieve with Dynamic Scheduling: OpenMP-based parallel divisor counting with configurable block sizes
• Linear Sieve with SPF (Smallest Prime Factor): Hybrid approach combining sequential sieve preprocessing with parallel factorization
• Huffman Tree Construction: Optimal binary decision tree for determining divisor counts with minimal expected questions

The implementation is optimized for modern multi-core systems and includes comprehensive benchmarking tools for performance analysis.

Project Structure

FactorGuessing/
├── include/              # Header files
│   ├── divisor.hpp      # Divisor function algorithms
│   ├── histogram.hpp    # Frequency counting utilities
│   └── huffman.hpp      # Huffman tree construction
├── src/                 # Implementation files
│   ├── divisor.cpp      # Core divisor algorithms
│   ├── histogram.cpp    # Histogram computation
│   ├── huffman.cpp      # Huffman tree logic
│   └── verify.cpp       # Verification executable
├── benchmark/           # Benchmarking suite
│   ├── bench_main.cpp   # Main benchmark driver
│   └── plots/           # Generated plots
├── scripts/             # Automation scripts
│   ├── build.sh         # Build automation
│   ├── divisor_function.py  # Divisor function plotting
│   ├── run_benchmarks.py    # Benchmark orchestration
│   └── plot_results.py      # Result visualization
├── ui/                  # Standalone interactive UI (Python)
│   ├── ui_app.py        # Huffman-based questioner; LS-SPF + histogram + explicit tree with leaf sets
│   └── README.md        # UI usage guide
├── doc/                     # Documentation
│   ├── The Magic Number.pdf # PDF report
│   └── Report.md            # Markdown report
├── CMakeLists.txt       # CMake build configuration
├── Makefile             # Alternative build system
└── requirements.txt     # Python dependencies

Requirements

Build Dependencies

• C++ Compiler: GCC 11+ with C++17 support
• CMake: 3.15 or higher
• OpenMP: For parallel execution

Python Dependencies (for benchmarking/plotting)

pip install -r requirements.txt

Required packages:

• matplotlib >= 3.5.0
• numpy >= 1.21.0

Building

bash scripts/build.sh

Build Targets

• bench: Main benchmarking executable
• verify: Correctness verification tool

Compiler Flags

The project uses aggressive optimizations:

• -O3: Maximum optimization level
• -march=native: CPU-specific optimizations
• -fopenmp: OpenMP support
• -std=c++20: C++20 standard

Usage

Interactive UI (Python demo)

Based on the C++ implementation, GitHub Copilot generates an interactive magic number solver you can directly play with:

python ui/ui_app.py --n 50            # Interactive session (y/n prompts)
python ui/ui_app.py --n 50 --secret 9 # Auto-simulate with magic number 9
# Building divisor table with LS-SPF for n=50 ...
# Distinct magic numbers: 9 (max value 10)
# Built Huffman tree: nodes=17, expected questions ~ 2.560
# Step 1: left weight=20 (p=0.400), right weight=30 (p=0.600)
# Is the magic number in {1, 3, 5, 6, 8, 9, 10}? [y/n]: 
# Answer: yes
# Step 2: left weight=8 (p=0.400), right weight=12 (p=0.600)
# Is the magic number in {3, 8}? [y/n]: 
# Answer: no
# Step 3: left weight=4 (p=0.333), right weight=8 (p=0.667)
# Is the magic number in {1, 5, 9, 10}? [y/n]: 
# Answer: yes
# Step 4: left weight=2 (p=0.500), right weight=2 (p=0.500)
# Is the magic number in {1, 5}? [y/n]: 
# Answer: no
# Step 5: left weight=1 (p=0.500), right weight=1 (p=0.500)
# Is the magic number in {9}? [y/n]: 
# Answer: yes
# Auto-run complete. Secret=9, guessed=9.

• --show-stats prints the frequency table.
• --max-steps caps the number of questions.
• To visualize the tree, render the DOT file (after installing Graphviz):

python ui/ui_app.py --n 50 --dot ui/huffman.dot  # Export Huffman tree to DOT
dot -Tpng ui/huffman.dot -o ui/huffman.svg
# or use https://dreampuf.github.io/GraphvizOnline/ to see the Huffman tree online

Running Benchmarks

Execute the automated benchmark suite:

# Run all benchmarks (from project root)
python scripts/run_benchmarks.py

# Generate performance plots
python scripts/plot_results.py

The benchmark suite tests multiple problem sizes (1M to 32M) and configurations, saving results to the benchmark/plots/ directory.

Manual Execution

Run individual benchmarks:

# From build directory
./bench <n> <algorithm> <block_size>

# Examples:
./bench 1000000 linear_spf 0     # Linear sieve with SPF
./bench 1000000 parallel 8       # Parallel sieve with block size 8
./bench 1000000 linear_plain 0   # Plain linear sieve

Verification

Test algorithm correctness:

make verify
./build/verify <n>

# Examples:
./build/verify 10000
./build/verify 100000

Algorithms

1. Parallel Sieve (PS)

Parallelizes the classical divisor sieve using OpenMP dynamic scheduling.

• Complexity: Work $O(n \log n)$, Span $O(\log n)$
• Best for: Scalability studies, systems with many cores
• Configuration: Adjustable block size for load balancing

2. Linear Sieve with SPF (LS-SPF)

Computes smallest prime factors sequentially, then parallelizes factorization.

• Complexity: Work $O(n)$, Span $O(n)$ (sieve) + $O(\log n)$ (factorization)
• Best for: Large problem sizes (n ≥ 4M)
• Advantage: Optimal work complexity with parallel acceleration

3. Linear Sieve Plain (LS-Plain)

Sequential divisor computation during sieve construction.

• Complexity: Work $O(n)$, Span $O(n)$
• Best for: Baseline comparison, cache-sensitive workloads
• Advantage: Best cache locality

Documentation

• Project report: see doc/
• UI demo: see ui/README.md

License

See LICENSE for details.