Блог

Я довольно новичок в Fortran, так как начал изучать его 2 дня назад. Я начал изучать Fortran, потому что я разбирался в простых числах, и я написал программу на python, которая была настолько быстрой, что могла определить, что 123098237 является простым числом за 0,1 секунды. Впечатляет, я знаю. Что не впечатляет, так это когда я пытаюсь выяснить, является ли (2 ^ 127) -1 или 170141183460469231731687303715884105727 (это, кстати) простым числом. Программа работала так долго, что мне просто пришлось ее остановить. Итак, я начал искать более быстрые языки для записи, поэтому я написал программу на C. Это было быстрее, но возникла проблема сверхбольших простых чисел. Я собирался посмотреть, есть ли решение, но потом я услышал через виноградную лозу, что, если вы программируете с числами, Fortran — самый быстрый и лучший способ. Я смутно помню старые учебники моего отчима по Fortran 77 из колледжа, но они были в основном бесполезны для меня, потому что в них говорилось о работе с перфокартами. Итак, я вышел в Интернет, получил gfortran для Ubuntu 12.04 x86, получил пару PDF-файлов и начал изучать. Прежде чем вы это узнаете, я создал программу, которая получала входные данные, тестировалась на простоту и работала! Но возникла та же старая проблема, число было слишком большим. Итак, как мне обрабатывать такие большие числа с помощью Fortran?

Fortran, как и многие другие скомпилированные языки, не предоставляет таких больших целых чисел или операций над ними «из коробки». Обновленный компилятор должен предоставлять целое число с 18 десятичными цифрами, но не более того.

Если вы хотите программировать на Fortran типы данных и операции для таких больших целых чисел, используйте свою любимую поисковую систему по таким терминам, как Fortran multiple precision . Вы даже можете поискать здесь, на SO, соответствующие вопросы и ответы.

Если вы хотите исследовать математику таких больших целых чисел, придерживайтесь Python; вам будет сложно самостоятельно написать программное обеспечение, которое соответствует его скорости операций с арифметикой множественной точности. Одна из причин, по которой Python требует много времени для определения простоты большого числа, заключается в том, что программе, любой программе, написанной на любом языке, требуется много времени для определения простоты большого числа. Если вы покопаетесь, вы, вероятно, обнаружите, что соответствующие подпрограммы Python на самом деле вызывают код, написанный на C или что-то подобное низкоуровневое. Исследуйте, если хотите, тему вычислительной сложности тестирования на простоту.

Я не говорю, что вы не сможете написать код, превосходящий встроенные функции Python, просто вам будет сложно.

Большинство языков предоставляют определенные стандартные встроенные типы, которые полностью подходят для решения стандартных научных и инженерных задач. Вам не нужны 80-значные числа, чтобы рассчитать толщину балки моста или спланировать орбиту космического корабля. Было бы трудно измерить с такой точностью. В Fortran, если вы хотите выполнять вычисления с повышенной точностью (например, для теории чисел), вам нужно обратиться к библиотекам, которые дополняют язык, например, mpfun90 в http://crd-legacy.lbl.gov /~dhbailey/mpdist/ или fmlib в http://myweb.lmu.edu/dmsmith/fmlib.html

Я предполагаю, что ваш алгоритм — это пробное деление. Если это так, вам нужен лучший алгоритм; язык реализации не будет иметь значения.

Псевдокод для теста простоты Миллера-Рабина показан ниже. Это вероятностно, но вы можете уменьшить вероятность ошибки, увеличив параметр k, максимум до 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
 

Я предоставляю вам перевести это на Fortran или какой-либо другой язык; если вы программируете на C, существует библиотека под названием GMP, которая часто используется для обработки очень больших чисел, и функция, показанная выше, встроена в эту библиотеку. Это очень быстро; четные числа длиной в сотни цифр должны быть классифицированы как простые или составные почти мгновенно.

Если вы хотите быть уверены в простоте числа, существуют другие алгоритмы, которые действительно могут обеспечить доказательство простоты. Но они намного сложнее и намного медленнее.

Возможно, вас заинтересует эссе «Программирование с простыми числами» в моем блоге.