Karatsuba algoritması çok fazla özyineleme

Question

Karayoluyla çarpma algoritmasını C++ 'da uygulamaya çalışıyorum ama şu anda sadece python'da çalışmaya çalışıyorum.

def mult(x, y, b, m): 
    if max(x, y) < b: 
     return x * y 

    bm = pow(b, m) 
    x0 = x/bm 
    x1 = x % bm 
    y0 = y/bm 
    y1 = y % bm 

    z2 = mult(x1, y1, b, m) 
    z0 = mult(x0, y0, b, m) 
    z1 = mult(x1 + x0, y1 + y0, b, m) - z2 - z0 

    return mult(z2, bm ** 2, b, m) + mult(z1, bm, b, m) + z0 

Ne alamadım geçerli:: z2, z1 ve z0 nasıl oluşturulmalıdır İşte

benim kodudur? mult işlevini kullanarak yinelemeli doğru mu? Eğer öyleyse, bir yerde karışıklık yapıyorum çünkü özyineleme durmuyor.

Birisi hatanın nerede olduğunu belirleyebilir mi?

Answer 1

Not: adreslerine doğrudan OP'ın sorusu yaklaşık aşırı tekrarlama, ancak doğru bir Karatsuba algoritması sağlamak denemez aşağıda yanıt. Diğer yanıtlar ise bu konuda numaralı telefondan çok daha bilgilendiricidir.

bu sürümü deneyin:

def mult(x, y, b, m): 
    bm = pow(b, m) 

    if min(x, y) <= bm: 
     return x * y 

    # NOTE the following 4 lines 
    x0 = x % bm 
    x1 = x/bm 
    y0 = y % bm 
    y1 = y/bm 

    z0 = mult(x0, y0, b, m) 
    z2 = mult(x1, y1, b, m) 
    z1 = mult(x1 + x0, y1 + y0, b, m) - z2 - z0 

    retval = mult(mult(z2, bm, b, m) + z1, bm, b, m) + z0 
    assert retval == x * y, "%d * %d == %d != %d" % (x, y, x * y, retval) 
    return retval 

sürümü ile en ciddi sorun x0 ve ve y0 ve y1 x1 sizin hesaplamaları çevrilmiş olmasıdır. Ayrıca, x1 ve y1'un 0 olması durumunda algoritmanın türetmesi geçerli değildir, çünkü bu durumda bir çarpanlaştırma adımı geçersiz olur. Bu nedenle, hem x hem de y'nin b ** m'den daha büyük olmasını sağlayarak bu olasılığı önlemelisiniz.

DÜZENLEME: kodda bir yazım hatası düzeltildi; eklenen açıklamalar

EDIT2:

orijinal versiyonunda direk yorum, daha net olmak gerekirse:

def mult(x, y, b, m): 
    # The termination condition will never be true when the recursive 
    # call is either 
    # mult(z2, bm ** 2, b, m) 
    # or mult(z1, bm, b, m) 
    # 
    # Since every recursive call leads to one of the above, you have an 
    # infinite recursion condition. 
    if max(x, y) < b: 
     return x * y 

    bm = pow(b, m) 

    # Even without the recursion problem, the next four lines are wrong 
    x0 = x/bm # RHS should be x % bm 
    x1 = x % bm # RHS should be x/bm 
    y0 = y/bm # RHS should be y % bm 
    y1 = y % bm # RHS should be y/bm 

    z2 = mult(x1, y1, b, m) 
    z0 = mult(x0, y0, b, m) 
    z1 = mult(x1 + x0, y1 + y0, b, m) - z2 - z0 

    return mult(z2, bm ** 2, b, m) + mult(z1, bm, b, m) + z0 

Answer 2

Tekniğin arkasındaki fikir, z _i terimlerinin, özyinelemeli algoritma kullanılarak hesaplandığına inanıyorum, ancak sonuçlar bu şekilde birleştirilmiş değil. İstediğiniz Net sonuç, B'nin uygun bir değer seçin varsayarsak

z0 B^2m + z1 B^m + z2 

olduğundan (diyelim ki, 2) Eğer herhangi bir çarpmanın yapmadan B^m hesaplayabilir. Örneğin, B = 2 kullanılırken, B^m'yi çarpımlar yerine bit vardiyaları kullanarak hesaplayabilirsiniz. Bu, son adımın hiç bir çoğaltma yapılmadan yapılabileceği anlamına gelir.

Bir şey daha - Tüm algoritma için sabit bir m değeri aldığınızı fark ettim. Tipik olarak, bu algoritmayı, her zaman B^m'nin B ve B harfleri ile yazılırken, x'in ve y harflerinin yarısı kadar bir sayıya sahip olacak şekilde bir değere sahip olacaksınız. m = ceil ((log x)/2) seçerek.

Bu yardımcı olur umarız!

Answer 3

Genellikle büyük sayılar tam sayıların diziler olarak depolanır. Her bir tam sayı bir rakamı temsil eder. Bu yaklaşım, dizinin basit sola kaymasıyla tabanın gücü ile herhangi bir sayıyı çoğaltmanıza izin verir.

İşte (hatalar içerebilir) benim liste tabanlı bir uygulamasıdır:

def normalize(l,b): 
    over = 0 
    for i,x in enumerate(l): 
     over,l[i] = divmod(x+over,b) 
    if over: l.append(over) 
    return l 
def sum_lists(x,y,b): 
    l = min(len(x),len(y)) 
    res = map(operator.add,x[:l],y[:l]) 
    if len(x) > l: res.extend(x[l:]) 
    else: res.extend(y[l:]) 
    return normalize(res,b) 
def sub_lists(x,y,b): 
    res = map(operator.sub,x[:len(y)],y) 
    res.extend(x[len(y):]) 
    return normalize(res,b) 
def lshift(x,n): 
    if len(x) > 1 or len(x) == 1 and x[0] != 0: 
     return [0 for i in range(n)] + x 
    else: return x 
def mult_lists(x,y,b): 
    if min(len(x),len(y)) == 0: return [0] 
    m = max(len(x),len(y)) 
    if (m == 1): return normalize([x[0]*y[0]],b) 
    else: m >>= 1 
    x0,x1 = x[:m],x[m:] 
    y0,y1 = y[:m],y[m:] 
    z0 = mult_lists(x0,y0,b) 
    z1 = mult_lists(x1,y1,b) 
    z2 = mult_lists(sum_lists(x0,x1,b),sum_lists(y0,y1,b),b) 
    t1 = lshift(sub_lists(z2,sum_lists(z1,z0,b),b),m) 
    t2 = lshift(z1,m*2) 
    return sum_lists(sum_lists(z0,t1,b),t2,b) 

sum_lists ve sub_lists döner normalize edilmemiş sonuç - tek haneli taban değerinden büyük olabilir. normalize işlevi bu sorunu çözdü.

Tüm işlevler, rakamların ters sırayla alınmasını bekler. Örneğin, taban 10'daki 12, [2,1] olarak yazılmalıdır. geliştirmek böl-ve dört yerine 3 özyinelemeli çağrılar yaparak çarpma algoritmasını ele geçirmek Karastuba Çarpmanın hedeftir 9987654321.

» a = [1,2,3,4,5,6,7,8,9] 
» res = mult_lists(a,a,10) 
» res.reverse() 
» res 
[9, 7, 5, 4, 6, 1, 0, 5, 7, 7, 8, 9, 9, 7, 1, 0, 4, 1] 

Answer 4

bir kare almak sağlar. Bu nedenle, kodunuzdaki çoğaltmaya yinelemeli bir çağrı içermesi gereken tek satırlar, z0, z1 ve z2 atanmasıdır. Başka bir şey size daha kötü bir karmaşıklık verecektir. Çarpmayı henüz tanımlayamadığınız zaman (ve bir fortiori exponentiation), b^m'u hesaplamak için pow'u kullanamazsınız. Bunun için, algoritma, önemli bir şekilde, bir konumsal notasyon sisteminin kullanıldığı gerçeğini kullanır. temsili temsile sahipseniz, x*b^m bu temsilin bitlerini m kez sola kaydırarak kolayca elde edilir. Bu kaydırma işlemi, herhangi bir konumsal notasyon sistemi ile esasen "özgür" dir. Bu aynı zamanda onu uygulamak istiyorsanız, bu konumsal gösterimi ve "serbest" kaymayı yeniden üretmeniz gerektiği anlamına gelir. Ya b=2 bazında hesaplamayı seçtiniz ve python'un bit operatörlerini (veya test platformunuz varsa, belirli bir ondalık, onaltılık tabanın bit operatörlerini), kullanın ya da eğitim amaçlarına yönelik çalışmaya karar verdiniz. rastgele bir b, ve bu konumsal aritmetiği dizgiler, diziler veya gibi listelerle yeniden üretirsiniz.

Zaten bir solution with lists var. int(s,base), base bazında bir sayı gösterimi olarak görülen s dizgesine karşılık gelen tam sayıyı vereceğinden python dizeleriyle çalışmayı seviyorum: bu, testleri kolaylaştırır. Çok iyi yorumlanabilmeniz için string-to-number ve sayıdan dizeye ilkel değerler dahil olmak üzere, here numaralı bir öznitelik olarak ağır yorumlanmış dizeye dayalı bir uygulama yayınladım.

Sen mult için üs ve argümanlar olarak (eşit) uzunluğunda yastıklı dizeleri sağlayarak test edebilirsiniz:

In [169]: mult("987654321","987654321",10,9) 

Out[169]: '966551847789971041' 

sen dize uzunlukları dolgu anlamaya veya saymak istemiyorsanız, bir

In [170]: padding("987654321","2") 

Out[170]: ('987654321', '000000002', 9) 

Ve tabii ki b>10 ile çalışır: dolgu fonksiyonu sizin için yapabilir

In [171]: mult('987654321', '000000002', 16,9) 

Out[171]: '130eca8642' 

(wolfram alpha ile kontrol edin)