Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Python: Общие вопросы > NTL в Python

Автор: fearuth 14.1.2009, 19:58

Привет всем. Столкнулся с проблемой бесконечно длинных чисел. Знаю, что в с++ есть NTL. Есть ли он в Python, если есть то подскажите, как и где его искать.

ЗЫ. Заранее спасибо.

Автор: Lazin 14.1.2009, 21:21

в Python 3000, они там такие по умолчанию

Автор: Void 14.1.2009, 21:42

Цитата(Lazin @ 14.1.2009, 23:21

)

в Python 3000, они там такие по умолчанию

С практической точки зрения в 2.x (по-видимому и раньше тоже) точно так же можно считать арифметику длинной по умолчанию.

Автор: fearuth 15.1.2009, 02:47

По умолчанию, нет.
Сложите два числа 1478927459072459087439087593847598679832758927345893427509275759027589275907598759873509375934759327459347598347593475
9347590348875903427590347590347593759034579347593875937598357935798345790347593475976927592375908324
и
1478927459072459087439087593847598679832758927345893427509275759027589275907598759873509375934759327459347598347593475
9347590348875903427590347590347593759034579347593875937598357935798345790347593475976927592375908324827345987689237459
8027349687938245707894357908234758923456843287568923645897632458796342895643276589734

Автор: Void 15.1.2009, 06:38

Что не так?

Цитата

Python 2.5.2 (r252:60911, Oct 5 2008, 19:24:49)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 14789274590724590874390875938475986798327589273458934275092757590275892759075987598735093759347593274593475983475934759347590348875903427590347590347593759034579347593875937598357935798345790347593475976927592375908324 + 147892745907245908743908759384759867983275892734589342750927575902758927590759875987350937593475932745934759834759347593475903488759034275903475903475937590345793475938759375983579357983457903475934759769275923759083248273459876892374598027349687938245707894357908234758923456843287568923645897632458796342895643276589734
147892745907245908743908759384759867983275892734589342750927575902758927590759875987350937593475932745949549109350072184350294364697510262701803492749396524620886233529035268742655345582192997235282353043869399742559183032807467241250501454940035528593301653392487582352799394441645504721991687980052272319823235652498058L

Автор: fearuth 15.1.2009, 10:34

Ясно, спасибо
А формула a^b mod C = (a**b)%c?

Автор: alex_smirnov 15.1.2009, 11:12

Цитата

А формула a^b mod C = (a**b)%c?

Точно.

Автор: fearuth 15.1.2009, 12:01

Хочу с RSA самореализованным разобраться =)

Автор: fearuth 18.1.2009, 07:22

Ан нет. Не работает это с кодом:

Код


def searchsimple(m,array):
    for n in xrange(2, m):
        for x in xrange(2, n):
            if n % x == 0: break
        else: storeg.append(n)
        print str(float(n*100)/float(m))+"%"
storeg=[]
a=5646546516546515616511531535456465464646464
searchsimple(a,storeg)

Выдает ошибку

Код


Traceback (most recent call last):
  File "E:/___/simpl.py", line 9, in <module>
    searchsimple(a,storeg)
  File "E:/___/simpl.py", line 2, in searchsimple
    for n in xrange(2, m):
OverflowError: long int too large to convert to int

А если просто складывать, перемножать и т.д. то работает с большими числами.
Если урезать a до следующиего вида
a=564654651
то все работает

ЗЫ. В чем может быть косяк? smile

Автор: Void 18.1.2009, 10:57

Аргументы xrange по соображениям эффективности ограничены машинным целым. Обойти это можно, заменив на while с инкрементом.
Если, конечно, не смущает, что вселенная исчезнет прежде, чем закончится выполнение 10^80 операций.

Автор: alex_smirnov 18.1.2009, 13:41

Цитата

Аргументы xrange по соображениям эффективности ограничены машинным целым. Обойти это можно, заменив на while с инкрементом.

Не-не-не, какой while, он медленный до чертиков (http://www.python.org/doc/essays/list2str.html). Генератор надо писать, и всё. xrange тоже генератор.

Автор: Void 18.1.2009, 13:59

Конечно, intrinsic functions всегда быстрее. А теперь изобразите на них генератор а-ля xrange, но с поддержкой long.

Автор: fearuth 18.1.2009, 14:05

Не смущает =)