logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

[mips] - przekroczenie zakresu liczb i operacja modulo

newsted89 06 Sty 2009 18:32 3582 11
REKLAMA
  • #1 5959832
    newsted89
    Poziom 10  
    Mam do napisania pewien program. A mianowicie

    Cytat:
    Napisz procedure, która wylicza a^n mod m. Procedura powinna dzialac dla dowolnych a, m i n mieszcz¡cych sie na 32-bitach.


    i teraz tak wydaje mi sie ze jak podniose a do potegi n to przekrocze maksymalny zakres liczb, wiec z dzielenia nic nie wyjdzie. Ma ktos pomysl jak to zrobic?? Chodzi o sam algorytm lub wzor bo zaimplementuje to sam.
  • REKLAMA
  • #2 5959907
    piotr_go
    Konstruktor DIY elektronika
    Coś mi sie zdaje że dla dowolnych 32 bitowych to nie da rady, raz dwa pojawią się gigantyczne liczby których nie będzie można w sensownym czasie i zajętości pamięci policzyć.
  • #3 5959919
    newsted89
    Poziom 10  
    no tutaj jest problem bo musi dzialac na dowolnych. Jezeli to cos zmienia to program odpale na emulatorze mars
  • REKLAMA
  • #5 5960004
    newsted89
    Poziom 10  
    zapytam bo faktycznie moze tak byc
  • REKLAMA
  • #6 5960975
    Konto nie istnieje
    Konto nie istnieje  
  • #8 5962270
    piotr_go
    Konstruktor DIY elektronika
    Przyznam że nie bardzo wiem jak by to miało działać :(
    Moja matematyka nieco zardzewiała.

    Najpierw zrobić A mod M
    potem wynik mnożyć N razy, ....
    i tu widzę problem bo potem trzeba zrobić mod z tego co może przekroczyć 32 bit :(

    A nie, sorry, przecież można robić to ostatnie modulo po każdym mnożeniu i jego wynik dawać do mnożenia * (a mod m). Dobrze myślę ? Czy już za późno i piszę głupoty?
    tmp = 1;
    for(unsigned int i = 0; i<n; i++){
        tmp = (tmp*a) mod m;
    }
    return tmp;

    jako tmp dać 64 bitową zmienną
  • #9 5963768
    Dr.Vee
    VIP Zasłużony dla elektroda
    Chyba doczytałeś tylko do pierwszego algorytmu na w/w stronie... :]

    Oczywiście mnożenie dwóch zmiennych 32 bitowych da Ci 64 bity wyniku, więc i mnożenie i dzielenie modulo musisz wykonywać na takich argumentach.

    Pozdrawiam,
    Dr.Vee
  • #10 5977947
    newsted89
    Poziom 10  
    no dobra panowie czyli potrzebuje zmiennej 64-bitowej. Doszedlem do tego ze jak sie dwie zmienne 32-bitowe pomnozy to pierwsze 32 bity sa w rejestrze $hi a kolejne 32 w $lo. No i niestety mam ten wynik rozbity na 2 rejestry a jak chce mnozyc to musze przez jeden rejestr. Jakos da rade to zrobic??
  • REKLAMA
  • #12 5978346
    newsted89
    Poziom 10  
    no tak tylko wyniku tych obliczen nie zapisze do zadnego rejestru
REKLAMA