25600. Iloczyn [AL_25_06]

[romic]

Z jakiegoś powodu zmienna ll Z w funkcji karacuba przekracza mi zakres i nie mam pojęcia dlaczego.
Dla przykładu ze strony pierwszy przypadek gdy wychodzi błędna wartość to gdy wchodzi
4553316145160088152 i 3900000000000000006. Gdy przemnożę te liczby normalnie (czyli result = f(a, b, mod)) to wychodzi wynik prawidłowy

//problem został rozwiązany

[quenthui]

Dobry jesteś, że naklepałeś Karatsubę do tego zadania.
Podpowiem tylko, że w tej linijce:

ll Z = ll_karacuba(begin1 + end1, begin2 + end2, mod) - X - Y;

'Z' ma czasem wartości większe niż 'mod'.
Po małej poprawce udało mi twoim kodem się zaliczyć przykładowe testy, ale nie sprawdzałem, czy zadanie przejdzie testy na spoju.
Jak będziesz mieć dalej problemy, to pisz.

PS. Wydaje mi się, że algorytm nazywa się Karatsuba, a nie Karacuba. Problem w tym, że Wikipedia mówi jedno, a inne strony drugie. Ciężko powiedzieć, kto ma rację.
Pozdrawiam

[romic]

Nie widzę tego Wszystkie wejścia i wyjścia po obstawiałem modami i nie działa. Jak wyjaśnić to, że mnożenie poza pętlą tych 2 liczb jest ok, a w pętli generuje błąd? Zwiększony zakres na unsigned daje zły wynik (też tylko w pętli)

[quenthui]

Przedtem jak to liczyłem, to mi tak wychodziło. Teraz nie mogę tego powtórzyć. Musiałem coś jeszcze zmienić w twoim kodzie.
Ale widzę drugą rzecz. Jeśli liczyłbyś bez modulo (zakładając, że nie ma przepełnienia), to Z zawsze będzie dodatnie. Tymczasem u Ciebie Z może wyjść ujemne. I przez to potem pojawia się odejmowanie, zamiast dodawania.
Zobacz, co się stanie, jeśli dodasz taką linijkę po obliczeniu Z

    if ( Z < 0 )
        Z += mod;

PS. U Ciebie twój kod się kompiluje? Ideone.com krzyczy, że nie zna funkcji pow oraz, że 4611686018427387847 nie mieści się w int'cie.

[romic]

Dzięki! if pomógł i liczy poprawnie. Teraz tylko muszę poradzić sobie z tle