Skip to content

QuanBlue/miller-rabin

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

icon
Miller Rabin

Probabilistic Primality test.

contributors last update forks stars open issues license

DocumentationReport BugRequest Feature


Table of Contents

Getting Started

Prerequisites

Before proceeding with the installation and usage of this project, ensure that you have the following prerequisites in place:

Run Locally

Step 1: Extract dataset file at ./dataset/billion-primes.7z

You can download at here

Step 2: Compile program, it will generate miller_rabin file (executable file) from miller_rabin.cpp:

g++ -o miller_rabin miller_rabin.cpp

Step 3: Run executable file and wait :))

./miller_rabin

Benchmark

Benchmarking on dataset from 1 to 1 billion

Using a simple C++ script with 3 testing rounds and 20 benchmark rounds, which took about total 02:10:09 (7808.97 sec) :))

OS: Ubuntu 22.04.4 LTS x86_64
CPU: Intel i7-9750H (12) @ 4.500GHz

      /=================================\
      |                                 |
      |          MILLER RABIN           |
      |      ____________________       |
      |  Probabilistic primality test   |
      |                                 |
      \=================================/
           \_______QuanBlue_______/

================[ BENCHMARK ]=================
                     ***
[+] Benchmarking round <1>...Done! - Run in 388319.787326 (ms)
[+] Benchmarking round <2>...Done! - Run in 384664.877112 (ms)
[+] Benchmarking round <3>...Done! - Run in 382277.636380 (ms)
[+] Benchmarking round <4>...Done! - Run in 379976.218502 (ms)
[+] Benchmarking round <5>...Done! - Run in 380489.474973 (ms)
[+] Benchmarking round <6>...Done! - Run in 389533.944643 (ms)
[+] Benchmarking round <7>...Done! - Run in 391716.273947 (ms)
[+] Benchmarking round <8>...Done! - Run in 394091.112519 (ms)
[+] Benchmarking round <9>...Done! - Run in 397559.886904 (ms)
[+] Benchmarking round <10>...Done! - Run in 398380.716659 (ms)
[+] Benchmarking round <11>...Done! - Run in 394647.207036 (ms)
[+] Benchmarking round <12>...Done! - Run in 396271.656236 (ms)
[+] Benchmarking round <13>...Done! - Run in 400568.897206 (ms)
[+] Benchmarking round <14>...Done! - Run in 390854.019236 (ms)
[+] Benchmarking round <15>...Done! - Run in 389165.656980 (ms)
[+] Benchmarking round <16>...Done! - Run in 391387.991854 (ms)
[+] Benchmarking round <17>...Done! - Run in 390859.553101 (ms)
[+] Benchmarking round <18>...Done! - Run in 382307.175902 (ms)
[+] Benchmarking round <19>...Done! - Run in 395381.857096 (ms)
[+] Benchmarking round <20>...Done! - Run in 390516.020479 (ms)
----------------------------------------------
Total runtime for 20 benchmark rounds: 7808969.964091 (ms)

================[ STATISTICS ]================
            *** Average result ***
ROUND
[+] Total test     : 1000000000
[+] Total correct  : 999999992
[+] Total runtime  : 328557.100229 (ms)
----------------------------------------------
ALGORITHM
[+] Average runtime: 0.000329 (ms)
[+] Average correct: 100.000000%

(Program output)

Roadmap

  • Miller Rabin algorithm
  • Benchmark

Contributors

Contributions are always welcome!

Credits

License

Distributed under MIT license. See LICENSE for more information.


Bento @quanblue  ·  GitHub @QuanBlue  ·  Gmail quannguyenthanh558@gmail.com