|
|
|
| Как вычислить остаток от деления числа 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 и больше
|
? | |
|
|
|
|
|
|
|
для: sasha1133
(05.03.2010 в 17:59)
| | Подскажите хоть в какую сторону надо копать) Вычислять число L не представляется реальным. нужен только остаток от деления. | |
|
|
|
|
автор: .exp (08.03.2010 в 23:20) |
|
|
для: sasha1133
(06.03.2010 в 18:56)
| | я вообще не понял почему 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) я вообще не понимаю
или я про другое ? | |
|
|
|
|
|
|
|
для: .exp
(08.03.2010 в 23:20)
| | > при этом p - простое число;
простые числя этот 1,3,5,7,11,13 ......
те которые делятся только на 1 и на само себя
// можно просто одним сдвигом идти в обратном порядке
for (UINT x = ~0; x; x>>=1); | |
|
|
|
|
|
|
|
для: exp
(08.03.2010 в 23:25)
| | > остаток деления вычисляется просто оператором (остаток = x%y)
эти обозначения типа M(p) я вообще не понимаю
так ведь этот оператор работает с обычными переменными, в которые никак не поместятся такие числа.
Насчёт обозначений: M(p) - числа мерсена, p - нижний индекс, обозначающий порядковый номер числа. L - число, нужное для проверки чисел мерсена на простоту. | |
|
|
|
|
|
|
|
для: sasha1133
(09.03.2010 в 01:16)
| | > ( x=(x<<1)&1 )
ошибся должно было быть ( x=(x<<1) | 1 )
>Число p примерно от 10 000 000 и больше
не понял сразу про число p , значит 10 000 000 бит или 1 250 000 байт
Интересная задачка :)
даже не знаю чего тут можно посоветовать , результат поискового запроса типа "остаток деления вычисление" вроде умалчивает о том как без деления получать остаток, но я сильно не читал, пока для себя не вижу пользы от вычислений с такими большими числами. // научиться-бы хотя-бы с маленькими | |
|
|
|
|
|
|
|
для: exp
(09.03.2010 в 14:33)
| | Польза в том, что за простое число, содержащее в записи более 100 000 000 цифр дают приз в 150 000$. Хотя теперь думаю, что нельзя придумать такой мега-хитрый алгоритм, который способен за приемлимое время на нескольких обычных компах вычислить такое число. | |
|
|
|
|
|
|
|
для: sasha1133
(09.03.2010 в 15:28)
| | Думаю в домашних условиях посчитать такие числа будет затруднительно. Даже если правильно продумать алгоритм то упираемся в проблему нехватки вычислительной мощности ПК. Реально распараллелить вычисления, можно даже подключить CUDA платы на GPU 200й серии уже лучше работают с большими числами в отличие от предков. Но иногда подумать о таких вещах интересно а вдруг чтото и получится с оптимизацией алгоритма общета. Дерзай, нет ничего невозможного! (Я матику даже по школьной программе всегда заваливаю - не дано мне. хотя поступил на физмат - наверно везение).Кстати не интересуешся распределенными вычислениями? | |
|
|
|
|
|
|
|
для: Miha_drinking_bout
(09.03.2010 в 16:38)
| | Интересно, а что за платы такие?
У меня кстати в общих чертах появилась идея такого алгоритма (как реализовать не знаю):
Например есть столько то бит памяти (с адресами, тк потом нужно будет узнать номер бита). Сначала в каждый записываем 1 (единица будет обозначать простое число). Затем каждому чётному биту (2, 4, 6 и тп) присваиваем значение 0 (составное число). Ищем бит со значением 1 с минимальным адресом - его номер 3. "Вычёркиваем" каждый 3-й бит (3, 6, 9 и т.п.). И т.д. То есть таким образом находим идущие подряд простые числа. Но опять таки возникает проблема с величиной чисел и объёмом памяти. Например если для этой цели использовать жёсткий диск на 2 терабайта, то полученные числа не будет превышать ~16 000 000 000 000. Получается всего десятичных 14 разрядов => приз не достанется)).
По видимому проверка именно чисел Мерсена на простоту наиболее простой и быстрый способ найти простые числа. Но всё равно не для обычного ПК | |
|
|
|
|
|
|
|
для: sasha1133
(09.03.2010 в 17:55)
| | насчет скидывания данных на жестяк согласен 2Тб маловато. Можно создать файл подобие контейнера со своей файловой системой и организовать сжатие. Проще под линухом создать архив пимонтировать его как диск и направить вывод данных туда (лучше конечно многотомные архивы - не пробовал поддерживаются ли они для монтирования?). Таким образом проблему с нехваткой места решили - а нагрузки на ЦП добавили хотя и незначительно. | |
|
|
|
|
|
|
|
для: Miha_drinking_bout
(10.03.2010 в 01:13)
| | Придумал - надо поиск производить в оперативке, а на веник сбрасывать только простые числа. К примеру есть 2 гига оперативки. Сначала все биты ставим единичками. Потом каждый чётный - 0, каждый, делящийся на 3, 5 и тд - 0. Остаются простые числа до 16 000 000 000, которые сбрасываем на веник. В тоже время надо запоминать, где было последнее "вычёркивание" для каждого простого числа. То есть например 3 последний раз встретилось в числе 15 999 999 999. Это нужно для того, чтобы знать, откуда начинать "вычёркивать" числа в диапазоне от 16 000 000 001 до 32 000 000 000. По идее должно работать быстро, если грамотно написать. Не знаю как реализовать работу с памятью. | |
|
|
|