NWD liczb w zapisie binarym

Witam!

Mam problem z napisaniem programu do obliczania nwd dwóch liczb w zapisie binarnym. Mój program jest za wolny.

kod:

 #include <iostream>
#include <string>
std::string odejmij(const std::string, const std::string);
std::string gcd(std::string, std::string);
int main() {
	int lt;
	std::cin >> lt;
    std::string a;
    std::string b;
	while(lt--)
	{
		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) << "\n";
		a.clear();
		b.clear();
	}
}
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;
} 

dziękuję za wszelką pomoc!

Musisz te operacje robić w zapisie binarnym? Wrzuć to do tablicy intów i dopiero wtedy obliczaj jak nie chcesz użyć gotowej biblioteki. Najlepiej zamknij to w klasie do obliczeń całkowitoliczbowych o dowolnej precyzji.

Pracuj na bitach (int), a nie na znakach (string).

Ok, mogę to zamienić na inty, ale czy to cokolwiek da? Zależy mi na znacznym przyspieszeniu tego, a nie tylko "dopieszczaniu". Szczerze mówiąc, nie korzystałem nigdy z niestandardowych bibliotek, ale znalazłem GNU MP Bignum Library (gmplib.org), i używanie tego nie wydaje się aż tak trudne, mam natomiast pytanie: czy da się "skleić" tę bibliotekę z kodem programu, aby można było to wkleić do serwisu podobnego do spoja? Ew. jak powinienem napisac funkcję, która by mi to wyliczyła? (chodzi oczywiście o algorytm, a nie o gotowy kod).

Sam algorytm nie wygląda źle. Operowanie na intach (w których będziesz trzymał np. 31 bitów (dodawanie i odejmowanie jest prostsze, nie trzeba używać long long)) przyspieszy Ci ten program pewnie kilkanaście razy, co w przypadku limitów czasowych na takim spoju jest dużym usprawnieniem. Przerobienie biblioteki, żeby zmieściła się w limicie wielkości kodu źródłowego SPOJa może być trudniejsze niż napisanie czegoś takiego samemu (nie jest to takie trudne, a dla Ciebie może być pouczające).

To zadanie nie jest na spoja, ale na lekcje (kod max 64mb, więc problmu nie ma :) ) Może prościej będzie na bitsecie? I za co "-1"? :)