Mercurial > octave

comparison scripts/specfun/isprime.m @ 31051:5f015f2829b7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
maint: Merge stable to default
author Arun Giridhar <arungiridhar@gmail.com>
date Wed, 01 Jun 2022 17:20:22 -0400
parents 83f9f8bda883 3a93a77dd4cf
children 597f3ee61a48
comparison
equal deleted inserted replaced
31049:d5997bbdb641 31051:5f015f2829b7
101 ## because of the method used by __isprimelarge__ below. 101 ## because of the method used by __isprimelarge__ below.
102 maxp = 37; 102 maxp = 37;
103 pr = [2 3 5 7 11 13 17 19 23 29 31 37]; 103 pr = [2 3 5 7 11 13 17 19 23 29 31 37];
104 tf = lookup (pr, x, "b"); # quick search for table matches. 104 tf = lookup (pr, x, "b"); # quick search for table matches.
105 105
106 THRESHOLD = 29e9; 106 THRESHOLD = 195e8;
107 ## FIXME: THRESHOLD is the input value at which Miller-Rabin 107 ## FIXME: THRESHOLD is the input value at which Miller-Rabin
108 ## becomes more efficient than direct division. For smaller numbers, 108 ## becomes more efficient than direct division. For smaller numbers,
109 ## use direct division. For larger numbers, use Miller-Rabin. 109 ## use direct division. For larger numbers, use Miller-Rabin.
110 ## 110 ##
111 ## From numerical experiments in Oct 2021, this was observed: 111 ## From numerical experiments in Jun 2022, this was observed:
112 ## THRESHOLD Division Miller-Rabin 112 ## THRESHOLD Division Miller-Rabin
113 ## 380e9 75.0466s 30.868s 113 ## 29e9 29.8196s 26.2484s (previous value)
114 ## 100e9 45.0874s 29.1794s 114 ## 20e9 26.7445s 26.0161s
115 ## 10e9 18.5075s 25.4392s 115 ## 10e9 20.9330s 25.3247s
116 ## 50e9 31.6317s 27.7251s 116 ## 19e9 26.5397s 26.8987s
117 ## 25e9 25.1215s 27.004s 117 ## 195e8 26.5735s 26.4749s
118 ## 38e9 31.4674s 28.1336s 118 ## which is close enough, so new threshold = 195e8.
119 ## 30e9 28.3848s 27.9982s
120 ## which is close enough to interpolate, so final threshold = 29 billion.
121 ## 119 ##
122 ## The test code was this: 120 ## The test code was this:
123 ## n = THRESHOLD - (1:1e7); tic; isprime(n); toc 121 ## n = THRESHOLD - (1:1e7); tic; isprime(n); toc
124 ## n = THRESHOLD + (1:1e7); tic; isprime(n); toc 122 ## n = THRESHOLD + (1:1e7); tic; isprime(n); toc
125 ## 123 ##