[C++] duża liczba float na str/int

Question

Dzień dobry,

szukałem na tym forum (i nie tylko) odpowiedzi na podobne pytania, ale wciąż nie mogę rozwiązać swojego problemu. W C++ chcę operować dużymi liczbami i muszę np. mieć 26^16 lub dużo większe. To już jest ponad 20 cyfr. Zapisać jej nie mogę, bo nawet unsigned long long nie wystarcza. Chciałem wynik potęgowania zapisać jako tekst, ale to_string od jakiejś wielkości przekłamuje wyniki. Później chciałbym wyznaczyć resztę z dzielenia tej liczby przez jakąś liczbę pierwszą, która zmieściłaby się w unsigned short, ale wpierw potrzebuję wyniku potęgowania z dokładnością do jedności. W ostateczności chyba dałoby się ją uzyskać za pomocą arytmetyki modularnej: https://pl.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication

Jednak zamiast potęgowania musiałbym mnożyć tyle razy, ile wynosi wykładnik i za każdym razem wyciągać resztę, i jeszcze raz ją wyliczyć na końcu.

Proszę o pomoc.

Answer 1

Jeśli cały wzór masz zdefiniowany jako arytmetykę modulo, to to nie jest "w ostateczności" - to jest normalny sposób robienia tego. Nie potrzebujesz bigintów w ogóle. Jeśli Twoim zastosowaniem jest kryptografia to też daj znać :P

A jeśli jesteś pewny że potrzebujesz, to np boost::multiprecision ma liczby całkowite dowolnej wielkości, na przykład: https://www.boost.org/doc/libs/1_72_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/egs/factorials.html

Comments

Cześć. Dzięki za odpowiedź. Moim zastosowaniem jest funkcja haszująca do algorytmu Karpa-Rabina. https://eduinf.waw.pl/inf/alg/001_search/0052.php

W przykładzie alfabet ma 3 znaki, a długość okna do wzorca to 5. Jeśli alfabetem byłoby chociaż pół tablicy ASCII i wzorzec miałby tych znaków ponad 20, no to naprawdę mogłyby powychodzić duże liczby. Właśnie kombinuję ze schematem Hornera, ale obawiam się, że mogą być problemy z uaktualnianiem hasza tekstowego.