Anonymous user
Miller–Rabin primality test: Difference between revisions
m
→{{header|REXX}}: added DO-end labels, removed superflous blank lines (before suboutines), changed section header comments, added whitespade in multi-line statements.. -- ~~~~
m (→{{header|REXX}}: added DO-end labels, removed superflous blank lines (before suboutines), changed section header comments, added whitespade in multi-line statements.. -- ~~~~) |
|||
Line 1,451:
=={{header|REXX}}==
With a K of 1, there seems to be a not uncommon number of failures, but
: with a K ≥ 2, the failures are rare,
: with a K ≥ 3, rare as hen's teeth.
This would be in the same vein as: 3 is prime, 5 is prime, 7 is prime, all odd numbers are prime.
Line 1,489:
exit
/*─────────────────────────────────────Miller-Rabin primality test.─────*/
/*─────────────────────────────────────Rabin-Miller (also known as)─────*/
Miller_Rabin: procedure; parse arg n,k
if n==2 then return 1 /*special case of an even prime. */
if n<2 | n//2==0 then return 0 /*check for low, or even number.
d=n-1
nL=n-1 /*saves a bit of time, down below*/
s=0
do while d//2==0; d=d%2; s=s+1; end /*while d//2==0 */
do k
a=random(2,nL)
x=(a**d) //
if x==1 | x==nL then iterate
do r=1 for s-1
x=(x*x) // n
if x==1 then return 0 /*definately it's not prime. */
if x==nL then leave
end
if x\==nL then return 0
end /*k*/
/*maybe it is, maybe it ain't ...*/
return 1 /*coulda/woulda/shoulda be prime.*/
/*─────────────────────────────────────SUSPENDERS subroutine────────────*/
suspenders: @.=0; !.=0
@.1=2; @.2=3; @.3=5; #=3 /*prime the pump with low primes.*/
!.2=1; !.3=1; !.5=1 /*and don't forget the water jar.*/
| |||