‟overcq”

Moduł dużych liczb pozwala przechowywać w postaci dwójkowej liczby większe niż liczba naturalna procesora i przeprowadzać na nich obliczenia. Są to liczby bardzo podobne do liczb zmiennoprzecinkowych. Jednak nie mają stałej precyzji dwójkowej, jak zwykłe liczby zmiennoprzecinkowe, ale precyzja jest ograniczana w konkretnym obliczeniu, np. dzieleniu z modulo. Ponieważ są to binarnie liczby zmiennoprzecinkowe, to podlegają podobnym niedokładnościom obliczeń części ułamkowej, jak zwykłe liczby zmiennoprzecinkowe, których wartości nie da się przedstawić w postaci binarnej w ogóle lub w określonej precyzji.

Duża liczba jakby zmiennoprzecinkowa jest przechowywana w następującej strukturze danych i przekazywana jako wskaźnik do niej:

struct E_math_bignum_Z_num
{ N *digits;
  N digits_n;
  S exponent;
};

Postać liczby przechowywana w tej strukturze jest zawsze znormalizowana, więc można uprościć na przykład testy wartości liczb, gdy struktura zawiera tylko jedną cyfrę N, a “exponent” jest nieujemny, do porównywania zerowego elementu tablicy digits, jak w przykładach:

struct E_math_bignum_Z_num *num;
J_assert( num->digits_n == 1 );
if( !num->digits[0] ) // Liczba równa zero.
...
if( num->digits[0] > 10 ) // Liczba większa od 10 (i jednocześnie mniejsza lub równa maksymalnej wartości N).
...

Wtedy nie trzeba używać procedur obliczeń na dużych liczbach jakby zmiennoprzecinkowych.

Tworzenie i wyrzucanie

Dużą liczbę jakby zmiennoprzecinkową można utworzyć i zainicjować wartością 0 następującą procedurą:

struct E_math_bignum_Z_num *
E_math_bignum_M( void );

Natomiast są do dyspozycji procedury, które kopiują wartość lub przenoszą liczbę do nowej zmiennej:

struct E_math_bignum_Z_num *
E_math_bignum_M_copy( struct E_math_bignum_Z_num *num_0 );
void
E_math_bignum_M_move( struct E_math_bignum_Z_num *num_0
, struct E_math_bignum_Z_num *num_1
);
void
E_math_bignum_M_move_( struct E_math_bignum_Z_num *num_0
, struct E_math_bignum_Z_num *num_1
);

Procedura “E_math_bignum_M_copy” tworzy nową liczbę i nadaje jej wartość liczby podanej jako argument.

Procedury “E_math_bignum_M_move” i “E_math_bignum_M_move_” służą do przenoszenia liczby do nowej zmiennej. Pierwsza z tych procedur zastępuje liczbę podaną jako pierwszy argument liczbą podaną jako drugi argument, wcześniej wyrzuciwszy tę pierwszą. Natomiast druga procedura robi to samo, tylko nie wyrzuca już przeniesionej wartości liczby podanej jako pierwszy argument.

Więc te dwie procedury można używać w szeregu, by wykorzystać ponownie zmienne wskazujące na struktury dużych liczb, jak w przykładzie:

struct E_math_bignum_Z_num *num_0, *num_1, *num_2;
E_math_bignum_M_move( num_1, num_0 );
E_math_bignum_M_move_( num_0, num_2 );
W( num_2 );

W powyższym przykładzie liczba ze zmiennej “num_0” została przeniesiona do zmiennej “num_1”, wyrzucając wcześniej jej uprzednią wartość. Następnie liczba ze zmiennej “num_2” została przeniesiona do zmiennej “num_0” (z której przeniesiono wcześniej wartość), a po tym struktura na liczbę w zmiennej “num_2” została wyrzucona.

Dużą liczbę jakby zmiennoprzecinkową można wyrzucić następującą procedurą:

void
E_math_bignum_W( struct E_math_bignum_Z_num *num );

Porównywanie

Duże liczby jakby zmiennoprzecinkowe można porównywać procedurą:

S
E_math_bignum_I_compare(
  struct E_math_bignum_Z_num *num_0
, struct E_math_bignum_Z_num *num_1
);

W wyniku podaje ona wartości -2, 0, 2 w zależności od tego, czy pierwsza podana jako pierwszy argument liczba jest mniejsza, równa, większa od liczby podanej jako drugi argument. Jeśli wystąpił błąd, to wynikiem jest wartość “empty” (~0).

Operacje na liczbach

Konwencją jest, że procedura operacji zmienia wartość pierwszej lub też drugiej podanej jako argument liczby w wynik operacji. Natomiast procedury w wyniku podają wartość “empty” (~0) w przypadku niepowodzenia albo wartość 0, gdy operacja została wykonana.

Operacje podstawowe

Dodawanie, odejmowanie i mnożenie wykonuje się następujacymi procedurami:

N
E_math_bignum_I_add(
  struct E_math_bignum_Z_num *num_0
, struct E_math_bignum_Z_num *num_1
);
N
E_math_bignum_I_subtract(
  struct E_math_bignum_Z_num *num_0
, struct E_math_bignum_Z_num *num_1
);
N
E_math_bignum_I_multiply(
  struct E_math_bignum_Z_num *num_0
, struct E_math_bignum_Z_num *num_1
);

Wynikowa liczba zastępuje tę podaną jako pierwszy argument, a operacja jest wykonywana z pełną precyzją.

Dzielenie z modulo wykonuje się następującą procedurą:

N
E_math_bignum_I_divide_modulo_min_prec(
  struct E_math_bignum_Z_num *num_0
, struct E_math_bignum_Z_num *num_1
, N min_prec
);

Wynik dzielenia (iloraz) zastępuje liczbę podaną jako pierwszy argument, a reszta z dzielenia – liczbę podaną jako drugi argument.

Argument min_prec określa minimalną precyzję, w której zostanie obliczony wynik. Jeśli wartość liczby podanej jako pierwszy argument (dzielnej) ma większą precyzję, to wynik zostanie obliczony w precyzji tej liczby.

Jest również zoptymalizowana operacja mnożenia przez 2 procedurą:

N
E_math_bignum_I_multiply_2( struct E_math_bignum_Z_num *num );

Inne operacje

Można również wykonać operację negacji dużej liczby jakby zmiennoprzecinkowej lub obliczyć jej wartość dodatnią:

N
E_math_bignum_I_negate( struct E_math_bignum_Z_num *num );
N
E_math_bignum_I_abs( struct E_math_bignum_Z_num *num );

Operacje złożone

Do tych operacji zaliczają się obliczenie potęgi o wykładniku całkowitym nieujemnym, silni o wykładniku całkowitym nieujemnym, silni o wykładniku będącym dużą liczbą całkowitą nieujemną oraz rozwinięcia liczby π metodą Bailey‐Borwein‐Plouffe.

Konwersja pomiędzy postacią tekstową

Dużą liczbę jakby zmiennoprzecinkową można wczytać z postaci tekstowej procedurą:

struct E_math_bignum_Z_num *
E_math_bignum_I_scan( Pc s );

Format tekstowej postaci liczby może zawierać znak minus na początku, kropkę na początku, w środku lub na końcu liczby oraz dodatni lub ujemny (rozpoczynający się od znaku minus) wykładnik poprzedzony literą “e” na końcu liczby.

Dużą liczbę jakby zmiennoprzecinkową można otrzymać w postaci tekstowej procedurą:

Pc
E_math_bignum_I_print( struct E_math_bignum_Z_num *num );

Przydzielony przez menedżera pamięci wynikowy tekst po użyciu należy wyrzucić.