Operacje na dużych liczbach

Załóżmy, że mamy system, który operuje na liczbach 32-bitowych maksymalnie i j. programowania również nie ma większych wbudowanych.

Chcemy zrobić np. programowe operatory dla liczb np. 1024 bitowych.

Operatory +, -, -(jednostronny), =, <, >, ... to proste

Nieco bardziej skomplikowany jest *, ale i to nie jest specjalny problem, bo nie trudno się robi.

Pozostaje jednak operator /.

I tutaj pojawia się pytanie. Czy istnieje jakiś sposób rozbicia długiego dzielnika? Dla małego dzielnika łatwo policzyć, ale jak dzielnik jest duży, to co z tym można zrobić? Czy może jedyny sposób to metoda przechodzenia bit po bicie w wyniku na zasadzie:

 
for(i od 1023 do 0)
{
    wynik.bit[i] = 1;
    tmp = wynik * dzielnik;
    if (tmp > dzielna) wynik.bit[i] = 0;
    else if (tmp == dzielna) break;
}

No i operator mod, ale tutaj to może na zasadzie dzielimy, mnożymy, odejmujemy, chyba że jest jakiś prostszy sposób.

Spróbuj wykorzystać to: https://www.mathsisfun.com/long_division.html
lub to: http://www.nychold.com/em-arith.html

Akurat znalazłem bitową wersję

 
wynik = 0;
tmp = 0;
for(i od 1023 do 0)
{
    tmp <<= 1;
    tmp.bit[0] = dzielna.bit[i];
    if (tmp >= dzielnik)
    {
         tmp -= dzielna;
         wynik.bit[i] = 1;
    }
}

A jeszcze zastanawiałem się nad algorytmem wyświetlania takiej dużej liczby w systemie np. dziesiętnym.

Jedyne co mi przyszło do głowy, to dwie wersje: tablica wartości dla każdego z bitów, czyli np.

 
tablica[0] = {0,0,0,0,0,0,1}
tablica[1] = {0,0,0,0,0,0,2}
tablica[2] = {0,0,0,0,0,0,4}
tablica[3] = {0,0,0,0,0,0,8}
tablica[4] = {0,0,0,0,0,1,6}
tablica[5] = {0,0,0,0,0,3,2}
....
tablica[] = {0,0,6,5,5,3,6}
.....

i na koniec sumujemy.

Druga wersja to metoda wyznaczania reszty z dzielenia po prostu. Którą uznałbyś za szybszą?