Нестабильные результаты из факторинговой функции Python

Question

def test_prime(n):
    q = True
    for p in range(2,n):  #Only need to check up to rootn for primes and n/2 for factors
        if int(n%p) is 0:         
            q = False
            print(p, 'and', int(n/p), 'are factors of ', n)    
    if q:
        print(n, 'IS a prime number!')
    else:
        print(n, 'IS NOT a prime number')

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

Например, если я установлю n = 65432, я получу...

2 and 32716 are factors of  65432
4 and 16358 are factors of  65432
8 and 8179 are factors of  65432
8179 and 8 are factors of  65432
16358 and 4 are factors of  65432
32716 and 2 are factors of  65432
65432 IS NOT a prime number

что это то, что я ожидал. Но если я установлю n = 659306, я получу...

2 and 329653 are factors of  659306
71 and 9286 are factors of  659306
142 and 4643 are factors of  659306
4643 and 142 are factors of  659306
9286 and 71 are factors of  659306
659306 IS NOT a prime number

который отличается, потому что он не включает фактор 329653 в самом конце. Это не проблема, так как все факторы отображаются где-то, но меня раздражает, что я не знаю, ПОЧЕМУ это происходит для некоторых чисел!

Просто чтобы показать вам, что я не полный придурок, я решил, что это происходит только с целочисленными значениями длиной более 5 символов. Может кто-нибудь подскажите, пожалуйста, почему выходы разные в этих двух случаях?

Answer 1

Ты хочешь n % p == 0 не n % p is 0, is проверяет идентичность, а не равенство, и не каждый 0 совпадает с любым другим 0.

>>> 659306 % 329653
0
>>> (659306 % 329653) == 0
True
>>> (659306 % 329653) is 0
False
>>> id(0)
136748976
>>> id(659306 % 329653) 
3070888160

id там в основном соответствует месту в памяти.

Подумайте об этом так: если у вас есть луни, а у меня луни, то они равны друг другу по значению (1 == 1), но это не тот же объект (моя монета в один доллар не так же, как ваша монета в один доллар.) Мы могли бы использовать одну и ту же монету, но это не обязательно.

[PS: Вы можете использовать n//p для целочисленного деления вместо int(n/p).]

Answer 2

То, что происходит за кулисами, немного сложно. Мои комментарии относятся конкретно к CPython, Другие реализации, такие как PyPy, Jython, IronPython и т. Д., Будут вести себя по-другому.

Чтобы уменьшить использование памяти и повысить производительность, CPython кэширует диапазон маленьких целых чисел и пытается вернуть ссылку на эти объекты вместо создания другого целочисленного объекта с тем же значением. Когда вы сравниваете числа с isвы на самом деле проверяете, возвращал ли CPython ссылку на тот же кешированный объект. Но иногда CPython не проверяет, является ли значение одним из кэшированных целых чисел. Как такое могло произойти?

Я объясню CPython 3, так как он немного проще, чем CPython 2. int Видимый в CPython тип на самом деле называется PyLong внутренне переводчику. PyLong хранит целое число в виде массива digits где каждая цифра находится между 0 и 2**15-1 (32-битные системы) или 0 и 2**30-1 (64-битные системы). Массив увеличивается в размере по мере увеличения чисел; это позволяет эффективно неограниченные целые числа. При расчете %CPython проверяет, является ли второй аргумент одним digit долго. Если это так, он вызывает функцию C (divrem1), которая возвращает digit в результате. Следующий, PyLong_FromLong вызывается для преобразования значения, которое соответствует длине C (т. е. возвращаемое значение divrem) в PyLong. PyLong_FromLong проверяет, находится ли аргумент в диапазоне кэшированных целых чисел, и, если возможно, вернет ссылку на кэшированное целое число.

Если второй аргумент больше одного digit long вызывается другая функция C (x_divrem). x_divrem использует алгоритм деления произвольной точности общего назначения для вычисления остатка. поскольку x_divrem создает PyLong чтобы сохранить остаток во время вычисления, нет никакого преимущества, полученного, избегая создания другого двойного целого числа; это уже существует. Для вычислений со случайными большими числами остаток редко будет равен одному из кешированных целых чисел, поэтому не стоит тратить время на проверку.

Существуют и другие способы создания дублированных копий кэшированных целых чисел. Я только что проанализировал один из вопроса.

И вот почему вы не используете is для проверки числового равенства.....