Algorytm szybkiego obliczania reszty z dzielenia.

barytek · Post autor: **barytek** » 21 paź 2007, o 18:40

Czy istnieje jakiś szybki algorytm obliczania reszty z dzielenia? Nie potrzebuje wyniku dzielenia tylko samą resztę. Chcę dzielić liczby dwójkowe. Algorytm do obliczania CRC dość szybko oblicza resztę, ale z dzielenia wielomianów, a mi trzeba dzielić zwykłe liczby.

KARQL · Post autor: **KARQL** » 22 paź 2007, o 12:56

Możesz zobaczyć tutaj:
main.edu.pl/user.phtml?op=lesson&n=32

MGT · Post autor: **MGT** » 29 paź 2007, o 21:54

Polecam dzielenie w słupku, jak w podstawówce. Wrzucasz liczbę do tablicy znaków i odejmujesz dzielnik od możliwie najstarszej liczby znaczącej.

Np:

Kod: Zaznacz cały

 2457 : 22

 24
-22
--------
  25
 -22
--------
    37
   -22
--------
    15 < 22 => r = 15

l_smolinski · Post autor: **l_smolinski** » 17 paź 2008, o 20:20

Ciekawi mnie jak ten algorytm zadziała z takimi danymi bo coś mi tu nie gra:

2457:27

pozdrawiam.

kwak2k · Post autor: **kwak2k** » 17 paź 2008, o 20:41

barytek pisze:Czy istnieje jakiś szybki algorytm obliczania reszty z dzielenia? Nie potrzebuje wyniku dzielenia tylko samą resztę. Chcę dzielić liczby dwójkowe. Algorytm do obliczania CRC dość szybko oblicza resztę, ale z dzielenia wielomianów, a mi trzeba dzielić zwykłe liczby.

jesli ci chodzi o informatyczne rozwiazanie to np w c masz x % a = reszta z dzielenia x przez a (tzw mod)
reszte z dzielenia oblicza procesor (komendy dzielenia div i podobne) wiec chyba szybciej nie bedzie jesli chcesz algorytm wlasnoreczny (no chyba ze dzielenie przez wielokrotnosc 2 to wtedy mozna przesuwac bity w prawo a potem w lewo i reszta to to co zniknie [czy bedzie szybsze od div(raczej nie))

ale jesli musisz algorytm to jak kolega powyzej napisal.

MGT · Post autor: **MGT** » 18 paź 2008, o 10:25

l_smolinski pisze:Ciekawi mnie jak ten algorytm zadziała z takimi danymi bo coś mi tu nie gra:

2457:27

Kod: Zaznacz cały


 2457 : 27

 245
-243
-----
     27
    -27
    ----
       0 => r = 0