Python ограничить длину числа

Как в Python реализованы очень длинные числа типа integer?

Перевод статьи подготовлен специально для студентов курса «Разработчик Python».

Когда вы пишете на низкоуровневом языке, таком как С, вы беспокоитесь о выборе правильного типа данных и спецификаторах для ваших целых чисел, на каждом шаге анализируете достаточно ли будет использовать просто int или нужно добавить long или даже long double . Однако при написании кода на Python вам не нужно беспокоиться об этих «незначительных» вещах, потому что Python может работать с числами типа integer любого размера.

В С, если вы попытаетесь вычислить 2 20000 с помощью встроенной функции powl , то на выходе получите inf .

#include #include int main(void) < printf("%Lf\n", powl(2, 20000)); return 0; >$ ./a.out inf

Но в Python сделать это проще простого:

>>> 2 ** 20000 39802768403379665923543072061912024537047727804924259387134 . . . 6021 digits long . . 6309376

Должно быть под капотом Python делает что-то очень красивое и сегодня мы узнаем, что именно он делает, чтобы работать с целыми числами произвольного размера!

Представление и определение

Integer в Python это структура C, определенная следующим образом:

PyObject_VAR_HEAD – это макрос, он раскрывается в PyVarObject , который имеет следующую структуру:

typedef struct < PyObject ob_base; Py_ssize_t ob_size; /* Number of items in variable part */ >PyVarObject;

Другие типы, у которых есть PyObject_VAR_HEAD :

В структуре PyObject есть некоторые мета-поля, используемые для подсчета ссылок (сборки мусора), но для того, чтобы поговорить об этом нужна отдельная статья. Поле, на котором мы сосредоточимся это ob_digit и в немного ob_size .

Расшифровка ob_digit

ob_digit – это статически аллоцированый массив единичной длины типа digit (typedef для uint32_t) . Поскольку это массив, ob_digit в первую очередь является указателем на число, и, следовательно, при необходимости он может быть увеличен с помощью функции malloc до любой длины. Таким образом python может представлять и обрабатывать очень длинные числа.

Как правило в низкоуровневых языках, таких как С, точность целых чисел ограничена 64-битами, однако Python поддерживает целые числа произвольной точности. Начиная с версии Python 3, все числа представлены в виде bignum и ограничены только доступной памятью системы.

Расшифровка ob_size

ob_size хранит количество элементов в ob_digit . Python переопределяет и затем использует значение ob_size для определения фактического количества элементов, содержащихся в массиве, чтобы повысить эффективность выделения памяти массиву ob_digit .

Хранение

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

С таким подходом число 5238 будет сохранено так:

Такой подход неэффективен, поскольку мы будем использовать до 32-бит цифр (uint32_t) для хранения десятичной цифры, которая, по сути, колеблется от 0 до 9 и может быть легко представлена всего лишь 4 битами, ведь при написании чего-то столь же универсального как python, разработчик ядра должен быть еще изобретательнее.

Итак, можем ли мы сделать лучше? Конечно, иначе я бы не выложил эту статью. Давайте подробнее рассмотрим то, как Python хранит сверхдлинное целое число.

Путь Python

Вместо того, чтобы хранить только одну десятичную цифру в каждом элементе массива ob_digit , Python преобразует числа из системы счисления с основанием 10 в числа в системе с основанием 2 30 и вызывает каждый элемент, как цифру, значение которой колеблется от 0 до 2 30 — 1.

В шестнадцатеричной системе счисления, основание 16 ~ 2 4 означает, что каждая «цифра» шестнадцатеричного числа колеблется от 0 до 15 в десятичной системе счисления. В Python аналогично, «число» с основанием 2 30 , что означает, что число будет варьироваться от 0 до 2 30 – 1 = 1073741823 в десятичной системе счисления.

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

В зависимости от платформы Python использует либо 32-битные целочисленные беззнаковые массивы, либо 16-битные целочисленные беззнаковые массивы с 15-битными цифрами. Для выполнения операций, которые будут рассмотрены дальше, понадобится всего несколько битов.

Пример: 1152921504606846976

Как уже упоминалось, для Python числа представлены в системе с основанием 2 30 , то есть если вы конвертируете 1152921504606846976 в систему счисления с основанием 2 30 , вы получите 100.

1152921504606846976 = 1 * (2 30 ) 2 + 0 * (2 30 ) 1 + 0 * (2 30 ) 0

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

Структура _longobject для этого значения будет содержать:

• ob_size как 3
• ob_digit как [0, 0, 1]

Я создал демонстрационный REPL, который покажет, как внутри себя Python хранит integer, а также ссылается на члены структуры, такие как ob_size , ob_refcount и т. д.

Операции над длинными числами типа integer

Теперь, когда у нас есть четкое представление о том, как Python реализует целые числа произвольной точности, настало время понять, как с ними выполняются различные математические операции.

Сложение

Целые числа хранятся «в цифрах», это означает, что сложение выполняется также просто, как в начальной школе, и исходный код Python показывает нам, что именно так сложение и реализовано. Функция с именем x_add в файле longobject.c выполняет сложение двух чисел.

. for (i = 0; i < size_b; ++i) < carry += a->ob_digit[i] + b->ob_digit[i]; z->ob_digit[i] = carry & PyLong_MASK; carry >>= PyLong_SHIFT; > for (; i < size_a; ++i) < carry += a->ob_digit[i]; z->ob_digit[i] = carry & PyLong_MASK; carry >>= PyLong_SHIFT; > z->ob_digit[i] = carry; . 

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

Интереснее становится, когда результатом сложения является отрицательное число. Знак ob_size является знаком integer’а, то есть, если у вас есть отрицательное число, то ob_size будет минусом. Значение ob_size по модулю будет определять количество цифр в ob_digit .

Вычитание

Подобно тому, как происходит сложение, происходит и вычитание. Функция с именем x_sub в файле longobject.c выполняет вычитание одного числа из другого.

. for (i = 0; i < size_b; ++i) < borrow = a->ob_digit[i] - b->ob_digit[i] - borrow; z->ob_digit[i] = borrow & PyLong_MASK; borrow >>= PyLong_SHIFT; borrow &= 1; /* Keep only one sign bit */ > for (; i < size_a; ++i) < borrow = a->ob_digit[i] - borrow; z->ob_digit[i] = borrow & PyLong_MASK; borrow >>= PyLong_SHIFT; borrow &= 1; /* Keep only one sign bit */ > . 

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

Умножение

И снова умножение будет реализовано тем же наивным способом, который мы узнали из уроков математики в начальной школе, но он не отличается эффективностью. Чтобы поддерживать эффективность, Python реализует алгоритм Карацубы, который умножает два n-значных числа за O( n log ₂ 3 ) простых шагов.

Алгоритм непростой и его реализация выходит за рамки данной статьи, но вы можете найти его реализацию в функциях k_mul и k_lopsided_mul в файле longobject.c .

Деление и другие операции

Все операции над целыми числами определены в файле longobject.c , их очень просто найти и проследить работу каждой. Внимание: Детальное понимание работы каждой из них займет время, поэтому заранее запаситесь попкорном.

Оптимизация часто используемых целых чисел

Python заранее выделяет в памяти небольшое количество целых чисел в диапазоне от -5 до 256. Это выделение происходит во время инициализации, и поскольку мы не можем изменить целые числа (иммутабельность), эти предварительно выделенные числа являются синглтонами и на них ссылаются напрямую вместо реаллокации. Это значит, что каждый раз, когда мы используем/создаем маленькое число, Python вместо реаллокации просто возвращает ссылку на предварительно аллоцированное число.

Такую оптимизацию можно проследить в макросе IS_SMALL_INT и функции get_small_int в longobject.c . Так Python экономит много места и времени на вычисление часто используемых чисел типа integer.

Это вторая статья из серии Python Internals. Первая статья была о том, как я изменил свою версию Python, сделав его двусмысленным. Она поможет вам сделать первые шаги в понимании исходного кода Python и продолжить путь к становлению разработчиком ядра Python.

Если вы хотите увидеть больше похожих статей, подпишитесь на мою рассылку и получайте их прямо в свой почтовый ящик. Я пишу об инженерии, системном проектировании и немного о программировании каждую пятницу. Пишите мне на @arpit_bhayani. Мои предыдущие статьи вы найдете на @arpitbhayani.me/blogs.

На этом все. До встречи на курсе!

Источник

Практические советы по ограничению ввода чисел на Python до 6-значных значений

Python — это мощный инструмент для анализа данных и многих других задач. Однако, в некоторых случаях может возникнуть необходимость ограничения ввода чисел на Python до 6-значных значений.

Ограничение чисел в Python

Ограничение чисел в Python может происходить по нескольким причинам. Например, при работе с большими числами, Python может занимать много оперативной памяти, что замедляет вычисления или приводит к ошибкам.

Как ограничить ввод чисел до 6-значных значений

Один из способов ограничения ввода чисел до 6-значных значений в Python — это использование функции input с последующей проверкой введенного значения на соответствие критерию.

number = input("Введите число: ") if len(number)  

import re number_pattern = re.compile(r'\d') number = input("Введите число: ") if number_pattern.match(number): print("Верно") else: print("Ошибка")