NWD z bardzo dużych liczb

2011-07-05 22:17
0

Witam, mam problem z obliczeniem NWD z liczb reprezentowanych jako obiekty (o długości do 10100). Próbuję rozwiązać zadanie z: http://main.edu.pl/pl/user.phtml?op=showtask&task=nwd&con=ALG
Nie mogę wykorzystać algorytmu Euklidesa, ponieważ w kursie nie było mowy o reszcie z dzielenia, a:

while(a != b) {
a > b ? a -= b : b -= a
}

jest zbyt wolne. Proszę o jakieś wskazówki.

Pozostało 580 znaków

2011-07-05 22:32
0

a może tak: http://edu.i-lo.tarnow.pl/inf/alg/001_search/0005.php#Rozwiązanie_3

Pozostało 580 znaków

2011-07-06 10:30
0

Tylko jak rozwiązać przesunięcie bitowe, gdy liczba jest przechowywana w postaci tablicy? Bity z początku jednego elementu musiałby przejść na końcowe bity drugiego elementu.

Pozostało 580 znaków

2011-07-06 10:49
0
i=N; c=0
while(i>=0){
    c1=t[i] & 1;
    t[i]=(t[i]>>1) | (c << 31);
    i--; c=c1;
}

Pozostało 580 znaków

2011-07-06 14:30
0

Binarne NWD niekoniecznie musi być szybsze od normalnego algorytmu Euklidesa czy też np hybrydy dzielenia modulo i odejmowania, ponieważ przed binarnym GCD trzeba zamienić liczbę z postaci dziesiętnej na binarną. Ta hybryda polegałaby na odejmowaniu wielokrotności, np dla liczb n i m, przybliżamy długość tych liczb (czyli log10 n i log10 m) i np jeżeli pierwsza cyfra n jest większa od pierwszej cyfry m oraz liczba n jest dłuższa o k cyfr to robimy działanie: n -= m 10 k, przy czym możenie przez potęgi dwójki to po prostu dodawanie iluś tam kopii cyfry zero na koniec stringa. Jeżeli warunek dla pierwszych cyfr nie zachodzi to robimy działanie: n -= m 10 </sup> (k - 1). Szybka zamiana ze stringa zawierającego postać liczby w systemie dziesiętnym na liczbę zapisaną w systemie binarnym wymaga liczenia reszty z dzielenia lub stosowania podobnego triku co tu opisałem.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-07-07 17:53
0

Nie ma może innego sposobu? Zadanie powinno być do zrobienia wykorzystując techniki z kursu, czyli tylko +, -, *, /(przez int) i porównywanie. Siedzę nad tym binarnym GCD, ale na razie nie bardzo mi to idzie. Jeżeli nie ma łatwiejszego sposobu to jeszcze pokombinuję, bo to kwestia czasu, aż mi wyjdzie.

Pozostało 580 znaków

2011-07-07 18:16
0

Binarny GCD nie wypali bo przecież w standardzie nie ma funkcji które wczytują liczby rzędu 10^100 i konwertują na postać binarną. Jeśli użyjesz dodatkowej biblioteki, np GMP to równie dobrze mógłbyś użyć funkcji modulo z GMP.

Wykorzystaj mój sposób. Nie wykorzystuje on modulo (reszty z dzielenia) wprost.

Kod poglądowy:

#include <cstdio>

int potega(int podstawa, int wykladnik) {
    return wykladnik ? potega(podstawa, wykladnik - 1) * podstawa : 1;
}

//#define MOZNA_UZYWAC_MODULO
#define UZYJ_HYBRYDY

int gcd(int a, int b) {
#ifdef MOZNA_UZYWAC_MODULO
    a %= b;
#else
#ifdef UZYJ_HYBRYDY
    int wykladnik = 0;
    while (a >= b * potega(10, wykladnik + 1)) {
        wykladnik++;
    }
    if (a >= b) {
        a -= b * potega(10, wykladnik);
    }
#endif
    while (a >= b) {
        a -= b;
    }
#endif
    return a ? gcd(b, a) : b;
}

int main(int argc, char** argv) {

    printf("%d\n", gcd(95675769, 5675768));
    return 0;
}

Oczywiście zamiast intów będziesz miał stringi i zamiast mnożenia przez potęgi 10 będziesz miał doklejanie znaku '0' na koniec stringa.

PS:
Cały kod w #if to albo dzielenie modulo, albo emulacja dzielenia modulo - tak, powtarzane odejmowanie to emulowanie dzielenia modulo.

Edit:
Mam kod, trochę działa ale na testach się wywłaszcza (tylko 14 pkt zdobywa):


#include <iostream>
#include <string>

std::string odejmij(const std::string a, const std::string b) {
    std::string w;
    std::string::const_reverse_iterator ita = a.rbegin();
    std::string::const_reverse_iterator itb = b.rbegin();
    bool pozyczenie = false;
    char c;
    while (itb != b.rend()) {
        if (pozyczenie) {
            c = (*ita >= *itb + 1 ? *ita - *itb - 1 : *ita - *itb + 9) + '0';
            pozyczenie = *ita < *itb + 1;
        } else {
            c = (*ita >= *itb ? *ita - *itb : *ita - *itb + 10) + '0';
            pozyczenie = *ita < *itb;
        }
        w = c + w;
        ita++;
        itb++;
    }
    if (ita != a.rend()) {
        if (pozyczenie) {
            c = *ita - 1;
            w = c + w;
            ita++;
        }
        while (ita != a.rend()) {
            c = *ita;
            w = c + w;
            ita++;
        }
    }
    while ((w.size() > 1) && (w[0] == '0')) {
        w = w.substr(1, w.size() - 1);
    }
    return w;
}

std::string gcd(std::string a, std::string b) {
    std::string c(b);
    while ((a.size() > c.size() + 1) || ((a.size() == c.size() + 1) && (a >= c + '0'))) {
        c += '0';
    }
    if ((a.size() > c.size()) || ((a.size() == c.size()) && (a >= c))) {
        a = odejmij(a, c);
    }
    while ((a.size() > b.size()) || ((a.size() == b.size()) && (a >= b))) {
        a = odejmij(a, b);
    }
    return a != "0" ? gcd(b, a) : b;
}

int main(int argc, char** argv) {
    //std::cout << odejmij("996", "995") << std::endl;
    //std::cout << gcd("95675769", "5675768") << std::endl;
    std::string a;
    std::string b;
    std::cin >> a >> b;
    while ((a.size() > 1) && (a[0] == '0')) {
        a = a.substr(1, a.size() - 1);
    }
    while ((b.size() > 1) && (b[0] == '0')) {
        b = b.substr(1, b.size() - 1);
    }
    std::cout << gcd(a, b) << std::endl;
    return 0;
}

"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 2x, ostatnio: Wibowit, 2011-07-07 19:13

Pozostało 580 znaków

2011-07-08 22:02
0

Jutro wyjeżdżam, więc dopiero po powrocie zabiorę się znowu do tego zadania, ale jakby ktoś wymyślił dobry algorytm, który by się mieścił w czasie to niech napisze ;)

Pozostało 580 znaków

2011-07-26 12:36
0

Już wróciłem i wydaje mi się, że te zadanie trafiło do nieodpowiedniej lekcji ;) Wrócę do niego jak skończę kurs. Może wtedy coś wymyślę...

edytowany 1x, ostatnio: mark075, 2011-07-26 12:37

Pozostało 580 znaków

2011-07-26 13:23

modulo(a,b) = a- (a/b)*b; <-- dzielenie całkowitoliczbowe. ale pewnie da się jakoś szybciej - chociaz to i tak wydaje sie byc szybsze niz wersja z odejmowaniem


░█░█░█░█░█░█░█░█░█░█░█░
Pokaż pozostałe 5 komentarzy
Opisałem w pierwszym poście. Generalnie moja metoda opiera się na odejmowaniu. a%b to to samo co while(a>=b)a-=b. Ja dodatkowo sprawdzam o ile różnią się długości tych liczb. Jeżeli np a jest o pięć cyfr dłuższa od b, to odejmuję naraz 10000b lub 100000b (zależy czy oba są mniejsze od a czy nie). b*10000 to po prostu b z doklejonymi czterema zerami, można nawet ich nie doklejać jak się dobrze zaimplementuje algorytm. Sumaryczna ilość działań będzie nie większa niż dziesięć razy liczba działań przy wersji z modulo, ale liczenie modulo jest tu dużo więcej razy wolniejsze. - Wibowit 2011-07-26 14:29
Ja ten sposób rozumiem, tylko napisałeś, ze program wywłaszcza, więc dalej z tym nie kombinowałem :/ - mark075 2011-07-26 14:39
Jak wpiszę z palca liczby to działa ok, a ogólnie to nie chce mi się szukać błędu :] - Wibowit 2011-07-26 14:59
Przeanalizowałem Twój kod dokładniej, ale nie widzę błędu. Może coś przeoczyłem, ale im bardziej nad tym zadaniem myślę tym mniej zaczynam rozumieć. Wrócę do niego po całym kursie. Dzięki za pomoc :P - mark075 2011-07-27 11:13
Udało mi się zrobić to zadanie korzystając z algorytmu Euklidesa i algorytmów mnożenia i dzielenia z następnej lekcji - mark075 2011-07-31 15:43

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0