Как языки программирования обрабатывают огромное количество арифметики

Question

Для компьютера, работающего с 64-разрядным процессором, наибольшее число, которое он может обработать, будет 2 ⁶⁴ = 18 446 744 073 709 551 616. Как языки программирования, скажем, Java или C, C ++ обрабатывают арифметику чисел выше этого значения. Ни один регистр не может содержать его как один фрагмент. Как решалась эта проблема?

Answer 1

Существует множество специализированных методов для вычисления чисел, превышающих размер регистра. Некоторые из них описаны в этой статье в Википедии о произвольной точности арифметики

Языки низкого уровня, такие как C и C ++, оставляют большое количество вычислений в библиотеке по вашему выбору. Одна известная библиотека GNU Multi-Precision . Языки высокого уровня, такие как Python и другие, интегрируют это в ядро ​​языка, поэтому обычные числа и очень большие числа идентичны программисту.

Answer 2

Языки программирования, которые обрабатывают действительно огромные числа, используют пользовательские числовые примитивы, которые выходят за рамки обычных операций, оптимизированных для 32, 64 или 128-битных процессоров. Эти цифры особенно полезны в области компьютерной безопасности и математических исследований.

Библиотека Multiple Precision *1003*, вероятно, является наиболее полным примером этих подходов.

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

Точка, в которой JavaScript не работает

console.log(9999999999999998 + 1)
// expected 9999999999999999
// actual  10000000000000000  oops!

JavaScript не обрабатывает простые целые числа выше 9999999999999998. Но написать свой собственный числовой примитив - сделать этот расчет достаточно простым. Вот пример использования пользовательского класса сумматора чисел в JavaScript .

Сдача теста с использованием пользовательского номера класса

// Require a custom number primative class
const {Num} = require('./bases')

// Create a massive number that JavaScript will not add to (correctly)
const num = new Num(9999999999999998, 10)

// Add to the massive number
num.add(1)

// The result is correct (where plain JavaScript Math would fail)
console.log(num.val)  // 9999999999999999

Как это работает

Вы можете посмотреть в коде class Num {...} , чтобы увидеть подробности происходящего; но вот основная схема используемой логики:

Классы:

• Класс Num содержит массив отдельных классов Digit.
• Класс Digit содержит значение одной цифры и логику для обработки Carry flag

Шаги:

1. Выбранный номер превращается в строку
2. Каждая цифра превращается в класс Digit и сохраняется в классе Num в виде массива цифр
3. Когда Num увеличивается, он переносится на первый Digit в массиве (крайнее правое число)
4. Если значение Digit плюс Carry flag равно Base, то следующий Digit влево вызывается для увеличения, и текущее число сбрасывается на 0
5. ... Повторить до самой левой цифры массива

Логически это очень похоже на то, что происходит на уровне машины, но здесь оно не ограничено. Вы можете узнать больше о том, как цифры несут здесь ; это может применяться к номерам любой базы.

Answer 3

Более или менее так же, как вы . В школе вы запоминали сложение, умножение, вычитание и деление из одной цифры. Затем вы узнали, как выполнять многозначные задачи как последовательность однозначных задач.

Если вы хотите, вы можете умножить два двадцатизначных числа вместе, используя не более чем знание простого алгоритма и однозначных таблиц времени.

Answer 4

Ада фактически поддерживает это изначально, но только для своих постоянных без типа («именованные числа»). Для фактических переменных вам нужно найти пакет произвольной длины. См. Целое число произвольной длины в Ada

.

Answer 5

Вы принимаете не то. Наибольшее число, которое он может обработать в одном регистре , - это 64-разрядное число. Однако, используя некоторые умные методы программирования, вы можете просто объединить несколько десятков этих 64-битных чисел подряд, чтобы сгенерировать огромное 6400-битное число, и использовать его для дополнительных вычислений. Это не так быстро, как вписать номер в один регистр.

Даже старые 8 и 16-битные процессоры использовали этот трюк, где они просто позволили бы переполнению числа другим регистрам. Это делает математику более сложной, но она не ограничивает возможности.

Однако такая высокоточная математика чрезвычайно необычна. Даже если вы хотите рассчитать весь государственный долг США и сохранить результат в зимбабвийских долларах, я думаю, что 64-разрядное целое число все равно будет достаточно большим. Тем не менее, он достаточно большой, чтобы вместить сумму моего сберегательного счета.

Answer 6

Большинство языков хранят их как массив целых чисел. Если вы добавляете / вычитаете два из этих больших чисел, библиотека добавляет / вычитает все целые элементы в массиве отдельно и обрабатывает переносы / заимствования. Это похоже на ручное сложение / вычитание в школе, потому что так оно работает внутри.

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

Answer 7

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

Answer 8

В качестве мысленного эксперимента представьте числа, хранящиеся в виде строки. С функциями добавления, умножения и т. Д. Этих произвольно длинных чисел.

В действительности эти числа, вероятно, хранятся в более компактном виде.

Answer 9

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

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