PrimeMillerRabin
Test primes using the Miller-Rabin Method. See http://en.wikipedia.org/wiki/Miller-Rabin_primality_test for more details. For large prime numbers this is significantly faster than Ruby's default method.
Benchmarks
The current standard Ruby Prime Generators are Generator23, EratosthenesSieve, and TrialDivision
The following code was used to compare Miller-Rabin with the existing Ruby Prime Generators:
Prime::MillerRabin.speed_intercept
miller_rabin = Prime::MillerRabin.new
generator23 = Prime::Generator23.new
eratosthenes = Prime::EratosthenesGenerator.new
trial_division = Prime::TrialDivisionGenerator.new
generators = [miller_rabin, generator23, eratosthenes, trial_division]
generator_names = ['MillerRabin', 'Generator23', 'Eratosthenes', 'TrialDivision']
puts(("%-15s" * generator_names.size) % generator_names + " Number Tested")
primes.each_with_index do |number|
remove = []
timings = []
generators.each_with_index do |generator, j|
if generator
name = generator_names[j]
benchmark = Benchmark.measure { Prime.prime?(number, generator) }
if benchmark.total > 120
puts "Removing #{name} as it is now exceeding 2 minutes to determine primality"
remove << generator
end
timings << benchmark.total
else
timings << nil
end
end
timings.map! { |x| x ? '%-15.6f' % [x] : '%15s' % [' '] }
timings << number
puts timings.join(' ')
generators.map! { |x| remove.include?(x) ? nil : x }
end
The results (formatted for readability):
MillerRabin Generator23 Eratosthenes TrialDivision Number Tested
0.000000 0.000000 0.000000 0.000000 2
0.000000 0.000000 0.000000 0.000000 7
0.000000 0.000000 0.000000 0.000000 67
0.000000 0.000000 0.000000 0.000000 619
0.000000 0.000000 0.000000 0.000000 6197
0.000000 0.000000 0.000000 0.000000 61813
0.000000 0.000000 0.000000 0.000000 618041
0.000000 0.000000 0.010000 0.000000 6180341
0.000000 0.000000 0.000000 0.010000 61803419
0.000000 0.000000 0.020000 0.030000 618034003
0.000000 0.010000 0.050000 0.120000 6180339923
0.000000 0.040000 0.220000 1.690000 61803398903
0.000000 0.140000 0.990000 13.080000 618033988751
0.010000 0.390000 4.110000 119.750000 6180339887543
Removing TrialDivision as it is now exceeding 2 minutes to determine primality
0.000000 1.820000 30.460000 1081.650000 61803398875019
Removing Eratosthenes as it is now exceeding 2 minutes to determine primality
0.000000 7.180000 139.250000 618033988749911
0.010000 16.990000 6180339887498971
0.000000 53.850000 61803398874989489
Removing Generator23 as it is now exceeding 2 minutes to determine primality
0.010000 170.560000 618033988749894811
MillerRabin Number Tested
0.000000 6180339887498948681
0.000000 61803398874989486159
0.000000 618033988749894877249
0.000000 6180339887498948771861
0.020000 61803398874989479329793
0.000000 618033988749894843629693
0.010000 6180339887498948973166649
0.000000 61803398874989485436698673
0.000000 618033988749894820007248007
0.020000 6180339887498948474950385857
0.000000 61803398874989473754387579003
0.000000 618033988749894825504806010893
0.010000 6180339887498947551360618332249
0.020000 61803398874989482269005624377351
0.000000 618033988749894786661259224809529
0.010000 6180339887498948010727780323950599
0.020000 61803398874989484718963821666894041
0.000000 618033988749894884083126364088041501
0.010000 6180339887498948102961500692498350149
0.020000 61803398874989478668431765490160893959
0.000000 618033988749894805573783586380189794451
0.010000 6180339887498948055737835863801897943079
0.020000 61803398874989485393081637096535678255353
0.010000 618033988749894834588003257131289987252251
0.000000 6180339887498947881652517839295296785350671
0.020000 61803398874989486244165414105234617248252037
0.010000 618033988749894783213491626788008578938568879
0.020000 6180339887498948782872866439052136911913091139
0.010000 61803398874989490364029864846980172112537321529
0.020000 618033988749894863075479441166460873230870642701
0.010000 6180339887498948306236240753237881949152685850683
0.020000 61803398874989488254659266067206448022023187726371
0.010000 618033988749894861777405226532753966098246560383039
0.020000 6180339887498948285467053319098571435030700533743709
0.010000 61803398874989477537758550051322222735078764216058197
0.030000 618033988749894860448177230747838093194439500102631463
0.000000 6180339887498948264199405386539917468569787569258103079
0.030000 61803398874989493531029795335430005513685313509163794507
0.010000 618033988749894848198012021594053408512953632558975811599
0.020000 6180339887498947959306404625379054205386139310393785319457
0.010000 61803398874989483774453770978282381091808569225505635565881
0.030000 618033988749894815443792511252200669382367419606694849675361
0.020000 6180339887498947619220040347787051296966435652506272353222859
0.010000 61803398874989487610181945125549561435952112121023814594199579
0.030000 618033988749894876101819451255495614359521121210238145941995523
0.030000 6180339887498948212955080513466361817213398943496249088445251857
0.010000 61803398874989482129550805134663618172133989434962490884452515863
0.030000 618033988749894751143429459463296107944467923968039965359763095659
0.020000 6180339887498948446795342486410828729802972178101532233394458460333
0.020000 61803398874989478481642718356729934335736646975120073823244888571933
0.030000 618033988749894856652155661655839578904883367421943720360845238075493
0.030000 6180339887498948949645441833030610378635590461796733108293232926654757
0.010000 61803398874989480301481173134972953636273741716112229370497596164931657
0.030000 618033988749894753974954423641286068895632548351228417905324051774046223
0.030000 6180339887498948520546690390581730038298422859710161695046278715245855121
0.030000 61803398874989478928365168519136536547194805389435200848107342688424034467
0.030000 618033988749894789283651685191365365471948053894352008481073426884240343509
0.030000 6180339887498948294571027916661222540210003624234170715361482714540612255771
0.030000 61803398874989487766524411943583052027986313265829514720223808493784628461601
0.030000 618033988749894800532217995004297294265682700282490226136494383363790190149697
0.030000 6180339887498948416698319280344483481399122642162528507048910242032867738649237
0.020000 61803398874989489103496864767062961278898774093676800018696699321068267432312833
0.030000 618033988749894759394604061974146240391453136348727601568097742524293606434406857
0.030000 6180339887498947804570623956855835799750586730828140653471168226341158572966019139
0.030000 61803398874989483100696239659303319497571196124462157841676261489768925936587112561
0.040000 618033988749894911886802398044952578976757222303513599328195882519406702676701872319
0.030000 6180339887498948040470157294423934003086968742249909047796181923571167782622608752829
0.040000 61803398874989482130138159641880286889558652991755453590739062278308316616857143476423
0.040000 618033988749894793694396209256547719156563080809452726102954734101536945518474539565289
0.040000 6180339887498948378655728287161559587390005993824156217900521559920108985586295718806271
0.040000 61803398874989483786557282871615595873900059938241562179005215599201089855862957188055087
0.030000 618033988749894837865572828716155958739000599382415621790052155992010898558629571880550497
0.020000 6180339887498948830968576870427947960714166184011296269736399160078562264717483249716166887
0.040000 61803398874989484691182980038148372620548380318615842282676970799517996414125332249876365411
0.030000 618033988749894890333863264375057010044603181444123867803013957610391478937847325466187268189
0.040000 6180339887498947977001918745221006711878151744937975851870262250979402473717801191356835561549
0.050000 61803398874989483475366043046328320673053037727392809823342131810292073999820700166788504093107
0.040000 618033988749894819932273008086810192513444296161875893014863280900928542947636248655004447015003
0.030000 6180339887498948673607127596915238380081197557204429497142489999473035735094626582962223475327741
0.040000 61803398874989482941796095840775292161237938807358930435474042471020354906000153058324802711846941
0.030000 618033988749894799063759517380736188495787093956106388067133564520523529500432628412868570787086393
0.040000 6180339887498948233471206702023495749890609292500927210972190526722675451480877501491721358521925753
Larger numbers
For primes nearing a googol (10**100) it is still subsecond. Starting at a google - 3 the following was used for benchmarking,
Benchmark.bm do |x|
(1..50).each do |z|
exponent = "#{z}00".to_i
number = 10**exponent - 3
x.report("10**#{exponent} - 3") { number.prime? }
end
end
Results (formatted for readability)
user system total real
10**100 - 3 0.000000 0.000000 0.000000 ( 0.000873)
10**200 - 3 0.000000 0.000000 0.000000 ( 0.003954)
10**300 - 3 0.010000 0.000000 0.010000 ( 0.008990)
10**400 - 3 0.020000 0.000000 0.020000 ( 0.019595)
10**500 - 3 0.030000 0.000000 0.030000 ( 0.030311)
10**600 - 3 0.050000 0.000000 0.050000 ( 0.045907)
10**700 - 3 0.080000 0.010000 0.090000 ( 0.086039)
10**800 - 3 0.120000 0.000000 0.120000 ( 0.120604)
10**900 - 3 0.140000 0.000000 0.140000 ( 0.137074)
10**1000 - 3 0.190000 0.000000 0.190000 ( 0.197226)
10**1100 - 3 0.270000 0.010000 0.280000 ( 0.267312)
10**1200 - 3 0.340000 0.000000 0.340000 ( 0.344282)
10**1300 - 3 0.370000 0.000000 0.370000 ( 0.376330)
10**1400 - 3 0.520000 0.010000 0.530000 ( 0.530934)
10**1500 - 3 0.610000 0.010000 0.620000 ( 0.622023)
10**1600 - 3 0.810000 0.010000 0.820000 ( 0.817583)
10**1700 - 3 0.910000 0.010000 0.920000 ( 0.917380)
10**1800 - 3 1.050000 0.010000 1.060000 ( 1.071910)
10**1900 - 3 1.180000 0.020000 1.200000 ( 1.189116)
10**2000 - 3 1.410000 0.020000 1.430000 ( 1.438527)
10**2100 - 3 1.480000 0.020000 1.500000 ( 1.499630)
10**2200 - 3 1.820000 0.030000 1.850000 ( 1.838164)
10**2300 - 3 2.000000 0.030000 2.030000 ( 2.026655)
10**2400 - 3 1.970000 0.020000 1.990000 ( 1.997051)
10**2500 - 3 2.580000 0.040000 2.620000 ( 2.616159)
10**2600 - 3 3.060000 0.050000 3.110000 ( 3.110208)
10**2700 - 3 2.900000 0.050000 2.950000 ( 2.950306)
10**2800 - 3 2.900000 0.050000 2.950000 ( 2.945470)
10**2900 - 3 3.310000 0.050000 3.360000 ( 3.360690)
10**3000 - 3 3.700000 0.070000 3.770000 ( 3.765682)
10**3100 - 3 4.610000 0.070000 4.680000 ( 4.680919)
10**3200 - 3 5.530000 0.080000 5.610000 ( 5.615243)
10**3300 - 3 4.770000 0.090000 4.860000 ( 4.860779)
10**3400 - 3 5.190000 0.090000 5.280000 ( 5.278715)
10**3500 - 3 5.800000 0.100000 5.900000 ( 5.891275)
10**3600 - 3 6.310000 0.110000 6.420000 ( 6.417548)
10**3700 - 3 8.450000 0.070000 8.520000 ( 8.510452)
10**3800 - 3 8.830000 0.070000 8.900000 ( 8.901605)
10**3900 - 3 8.040000 0.080000 8.120000 ( 8.114340)
10**4000 - 3 10.030000 0.050000 10.080000 ( 10.087971)
10**4100 - 3 8.730000 0.060000 8.790000 ( 8.782747)
10**4200 - 3 11.550000 0.070000 11.620000 ( 11.607290)
10**4300 - 3 10.810000 0.100000 10.910000 ( 10.913006)
10**4400 - 3 12.380000 0.180000 12.560000 ( 12.552739)
10**4500 - 3 12.580000 0.180000 12.760000 ( 12.753963)
10**4600 - 3 13.130000 0.190000 13.320000 ( 13.311686)
10**4700 - 3 14.380000 0.190000 14.570000 ( 14.560988)
10**4800 - 3 13.680000 0.220000 13.900000 ( 13.895690)
10**4900 - 3 15.800000 0.220000 16.020000 ( 16.017528)
10**5000 - 3 15.290000 0.230000 15.520000 ( 15.513277)
Installation
Add this line to your application's Gemfile:
gem 'prime_miller_rabin'
And then execute:
$ bundle
Or install it yourself as:
$ gem install prime_miller_rabin
Usage
require 'prime_miller_rabin'
# You now have access to Prime::MillerRabin
Prime.prime?(large_number, Prime::MillerRabin.new)
# Even when using the generator, Ruby's method for #prime? is slower than having Miller Rabin determine it directly.
# Miller Rabin can intercept the Prime.prime? function and call Miller Rabin directly when its generator is used.
# To accomplish this use:
Prime::MillerRabin.speed_intercept
# To use the speed intercept and have Miller Rabin be the default prime generator in all cases use:
Prime::MillerRabin.make_default
Contributing
- Fork it
- Create your feature branch (
git checkout -b my-new-feature
) - Commit your changes (
git commit -am 'Add some feature'
) - Push to the branch (
git push origin my-new-feature
) - Create new Pull Request