Форум: Форум C++Разное
Новые темы: 00
PHP 5. На примерах. Авторы: Кузнецов М.В., Симдянов И.В., Голышев С.В. C++. Мастер-класс в задачах и примерах. Авторы: Кузнецов М.В., Симдянов И.В. MySQL на примерах. Авторы: Кузнецов М.В., Симдянов И.В. Социальная инженерия и социальные хакеры. Авторы: Кузнецов М.В., Симдянов И.В. PHP Puzzles. Авторы: Кузнецов М.В., Симдянов И.В.
ВСЕ НАШИ КНИГИ
Консультационный центр SoftTime

Разное

Выбрать другой форум

 

Здравствуйте, Посетитель!

вид форума:
Линейный форум Структурный форум

тема: Как вычислить остаток от деления?
 
 автор: sasha1133   (05.03.2010 в 17:59)   письмо автору
 
 

Как вычислить остаток от деления числа 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   (06.03.2010 в 18:56)   письмо автору
 
   для: 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:25)   письмо автору
 
   для: .exp   (08.03.2010 в 23:20)
 

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

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

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

  Ответить  
 
 автор: sasha1133   (09.03.2010 в 01:16)   письмо автору
 
   для: exp   (08.03.2010 в 23:25)
 

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


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

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

  Ответить  
 
 автор: exp   (09.03.2010 в 14:33)   письмо автору
 
   для: 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 байт

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

  Ответить  
 
 автор: sasha1133   (09.03.2010 в 15:28)   письмо автору
 
   для: exp   (09.03.2010 в 14:33)
 

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

  Ответить  
 
 автор: Miha_drinking_bout   (09.03.2010 в 16:38)   письмо автору
 
   для: sasha1133   (09.03.2010 в 15:28)
 

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

  Ответить  
 
 автор: sasha1133   (09.03.2010 в 17:55)   письмо автору
 
   для: 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 разрядов => приз не достанется)).

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

  Ответить  
 
 автор: Miha_drinking_bout   (10.03.2010 в 01:13)   письмо автору
 
   для: sasha1133   (09.03.2010 в 17:55)
 

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

  Ответить  
 
 автор: sasha1133   (11.03.2010 в 11:44)   письмо автору
 
   для: 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. По идее должно работать быстро, если грамотно написать. Не знаю как реализовать работу с памятью.

  Ответить  
Rambler's Top100
вверх

Rambler's Top100 Яндекс.Метрика Яндекс цитирования