Miller–Rabin primality test: Difference between revisions
Content added Content deleted
VincentARM (talk | contribs) (add task to aarch64 assembly raspberry pi 3) |
(Added Quackery.) |
||
Line 5,680: | Line 5,680: | ||
False |
False |
||
>>> </pre> |
>>> </pre> |
||
=={{header|Quackery}}== |
|||
Translated from the current (22 Sept 2023) pseudocode from [[wp:Miller-Rabin primality test#Miller–Rabin_test|Wikipedia]], which is: |
|||
'''Input #1''': ''n'' > 2, an odd integer to be tested for primality |
|||
'''Input #2''': ''k'', the number of rounds of testing to perform |
|||
'''Output''': “''composite''” if ''n'' is found to be composite, “''probably prime''” otherwise |
|||
'''let''' ''s'' > 0 and ''d'' odd > 0 such that ''n'' − 1 = 2<sup>''s''</sup>''d'' <u># by factoring out powers of 2 from ''n'' − 1</u> |
|||
'''repeat''' ''k'' '''times''': |
|||
''a'' ← random(2, ''n'' − 2) # ''n'' is always a probable prime to base 1 and ''n'' − 1 |
|||
''x'' ← ''a''<sup>''d''</sup> mod ''n'' |
|||
'''repeat''' ''s'' '''times''': |
|||
''y'' ← ''x''<sup>2</sup> mod ''n'' |
|||
'''if''' ''y'' = 1 and ''x'' ≠ 1 and ''x'' ≠ ''n'' − 1 '''then''' <u># nontrivial square root of 1 modulo ''n''</u> |
|||
'''return''' “''composite''” |
|||
''x'' ← ''y'' |
|||
'''if''' ''y'' ≠ 1 '''then''' |
|||
'''return''' “''composite''” |
|||
'''return''' “''probably prime''” |
|||
As Quackery does not have variables, I have included a "builder" (i.e. a compiler extension) to provide basic global variables, in order to facilitate comparison to the pseudocode. |
|||
<code>var myvar</code> will create a variable called <code>myvar</code> initialised with the value <code>0</code>, and additionally the words <code>->myvar</code> and <code>myvar-></code>, which assign a value to <code>myvar</code> and return the value of <code>myvar</code> respectively. |
|||
The variable <code>c</code> is set to <code>true</code> if the number being tested is composite. This is included as Quackery does not have a <code>break</code> that can exit nested iterative loops. |
|||
<code>eratosthenes</code> and <code>isprime</code> are defined at [[Sieve of Eratosthenes#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> [ nextword |
|||
dup $ "" = if |
|||
[ $ "var needs a name" |
|||
message put bail ] |
|||
$ " [ stack 0 ] is " |
|||
over join |
|||
$ " [ " |
|||
join over join |
|||
$ " replace ] is ->" |
|||
join over join |
|||
$ " [ " |
|||
join over join |
|||
$ " share ] is " |
|||
join swap join |
|||
$ "-> " join |
|||
swap join ] builds var ( [ $ --> [ $ ) |
|||
10000 eratosthenes |
|||
[ 1 & not ] is even ( n --> b ) |
|||
var n var d var s var a |
|||
var t var x var y var c |
|||
[ dup 10000 < iff isprime done |
|||
dup even iff |
|||
[ drop false ] done |
|||
dup ->n |
|||
[ 1 - 0 swap |
|||
[ dup even while |
|||
1 >> dip 1+ again ] ] |
|||
->d ->s |
|||
false ->c |
|||
20 times |
|||
[ n-> 2 - random 2 + ->a |
|||
s-> ->t |
|||
a-> d-> n-> **mod ->x |
|||
s-> times |
|||
[ x-> 2 n-> **mod ->y |
|||
y-> 1 = |
|||
x-> 1 != |
|||
x-> n-> 1 - != |
|||
and and iff |
|||
[ true ->c conclude ] |
|||
done |
|||
y-> ->x ] |
|||
c-> iff conclude done |
|||
y-> 1 != if |
|||
[ true ->c conclude ] ] |
|||
c-> not ] is prime ( n --> b ) |
|||
say "Primes < 100:" cr |
|||
100 times [ i^ prime if [ i^ echo sp ] ] |
|||
cr cr |
|||
[] 1000 times |
|||
[ i^ 9223372036854774808 + dup |
|||
prime iff join else drop ] |
|||
say "There are " |
|||
dup size echo |
|||
say " primes between 9223372036854774808 and 9223372036854775808:" |
|||
cr cr |
|||
witheach [ echo i^ 1+ 4 mod iff sp else cr ] |
|||
cr cr |
|||
4547337172376300111955330758342147474062293202868155909489 dup echo |
|||
prime iff |
|||
[ say " is prime." ] |
|||
else |
|||
[ say " is not prime." ] |
|||
cr cr |
|||
4547337172376300111955330758342147474062293202868155909393 dup echo |
|||
prime iff |
|||
[ say "is prime." ] |
|||
else |
|||
[ say " is not prime." ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Primes < 100: |
|||
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
|||
There are 23 primes between 9223372036854774808 and 9223372036854775808: |
|||
9223372036854774893 9223372036854774917 9223372036854774937 9223372036854774959 |
|||
9223372036854775057 9223372036854775073 9223372036854775097 9223372036854775139 |
|||
9223372036854775159 9223372036854775181 9223372036854775259 9223372036854775279 |
|||
9223372036854775291 9223372036854775337 9223372036854775351 9223372036854775399 |
|||
9223372036854775417 9223372036854775421 9223372036854775433 9223372036854775507 |
|||
9223372036854775549 9223372036854775643 9223372036854775783 |
|||
4547337172376300111955330758342147474062293202868155909489 is prime. |
|||
4547337172376300111955330758342147474062293202868155909393 is not prime.</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |