DjangoBB LoFi version

Полная версия: Умножение больших чисел. Метод Карацубы.

Начало » Python для новичков » Умножение больших чисел. Метод Карацубы.

1 2

jheniae

Апрель 17, 2015 18:51:19

Здравствуйте. Прошу помощи с кодом

def karatsuba(x,y):
    str_x, str_y=str(x), str(y)
    n=max(len(str_x), len(str_y))
    if n==1:
        return x*y
    elif n%2!=0:
        n+=1
    n_2=int(n/2)
    a, b = int(str_x[:n_2-1]), int(str_x[n_2:])
    c, d = int(str_y[:n_2-1]), int(str_y[n_2:])
    ac=karatsuba(a,c)
    bd=karatsuba(b,d)
    p=karatsuba((a+b),(c+d))-ac-bd
    return int((10**n)*ac+(10**(n/2)*p)+bd)
print(karatsuba(1685287499328328297814655639278583667919355849391453456921116729,7114192848577754587969744626558571536728983167954552999895348492))

При выполнение которого выдает ошибку ValueError: invalid literal for int() with base 10: ''
Не могу понять от куда она тянется, ткните носом если не сложно.
Спасибо

Romissevd

Апрель 17, 2015 19:12:01

ac=karatsuba(a,c)
bd=karatsuba(b,d)
p=karatsuba((a+b),(c+d))-ac-bd
return int((10**n)*ac+(10**(n/2)*p)+bd)

Как-то вообще непонятно… Объясните как это работает? Вы в функции вызываете саму себя, она выполняет тело функции доходит до ac=karatsuba(a,c) и опять вызывает саму себя….

jheniae

Апрель 17, 2015 19:47:59

Romissevd

Да функция рекурсивно вызываться до того момента пока длина аргумента не будет равна 1(один разряд). Хотя у меня тоже есть некоторые сомнения по этому поводу, но другого выхода как уменьшать аргумент я не придумал.

Romissevd

Апрель 17, 2015 20:05:47

if n==1:
    return x*y
 elif n%2!=0:
    n+=1

а если n разделится нацело, но не будет равна 1, тогда что?

jheniae

Апрель 17, 2015 20:20:20

Romissevd

Допустим n=4, делиться на 2 без остатка и не равно 1. Тогда получаем половину длины строки, потом присваиваем переменным a,b, c, d срезы и выполняется дальше рекурсия. Я так вижу по крайне мере, я пробовал например без вызова рекурсий, тогда выдавало результат но не верный.

py.user.next

Апрель 17, 2015 23:22:38

jheniae
При выполнение которого выдает ошибку

>>> int('')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: ''
>>>

jheniae
Не могу понять от куда она тянется

Когда с числами работаешь, действий со строками быть не должно.

jheniae

Апрель 18, 2015 15:19:40

py.user.next
Когда с числами работаешь, действий со строками быть не должно.

но я ведь преобразованную строку в число

a, b = int(str_x[:n_2-1]), int(str_x[n_2:])
    c, d = int(str_y[:n_2-1]), int(str_y[n_2:])

py.user.next

Апрель 18, 2015 23:17:15

jheniae
но я ведь преобразованную строку в число

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

Описание метода

jheniae

Апрель 20, 2015 09:15:55

py.user.next
Во-первых, строки занимают больше памяти и медленее работают, а во-вторых, получаются вот такие ситуации, не свойственные для чисел.
При срезе может остаться пустая строка, тогда как с числами остаётся ноль, который можно использовать в вычислениях.

Спасибо за подсказку. Пришлось с другой стороны подходить, и все заработало.

Antin3

Ноя. 18, 2015 14:02:56

Подскажите, где ошибка.

def karatsuba(x,y):
    if x < 10 and y < 10:
        return x*y
    else:
        if x > y:
            divider = pow(10,len(str(x)) / 2)
        else:
            divider = pow(10,len(str(y)) / 2)
    a = x // divider
    b = x % divider
    c = y // divider
    d = y % divider
    ac = karatsuba(a,c)
    bd = karatsuba(b,d)
    e = a+b
    f = c+d
    ef = karatsuba(e,f)
    return (ac*pow(divider,2) + bd + ((ef-bd-ac)*divider))
    print (karatsuba(21625695688898558125310188636840316594920403182768,13306827740879180856696800391510469038934180115260))

написал программу, но ничего не происходит. Заменил числа в последней строке на (x,y), ввел их через командную строку. Также ничего. Где ошибка?