Разное

Как вычислить остаток от деления числа L на число M, которые вычисляются так:

M(p) = 2^p - 1; // Число Мерсена, двойка в степени p минус 1; при этом p - простое число;                            // Число Мерсена M(p) в двоичном виде состоит из p единиц L(p-1) = L (p-2)^2 - 2;   // То есть например L(1) = 4;  L(2)= L(1)^2 - 2 = 16 - 2 = 14; L(3) = L(2)^2 - 2 = 194 и т.д. // Число L очень быстро возрастает, поэтому посчитать его напряжно // Но нужно не само число L, а только остаток от деления L на число M.  // Число p примерно от 10 000 000 и больше

?

Подскажите хоть в какую сторону надо копать) Вычислять число L не представляется реальным. нужен только остаток от деления.

я вообще не понял почему L(1) = 4; L(2)= L(1)^2 - 2 = 16 - 2 = 14;
числа мерсена начиная с 1 будут идти в такой последовательности ( x=(x<<1)&1 )
т.е. 1,3,7,15, 31, 63 ......
остаток деления вычисляется просто оператором (остаток = x%y)
эти обозначения типа M(p) я вообще не понимаю

или я про другое ?

> при этом p - простое число;

простые числя этот 1,3,5,7,11,13 ......
те которые делятся только на 1 и на само себя

// можно просто одним сдвигом идти в обратном порядке
for (UINT x = ~0; x; x>>=1);

> остаток деления вычисляется просто оператором (остаток = x%y)
эти обозначения типа M(p) я вообще не понимаю


так ведь этот оператор работает с обычными переменными, в которые никак не поместятся такие числа.

Насчёт обозначений: M(p) - числа мерсена, p - нижний индекс, обозначающий порядковый номер числа. L - число, нужное для проверки чисел мерсена на простоту.

> ( x=(x<<1)&1 )
ошибся должно было быть ( x=(x<<1) | 1 )

>Число p примерно от 10 000 000 и больше
не понял сразу про число p , значит 10 000 000 бит или 1 250 000 байт

Интересная задачка :)
даже не знаю чего тут можно посоветовать , результат поискового запроса типа "остаток деления вычисление" вроде умалчивает о том как без деления получать остаток, но я сильно не читал, пока для себя не вижу пользы от вычислений с такими большими числами. // научиться-бы хотя-бы с маленькими

Польза в том, что за простое число, содержащее в записи более 100 000 000 цифр дают приз в 150 000$. Хотя теперь думаю, что нельзя придумать такой мега-хитрый алгоритм, который способен за приемлимое время на нескольких обычных компах вычислить такое число.

Думаю в домашних условиях посчитать такие числа будет затруднительно. Даже если правильно продумать алгоритм то упираемся в проблему нехватки вычислительной мощности ПК. Реально распараллелить вычисления, можно даже подключить CUDA платы на GPU 200й серии уже лучше работают с большими числами в отличие от предков. Но иногда подумать о таких вещах интересно а вдруг чтото и получится с оптимизацией алгоритма общета. Дерзай, нет ничего невозможного! (Я матику даже по школьной программе всегда заваливаю - не дано мне. хотя поступил на физмат - наверно везение).Кстати не интересуешся распределенными вычислениями?

Интересно, а что за платы такие?

У меня кстати в общих чертах появилась идея такого алгоритма (как реализовать не знаю):

Например есть столько то бит памяти (с адресами, тк потом нужно будет узнать номер бита). Сначала в каждый записываем 1 (единица будет обозначать простое число). Затем каждому чётному биту (2, 4, 6 и тп) присваиваем значение 0 (составное число). Ищем бит со значением 1 с минимальным адресом - его номер 3. "Вычёркиваем" каждый 3-й бит (3, 6, 9 и т.п.). И т.д. То есть таким образом находим идущие подряд простые числа. Но опять таки возникает проблема с величиной чисел и объёмом памяти. Например если для этой цели использовать жёсткий диск на 2 терабайта, то полученные числа не будет превышать ~16 000 000 000 000. Получается всего десятичных 14 разрядов => приз не достанется)).

По видимому проверка именно чисел Мерсена на простоту наиболее простой и быстрый способ найти простые числа. Но всё равно не для обычного ПК

насчет скидывания данных на жестяк согласен 2Тб маловато. Можно создать файл подобие контейнера со своей файловой системой и организовать сжатие. Проще под линухом создать архив пимонтировать его как диск и направить вывод данных туда (лучше конечно многотомные архивы - не пробовал поддерживаются ли они для монтирования?). Таким образом проблему с нехваткой места решили - а нагрузки на ЦП добавили хотя и незначительно.

Придумал - надо поиск производить в оперативке, а на веник сбрасывать только простые числа. К примеру есть 2 гига оперативки. Сначала все биты ставим единичками. Потом каждый чётный - 0, каждый, делящийся на 3, 5 и тд - 0. Остаются простые числа до 16 000 000 000, которые сбрасываем на веник. В тоже время надо запоминать, где было последнее "вычёркивание" для каждого простого числа. То есть например 3 последний раз встретилось в числе 15 999 999 999. Это нужно для того, чтобы знать, откуда начинать "вычёркивать" числа в диапазоне от 16 000 000 001 до 32 000 000 000. По идее должно работать быстро, если грамотно написать. Не знаю как реализовать работу с памятью.