POTEGA - Potęgowanie

[kuba1996]

Napisałem algorytm, tyle że otrzymuję TLE
Do mnożenia wykorzystuję algorytm Karatsuby i korzystam z algorytmu szybkiego potęgowania.
Czy ktoś widzi co mozna by ulepszyć?
Podpowiedź koncepcyjna?
Tutaj kod:

Ideone.com

[mariusz193]

Bardzo ładny program, a uzyskanie TLE to też niezłe osiągnięcie, biorąc pod uwagę, że najszybsze rozwiązania mają czas 0.00

algorytm Karatsuby jest niepotrzebny, szybkie potęgowanie tak

na starym forum była dyskusja na temat tego zadania, niestety obecnie niedostępna, a na nowym nic nie ma - dawno już nikt na forum nie chwalił się niepowodzeniem, choć widzę, że sporo nieudanych prób było

ale skoro potrafiłeś zaimplementować algorytm Karatsuby (i dorobek na spoj-u masz niezły), to ze zmianą koncepcji też powinieneś sobie poradzić, życzę powodzenia

[redysz]

Potwierdzam, przepisałem jedynie funkcję mnożącą (product2Numbers) i otrzymałem AC. Zakomentuj kod bo jest zbyt bliski poprawnej odpowiedzi.

[kuba1996]

algorytm Karatsuby jest niepotrzebny?(n^(log_2(3) vs n^2)
Chodzi o inny równie dobry algorytm mnożący liczby?
Czy chodzi o poprawienie złożoności podnoszenia do kwadratu?

[kuba1996]

Zmieniłeś koncepcję mnożenia?(product2Numbers)

[redysz]

Tak, musiałeś coś tam zepsuć (nie czytałem), bo przepisałem tę funkcję na zwykłe mnożenie pisemne, reszty nie ruszyłem i otrzymałem 0.03. Jednocześnie odpowiada to na Twoje pytanie: tak, algorytm Karatsuby jest niepotrzebny.

W skrócie jak zrobiłem:
pierwszy string -> tablica cyfr
drugi string -> tablica cyfr
mnożę i sumuję jak na kresce ułamkowej.
Żadnej rekurencji.

[kuba1996]

String zamieniłeś na tablicę char-ów?
To ze względu na lepszą wydajność w stosunku do stringa?
Bo próbowałem wcześniej mnożenie pisemne na stringach i też TLE.
Czy typ ma wpływ?

[redysz]

Owszem, operacje na stringach są niesamowicie wolne.

String zamieniłeś na tablicę char-ów?

Nie. Na tablicę intów.
“123456789” * "987654321"
zamieniam na
[1][2][3][4][5][6][7][8][9] * [9][8][7][6][5][4][3][2][1]
teraz wszystkie obliczenia (mnożenie i dodawanie) przeprowadzam na zwykłych liczbach (muszę mieć dodatkowo vector wyników, który pomieści wynik takiego mnożenia) i na końcu scalam to z powrotem w stringa.

[narbej]

Owszem, operacje na stringach są niesamowicie wolne.

Niesamowicie wolne, jakie operacje?
Przecież, jeżeli chcesz coś wepchnąć do środka lub skasować, to musi to kosztować i boleć. Inne “operacje” na stringach są tak samo wolne [szybkie] ja takie same operacje na tablicy char. Ale na zwykłych tablicach char nie da się przeprowadzić [łatwo i szybko] tego co można [wolno] na stringach. ;-).

[kuba1996]

Zmieniłem, i nadal TLE. Coś chyba jednak nie tak robię ?

Ideone.com

[redysz]

Inne “operacje” na stringach są tak samo wolne [szybkie] ja takie same operacje na tablicy char.

Pewnie masz rację, ale powiedz… czy ja coś gdzieś w ogóle pisałem o tablicy charów?

@kuba1996 Zmieniłeś o wiele więcej niż ja wspomniałem.
Po pierwsze testuj na większych przykładach (np. 999 998), bo na małych nie zauważysz różnicy. Na takich dużych szybko spostrzeżesz, że Twój poprzedni kod był znacznie szybszy od aktualnego.

Przypomnę co napisałem: “… bo przepisałem tę funkcję na zwykłe mnożenie pisemne, reszty nie ruszyłem”, a Ty wszystko zmieniłeś na wektory, nie wiem czy tam było źle, nie czytałem, ale z pewnością było lepiej niż teraz.

Tak więc przywróć poprzedni kod, następnie przejdź do metody product2Numbers i zmień tylko jej kod, czyli żeby było jasne co ja zmieniłem:

#include <iostream>
#include <vector> //tylko to dodałem
#define SumOfDigits(x, y, z) x + y + z - 3 * '0'
//dotąd wszystko tak samo, nie zmieniłem jednej literki
    string product2Numbers(string x, string y){
       //wnętrze tej funkcji przeorałem jak polecił mariusz193
       //ale nawet nagłówka funkcji nie zmieniłem
    }
//dalej wszystko tak samo, nie zmieniłem jednej literki

Napisz wydajniej funkcję product2Numbers
Nie twierdzę, że to najlepszy sposób, po prostu sprawdziłem teorię mariusza i się okazało, że miał rację.

[kuba1996]

Mógłbyś dać jakieś wskazówki, co jest kluczowe by poprawić wydajność?
To działa wolniej niż rekurencyjna Karatsuba.
Link do całego kodu:

Ideone.com

string product2NumbersGreedy(string x, string y){
vector result = {0}, X, Y;
int displacement;

X = string2Vector(x);
Y = string2Vector(y);
result = addFrontZeros(result, x.size() + y.size());

for(int i = x.size() - 1; i >= 0; i--){
    displacement = x.size() - i - 1;
    for(int j = y.size() - 1; j >= 0; j--){
        result = add2Numbers(result, X[i] * Y[j], displacement);
        displacement++;
    }
}

result = deleteFrontZeros(result);

return vector2string(result);

}

[redysz]

Podpowiedź gdybyś chciał zadanie wykonać jak najbardziej samodzielnie: wykonaj najpierw zadanie TMUL. W nim właśnie pobierasz dwa stringi i jedyne co masz zrobić to pomnożyć dwie liczby. Ja mam tam dosyć dobry wynik stąd mogłem wkleić od razu odpowiedni kod w miejsce Twojej funkcji. Jak zejdziesz poniżej 0.05 to pewnie będziesz mógł zrobić tak samo, bo zadanie TMUL jest składową tego.

Nie wiem jak Ci podpowiedzieć, żeby Tobie i innym nie podać pełnego rozwiązania. Jako, że się starasz i nie rezygnujesz to na PW Ci wysłałem przykładowy kod, który zadziała choć da się lepiej (robiąc na przykład jak poniżej).

Jakbyś natomiast chciał wiedzieć co można zrobić w tym pomyśle lepiej żeby przeszło, to:
zamiast zamieniać dwóch stringów “123456789” i “987654321” na dwa vectory cyfr [1][2][3][4][5][6][7][8][9] i [9][8][7][6][5][4][3][2][1] i mnożyć każdą z każdą (co jak sam zobaczyłeś nie jest najszybsze) można zamienić dwa stringi które chcemy pomnożyć “123456789” i “987654321” na wektory powiedzmy… trójek [123][456][789] i [987][654][321] i w ten sposób zmniejszyć diametralnie ilość obliczeń.

[irgawro]

Cześć, Wyniki z Kalkulatora dużych liczb i z mojego programu są zgodna, a jednak błędna Odpowiedź ???
Ktoś ma pomysł ?

[irgawro]

Dzięki, znalazłem błąd