Как считать с таким большим числом?

Я изучаю Паскаль самостоятельно уже месяц и столкнулся с одной проблемой, которую никак не могу решить. В основном у меня есть 2 числа, N и M, где N меньше 10100 000 и M меньше 108, и оба больше 0. Мне нужно вычислить N по модулю M.

Я не могу понять, как это сделать, даже с QWord. Я пробовал это с string, но я не знаю хорошего способа. Для меня это всегда оказывается слишком сложным, потому что я использую функцию for, где я получаю последнее число из строки N и строки M, а затем вычитаю их с помощью двух функций if ( где последняя цифра N больше или совпадает с последней цифрой M, и если она меньше). В основном это становится слишком сложным для этой простой проблемы, я думаю.


pascal bignum modulus
person Luka    schedule 17.02.2014    source источник
comment
Также со строкой мне приходится много переводить из строки в целое число, затем целое число в строку или символ и т.д.   -  person Luka    schedule 18.02.2014
comment
Можете ли вы опубликовать свой код до сих пор?   -  person John Kugelman    schedule 18.02.2014
comment
Вам потребуется более 3 миллионов битов для хранения числа величиной 10^100000 (что является гугол, кстати). Для сравнения, информационная емкость наблюдаемой Вселенной составляет около 10^305 бит ссылка здесь< /а>. Короче говоря, нет никакого способа сделать это легко. Зачем вам такие большие числа?   -  person    schedule 18.02.2014
comment
... и N меньше 10 ^ 8? Вы имеете в виду ... и M меньше 10 ^ 8?   -  person Johan Råde    schedule 18.02.2014
comment
@MikeW Что ты имеешь в виду, что это невозможно сделать легко? Я не понимаю, какое отношение имеет информационная емкость Вселенной к вычислениям бигнумов.   -  person John Kugelman    schedule 18.02.2014
comment
@JohnKugelman Если у вас есть простой способ сделать это, я был бы рад его увидеть.   -  person    schedule 18.02.2014
comment
Как вы храните числа? Вы храните их в какой-то научной записи или мы говорим о строке чисел, которая на самом деле имеет длину 10 ^ 100 000 цифр? Если это первое, то это должно быть выполнимо. Если последнее, то я не думаю, что это возможно с современными технологиями.   -  person milestyle    schedule 18.02.2014
comment
@MikeW Я понятия не имею, возможен ли этот расчет или нет, но я знаю, что ваши рассуждения обманчивы. Физика тут не причем. Это математический вопрос. Если у вас есть теоретико-числовые или компьютерные научные аргументы, почему этот расчет сложен, пожалуйста, поделитесь.   -  person John Kugelman    schedule 18.02.2014
comment
@milestyle Обратите внимание, что строка цифр будет состоять из 100 000 цифр, а не 10 ^ 100 000 цифр.   -  person John Kugelman    schedule 18.02.2014
comment
Это задача одного из старых соревнований по Паскалю в моей стране, и они не опубликовали решения. Это действительно заинтриговало меня, как это решить, и, кстати, я знаю о гуголе, гуголплексе, гуголплексиане и т. д., но я думаю, что это не имеет никакого отношения к физике :) И да, число будет 10 ^ 100 000, что равно 1, за которым следует 100 000 нулей. И угадайте, что ограничение по времени для этой задачи составляет 0,1 секунды.   -  person Luka    schedule 18.02.2014
comment
@JohnKugelman Вы «не представляете, возможен ли этот расчет»: это так. Реализация арифметики произвольной точности в двоичном или двоично-десятичном коде возможна для любого размера. Однако это не так просто. Если вы собираетесь выдвигать обвинения в «мнимых» рассуждениях, я хотел бы увидеть ваши собственные рассуждения.   -  person    schedule 18.02.2014
comment
@MikeW Мои рассуждения о чем? Давайте обсудим это в чате.   -  person John Kugelman    schedule 18.02.2014
comment
Я не могу разговаривать в чате, мне нужно 20 репутации :\   -  person Luka    schedule 18.02.2014
comment
У меня 21 репутация, а мне все еще нужно 20 репутации, чтобы говорить :(   -  person Luka    schedule 18.02.2014
comment
Как вычислить модуль большого числа?   -  person Rob Kennedy    schedule 19.02.2014

Ответы (1)


arrow_upward
3
arrow_downward

Есть несколько пакетов bignum, например. пакет MPArith с открытым исходным кодом из http://www.wolfgang-ehrhardt.de/mp_intro.html< /а>. С прилагаемым демонстрационным калькулятором вы легко превысите лимит времени:

D:\Xtools\MPArith>t_calc.exe
T_CALC using MPArith V1.26.05 (31/32 bit) [mp_calc]  (c) W.Ehrhardt 2006-2013
Karatsuba cutoffs:  mul/sqr = 16/32,   Toom-3 cutoffs: mul/sqr = 32/64
Burnikel/Ziegler div cutoff = 32,   MaxBit = 520093696,   MaxFact = 22623931
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.

[D]:=> 10^100000 mod (10^8-1)
Result = 1
[D]:=> .
Time = 20.128 ms
[D]:=> 10^100000;
Result =  [>0, 332193 bits,  chksum=$CE01C341,  time=46.994 ms]

Но в зависимости от ваших требований и примеров вы можете получить результаты даже без пакетов bignum. Если вы хотите вычислить a ^ b mod n, вы не вычисляете a ^ b, а затем уменьшаете mod n на втором этапе, а уменьшаете каждый продукт в цикле. И вы должны использовать быстрое двоичное возведение в степень, см., например. описание и псевдокод на http://en.wikipedia.org/wiki/Modular_exponentiation. Для модулей n порядка 10 ^ 8 вам нужно уменьшить произведение двух 31/32-битных целых чисел, и поэтому вам нужно int64 или около того, чтобы накопить произведения (что не должно быть проблемой для вашей версии Pascal, которая имеет QWord). Я предполагаю, что такая программа будет намного быстрее, чем код MPArith bignum с его 20 миллисекундами.

person gammatester    schedule 18.02.2014
comment
Другой важный математический сайт Delphi: efg2.com/Lab/Library/Delphi/MathFunctions - person Marco van de Voort; 20.02.2014