Dzień dobry wszystkim.
Piszę program, który będzie podnosił bardzo duże liczby do dużych potęg. Coś w tym stylu (podnoszę pierwszą do potęgi o wykładniku drugiej):
1208908178601273562548687541755705969869521751795611085834976547
52314
Zamierzam użyć algorytmów szybkiego potęgowania i Karacuby. Nie wiem tylko jak podzielić liczby z danych wejściowych, tak aby nie przekraczały zakresów. Wiem, że trzeba je wczytać jako stringi i jakoś dzielić, ale na tym się moja wiedza kończy. Czy ktoś byłby tak dobry i podpowiedział jak mam to zrobić? Będę bardzo wdzięczny.
Dzięki z góry i miłego weekendu.
Potęgowanie bardzo dużych liczb
- Rejestracja: dni
- Ostatnio: dni
- Postów: 161
0
- Rejestracja: dni
- Ostatnio: dni
0
Jeżeli to nie jest nauka, to lepiej użyj gotowej biblioteki do operacji na dużych liczbach.
http://gmplib.org/
- Rejestracja: dni
- Ostatnio: dni
1
Jeśli celem jest łatwe i szybkie wyświetlanie liczb to podstawą powinien być miliard 1000000000 (dane trzymać jako unsigned int a obliczenenia robić na unsigned long long), bo to jest najwyższa potęga 10, która mieści się w 32 bitach.
Jeśli nie chcesz używać long long to musisz zmniejszyć podstawę.
- Rejestracja: dni
- Ostatnio: dni
- Postów: 2500
1
string number = "6332482634724823648273642734684723847634";
vector<int> digits;
for (string::const_iterator it = number.begin(); it != number.end(); ++it) {
digits.push_back(*it - '0');
}
- Rejestracja: dni
- Ostatnio: dni
- Postów: 161
0
A mam jeszcze dodatkowe pytanie:
bo napisałem sobie już al. Karacuby i szybkiego potęgowania, ale teraz będę musiał chyba w alg. potęgowania wpleść alg. Karacuby jeśli dobrze rozumiem?
Tzn. w potęgowaniu do mnożenia trzeba użyć Karacuby?
PS: Panowie nastąpiła pomyłka. Pisząc szybkie potęgowanie miałem na myśli metodę wielokrotnych kwadratów.