Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Всего известно 47 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 40.

Последовательность простых чисел Мерсенна и их показателей начинается так:

: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, …

: 2, 3, 5, 7, 13, 17, 19, 31, 61, …

В данной работе используется следующий алгоритм для поиска -ого простого числа Мерсенна:

1.

2. Проверяется, является ли простым числом. Если нет, то и возврат к шагу 2.

3. Вычисляется .

4. Проверяется, является ли простым числом. Если нет, то и возврат к шагу 2.

5. Если , то – искомое простое число Мерсенна, иначе , и возврат к шагу 2.

Результаты вычислительного эксперимента

Для 8-ого числа Мерсенна и 4-х потоков имеем:

Вывод: применение языка FPTL для распараллеливания решения предложенной задачи описанным методом не даёт какого-либо ускорения.

// Вычисление n-ого простого числа Мерсенна

// in [1] - номер простого числа Мерсенна (n)

Scheme MersenneSimple

{

@ = id.nMersenneSimple.print;

// Вычисление n-ого числа Мерсенна

// in [1] - номер числа Мерсенна (n)

// out [1] - n-ое число Мерсенна

nMersenne = [1].pow2.dec;

// Вычисление n-ого простого числа Мерсенна

// in [1] - номер простого числа Мерсенна (n)

nMersenneSimple = ([1] * 1 * 2).nMersenneSimpleR;

// in [2] - текущий номер простого числа Мерсенна (m)

// in [3] - номер текущего простого числа (p)

// out [1] - n-ое простое число Мерсенна

nMersenneSimpleR = ([1] * [2]).equal ->

([3].isSimple ->

([3].nMersenne.isSimple ->

[3].nMersenne,

([1] * [2] * [3].inc).nMersenneSimpleR

),

([1] * [2] * [3].inc).nMersenneSimpleR

),

([3].isSimple ->

([3].nMersenne.isSimple ->

([1] * [2].inc * [3].inc).nMersenneSimpleR,

([1] * [2] * [3].inc).nMersenneSimpleR

),

([1] * [2] * [3].inc).nMersenneSimpleR

)

;

// --- Вспомогательные функции ---

// Определение, является ли число простым

// in [1] - целое число

isSimple = ([1] * [1].sqrt.round).isSimpleR;

// in [2] - проверяемый делитель

// out [1] - true, если число простое, иначе - false

isSimpleR = ([2] * 1).lequal -> true,

([1] * [2]).equal -> ([1] * ([2] * 1).sub).isSimpleR,

(([1] * [2]).mod * 0).nequal -> ([1] * ([2] * 1).sub).isSimpleR, false;

// Возведение числа в степень

// in [1] - число

// in [2] - степень

// out [1] - результат возведения числа в степень

pow = ([2] * 0).equal -> 1, ([1] * ([1] * [2].dec).pow).mul;

// Возведение числа 2 в степень

// in [1] - степень

// out [1] - результат возведения числа 2 в степень

pow2 = (2 * [1]).pow;

// Инкремент

inc = ([1] * 1).add;

// Декремент

dec = ([1] * 1).sub;

}

Application

% MersenneSimple(8)

1 Среднее арифметическое по результатам 5 измерений

Москва, 2012

Характеристики

Список файлов лабораторной работы