 Деление с остатком |
Здравствуйте, гость ( Вход | Регистрация )
 09 Apr 2010, 09:41
Сообщение
#1
|
|
 🐓🐓🐓🐓🐓🐓🐓 Сообщений: 1 845 Спасибо сказали: 1570 раз  |
Нужно реализовать деление с остатком больших чисел, но не могу разобраться в алгоритме - и читабельного не нашел к сожалению. Везде какие-то неточности, и абсурдные на мой взгляд вещи.
Во-первых, глупейший вопрос: если я для хранения больших чисел использую, к примеру, Код type TDigit = array[0..63] of dword; то наименьшему или наибольшему элементу массива логичнее хранить младшую часть числа? -------------------- using namespace fbx;
|
  |
 
|
 |
Ответов
|
03 May 2010, 21:50
Сообщение
#2
|
|
|
🐓🐓🐓🐓🐓🐓🐓 Сообщений: 1 845 Спасибо сказали: 1570 раз |
Пришлось использовать для хранения чисел string, причем в читабельной десятичной форме. Сел сегодня, что-то сваял, для размера основания, степени и делителя по ~2048 бит программа работала 85 секунд. Если ~512 бит, то 1.5 секунд. Монтгомери ниасилил, поэтому сделал по-тупому.
Всем еще раз спасибо за помощь. -------------------- using namespace fbx;
|
|
|
|
Сообщений в этой теме
FBX Деление с остатком 09 Apr 2010, 09:41
etoprostoya Обычно младшая часть в начальных ячейках, а старша... 09 Apr 2010, 10:00 FBX Цитатаvar a,b,c: TDigit;
ab mod c = ?
для ... 13 Apr 2010, 21:01 etoprostoya Можно поконкретнее описать, что нужно? И большая л... 13 Apr 2010, 21:26 FBX Так вот я описал что нужно найти. Куда это вставля... 13 Apr 2010, 21:33 etoprostoya Всё равно не очень понятно.
Вариант: тупо умножат... 13 Apr 2010, 21:41 FBX В том-то и дело, что это не вариант степень - чис... 13 Apr 2010, 21:48 etoprostoya Есть вариант для такого случая: после каждого умно... 13 Apr 2010, 21:51 FBX не, количество итераций умножения / деления все ра... 13 Apr 2010, 22:08 etoprostoya Есть алгоритмы, оптимизирующие количество умножени... 13 Apr 2010, 22:23 gamecreator Цитата(FBX @ 13 Apr 2010, 22:48)Деление: http... 14 Apr 2010, 07:47 hippocamus возведение в целую степень. быстрый алгоритм.
Кодf... 04 May 2010, 15:58 gamecreator а что такое х? 04 May 2010, 15:59 hippocamus исправил. 04 May 2010, 16:01 gamecreator xa=Пi=0∞(x-ki)ai где
aєR
ai=[a'i]
a... 04 May 2010, 16:25 Дьяк не умничай )) 04 May 2010, 17:59 gamecreator дык это способ.
Добавлено (1272987048):
можно еще... 04 May 2010, 18:30 FBX Как реализовать расширенный алгоритм Евклида
( htt... 10 May 2010, 12:51 gamecreator а никак. поменять a и b местами. и алгоритмы там к... 10 May 2010, 13:49 FBX В этом коде выходит что x не меняется...
А еще пр... 10 May 2010, 14:18 gamecreator меняется. это была проверка на внимательность и ты... 10 May 2010, 15:07 FBX Потому что можно это реализовать без геморной реал... 10 May 2010, 15:40 gamecreator этот алгоритм - нельзя
Добавлено (1273495326):
и ... 10 May 2010, 15:42 FBX и будет ли целесообразным такой результат?
ведь у... 10 May 2010, 16:33 gamecreator оба верны
Добавлено (1273509342):
789-742=47
1024... 10 May 2010, 19:35 FBX Точно... надеюсь, это верно во всех случаях. 10 May 2010, 19:51
gamecreator во всех, можешь не сомневаться 11 May 2010, 15:51 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
| Текстовая версия | Сейчас: 2 September 2025 - 07:10 |
Copyright by Алексей Крючков
 Programming by Degtyarev Dmitry |
|