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 delimo na pola (zaokružujući naniže) do jedinice, a drugi dupliramo:

12   14
6    28
3    56
1    112

Potom, odbacujemo sve redove gde je prvi broj paran:

12   14
6    28
3    56
1    112

Na kraju, sabiramo brojeve koji su ostali u drugoj koloni.

     56
+   112
———————
    168

Implementacija u Python-u

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))

Implementacija u JS-u

Data je iterativna implementacija u JS-u:

function pomnozi(x, y) {
    let zbir = 0
    while (x > 0) {
        if (x % 2 === 1) zbir += y
        x = Math.floor(x / 2)
        y *= 2
    }
    return zbir
}

console.log(pomnozi(12, 14))

Rekurzivna implementacija

Moguće je algoritam implementirati i rekurzivno:

function 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)
}

console.log(pomnozi(12, 14))