 |
|
Модераторы: Daevaorn |
 
|
|
int miller-rabin( long long ); реализация на Си 
| Pete |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 318 Регистрация: 5.1.2006 Где: Москва Репутация: нет Всего: 12 |
Нужна реализация теста простоты Миллера-Рабина для чисел типа long long.
-------------------- Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу) Не откладывай на завтра то, что можешь сделать сегодня. (Пословица) А теперь выпишем точное значение числа пи... (Препод) Жахни, Пендальф! © Гоблин |
|||
|
||||
Загрузка ...
| JackYF |
|
|||
 полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 18 Всего: 162 |
Посмотри на Algolist
|
|||
|
||||
| Pete |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 318 Регистрация: 5.1.2006 Где: Москва Репутация: нет Всего: 12 |
Там Паскаль.. Мне нужен именно на Си. Проблема в вычислении
(См. Кормен) -------------------- Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу) Не откладывай на завтра то, что можешь сделать сегодня. (Пословица) А теперь выпишем точное значение числа пи... (Препод) Жахни, Пендальф! © Гоблин |
|||
|
||||
| JackYF |
|
|||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: 18 Всего: 162 |
В чем проблема? Какого типа переменная d?
|
|||
|
||||
| Pete |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 318 Регистрация: 5.1.2006 Где: Москва Репутация: нет Всего: 12 |
Мне нужно это правильно вычислять, причем быстро (это часть процедуры witness(), которая вызывается из метода miller-rabin() несколько раз. Сам метод miller-rabin() вызывается для каждого числа, простоту которого надо проверить). Вопрос заключается вот в чем. Как, не реализуя длинной арифметики, вычислить (d*d)%n, если d имеет тип long long? Нашел на koders.com вот это. Только этот код довольно напряжно понимать... Мне нужен частный случай. -------------------- Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу) Не откладывай на завтра то, что можешь сделать сегодня. (Пословица) А теперь выпишем точное значение числа пи... (Препод) Жахни, Пендальф! © Гоблин |
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 17 Всего: 110 |
насколько большие n?
если меньше sqrt(max), то проблем не возникнет: sqr(d)%n=sqr(d%n)%n хотя, подозреваю, n>sqrt(max) можно попробовать разложить d в сумму старшей половины бит и младшей, а там использовать квадрат суммы -------------------- qqq |
|||
|
||||
| Rockie |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 1143 Регистрация: 23.4.2006 Репутация: 8 Всего: 31 |
imho все вычисляется.. возможно, проблема в неверном спецификаторе при выводе? imho стоит юзать %ld:
p.s.: если не имеется ввиду переполнение типа, как похоже ввиду и имеется  Это сообщение отредактировал(а) Rockie - 19.10.2006, 18:00 -------------------- Чтобы иметь большой гардероб - надо иметь большой гардероб. |
|||
|
||||
| Pete |
|
||||||
|
Опытный Профиль Группа: Участник Сообщений: 318 Регистрация: 5.1.2006 Где: Москва Репутация: нет Всего: 12 |
Для long long -- %lld.
настолько большие, что произведение d*d будет вычислено неверно. Скажем, порядка 2^60.
То есть d = a*2^32 + b, где a и b -- int? -------------------- Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу) Не откладывай на завтра то, что можешь сделать сегодня. (Пословица) А теперь выпишем точное значение числа пи... (Препод) Жахни, Пендальф! © Гоблин |
||||||
|
|||||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 17 Всего: 110 |
да тогда получится: a*a*2^64+b*b*2^64+2*a*b*2^32 в первых двух слагаемых нужно заменить 2^64 на (2^64)%n и a*a и b*bуже вмещается в 64 бита во втором можно разделить a*b на старший int и младший до конца не просматривал, но, кажется, проблем тамбыть не должно... -------------------- qqq |
|||
|
||||
| Pete |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 318 Регистрация: 5.1.2006 Где: Москва Репутация: нет Всего: 12 |
Ладно, попробую. Однако сомневаюсь, что это достаточно быстрый способ...
-------------------- Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу) Не откладывай на завтра то, что можешь сделать сегодня. (Пословица) А теперь выпишем точное значение числа пи... (Препод) Жахни, Пендальф! © Гоблин |
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0777 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |