ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexandr Zhizhin                     2:5020/400     10 May 2003  17:48:13
 To : Rodion Gorkovenko
 Subject : Re: RSA
 -------------------------------------------------------------------------------- 
 

 Hello, Rodion!
 
 AZ>> Задача: реализовать быстрое возведение в степень по модулю :)  Первое
  AZ>> отпадает. В long double вроде немного побольше чем 19 знаков.
  RG> Скажем так - побольше чем 19 и поменьше чем 20 ;)
 
 Да, наверное что-то типа такого, хз все эти типы :)
 
 AZ>> Вообще было бы неплохо иметь в Си целочисленный тип на 80 бит.
  RG> Действительно - помню, как-то столкнувшись с такой задачей решили, что
  RG> проще сделать на паскале... А вообще проблема-то невелика - встроенным
  RG> ассемблером загрузить-выгрузить число в сопроцессор... Хотя все
  RG> операции переписывать придется...
 
 Ээ это же ещё с этим ассемблером разбиратся придется %) Лит-ру по
 сопроцессору читать.
 
  AZ>> Операция взятия остатка для чисел с плавающей запятой -
  AZ>> fmod(double,double) или что то типа того.
  RG> Это да, но для такой точности она ничего путевого не скажет,
  RG> подозреваю... Вот сейчас поэксперементировал с взятием остатка от
  RG> деления 1.24Е+3000 на 1.23Е+3000 - получилось нецелое число...
 
 Остаток нецелое число - гон или глюк.
 Кстати, а как насчет быстродействия? Эти операции медленее выполняются, чем
 целочисленные?
  AZ>> Здесь ты полностью прав. Такой способ прокатывает. Всё сходится. У
  AZ>> меня это немного по другому реализовано реализовано:
  RG> Hе, дружище, ты чуть-чуть неправильно понял - в твоем алгоритме E
  RG> итераций, в предложенном Евгением Ключниковым (и описанном мной)
  RG> log2(E). Идея вкратце такова - мы пользуемся тем, что A^(B+C)=A^B*A^C -
  RG> и расчитываем значение A^X для следующих X:
  RG> 1,2,4,8,16,32...
  RG> Путем возведения в квадрат каждого предыдущего и потом перемножаем
  RG> нужные значения (то есть те, для которых соответствующий бит в
  RG> показателе установлен): A^25=
  RG> A^11001b=
  RG> A^10000b+A^1000+A^1
  RG> а эти значения мы расчитываем в цикле за 6 итераций...
 
 Да уж чуть-чуть неправильно ;) Спасибо. Весьма доходчиво объяснил :)
 
  AZ>> Блин, ну это чудовищно медленно.
  RG> Hу цикл с Е итерациями где Е порядка 1Е+24 это не просто медленно...
  RG> это вообще никак ;)
 
 Согласен. Позор мне :) Hу не программер я всё таки. :)  Пойду читать Кнута и
 Теорию чисел.
 
 AZ>> Мне по мылу Kluchnikov Eugene прислал алгоритмик  там число операций
 AZ>> не e, а log2(e).
  RG> Вот это оно и есть - вообще учителя программирования любят задавать
  RG> этот вопрос на засыпку...
 
 Мне с ними не приходится часто встречаться :)
 
  AZ>> Как это примерно выглядит допустим на  Си.
  RG> Вот так, как я выше и написал... ;)
 
 Да кстати спасибо, выручил, твоя функция была использована и весьма ускорила
 работу проги.
 With best regards, Alexandr Zhizhin.  E-mail: hokum@sibmail.com
 --- ifmail v.2.15dev5
  * Origin: TUCS&R/Center TUSUR Telecom (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    RSA   Alexandr Zhizhin   02 May 2003 17:06:27   RSA   Rodion Gorkovenko   03 May 2003 09:06:00   Re: RSA   Alexandr Zhizhin   04 May 2003 08:51:14   RSA   Rodion Gorkovenko   05 May 2003 10:32:00   Re: RSA   Alexandr Zhizhin   10 May 2003 17:48:13   RSA   Rodion Gorkovenko   14 May 2003 17:20:00   RSA   Evgenij Masherov   04 May 2003 18:50:08   Re: RSA   Alexandr Zhizhin   10 May 2003 17:49:43   Re: RSA   Evgenij Masherov   10 May 2003 22:04:03   RSA   Marckel Barsuckov   10 May 2003 22:16:29