Miller–Rabin primality test: Difference between revisions
→{{header|Fortran}}: Split.
(→{{header|Fortran}}: When generating X**P via repeated squarings of W, square W only if more power is needed. The resulting code loses DO WHILE and has a GO TO...) |
(→{{header|Fortran}}: Split.) |
||
Line 1,247:
=={{header|Fortran}}==
===Direct translation===
{{works with|Fortran|95}}
For the module ''PrimeDecompose'', see [[Prime decomposition#Fortran|Prime decomposition]].
Line 1,333 ⟶ 1,334:
''Possible improvements'': create bindings to the [[:Category:GMP|GMP library]], change <code>integer(huge)</code> into something like <code>type(huge_integer)</code>, write a lots of interfaces to allow to use big nums naturally (so that the code will be unchanged, except for the changes said above)
===With some avoidance of overflow===
Integer overflow is a severe risk, and even 64-bit integers won't get you far when the formulae are translated as <code>MOD(A**D,N)</code> - what is needed is a method for raising to a power that incorporates the modulus along the way. There is no library routine for that, so... <lang Fortran> MODULE MRTEST !Try the Miller-Rabin primality test.
CONTAINS !Working only with in-built integers.
Line 1,521 ⟶ 1,523:
35 F
</pre>
In this run, 32-bit integers falter for 19 in calculating 17<sup>9</sup>, and 64-bit integers falter for 31 with 19<sup>15</sup> by showing a negative number. Other 64-bit overflows however do not show a negative (as with 23<sup>15</sup>) because there is about an even chance that the high-order bit will be on or off. The compiler option for checking integer overflow does not report such faults with 64-bit integers, at least with the Compaq V6.6 F90/95 compiler. In this context, one misses the <code>IF OVERFLOW ... </code> that was part of Fortran II but which has been omitted from later versions.
Thus, there is no avoiding a special MODEXP function, even for small test numbers.
| |||