439. Not So Fast Multiplication [TMUL]

[TheTrip]

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdio.h>
#include <iostream>
const int BASE = 1000000000; /* podstawa */
const int DIGS = 9; /* liczba cyfr dziesietnych kazdej cyfry w zapisie
przy powyzszej podstawie */
const int LEN = 1000; /* stala dlugosc liczb */
struct liczba
{
int t[LEN];
int l; /* faktyczna dlugosc liczby */
};
using namespace std;
void wypisz(liczba x)
{
printf("%d", x.t[x.l - 1]);
for (int i = x.l - 2; i >= 0; i--)
printf("%0*d", DIGS, x.t[i]);
printf("\n");
}
void czytaj(liczba &x)
{
char s[LEN * DIGS + 1];
scanf("%s", s); /* czytamy lancuch - zakladamy, ze nie ma zer wiodacych */
/* Ustalamy dlugosc liczby */
int j = strlen(s); /* pozycja w lancuchu s */
if (j % DIGS == 0)
x.l = j / DIGS;
else
x.l = j / DIGS + 1;
j--;
for (int i = 0; i < x.l; i++)
{
/* ustalamy i-ta cyfre */
x.t[i] = 0;
for (int k = max(0, j - DIGS + 1); k <= j; k++)
x.t[i] = 10 * x.t[i] + (s[k] - '0');
j -= DIGS;
}
}
liczba operator* (liczba x, liczba y)
{
liczba z;
z.l = x.l;
int c = 0;
for (int i = 0; i < x.l; i++)
{
z.t[i] = int(((long long)(x.t[i]) * (long long)(y.t[i]) + c) % BASE);
c = int(((long long)(x.t[i]) * (long long)(y.t[i]) + c) / BASE);
}
while (c > 0)
{
z.t[z.l] = c % BASE;
c /= BASE;
z.l++;
}
return z;
}
int main(int argc, char *argv[])
{
int n;
cin>>n;
while(n) {
liczba a,b,c;
czytaj(a);
czytaj(b);
c=a*b;
wypisz(c);
n--;
}
//system("PAUSE");
return 0;
}

błąd wykonania (SIGSEGV) ????????????????????? czemu??? liczy przeciez elegancko all

[Mariusz_Marian]

Czy podane liczby mogą być ujemne?

[xan_sof]

To jest dobre pytanie. Dołączam się do niego. W zadaniu nie ma jakie to liczby..

[kokosek_sof1]

Wg mnie nie - dodałem do mojego kodu (w PHP):

if($a[0]=='-'||$b[0]=='-')yyy;

i mi nie wywaliło NZECa, więc raczej same liczby dodatnie.

[xan_sof]

Nie, to nie to.. Sprawdziłem i nie chodziło o liczby ujemne. Nie mam już siły na to zadanie.. Czy tutaj naprawdę zwykły program na tablicach, mnożący sposobem na "pod kreską" nie wystarczy..?

[kokosek_sof1]

Sprawdź sobie algorytm Karatsuby.

[ALBI_sof]

po problemi mam już AC

[ronwsh]

zmień język

[xan_sof]

Podchodzę do tego zadania chyba już od roku, ale mniejsza o to Otóż mam takie pytanie. Wpadłem na pomysł żeby w ramach dodatkowego edukowania się, popróbować pisania na spoju w innych językach. Nie ukrywam, że zachęcił mnie do tego fakt, iż zobaczyłem że niektóre programy w PHP są o ponad połowę szybsze niż te wolniejsze w C++. Czy ktoś mógłby mi wytłumaczyć jak to się dzieje? Rozumiem że pewnie jest tak, że zależy od algorytmu, który sprytniejszy. Jednak ogólna opinia jest taka że języki interpretowane są wolniejsze od kodu natywnego. Mimo to dość sporo osób skłoniło się rozwiązać to zadanko w PHP. Czemu? Jakaś korzyść z tego płynie?

[rotoZOOM]

długości mnożnej i mnożnika mogą mieć do 10 tysięcy cyfr (razy do 1000 testów w jednym zadaniu)

[anim_90]

Odgrzewam wątek. I w sumie zwracam się do osób, które wykonały to zadanie w C++. Czy jedynym rozwiązaniem jest korzystanie z klasy string (ew. typ char)? i bawić się w ciągłą konwersję ? Czy to ma sens ? A może jakoś inaczej to spróbować? Ktoś "podrzuci" pomysł wejściowy ? Z góry dziękuję.

[narbej]

zwracam się do osób, które wykonały to zadanie w C++

Nawet nie chce mi się sprawdzać, czy zrobiłem je w c czy nie.

Czy jedynym rozwiązaniem jest korzystanie z klasy string (ew. typ char)?

Tak

i bawić się w ciągłą konwersję ?

Czemu ciągłą? Przecież wczytując dowolną liczbę, program za każdym razem to robi za nas [niejawnie gdzieś w tle, w bibliotece std]. Jeżeli po wczytaniu liczby i podzieleniu jej na odpowiednie bloki, przekonwertowałeś bloki na liczby, to przy wypisywaniu już nie musisz robić konwersji, zrobi to za Ciebie bibl. std. przy wypisywaniu kolejnych bloków - pamietaj, że czasami trzeba wypisać zera wiodące. Poczytaj opisy operowania bignumbers np main.edu.pl, u Stańczyka, czy w manualu biblioteki GMP [The GNU Multiple Precision Arithmetic Library] lub dowolnym innym źródle.

[anim_90]

Bardzo dzięĸuję za wskazówki Mam nadzieję, że uda mi się to "oddać' do końca tygodnia

Ps: Jeśli przeskok umiejętności jaki jest potrzebny do rozwiązania zadań trudnych w stosunku do średnich jest tak samo duży jak pomiędzy łatwym i średnim, to nie chcę tam iść - w sensie do trudnych ;p

[narbej]

Zostały jeszcze Chalange. Ale nawet w trydnych są łatwe, średnie i trudne. Jeżeli jednak lubisz wyzwania i chcesz się więcej nauczyć, lub zrobisz wszystkie lub większość zadań łatwiejszych, to nie masz wyjścia.

[tarpauwatratar]

A ja odradzam string/char.

Na SPOJu istnieje nie tak znowu mało zadań, które opierają się na arytmetyce wielkich liczb. Zwykle w tych zadaniach niedostępne są języki, w których arytmetyka wielkich liczb nie jest problemem. Według mnie nie ma sensu za każdym razem trzaskać te same/podobne operacje i lepiej zrobić to raz a porządnie.

W internecie krążą prawie gotowe klasy do arytmetyki wielkich liczb. Ja wolałem dorzucić sobie kilka ciekawych funkcji (typu liczby Bella, tak zwany ciąg tetranacciego, sorty itd) użytecznych na spoju a inne rzeczy napisać po swojemu, ale co kto lubi. Zrobienie własnej klasy trochę mi zajęło, ale pozwoliło mi to nauczyć się obiektówki, poznać różne nietrywialne algorytmy i oswoić z pracą z kilkoma tysiącami linii kodu.

Czy było warto? Tak. Z racji, że temat mnie ciekawi, będę jeszcze dłuuuugo doskonalił tą klasę (marzy mi się implementacja arytmetyki zmiennoprzecinkowej z dokładnością do chociaż 1000 miejsc po przecinku) i wykorzystywał ją do swoich problemów biol-chem-mat-fiz.

Okazuje się jednak, że przydaje się ona też w problemach... informatycznych! Dodawanie? BigInt a, b; i a + b na out. Odejmowanie? Tak samo. Mnożenie? Też. Jakieś zadanie z potęgowaniem modulo (też jest w średnich)? Żaden problem. WIelkie silnie, szybko rosnące rekurencje? AC w paru liniach. W trudnych jest chyba zadanie z obliczeniem liczby pi z żądaną dokładnością a gdzieś widziałem dużo innych zadań tego typu. W średnich widziałem też zadanie z rozwiązaniem równania kwadratowego z dokładnością do entego miejsca po przecinku. Oczywiście, można to zrobić przy pomocy char czy string, ale według mnie wygodniej mieć już napisaną porządną "maszynkę do trzaskania zadań" i nie męczyć się z pisaniem kodu pod dane zadanie.

Oczywiście są dwie wady mojego podejścia: może się okazać, że komuś szybciej pójdzie własna arytmetyka pod kątem zadania niż własna klasa i nawet ilość zadań nie zmieni tej zależności. Dodatkowo klasa będzie zawsze wolniejsza niż rozwiązania pomyślane stricte pod dany problem. Mimo to mam tym sposobem same AC w rozsądnym czasie a poprawki w klasie poprawią wyniki we wszystkich zadaniach.

A swoją drogą to muszę tu podziękować rr_ za podsunięcie mi tego pomysłu

[narbej]

Brawo!

PS
A jak "wprowadzasz" bigliczby do swojej klasy? [nie korzystając z string/char]?

PS 2

W internecie krążą prawie gotowe klasy do arytmetyki wielkich liczb.

W: Stańczyk Algorytmika ... masz gotową, jak by co.

PS 3

... poznać nietrywialne algorytmy ,,,

Większość algorytmów ma to do siebie, że są nietrywialne i można je poznawać, uczyć się i używać niezależnie od bignumber, czy stosując zarówno podejście obiektowe lub funkcyjne albo funkcjonalne.

[tarpauwatratar]

Tablica intów. Operacje są szybsze niż na string/char bo podstawa systemu liczbowego jest dużo większa (u mnie static const int BASE = 1E9;). Nie znalazłem jednak informacji o tym, dlaczego nie warto robić tego na long longach, albo dlaczego dla komputera ta podstawa ma aż takie znaczenie (sądziłem, że procesor i tak musi przebić się przez całą tablicę więc czy to będzie dużo małych liczb w tablicy czy mało dużych liczb to żadna różnica). Ktoś z tak zwanego reala sugerował mi, że ma to związek z budową procesora (wspominał coś o amortyzowanym czasie stałym mnożenia więc jeżeli mnożenie komórki jest w O(1) to czas mnożenia zależy od długości liczby (liczby komórek), ale nie pamiętam dokładnie jego rozumowania a i on sam nie był tego pewien), ale nie znam się prawie wcale na informatyce i programowaniu by coś o tym wiedzieć.

Co do Stańczyka - dziękuję za informację!

A co do ostatniego PS to oczywiście masz rację. Niemniej pisanie takiego Karatsuby dla samego faktu napisania jest dla mnie mało motywujące. Jeżeli zadanie polega na zaprogramowaniu większej liczby konkretnych, jasno określonych funkcjonalności, to sprawia dużo więcej frajdy, daje więcej wiedzy i jednocześnie jest to coś, czym faktycznie można się pochwalić jako konkretnym, własnym osiągnięciem (bo jest różnica między "Mój program rozwiązuje zadanie 439" a "Moja klasa definitywnie nie jest najwydajniejsza i aby taka była wymaga kompletnej przebudowy, ale pozwoliła mi rozwiązać liczne zadania algorytmiczne na SPOJu oraz posłużyła do stworzenia takiego i siakiego programu przeznaczonego do - dajmy na to - symulowania prostych epidemii według modelu SIR").

Przepraszam, jeżeli coś napisałem nieskładnie, ale się spieszę.

---

Właśnie zrozumiałem o co chodziło Ci z wprowadzaniem liczb - tak, wczytuję je jako string a następnie przetwarzam do tablicy intów.

[narbej]

Właśnie zrozumiałem o co chodziło Ci z wprowadzaniem liczb - tak, wczytuję je jako string a następnie przetwarzam do tablicy intów.

Właśnie dokładnie tylko o to

Krótko. Co do basy 10e9, bo mnożąc dwie takie liczby nie otrzymamy liczby większej niż 10e18, a taka liczba mieści się jeszcze w standartowym typie [long long] i możemy ją standartowo "obsłużyć".

czy to będzie dużo małych liczb w tablicy czy mało dużych liczb to żadna różnica

Jednak jest istotna różnica. Dużo małych liczb - dużo mnożeń, dużo wczytywania i zapisywania do tablicy. Kilka dużych, tylko kilka wczytywań, kilka mnożeń i kilka zapisów wyników da tablicy.

[tarpauwatratar]

Możliwe, że przyczyna jest tak "trywialna". Twoje wyjaśnienie jest jednak najrozsądniejszym ze wszystkich, jakie znalazłem, więc przyjmuję je za fakt.

A szybkość... niby przyjmuję to rozumowanie, ale dla mnie to takie... dziwne. Bo liczba niby ta sama, tylko inaczej zapisana. Może kiedyś dowiem się jak działa procesor i wtedy to zaakceptuję albo nawet w sensie matematycznym udowodnię. W sumie kiedyś dziwiłem się, że niby komputer, ale O(n!) nie policzy w 10 milisekund a dzisiaj dziwiłem się, że pytania na egzaminie były jakie były

[anim_90]

Cześć Wróciłem do tego zadania, którego wcześniej nie zrobiłem. Wczoraj przysiadłem na kilka godzin do problemu wielkich liczb i.... nie udaje się ;p

Mam następujący problem. Poniższy kod działa "jak ta lala".... prawie ;p otóż gdy wrzucam jednorazowo dowolne przypadki, to wynik wyrzuca mi dobry. Dobry wynik uzyskuję również w momencie, gdy wrzucę kilka testów na raz, ale pod warunkiem, że długość charow zwiększa się z każdym przypadkiem, czyli działa na przykład :

2
34 56
111 1111

ale nie działa już sytuacja odwrotna:

2
111 1111
34 56

Niestety memset nie działa tak jakbym tego oczekiwał (z pewnością to ja źle z niego korzystam). Tutaj moja pierwsza moja prośba - czy ktoś mógłby mi pokazać odpowiedni sposób "kasowania" pamięci w moim programie?

Po drugie obawiam się, że nawet jak to zostanie rozwiązane, to nie wyrobię się z czasem. Czy taki sposób rozwiązania jaki stosuję ma sens w tym zadaniu?

Link:
http://ideone.com/Ap4wBR

Wiem, że kod ma trochę linii, mimo to byłbym wdzięczny za zainteresowanie tematem. Dziękuję.