Miller–Rabin primality test: Difference between revisions
m
→{{header|Wren}}: Minor tidy
VincentARM (talk | contribs) (add task to aarch64 assembly raspberry pi 3) |
m (→{{header|Wren}}: Minor tidy) |
||
| (2 intermediate revisions by one other user not shown) | |||
Line 5,680:
False
>>> </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]].
<code>**mod</code> is defined at [[Modular exponentiation#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}}==
Line 6,710 ⟶ 6,834:
I've therefore used this method to check the same numbers as in my Kotlin entry.
<syntaxhighlight lang="
var iters = 10
| |||