Rust Prime Number Generator

Overview

This project is a high-performance prime number generator implemented in Rust, designed to demonstrate system performance monitoring and optimization techniques. The application generates prime numbers within the u64 range while tracking execution time and memory usage, providing valuable insights into computational performance across different hardware platforms.

Project Purpose & Learning Objectives

This project demonstrates:

• Rust Programming: Modern systems programming with memory safety
• Performance Monitoring: Real-time system resource tracking
• Algorithm Optimization: Efficient prime number generation algorithms
• Cross-platform Development: Performance comparison across different architectures
• System Programming: Low-level system information access
• Performance Analysis: Understanding computational complexity and resource usage

Technical Implementation

Core Algorithm

The project implements an optimized prime number checking algorithm:

• 6k±1 Optimization: Only checks numbers of the form 6k±1 (except 2 and 3)
• Square Root Optimization: Only checks divisors up to √n
• Early Termination: Stops at first divisor found
• Efficient Loop Structure: Minimizes computational overhead

Performance Monitoring

• Execution Time Tracking: Uses Rust's Instant for precise timing
• Memory Usage Monitoring: Tracks process memory consumption
• System Information: Utilizes sysinfo crate for system metrics
• Real-time Reporting: Displays metrics during execution

Key Features

• High Performance: Optimized for maximum computational efficiency
• Memory Efficient: Minimal memory footprint during execution
• Cross-platform: Runs on both x86_64 and ARM architectures
• Configurable Limits: Adjustable prime count and range limits
• Detailed Metrics: Comprehensive performance reporting

File Structure

rust-prime-generator/
├── src/
│   └── main.rs              # Main prime generation logic
├── Cargo.toml               # Rust project configuration
├── Cargo.lock               # Dependency lock file
├── target/                  # Build artifacts
├── imgs/
│   ├── laptop_output.png    # Laptop performance metrics
│   └── raspberrypi_output.png # Raspberry Pi performance metrics
├── README.md               # This file
└── video_link.txt          # Demonstration video links

Dependencies

• Rust 2021 Edition: Modern Rust programming language
• sysinfo 0.25.1: System information and process monitoring
• Standard Library: Core Rust functionality for timing and I/O

Installation & Setup

Prerequisites

# Install Rust (if not already installed)
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
source ~/.cargo/env

Building the Project

# Clone and navigate to project directory
cd rust-prime-generator

# Build in debug mode
cargo build

# Build in release mode (optimized)
cargo build --release

Usage

Running the Application

# Run in debug mode
cargo run

# Run optimized release version
cargo run --release

Configuration

The application can be configured by modifying constants in main.rs:

• Prime Count Limit: Change the count >= 10 condition
• Range Limits: Modify the u64::MAX range
• Output Format: Customize the display format

Performance Analysis

Hardware Performance Comparison

Test Results

Our performance testing revealed interesting results when comparing x86 (laptop) and ARM (Raspberry Pi) architectures:

Raspberry Pi (ARM)

• Better Overall Performance: The ARM architecture showed superior metrics
• Memory Efficiency: Lower memory footprint during execution
• Execution Speed: Faster processing time for prime number generation
• Resource Utilization: More efficient use of system resources

This unexpected but fascinating result demonstrates that ARM architecture can be particularly efficient for certain computational tasks, especially those involving integer operations like prime number generation.

Algorithm Complexity

• Time Complexity: O(√n) per prime check
• Space Complexity: O(1) - constant space usage
• Optimization: 6k±1 form reduces checks by ~66%

Performance Metrics Tracked

• Execution Time: Total time to find specified number of primes
• Memory Usage: Process memory consumption in KB
• Prime Discovery Rate: Primes found per unit time
• System Resource Usage: CPU and memory utilization

Cross-Platform Performance

Tested Platforms

• Laptop (x86_64): Intel/AMD processors with high clock speeds
• Raspberry Pi (ARM): ARM-based single-board computer

Performance Comparison

The project includes performance screenshots showing:

• Laptop Performance: imgs/laptop_output.png
• Raspberry Pi Performance: imgs/raspberrypi_output.png

Key Differences Observed

• Architecture Impact: x86_64 vs ARM performance characteristics
• Clock Speed Effects: Higher frequency processors show better performance
• Memory Access Patterns: Different memory hierarchies affect performance
• Compiler Optimizations: Release builds show significant improvements

Technical Specifications

• Language: Rust 2021 Edition
• Target Platforms: x86_64, ARM64
• Number Range: u64 (0 to 18,446,744,073,709,551,615)
• Prime Algorithm: Optimized trial division with 6k±1 form
• Monitoring: Real-time system metrics collection
• Build System: Cargo (Rust package manager)

Optimization Techniques

Algorithm Optimizations

• 6k±1 Form: Only test numbers of form 6k±1 (except 2, 3)
• Square Root Limit: Only check divisors up to √n
• Early Exit: Terminate on first divisor found
• Efficient Loops: Minimize loop overhead

Rust-Specific Optimizations

• Zero-Cost Abstractions: Leverage Rust's performance guarantees
• Memory Safety: No runtime overhead for bounds checking in release mode
• Compiler Optimizations: LLVM backend provides excellent optimization
• Release Builds: --release flag enables maximum optimization

Demonstration

Video Demonstration

Click the image above to watch the full demonstration

Performance Screenshots

• Laptop Performance:
• Raspberry Pi Performance:

The video and screenshots show:

• Real-time prime number generation
• Performance metrics comparison between platforms
• Memory usage and execution time tracking
• Cross-platform performance analysis

Educational Value

This project serves as an excellent learning tool for:

• Rust Programming: Understanding systems programming with Rust
• Performance Optimization: Learning algorithm optimization techniques
• System Monitoring: Understanding how to track system resources
• Cross-platform Development: Comparing performance across architectures
• Computational Complexity: Understanding algorithm efficiency
• Real-world Applications: Applying theoretical knowledge to practical problems

Future Enhancements

• Parallel Processing: Implement multi-threaded prime generation
• Sieve Algorithms: Add Sieve of Eratosthenes implementation
• Probabilistic Testing: Implement Miller-Rabin primality testing
• GPU Acceleration: Add CUDA/OpenCL support for massive parallelization
• Web Interface: Create web-based performance monitoring dashboard
• Benchmarking Suite: Add comprehensive performance benchmarking

Performance Insights

• Rust Performance: Demonstrates Rust's zero-cost abstractions
• Algorithm Efficiency: Shows impact of algorithmic optimizations
• Hardware Differences: Illustrates performance variations across platforms
• Compiler Optimizations: Highlights importance of release builds
• Memory Management: Shows efficient memory usage patterns

License

This project is part of ECE4301 coursework and is intended for educational purposes.