Witam. Mam następujący problem. Potrzebuję "czegoś" w czym mógłbym przechowywać liczbę, na której mógłbym wykonywać działania. Problem jest w tym, że ta liczba może mieć nawet 250 cyfr (takie wytyczne). Nie zmieści się ona nawet w zmiennej typu long long int, a na tablicy nie mógłbym raczej wykonywać działania. Zamierzam na tej liczbie przede wszystkim wykonywać dzielenie przez 2 i 5 oraz odejmowanie 1. Za każdą odpowiedź byłbym wdzięczny.
0
0
z taka ilościa cyfr to string mi przychodzi do głowy, przechowywać możesz np w pliku tekstowym ;)
0
No ale na stringu raczej nie będę mógł wykonywać działań.
2
Są dwa sposoby, albo używasz gotowej biblioteki do operacji na liczbach o dowolnej precyzji (np. gnu MP), albo piszesz ją samemu. W drugim przypadku to właśnie przechowujesz części liczby w tablicy. Jeżeli to jest na jakieś zaliczenie, to pewnie chodzi o to drugiego. String nie jest w tym wypadku najlepszym rozwiązaniem, lepiej jest pogrupować po większe kawałki. Zakładająć, że głównie ta liczba będzie dzielona przez 5 lub 2 to podział na kawałki o długości powiedzmy 10^9 i trzymanie tego w tablicy intów będzie akurat.
0
Ok. Czyli musiałbym taką liczbę powkładać w tablicę dzieląc na poszczególne kawałki, tak? Dobrze zrozumiałem? Tylko jak miałbym na takiej tablicy wykonać działania?
PS. jakby co chodzi o C++
2
@Zjarek właśnie miałem pisać o GNU, ale mnie uprzedziłeś. Za to dorzucę kilka linków :
http://gmplib.org/
oraz wiki:
http://pl.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library
http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library
1
@compl:
Przypomnij sobie, jak uczyli działań "pod kreską" w podstawówce. Tam masz liczbę przedstawioną jako tablica cyfr, możesz spokojnie (jeżeli nie musi być to za wydajne) stosować te same algorytmy jak wtedy. Np. dodawanie. Bierzesz 2 cyfry z prawej strony, dodajesz je do siebie, jeżeli wynik jest większy od 10 to przenosisz jeden dalej itd.
0
W sumie, to też o tym pomyślałem, tylko zastanawiałem się, czy nie ma jakiegoś prostszego sposobu (bo nie chciałem całego dotychczas napisanego programu zmieniać). Aczkolwiek dzięki, spróbuję tego. Swoją drogą fajne porównanie z tym działaniem pisemnym ;) Dziękuje wszystkim za odpowiedzi.
1
@compl jakbyś dobrze ten program napisał to nic by nie trzeba bylo zmieniać, ot podmieniłbyś tylko typ obiektów z int / long long na ten swój własny. Nauczka na przyszłość.
0
moze troche spoznione ale chyba chodzi o strukture/klase i przeciazanie operatorow...
0
operacje na tablicy 250-elementowej mogą być bardzo kosztowne. wiedz że nie musisz stosować systemu dziesiętnego i przechowywać w jednej komórce jedną cyfrę 0-9. wystarczy tablica 14 elementów typu long int (8 bajtów) i użyć systemu pozycyjnego o podstawie 2^64. operacja wykonuje się tak jak w systemie dziesiętnym, tylko że cyfr jest trochę więcej (ale liczb składa się z tylko 14). jeżeli zależy Ci na wydajności to może znacznie przyśpieszyć program. wadą jest dość kosztowna konwersja liczby na system dziesiętny żeby ją wyświetlić, ale jeśli do wyświetlania czy zapisu możesz stosować system 16 to będzie to proste. no i można dość szybko wykonać dzielenie i mnożenie przez 2 (i potęg 2) korzystając z przesunięcia bitowego.
0
Liczba 250-cyfrowa to bardzo duża liczba. Najprostsze będzie oczywiście skorzystanie z zewnętrznej biblioteki. Jeżeli chcesz działania na tych liczbach zaimplementować sam to proponuję jednak operowanie w systemie dziesiętnym na napisie. Jeżeli nie masz nic przeciwko temu, by się pobawić, możesz zaimplementować arytmetykę dla liczb w systemie o większej podstawie, np. 64, jak proponuje mój poprzednik. Tylko nie używaj long int, bo nigdzie nie jest napisane, że musi ona wynosić 8 bajtów (a tyle potrzebujesz, żeby przechować jedną cyfrę takiej dużej liczby). Użyj uint64_t, unsigned __int64 (typ Visual C++) albo unsigned long long (int) (może być mniej niż 64 bity). W takiej kolejności preferencji.
Liczba 250 cyfrowa (w systemie dziesiętnym) będzie miała 13 cyfr w systemie o podstawie 64 i będzie zajmować 104 bajty.
1
compl napisał(a):
Zamierzam na tej liczbie przede wszystkim wykonywać dzielenie przez 2 i 5 oraz odejmowanie 1.
Sprecyzuj problem. Może się okazać, że można go rozwiązać, bez posługiwania się wielkimi typami.
Przykładowo wykonanie obliczeń typu "2a mod b" wcale nie wymaga posługiwania się dużymi liczbami, nawet gdy a i b są rzędu milionów.