JavaScript: эффективная целочисленная арифметика

Question

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

В частности, поведение переполнения должно быть совместимо с другими языками: например, добавление одного к INT_MAX должно дать INT_MIN. Целые числа должны быть 32-разрядными или 64-разрядными.

Answer 1

Итак, как наиболее эффективно реализовать целые числа в JavaScript?

Тип примитивного числа настолько эффективен, насколько это возможно. Многие современные JS-движки поддерживают JIT-компиляцию, поэтому она должна быть почти такой же эффективной, как собственная арифметика с плавающей точкой.

В частности, поведение переполнения должно быть совместимым с другими языками: например, добавление одного к INT_MAX должно дать INT_MIN. Целые числа должны быть 32-разрядными или 64-разрядными.

Вы можете достичь семантики стандартной 32-разрядной целочисленной арифметики, отметив, что JavaScript преобразует «числа» в 32-разрядные целые числа для побитовых операций. >>> (беззнаковое смещение вправо) преобразует свой операнд в 32-разрядное целое число без знака, тогда как остальные (все другие сдвиги и побитовое И / ИЛИ) преобразуют свой операнд в 32-разрядное целое число со знаком. Например:

• 0xFFFFFFFF | 0 выход -1 (подписанный актерский состав)
• (0xFFFFFFFF + 1) | 0 выход 0 (переполнение)
• -1 >>> 0 выход 0xFFFFFFFF (без знака)

Answer 2

Я нашел эту реализацию BigIntegers в Javascript: http://www -cs-students.stanford.edu / ~ tjw / jsbn /

Возможно, это поможет?

Редактировать: Кроме того, в библиотеке Google Closure реализованы 64-разрядные целые числа: http://code.google.com/p/closure-library/source/browse/trunk/closure/goog/math/long.js

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

Answer 3

На современном процессоре, если вы ограничите свои целочисленные значения диапазоном + - 2 ^ 52, тогда использование double будет чуть менее эффективным, чем использование long.

Тип double IEE754 имеет 53 бита мантиссы, так что вы можете легко представить 32-битный целочисленный диапазон, а затем и немного.

В любом случае остальная часть Javascript будет гораздо более узким местом, чем отдельные инструкции ЦП, используемые для обработки арифметики.

Answer 4

Все числа являются числами.Обойти это невозможно.У JavaScript нет ни байтов, ни типа int.Либо справьтесь с ограничениями, либо используйте язык более низкого уровня для написания вашего компилятора.

Единственный разумный вариант, если вы хотите добиться этого, - это отредактировать один из интерпретаторов JavaScript (скажем, V8) и расширить JS доразрешить доступ к собственным байтам C.

Answer 5

Обратите внимание, что добавлена ​​версия ECMA-262 Edition 3 Number.prototype.toFixed, который принимает точный аргумент, говорящий, сколько цифры после десятичной точки шоу. Используйте этот метод хорошо, и вы не будет против различий между Конечная точность базы 2 и «произвольная» или «подходящая» точность База 10, которую мы используем каждый день. - Брендан Айх

Answer 6

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

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

Answer 7

Ну, вы можете выбрать тип номера JavaScript, который, вероятно, вычисляется с использованием примитивов вашего ЦП, или вы можете выбрать наложение полного пакета операторов и функций, а не на эмулируемую серию битов ...?

... Если вам важны производительность и эффективность, придерживайтесь двойников.