CODEWITHSUNDEEP
fortranbigdataprimesgfortranfortran95
micahjam97
micahjam97

Reputation: 33

Fortran 95: super large numbers for prime test

I'm pretty new to Fortran, as in started learning it 2 days ago new. I started learning Fortran because I was getting into prime numbers, and I wrote a program in python that was so fast, it could determine 123098237 was a prime in 0.1 seconds. Impressive, I know. What's not impressive is when I try to find out if (2^127)-1 or 170141183460469231731687303715884105727 (it is, by the way) is a prime number. The program ran so long, I just ended up having to stop it. So, I started looking for some faster languages to write it in, so I wrote the program in C. It was faster, but the problem of super large prime numbers came into play. I was going to to see if there was a solution but then I heard through the grapevine that, if your programming with numbers, Fortran is the fastest and best way to go. I vaguely remember my step dad's old Fortran 77 text books from college, but they were basically useless to me, because they were talking about working with punch cards. So, I went online, got gfortran for Ubuntu 12.04 x86, got a couple of pdfs, and started learning. Before you know it I made a program that received input and tested for primality, and worked! But, the same old problem came up, the number was too big. And so, how do I handle big numbers like this with Fortran?

Upvotes: 2

Views: 1019

Answers (3)

user448810
user448810

Reputation: 17866

I'll guess that your algorithm is trial division. If that's true, you need a better algorithm; the implementation language won't matter.

Pseudocode for the Miller-Rabin primality test is shown below. It's probabilistic, but you can reduce the chance of error by increasing the k parameter, up to a maximum of about k=25:

function isPrime(n, k=5)
    if n < 2 then return False
    for p in [2,3,5,7,11,13,17,19,23,29]
        if n % p == 0 then return n == p
    s, d = 0, n-1
    while d % 2 == 0
        s, d = s+1, d/2
    for i from 0 to k
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1 then next i
        for r from 1 to s
            x = (x * x) % n
            if x == 1 then return False
            if x == n-1 then next i
        return False
    return True

I'll leave it to you to translate that to Fortran or some other language; if you're programming in C, there is a library called GMP that is frequently used for handling very large numbers, and the function shown above is built-it to that library. It's very fast; even numbers that are hundreds of digits long should be classified as prime or composite almost instantly.

If you want to be certain of the primality of a number, there are other algorithms that can actually provide a proof of primality. But they are much more complicated, and much slower.

You might be interested in the essay Programming with Prime Numbers at my blog.

Upvotes: 1

M. S. B.
M. S. B.

Reputation: 29401

Most languages provide certain standard intrinsic types which are fully adequate for solving standard scientific and engineering problems. You don't need 80 digit numbers to calculate the thickness of a bridge girder or plan a spacecraft orbit. It would be difficult to measure to that accuracy. In Fortran, if you want to do extra precision calculations (e.g., for number theory) you need to look to libraries that augment the language, e.g., mpfun90 at http://crd-legacy.lbl.gov/~dhbailey/mpdist/ or fmlib at http://myweb.lmu.edu/dmsmith/fmlib.html

Upvotes: 1

High Performance Mark
High Performance Mark

Reputation: 78364

Fortran, like many other compiled languages, doesn't provide such large integers or operations on them out-of-the-box. An up to date compiler ought to provide an integer with 18 decimal digits, but no more than that.

If you want to program, in Fortran, data types and operations for such big integers use your favourite search engine on terms such as Fortran multiple precision. You could even search around here on SO for relevant questions and answers.

If you want to investigate the mathematics of such large integers stick with Python; you'll struggle to write software yourself which matches its speed of operations on multiple precision arithmetic. One of the reasons that Python takes a long time to determine the primality of a large number is that it takes a program, any program written in any language, a long time to determine the primality of a large number. If you dig around you're likely to find that the relevant Python routines actually call code written in C or something similarly low-level. Investigate, if you wish, the topic of the computational complexity of primality testing.

I'm not saying you won't be able to write code to outperform the Python intrinsics, just that you will find it a challenge.

Upvotes: 2

Related Questions