NWD z bardzo dużych liczb

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.

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.

0
i=N; c=0
while(i>=0){
    c1=t[i] & 1;
    t[i]=(t[i]>>1) | (c << 31);
    i--; c=c1;
}
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.

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.

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

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ę...

0

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

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