VPF::NTL в Python - Форум программистов

fearuth

Дата 14.1.2009, 19:58 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 9.9.2008

Репутация: нет
Всего: 1

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

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

Lazin

Дата 14.1.2009, 21:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 2
Всего: 154

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

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Void

Дата 14.1.2009, 21:42 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 10
Всего: 173

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

)

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

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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

fearuth

Дата 15.1.2009, 02:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 9.9.2008

Репутация: нет
Всего: 1

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

Это сообщение отредактировал(а) fearuth - 15.1.2009, 02:48

Void

Дата 15.1.2009, 06:38 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 10
Всего: 173

Что не так?

Цитата

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

Это сообщение отредактировал(а) Void - 15.1.2009, 06:40

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

fearuth

Дата 15.1.2009, 10:34 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 9.9.2008

Репутация: нет
Всего: 1

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

alex_smirnov

Дата 15.1.2009, 11:12 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 22.6.2007
Где: Санкт-Петербург

Репутация: 2
Всего: 4

Цитата

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

Точно.

fearuth

Дата 15.1.2009, 12:01 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 9.9.2008

Репутация: нет
Всего: 1

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

fearuth

Дата 18.1.2009, 07:22 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 9.9.2008

Репутация: нет
Всего: 1

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

Код


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 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 10
Всего: 173

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

Это сообщение отредактировал(а) Void - 18.1.2009, 11:01

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

alex_smirnov

Дата 18.1.2009, 13:41 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 22.6.2007
Где: Санкт-Петербург

Репутация: 2
Всего: 4

Цитата

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

Не-не-не, какой while, он медленный до чертиков (читайте Гвидо). Генератор надо писать, и всё. xrange тоже генератор.

Void

Дата 18.1.2009, 13:59 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 10
Всего: 173

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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

fearuth

Дата 18.1.2009, 14:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 9.9.2008

Репутация: нет
Всего: 1

Не смущает =)

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Python: Общие вопросы \| Следующая тема »