Fortran 95: сверхбольшие числа для простого теста

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


gfortran bigdata fortran primes fortran95
person micahjam97    schedule 27.06.2014    source источник

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

person High Performance Mark    schedule 27.06.2014

arrow_upward
1
arrow_downward

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

person M. S. B.    schedule 27.06.2014

arrow_upward
1
arrow_downward

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

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

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

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

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

person user448810    schedule 27.06.2014