www.elektronik.si Seznam forumov www.elektronik.si
Forum o elektrotehniki in računalništvu
 
 PomočPomoč  IščiIšči  Seznam članovSeznam članov  SkupineSkupine  StatisticsStatistika  AlbumAlbum  DatotekeFilemanager DokumentacijaDocDB LinksPovezave   Registriraj seRegistriraj se 
  PravilaPravila  LinksBolha  PriponkePriponke  KoledarKoledar  ZapiskiZapiski Tvoj profilTvoj profil Prijava za pregled zasebnih sporočilPrijava za pregled zasebnih sporočil PrijavaPrijava 

Modulo operator

 
Objavi novo temo   Odgovori na to temo   Printer-friendly version    www.elektronik.si Seznam forumov -> Programiranje embedded sistemov
Poglej prejšnjo temo :: Poglej naslednjo temo  
Avtor Sporočilo
MatevzM
Član
Član



Pridružen-a: Ned 02 Jan 2011 23:09
Prispevkov: 40
Aktiv.: 0.23
Kraj: Novo mesto
PrispevekObjavljeno: Ned Nov 04, 2012 4:18 pm    Naslov sporočila:  Modulo operator Odgovori s citatom
Pri optimizaciji nekega problema sem naletel na težavo, ki je ne morem rešiti.
Vem da ostanek pri deljenju (modulo, %) s številom 2^n lahko izračunamo z
Koda:
x%(2^n) = x & ((1 << n) -1)

Sedaj me pa zanima, kako bi izračunal modulo s številom (2^n)-1 brez uporabe deljenja ali množenja, se pravi samo z bitwise operatorji ali seštevanjem in odštevanjem.
Ali obstaja kakšna enostavna rešitev za to?
Nazaj na vrh
Odsoten Poglej uporabnikov profil Pošlji zasebno sporočilo
aly
Član
Član



Pridružen-a: Tor 28 Sep 2004 14:51
Prispevkov: 9407
Aktiv.: 39.71
Kraj: Kranj - struževo
PrispevekObjavljeno: Pon Nov 05, 2012 3:20 am    Naslov sporočila:   Odgovori s citatom
Kaj pa je z opisanim shiftanjem narobe? To je ekspresna low-level operacija, ki se je ne da / ne splača še bolj optimizirati.
_________________
I'm going to stand outside, so if anyone asks, I'm outstanding Smile
Nazaj na vrh
Skrit Poglej uporabnikov profil Pošlji zasebno sporočilo Obišči avtorjevo spletno stran MSN Messenger - naslov
gregoral
Član
Član



Pridružen-a: Pet 24 Nov 2006 9:42
Prispevkov: 688
Aktiv.: 3.04
Kraj: Ljubljana
PrispevekObjavljeno: Pon Nov 05, 2012 2:42 pm    Naslov sporočila:   Odgovori s citatom
@aly: opisano deluje kadar je modulo 2^n, Matevz bi rad pa optimiziral: x % ((2^n)-1)

Recimo: x%3, x%7, x%15, x%31, ..., x%63, ..., x%1023, ...
Nazaj na vrh
Odsoten Poglej uporabnikov profil Pošlji zasebno sporočilo
Umnik
Član
Član



Pridružen-a: Čet 16 Sep 2004 17:52
Prispevkov: 958
Aktiv.: 4.04
Kraj: Novo mesto
PrispevekObjavljeno: Pon Nov 05, 2012 2:52 pm    Naslov sporočila:   Odgovori s citatom
Koda:
/*  modulus division by (1 << s) - 1 */

uint32_t  n;                      // numerator
const uint32_t s;                // s > 0
const uint32_t d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
uint32_t m;                      // n % d.

for (m = n; n > d; n = m) {
  for (m = 0; n; n >>= s) {
    m += n & d;
  }
}
// m is a value from 0 to d, with modulus division we want m to be 0 when it is d.
m = m == d ? 0 : m;


Vir: Internet.
Nazaj na vrh
Odsoten Poglej uporabnikov profil Pošlji zasebno sporočilo
MatevzM
Član
Član



Pridružen-a: Ned 02 Jan 2011 23:09
Prispevkov: 40
Aktiv.: 0.23
Kraj: Novo mesto
PrispevekObjavljeno: Pon Nov 05, 2012 3:33 pm    Naslov sporočila:   Odgovori s citatom
Našel sem eno kodo, ki tudi dela. Vendar je rešitev, ki jo je Umnik podal hitrejša. Njegova rešitev rabi povprečno 3.18409 ms, spodnja pa 5.61027ms.
Koda:
def modulo(x, k):
    m = 2**k-1
    r = binmod(x, k)
    q = x >> k
    while q!=0:
        while q!=0:
            r += q & ((1 << k) - 1)
            q = q >> k
        q = r >> k
        r = r & ((1 << k) - 1)
    while r >= m:
        r -= m
    return r

Hvala za boljšo rešitev Smile
Nazaj na vrh
Odsoten Poglej uporabnikov profil Pošlji zasebno sporočilo
Pokaži sporočila:   
Objavi novo temo   Odgovori na to temo   Printer-friendly version    www.elektronik.si Seznam forumov -> Programiranje embedded sistemov Časovni pas GMT + 2 uri, srednjeevropski - poletni čas
Stran 1 od 1

 
Pojdi na:  
Ne, ne moreš dodajati novih tem v tem forumu
Ne, ne moreš odgovarjati na teme v tem forumu
Ne, ne moreš urejati svojih prispevkov v tem forumu
Ne, ne moreš brisati svojih prispevkov v tem forumu
Ne ne moreš glasovati v anketi v tem forumu
Ne, ne moreš pripeti datotek v tem forumu
Ne, ne moreš povleči datotek v tem forumu

Uptime: 492 dni


Powered by phpBB © 2001, 2005 phpBB Group