Deo zbornika Učimo algoritme

Rusko seljačko množenje

Rusko seljačko množenje je algoritam koji omogućuje množenje velikih brojeva uz pomoć prostih operacija sabiranja i deljenja sa dva.

Bio je u upotrebi među seljacima koji nisu bili školovani i nisu znali tablicu množenja. Sličan algoritam se takođe koristio i u drevnom Egiptu, pa se naziva i egipatsko množenje.

Koraci

Da bismo pomnožili dva broja, na primer 12 i 14, potrebno je da prvi neprestano delimo sa dva (bez ostatka), a drugi množimo sa dva:

12   14
6    28
3    56
1    112

Potom, precrtati sve redove gde je prvi broj neparan:

12   14
6    28
3    56
1    112

Na kraju, sabrati brojeve koji su preostali u drugoj koloni.

     56
+   112
-------
    168

Implementacija

Data je iterativna implementacija u Python-u:

def pomnozi(x, y):
    zbir = 0
    while x > 0:
        if x % 2 == 1:  # ako je neparan dodaje na zbir
            zbir += y
        x = x >> 1      # deli sa dva bez ostatka
        y = y << 1      # mnozi sa dva
    return zbir

print (pomnozi(12, 14))

Moguće je algoritam implementirati i rekurzivno:

def pomnozi(x, y):
    if x == 0: return 0
    if x % 2 == 0:
        return 2 * pomnozi(x / 2, y)
    else:
        return y + 2 * pomnozi((x - 1) / 2, y)

print (pomnozi(12, 14))