Как компьютеры оценивают огромные числа?

Если я введу значение, например, 1234567 ^ 98787878 в Wolfram Alpha, оно может предоставить мне ряд подробностей. Это включает десятичное приближение, общую длину, последние цифры и т.д. Как вы оцениваете такие большие числа? Насколько я понимаю, язык программирования должен был иметь специальный тип данных для хранения номера, не говоря уже о его добавлении к чему-то другому. Хотя я могу видеть, как можно приблизиться к добавлению двух очень больших чисел, я не вижу, как оцениваются огромные числа.

10 ^ 2 можно было бы рассчитать с помощью повторного добавления. Однако такое число, как приведенный выше пример, потребует гигантский цикл. Может ли кто-нибудь объяснить, как оцениваются такие большие числа? Кроме того, как может кто-то создать настраиваемый большой тип данных для поддержки больших чисел в С#, например?

Ответ 1

Ну, это довольно легко, и вы можете сделать это сами.

Количество цифр может быть получено с помощью логарифма:

так как A^B = 10 ^ (B * log(A, 10))

мы можем вычислить (A = 1234567; B = 98787878) в нашем случае, что

B * log(A, 10) = 98787878 * log(1234567, 10) = 601767807.4709646...

integer part + 1 (601767807 + 1 = 601767808) - это количество цифр
Сначала, скажем, пять, цифры могут быть получены через логарифм; теперь мы должны проанализировать дробную часть

B * log(A, 10) = 98787878 * log(1234567, 10) = 601767807.4709646...

f = 0.4709646...

первые цифры 10^f (десятичная точка удалена) = 29577...
Наконец, скажем, пять цифр могут быть получены как соответствующий остаток:

последние пять цифр = A^B rem 10^5

A rem 10^5 = 1234567 rem 10^5 = `34567

A ^ B rem 10 ^ 5 **=** ((A rem 10 ^ 5) ^ B) rem 10 ^ 5 **=** (34567 ^ 98787878) rem 10 ^ 5 = 45009`

последние пять цифр 45009

Вы можете найти здесь BigInteger.ModPow (С#)

Наконец

1234567 ^ 98787878 = 29577... 45009 (601767808 цифр)

Ответ 2

Обычно существуют библиотеки, предоставляющие бинарный тип данных для произвольно больших целых чисел (например, сопоставление цифр k*n...(k+1)*n-1, k=0..<some m depending on n and number magnitude> с машинным словом размера n переопределение арифметических операций). для С# вас может заинтересовать BigInteger.

возведение в степень может быть рекурсивно разбито:

pow(a,2*b)   = pow(a,b) * pow(a,b);
pow(a,2*b+1) = pow(a,b) * pow(a,b) * a;

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

Ответ 3

Чтобы вычислить, сколько цифр есть, используется следующее выражение:

decimal_digits(n) = 1 + floor(log_10(n))

Это дает:

decimal_digits(1234567^98787878) = 1 + floor(log_10(1234567^98787878))
                                 = 1 + floor(98787878 * log_10(1234567))
                                 = 1 + floor(98787878 * 6.0915146640862625)
                                 = 1 + floor(601767807.4709647)
                                 = 601767808

Конечные k-цифры вычисляются путем выполнения экспоненциации mod 10 ^ k, что делает промежуточные результаты когда-либо слишком большими.

Аппроксимация будет вычисляться с использованием (программной) реализации с плавающей запятой, которая эффективно оценивает a ^ (98787878 log_a (1234567)) с некоторой фиксированной точностью для некоторого числа a, что делает арифметику хорошо работать (обычно 2 или e или 10). Это также позволяет избежать необходимости работать с миллионами цифр в любой момент.

Ответ 4

Для этого существует много библиотек, и возможность встроена в случае python. Вы, по-видимому, в первую очередь относитесь к размеру таких чисел и времени, которое может потребоваться для выполнения вычислений, подобных экспоненте в вашем примере. Поэтому я немного объясню.

Представление Вы можете использовать массив для хранения всех цифр больших чисел. Более эффективным способом было бы использовать массив из 32-битных беззнаковых целых чисел и хранить "32-битные куски" большого числа. Вы можете представить эти куски как отдельные цифры в числовой системе с 2 ^ 32 отдельными цифрами или символами. Я использовал массив байтов для этого на 8-битном Atari800 в тот же день.

Выполнение математики Очевидно, вы можете добавить два таких числа, перейдя по всем цифрам и добавив элементы одного массива в другой и отслеживая переносы. Когда вы знаете, как добавить, вы можете написать код, чтобы сделать "ручное" умножение, умножив цифры и помещая результаты в нужное место и много дополнений, но программное обеспечение сделает все это довольно быстро. Существуют более быстрые алгоритмы умножения, чем те, которые вы использовали бы вручную на бумаге. Умножение бумаги - O (n ^ 2), где другие методы - O (n * log (n)). Что касается экспоненты, вы можете, конечно, умножить на одно и то же число миллионы раз, но каждое из этих умножений будет использовать вышеупомянутую функцию для выполнения умножения. Есть более быстрые способы сделать возведение в степень, которые требуют гораздо меньше размножений. Например, вы можете вычислить x ^ 16, вычислив (((x ^ 2) ^ 2) ^ 2) ^ 2, который включает только 4 действительных (больших целочисленных) умножения.

На практике Это интересно и учебно, чтобы попытаться написать эти функции самостоятельно, но на практике вы захотите использовать существующую библиотеку, которая была оптимизирована и проверена.

Ответ 5

Я думаю, что часть ответа находится в самом вопросе:). Чтобы хранить эти выражения, вы можете хранить базу (или мантиссу) и экспоненту отдельно, например, научную нотацию. Расширяясь до этого, вы не можете полностью оценить выражение и сохранить такие большие числа, хотя теоретически вы можете предсказать определенные свойства последующего выражения. Я расскажу вам о каждом из свойств, о которых вы говорили:

Десятичное приближение: может быть рассчитано путем оценки простых значений журнала.
Общее количество цифр для выражения a ^ b, может быть вычислено по формуле Digits = функция floor (1 + Log10 (a ^ b)), где функция floor - это самое близкое целое число, меньшее числа. Напр. число цифр в 10 ^ 5 равно 6.
Последние цифры: они могут быть вычислены в силу того факта, что выражение линейно возрастающих показателей составляет арифметическую прогрессию. Напр. на месте установки; 7, 9, 3, 1 повторяется для показателей 7 ^ x. Итак, вы можете вычислить, что если x% 4 равно 0, последняя цифра равна 1. Может кто-то создать собственный тип данных для больших чисел, я не могу сказать, но я уверен, что число не будет оцениваться и храниться.