xref: /dports/lang/seed7/seed7/src/big_rtl.c

/********************************************************************/
/*                                                                  */
/*  big_rtl.c     Functions for the built-in bigInteger support.    */
/*  Copyright (C) 1989 - 2019  Thomas Mertes                        */
/*                                                                  */
/*  This file is part of the Seed7 Runtime Library.                 */
/*                                                                  */
/*  The Seed7 Runtime Library is free software; you can             */
/*  redistribute it and/or modify it under the terms of the GNU     */
/*  Lesser General Public License as published by the Free Software */
/*  Foundation; either version 2.1 of the License, or (at your      */
/*  option) any later version.                                      */
/*                                                                  */
/*  The Seed7 Runtime Library is distributed in the hope that it    */
/*  will be useful, but WITHOUT ANY WARRANTY; without even the      */
/*  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR */
/*  PURPOSE.  See the GNU Lesser General Public License for more    */
/*  details.                                                        */
/*                                                                  */
/*  You should have received a copy of the GNU Lesser General       */
/*  Public License along with this program; if not, write to the    */
/*  Free Software Foundation, Inc., 51 Franklin Street,             */
/*  Fifth Floor, Boston, MA  02110-1301, USA.                       */
/*                                                                  */
/*  Module: Seed7 Runtime Library                                   */
/*  File: seed7/src/big_rtl.c                                       */
/*  Changes: 2005, 2006, 2008 - 2010, 2013 - 2019 Thomas Mertes     */
/*  Content: Functions for the built-in bigInteger support.         */
/*                                                                  */
/********************************************************************/

#define LOG_FUNCTIONS 0
#define VERBOSE_EXCEPTIONS 0

#include "version.h"

#if BIGINT_LIB == BIG_RTL_LIBRARY
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include "limits.h"

#include "common.h"
#include "data_rtl.h"
#include "heaputl.h"
#include "striutl.h"
#include "int_rtl.h"
#include "rtl_err.h"

#undef EXTERN
#define EXTERN
#include "big_drv.h"


#define KARATSUBA_MULT_THRESHOLD 32
#define KARATSUBA_SQUARE_THRESHOLD 32
#define OCTAL_DIGIT_BITS 3


/* Defines to describe a bigdigit:                                  */
/* BIGDIGIT_MASK              All bits in a bigdigit are set.       */
/* BIGDIGIT_SIGN              The highest bit of a bigdigit is set. */
/* POWER_OF_10_IN_BIGDIGIT    The biggest power of 10 which fits    */
/*                            in a bigdigit.                        */
/* DECIMAL_DIGITS_IN_BIGDIGIT The number of zero digits in          */
/*                            POWER_OF_10_IN_BIGDIGIT.              */


#if BIGDIGIT_SIZE == 8

/* typedef uint8Type             bigDigitType; */
typedef int8Type                 signedBigDigitType;
typedef uint16Type               doubleBigDigitType;
typedef int16Type                signedDoubleBigDigitType;
#define digitMostSignificantBit  uint8MostSignificantBit
#define digitLeastSignificantBit uint8LeastSignificantBit
#define BIGDIGIT_MASK                    0xFF
#define BIGDIGIT_SIGN                    0x80
#define BIGDIGIT_SIZE_MASK                0x7
#define BIGDIGIT_LOG2_SIZE                  3
#define POWER_OF_10_IN_BIGDIGIT           100
#define DECIMAL_DIGITS_IN_BIGDIGIT          2
#define POWER_OF_5_IN_BIGDIGIT            125
#define QUINARY_DIGITS_IN_BIGDIGIT          3
#define F_D_DIG(width) F_D8(width)
#define F_U_DIG(width) F_U8(width)
#define F_X_DIG(width) F_X8(width)
#define FMT_D_DIG FMT_D8
#define FMT_U_DIG FMT_U8
#define FMT_X_DIG FMT_X8
#define F_D_DIG2(width) F_D16(width)
#define F_U_DIG2(width) F_U16(width)
#define F_X_DIG2(width) F_X16(width)
#define FMT_D_DIG2 FMT_D16
#define FMT_U_DIG2 FMT_U16
#define FMT_X_DIG2 FMT_X16
static const bigDigitType powerOfRadixInBigdigit[] = {
    /*  2 */ 128, 243,  64, 125, 216,
    /*  7 */  49,  64,  81, 100, 121,
    /* 12 */ 144, 169, 196, 225,  16,
    /* 17 */  17,  18,  19,  20,  21,
    /* 22 */  22,  23,  24,  25,  26,
    /* 27 */  27,  28,  29,  30,  31,
    /* 32 */  32,  33,  34,  35,  36
  };
static const uint8Type radixDigitsInBigdigit[] = {
    /*  2 */  7,  5,  3,  3,  3,  2,  2,  2,  2,  2,
    /* 12 */  2,  2,  2,  2,  1,  1,  1,  1,  1,  1,
    /* 22 */  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
    /* 32 */  1,  1,  1,  1,  1
  };

#elif BIGDIGIT_SIZE == 16

/* typedef uint16Type            bigDigitType; */
typedef int16Type                signedBigDigitType;
typedef uint32Type               doubleBigDigitType;
typedef int32Type                signedDoubleBigDigitType;
#define digitMostSignificantBit  uint16MostSignificantBit
#define digitLeastSignificantBit uint16LeastSignificantBit
#define BIGDIGIT_MASK                  0xFFFF
#define BIGDIGIT_SIGN                  0x8000
#define BIGDIGIT_SIZE_MASK                0xF
#define BIGDIGIT_LOG2_SIZE                  4
#define POWER_OF_10_IN_BIGDIGIT         10000
#define DECIMAL_DIGITS_IN_BIGDIGIT          4
#define POWER_OF_5_IN_BIGDIGIT          15625
#define QUINARY_DIGITS_IN_BIGDIGIT          6
#define F_D_DIG(width) F_D16(width)
#define F_U_DIG(width) F_U16(width)
#define F_X_DIG(width) F_X16(width)
#define FMT_D_DIG FMT_D16
#define FMT_U_DIG FMT_U16
#define FMT_X_DIG FMT_X16
#define F_D_DIG2(width) F_D32(width)
#define F_U_DIG2(width) F_U32(width)
#define F_X_DIG2(width) F_X32(width)
#define FMT_D_DIG2 FMT_D32
#define FMT_U_DIG2 FMT_U32
#define FMT_X_DIG2 FMT_X32
static const bigDigitType powerOfRadixInBigdigit[] = {
    /*  2 */ 32768, 59049, 16384, 15625, 46656,
    /*  7 */ 16807, 32768, 59049, 10000, 14641,
    /* 12 */ 20736, 28561, 38416, 50625,  4096,
    /* 17 */  4913,  5832,  6859,  8000,  9261,
    /* 22 */ 10648, 12167, 13824, 15625, 17576,
    /* 27 */ 19683, 21952, 24389, 27000, 29791,
    /* 32 */ 32768, 35937, 39304, 42875, 46656
  };
static const uint8Type radixDigitsInBigdigit[] = {
    /*  2 */ 15, 10,  7,  6,  6,  5,  5,  5,  4,  4,
    /* 12 */  4,  4,  4,  4,  3,  3,  3,  3,  3,  3,
    /* 22 */  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
    /* 32 */  3,  3,  3,  3,  3
  };

#elif BIGDIGIT_SIZE == 32

/* typedef uint32Type            bigDigitType; */
typedef int32Type                signedBigDigitType;
typedef uint64Type               doubleBigDigitType;
typedef int64Type                signedDoubleBigDigitType;
#define digitMostSignificantBit  uint32MostSignificantBit
#define digitLeastSignificantBit uint32LeastSignificantBit
#define BIGDIGIT_MASK              0xFFFFFFFF
#define BIGDIGIT_SIGN              0x80000000
#define BIGDIGIT_SIZE_MASK               0x1F
#define BIGDIGIT_LOG2_SIZE                  5
#define POWER_OF_10_IN_BIGDIGIT    1000000000
#define DECIMAL_DIGITS_IN_BIGDIGIT          9
#define POWER_OF_5_IN_BIGDIGIT     1220703125
#define QUINARY_DIGITS_IN_BIGDIGIT         13
#define F_D_DIG(width) F_D32(width)
#define F_U_DIG(width) F_U32(width)
#define F_X_DIG(width) F_X32(width)
#define FMT_D_DIG FMT_D32
#define FMT_U_DIG FMT_U32
#define FMT_X_DIG FMT_X32
#define F_D_DIG2(width) F_D64(width)
#define F_U_DIG2(width) F_U64(width)
#define F_X_DIG2(width) F_X64(width)
#define FMT_D_DIG2 FMT_D64
#define FMT_U_DIG2 FMT_U64
#define FMT_X_DIG2 FMT_X64
static const bigDigitType powerOfRadixInBigdigit[] = {
    /*  2 */ 2147483648u, 3486784401u, 1073741824u, 1220703125u, 2176782336u,
    /*  7 */ 1977326743u, 1073741824u, 3486784401u, 1000000000u, 2357947691u,
    /* 12 */  429981696u,  815730721u, 1475789056u, 2562890625u,  268435456u,
    /* 17 */  410338673u,  612220032u,  893871739u, 1280000000u, 1801088541u,
    /* 22 */ 2494357888u, 3404825447u,  191102976u,  244140625u,  308915776u,
    /* 27 */  387420489u,  481890304u,  594823321u,  729000000u,  887503681u,
    /* 32 */ 1073741824u, 1291467969u, 1544804416u, 1838265625u, 2176782336u
  };
static const uint8Type radixDigitsInBigdigit[] = {
    /*  2 */ 31, 20, 15, 13, 12, 11, 10, 10,  9,  9,
    /* 12 */  8,  8,  8,  8,  7,  7,  7,  7,  7,  7,
    /* 22 */  7,  7,  6,  6,  6,  6,  6,  6,  6,  6,
    /* 32 */  6,  6,  6,  6,  6
  };

#endif


bigIntType *conversionDivisorCache[] = {
    /*  0 */ NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    /* 10 */ NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    /* 20 */ NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    /* 30 */ NULL, NULL, NULL, NULL, NULL, NULL, NULL
  };

unsigned int conversionDivisorCacheSize[] = {
    /*  0 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    /* 30 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  };


#define IS_NEGATIVE(digit) (((digit) & BIGDIGIT_SIGN) != 0)

static const unsigned int digit_value[] = {
     0,  1,  2,  3,  4,  5,  6,  7,  8,  9,              /* Digits 0 - 9   */
    36, 36, 36, 36, 36, 36, 36,                          /* Illegal digits */
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,  /* Digits A - M */
    23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,  /* Digits N - Z */
    36, 36, 36, 36, 36, 36,                              /* Illegal digits */
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,  /* Digits a - m */
    23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35   /* Digits n - z */
  };


#if DO_HEAP_STATISTIC
const size_t sizeof_bigDigitType = sizeof(bigDigitType);
const size_t sizeof_bigIntRecord = sizeof(bigIntRecord);
#endif


#define SIZ_RTLBIG(len)  ((sizeof(bigIntRecord) - sizeof(bigDigitType)) + \
                         (len) * sizeof(bigDigitType))
#define MAX_BIG_LEN      ((MAX_MEMSIZETYPE - sizeof(bigIntRecord) + \
                         sizeof(bigDigitType)) / sizeof(bigDigitType))

#if WITH_BIGINT_CAPACITY
#define HEAP_ALLOC_BIG(var,len)  (ALLOC_HEAP(var, bigIntType, SIZ_RTLBIG(len))? \
                                 ((var)->capacity = len, CNT(CNT1_BIG(len, SIZ_RTLBIG(len))) TRUE): \
                                 FALSE)
#define HEAP_FREE_BIG(var,len)   (CNT(CNT2_BIG(len, SIZ_RTLBIG(len))) \
                                 FREE_HEAP(var, SIZ_RTLBIG(len)))

#define HEAP_REALLOC_BIG(v1,v2,l1,l2) if((v1=REALLOC_HEAP(v2, bigIntType, SIZ_RTLBIG(l2)))!=NULL) \
                                      (v1)->capacity=l2;
#else
#define HEAP_ALLOC_BIG(var,len)  (ALLOC_HEAP(var, bigIntType, SIZ_RTLBIG(len))? \
                                 CNT(CNT1_BIG(len, SIZ_RTLBIG(len))) TRUE:FALSE)
#define HEAP_FREE_BIG(var,len)   (CNT(CNT2_BIG(len, SIZ_RTLBIG(len))) \
                                 FREE_HEAP(var, SIZ_RTLBIG(len)))

#define HEAP_REALLOC_BIG(v1,v2,l1,l2) v1=REALLOC_HEAP(v2, bigIntType, SIZ_RTLBIG(l2));
#endif
#define COUNT3_BIG(len1,len2)    CNT3(CNT2_BIG(len1, SIZ_RTLBIG(len1)), \
                                 CNT1_BIG(len2, SIZ_RTLBIG(len2)))

#if WITH_BIGINT_FREELIST
#if WITH_BIGINT_CAPACITY

#define BIG_FREELIST_ARRAY_SIZE 32

static freeListElemType flist[BIG_FREELIST_ARRAY_SIZE] = {
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL};
static unsigned int flist_allowed[BIG_FREELIST_ARRAY_SIZE] = {
    0, 100, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
    20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20};

#define POP_BIG_OK(len)    (len) < BIG_FREELIST_ARRAY_SIZE && flist[len] != NULL
#define PUSH_BIG_OK(var)   (var)->capacity < BIG_FREELIST_ARRAY_SIZE && \
                           flist_allowed[(var)->capacity] > 0

#define POP_BIG(var,len)   (var = (bigIntType) flist[len], flist[len] = flist[len]->next, \
                           flist_allowed[len]++, TRUE)
#define PUSH_BIG(var,len)  {((freeListElemType) var)->next = flist[len]; \
                           flist[len] = (freeListElemType) var; flist_allowed[len]--; }

#define ALLOC_BIG_SIZE_OK(var,len)    (POP_BIG_OK(len) ? POP_BIG(var, len) : \
                                      HEAP_ALLOC_BIG(var, len))
#define ALLOC_BIG_CHECK_SIZE(var,len) (POP_BIG_OK(len) ? POP_BIG(var, len) : \
                                      ((len)<=MAX_BIG_LEN?HEAP_ALLOC_BIG(var, len): \
                                      (var=NULL, FALSE)))
#define FREE_BIG(var,len)  if (PUSH_BIG_OK(var)) PUSH_BIG(var, (var)->capacity) else \
                           HEAP_FREE_BIG(var, (var)->capacity);

#else

static freeListElemType flist = NULL;
static unsigned int flist_allowed = 100;

#define POP_BIG_OK(len)    (len) == 1 && flist != NULL
#define PUSH_BIG_OK(len)   (len) == 1 && flist_allowed > 0

#define POP_BIG(var)       (var = (bigIntType) flist, flist = flist->next, flist_allowed++, TRUE)
#define PUSH_BIG(var)      {((freeListElemType) var)->next = flist; \
                           flist = (freeListElemType) var; flist_allowed--; }

#define ALLOC_BIG_SIZE_OK(var,len)    (POP_BIG_OK(len) ? POP_BIG(var) : HEAP_ALLOC_BIG(var, len))
#define ALLOC_BIG_CHECK_SIZE(var,len) (POP_BIG_OK(len) ? POP_BIG(var) : \
                                      ((len) <= MAX_BIG_LEN?HEAP_ALLOC_BIG(var, len): \
                                      (var=NULL, FALSE)))
#define FREE_BIG(var,len)  if (PUSH_BIG_OK(len)) PUSH_BIG(var) else HEAP_FREE_BIG(var, len);

#endif
#else

#define ALLOC_BIG_SIZE_OK(var,len)    HEAP_ALLOC_BIG(var, len)
#define ALLOC_BIG_CHECK_SIZE(var,len) ((len) <= MAX_BIG_LEN?HEAP_ALLOC_BIG(var, len): \
                                      (var=NULL, FALSE))
#define FREE_BIG(var,len)             HEAP_FREE_BIG(var, len)

#endif

#define ALLOC_BIG(var,len)                  ALLOC_BIG_CHECK_SIZE(var, len)
#define REALLOC_BIG_SIZE_OK(v1,v2,l1,l2)    HEAP_REALLOC_BIG(v1,v2,l1,l2)
#define REALLOC_BIG_CHECK_SIZE(v1,v2,l1,l2) if((l2) <= MAX_BIG_LEN) \
                                            {HEAP_REALLOC_BIG(v1,v2,l1,l2)}else v1=NULL;


void bigAddAssign (bigIntType *const big_variable, const const_bigIntType delta);
intType bigLowestSetBit (const const_bigIntType big1);
void bigLShiftAssign (bigIntType *const big_variable, intType lshift);
bigIntType bigRem (const const_bigIntType dividend, const const_bigIntType divisor);
bigIntType bigRShift (const const_bigIntType big1, const intType rshift);
void bigRShiftAssign (bigIntType *const big_variable, intType rshift);
bigIntType bigSbtr (const const_bigIntType minuend, const const_bigIntType subtrahend);
void bigSbtrAssign (bigIntType *const big_variable, const const_bigIntType big2);
striType bigStr (const const_bigIntType big1);



/**
 *  Setup bigInteger computations.
 *  This function must be called before doing any bigInteger computations.
 */
void setupBig (void)

  { /* setupBig */
  } /* setupBig */



cstriType bigHexCStri (const const_bigIntType big1)

  {
    /* Length of the hex prefix (16#): */
    const memSizeType hexPrefixLen = STRLEN("16#");
    /* Number of hex digits in a byte: */
    const memSizeType hexDigitsInByte = 2;
    memSizeType pos;
    memSizeType digitPos;
    memSizeType len;
    const_cstriType stri_ptr;
    cstriType buffer;
    cstriType result;

  /* bigHexCStri */
    if (likely(big1 != NULL && big1->size > 0)) {
      if (unlikely(big1->size > (MAX_CSTRI_LEN - hexPrefixLen) /
                                hexDigitsInByte / (BIGDIGIT_SIZE >> 3) ||
                   !ALLOC_CSTRI(result, big1->size * (BIGDIGIT_SIZE >> 3) *
                                hexDigitsInByte + hexPrefixLen))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        buffer = result;
        memcpy(buffer, "16#", hexPrefixLen);
        buffer += hexPrefixLen;
        pos = big1->size - 1;
#if BIGDIGIT_SIZE == 8
        sprintf(buffer, F_X_DIG(02), big1->bigdigits[pos]);
#elif BIGDIGIT_SIZE == 16
        sprintf(buffer, F_X_DIG(04), big1->bigdigits[pos]);
#elif BIGDIGIT_SIZE == 32
        sprintf(buffer, F_X_DIG(08), big1->bigdigits[pos]);
#endif
        digitPos = 0;
        if (IS_NEGATIVE(big1->bigdigits[pos])) {
          while (digitPos < BIGDIGIT_SIZE >> 2 &&
                 memcmp(&buffer[digitPos], "ff", 2) == 0 &&
                 ((buffer[digitPos + 2] >= '8' && buffer[digitPos + 2] <= '9') ||
                  (buffer[digitPos + 2] >= 'a' && buffer[digitPos + 2] <= 'f'))) {
            digitPos += 2;
          } /* while */
        } else {
          while (digitPos < BIGDIGIT_SIZE >> 2 &&
                 memcmp(&buffer[digitPos], "00", 2) == 0 &&
                 buffer[digitPos + 2] >= '0' && buffer[digitPos + 2] <= '7') {
            digitPos += 2;
          } /* while */
        } /* if */
        len = (BIGDIGIT_SIZE >> 2) - digitPos;
        memmove(buffer, &buffer[digitPos], len + 1);
        buffer += len;
        while (pos > 0) {
          pos--;
#if BIGDIGIT_SIZE == 8
          sprintf(buffer, F_X_DIG(02), big1->bigdigits[pos]);
#elif BIGDIGIT_SIZE == 16
          sprintf(buffer, F_X_DIG(04), big1->bigdigits[pos]);
#elif BIGDIGIT_SIZE == 32
          sprintf(buffer, F_X_DIG(08), big1->bigdigits[pos]);
#endif
          buffer += (BIGDIGIT_SIZE >> 3) * hexDigitsInByte;
        } /* while */
      } /* if */
    } else {
      if (big1 == NULL) {
        stri_ptr = " *NULL_BIGINT* ";
        len = STRLEN(" *NULL_BIGINT* ");
      } else {
        stri_ptr = " *ZERO_SIZE_BIGINT* ";
        len = STRLEN(" *ZERO_SIZE_BIGINT* ");
      } /* if */
      if (unlikely(!ALLOC_CSTRI(result, len))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        strcpy(result, stri_ptr);
      } /* if */
    } /* if */
    return result;
  } /* bigHexCStri */



/**
 *  Remove leading zero (or BIGDIGIT_MASK) digits from a signed big integer.
 *  @return the normalized big integer.
 */
static bigIntType normalize (bigIntType big1)

  {
    memSizeType pos;
    bigDigitType digit;

  /* normalize */
    pos = big1->size;
    if (pos >= 2) {
      pos--;
      digit = big1->bigdigits[pos];
      if (digit == BIGDIGIT_MASK) {
        do {
          pos--;
          digit = big1->bigdigits[pos];
        } while (pos > 0 && digit == BIGDIGIT_MASK);
        if (!IS_NEGATIVE(digit)) {
          pos++;
        } /* if */
      } else if (digit == 0) {
        do {
          pos--;
          digit = big1->bigdigits[pos];
        } while (pos > 0 && digit == 0);
        if (IS_NEGATIVE(digit)) {
          pos++;
        } /* if */
      } /* if */
      pos++;
#ifdef NORMALIZE_DOES_RESIZE
      if (big1->size != pos) {
        bigIntType resized_big1;

        REALLOC_BIG_SIZE_OK(resized_big1, big1, big1->size, pos);
        /* Avoid a MEMORY_ERROR in the strange case   */
        /* if a 'realloc' which shrinks memory fails. */
        if (likely(resized_big1 != NULL)) {
          big1 = resized_big1;
        } /* if */
        COUNT3_BIG(big1->size, pos);
        big1->size = pos;
      } /* if */
#else
      big1->size = pos;
#endif
    } /* if */
    return big1;
  } /* normalize */



static void negate_positive_big (const bigIntType big1)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 1;

  /* negate_positive_big */
    do {
      carry += ~big1->bigdigits[pos] & BIGDIGIT_MASK;
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big1->size);
  } /* negate_positive_big */



static void positive_copy_of_negative_big (const bigIntType dest,
    const const_bigIntType big1)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 1;

  /* positive_copy_of_negative_big */
    do {
      carry += ~big1->bigdigits[pos] & BIGDIGIT_MASK;
      dest->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big1->size);
    if (unlikely(IS_NEGATIVE(dest->bigdigits[pos - 1]))) {
      dest->bigdigits[pos] = 0;
      pos++;
    } /* if */
    dest->size = pos;
  } /* positive_copy_of_negative_big */



static bigIntType alloc_positive_copy_of_negative_big (const const_bigIntType big1)

  {
    memSizeType pos;
    doubleBigDigitType carry = 1;
    bigIntType result;

  /* alloc_positive_copy_of_negative_big */
    if (likely(ALLOC_BIG_SIZE_OK(result, big1->size))) {
      pos = 0;
      do {
        carry += ~big1->bigdigits[pos] & BIGDIGIT_MASK;
        result->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos++;
      } while (pos < big1->size);
      result->size = pos;
    } /* if */
    return result;
  } /* alloc_positive_copy_of_negative_big */



/**
 *  Multiplies big1 by POWER_OF_10_IN_BIGDIGIT and adds carry to the product.
 *  The resulting sum is assigned to big1. This function works
 *  for unsigned big integers. It is assumed that big1 contains
 *  enough memory.
 */
static inline void uBigMultByPowerOf10AndAdd (const bigIntType big1, doubleBigDigitType carry)

  {
    memSizeType pos = 0;

  /* uBigMultByPowerOf10AndAdd */
    do {
      carry += (doubleBigDigitType) big1->bigdigits[pos] * POWER_OF_10_IN_BIGDIGIT;
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big1->size);
    if (carry != 0) {
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      big1->size++;
    } /* if */
  } /* uBigMultByPowerOf10AndAdd */



/**
 *  Multiplies big1 by a factor and adds carry to the product.
 *  The resulting sum is assigned to big1. This function works
 *  for unsigned big integers. It is assumed that big1 contains
 *  enough memory.
 */
static inline void uBigMultiplyAndAdd (const bigIntType big1, bigDigitType factor,
    doubleBigDigitType carry)

  {
    memSizeType pos = 0;

  /* uBigMultiplyAndAdd */
    do {
      carry += (doubleBigDigitType) big1->bigdigits[pos] * factor;
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big1->size);
    if (carry != 0) {
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      big1->size++;
    } /* if */
  } /* uBigMultiplyAndAdd */



/**
 *  Divides the unsigned big integer big1 by POWER_OF_10_IN_BIGDIGIT.
 *  The quotient is assigned to big1.
 *  @return the remainder of the unsigned big integer division.
 */
static inline bigDigitType uBigDivideByPowerOf10 (const bigIntType big1)

  {
    memSizeType pos;
    doubleBigDigitType carry = 0;
    bigDigitType bigdigit;

  /* uBigDivideByPowerOf10 */
    pos = big1->size;
    do {
      pos--;
      carry <<= BIGDIGIT_SIZE;
      carry += big1->bigdigits[pos];
      bigdigit = (bigDigitType) (carry / POWER_OF_10_IN_BIGDIGIT);
#if POINTER_SIZE <= BIGDIGIT_SIZE
      /* There is probably no machine instruction for division    */
      /* and remainder of doubleBigDigitType values available.    */
      /* To compute the remainder fast the % operator is avoided  */
      /* and the remainder is computed with a multiplication and  */
      /* a subtraction. The overflow in the multiplication can be */
      /* ignored, since the result of the subtraction fits in the */
      /* lower bigdigit of carry. The wrong bits in the higher    */
      /* bigdigit of carry are masked away.                       */
      carry = (carry - bigdigit * POWER_OF_10_IN_BIGDIGIT) & BIGDIGIT_MASK;
#else
      /* There is probably a machine instruction for division     */
      /* and remainder of doubleBigDigitType values available.    */
      /* In the optimal case quotient and remainder can be        */
      /* computed with one instruction.                           */
      carry %= POWER_OF_10_IN_BIGDIGIT;
#endif
      big1->bigdigits[pos] = bigdigit;
    } while (pos > 0);
    return (bigDigitType) (carry);
  } /* uBigDivideByPowerOf10 */



/**
 *  Divides the unsigned big integer big1 by POWER_OF_5_IN_BIGDIGIT.
 *  The quotient is assigned to big1.
 *  @return the remainder of the unsigned big integer division.
 */
static inline void uBigDivideByPowerOf5 (const bigIntType big1)

  {
    memSizeType pos;
    doubleBigDigitType carry = 0;
    bigDigitType bigdigit;

  /* uBigDivideByPowerOf5 */
    pos = big1->size;
    do {
      pos--;
      carry <<= BIGDIGIT_SIZE;
      carry += big1->bigdigits[pos];
      bigdigit = (bigDigitType) (carry / POWER_OF_5_IN_BIGDIGIT);
#if POINTER_SIZE <= BIGDIGIT_SIZE
      /* There is probably no machine instruction for division    */
      /* and remainder of doubleBigDigitType values available.    */
      /* To compute the remainder fast the % operator is avoided  */
      /* and the remainder is computed with a multiplication and  */
      /* a subtraction. The overflow in the multiplication can be */
      /* ignored, since the result of the subtraction fits in the */
      /* lower bigdigit of carry. The wrong bits in the higher    */
      /* bigdigit of carry are masked away.                       */
      carry = (carry - bigdigit * POWER_OF_5_IN_BIGDIGIT) & BIGDIGIT_MASK;
#else
      /* There is probably a machine instruction for division     */
      /* and remainder of doubleBigDigitType values available.    */
      /* In the optimal case quotient and remainder can be        */
      /* computed with one instruction.                           */
      carry %= POWER_OF_5_IN_BIGDIGIT;
#endif
      big1->bigdigits[pos] = bigdigit;
    } while (pos > 0);
  } /* uBigDivideByPowerOf5 */



/**
 *  Divides the unsigned big integer big1 by divisor_digit.
 *  The quotient is assigned to big1.
 *  @return the remainder of the unsigned big integer division.
 */
static inline bigDigitType uBigDivideByDigit (const bigIntType big1,
    const bigDigitType divisor_digit)

  {
    memSizeType pos;
    doubleBigDigitType carry = 0;
    bigDigitType bigdigit;

  /* uBigDivideByDigit */
    pos = big1->size;
    do {
      pos--;
      carry <<= BIGDIGIT_SIZE;
      carry += big1->bigdigits[pos];
      bigdigit = (bigDigitType) (carry / divisor_digit);
#if POINTER_SIZE <= BIGDIGIT_SIZE
      /* There is probably no machine instruction for division    */
      /* and remainder of doubleBigDigitType values available.    */
      /* To compute the remainder fast the % operator is avoided  */
      /* and the remainder is computed with a multiplication and  */
      /* a subtraction. The overflow in the multiplication can be */
      /* ignored, since the result of the subtraction fits in the */
      /* lower bigdigit of carry. The wrong bits in the higher    */
      /* bigdigit of carry are masked away.                       */
      carry = (carry - bigdigit * divisor_digit) & BIGDIGIT_MASK;
#else
      /* There is probably a machine instruction for division     */
      /* and remainder of doubleBigDigitType values available.    */
      /* In the optimal case quotient and remainder can be        */
      /* computed with one instruction.                           */
      carry %= divisor_digit;
#endif
      big1->bigdigits[pos] = bigdigit;
    } while (pos > 0);
    return (bigDigitType) (carry);
  } /* uBigDivideByDigit */



/**
 *  Convert a numeric string, with a specified radix, to a 'bigInteger'.
 *  The numeric string must contain the representation of an integer
 *  in the specified radix. It consists of an optional + or - sign,
 *  followed by a sequence of digits in the specified radix. Digit values
 *  from 10 upward can be encoded with upper or lower case letters.
 *  E.g.: 10 can be encoded with A or a, 11 with B or b, etc. Other
 *  characters as well as leading or trailing whitespace characters
 *  are not allowed. The radix of the conversion is a power of two and
 *  it is specified indirectly with the parameter shift.
 *  @param stri Numeric string with integer in the specified radix.
 *  @param shift Logarithm (log2) of the specified radix.
 *  @return the 'bigInteger' result of the conversion.
 *  @exception RANGE_ERROR If the string does not contain an integer
 *             literal with the specified base.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
static bigIntType bigParseBasedPow2 (const const_striType stri, unsigned int shift)

  {
    memSizeType mostSignificantDigitPos = 0;
    boolType negative;
    memSizeType bits_necessary;
    boolType okay;
    memSizeType charPos;
    strElemType digit;
    unsigned int base;
    unsigned int digitval;
    memSizeType bigDigitPos;
    doubleBigDigitType bigDigit;
    unsigned int bigDigitShift;
    memSizeType result_size;
    bigIntType result;

  /* bigParseBasedPow2 */
    logFunction(printf("bigParseBasedPow2(\"%s\", %u)\n",
                       striAsUnquotedCStri(stri), shift););
    if (likely(stri->size != 0)) {
      if (stri->mem[0] == ((strElemType) '-')) {
        negative = TRUE;
        mostSignificantDigitPos++;
      } else {
        if (stri->mem[0] == ((strElemType) '+')) {
          mostSignificantDigitPos++;
        } /* if */
        negative = FALSE;
      } /* if */
    } /* if */
    /* printf("mostSignificantDigitPos: " FMT_U_MEM "\n", mostSignificantDigitPos); */
    if (unlikely(mostSignificantDigitPos >= stri->size)) {
      logError(printf("bigParseBasedPow2(\"%s\", %u): "
                      "Digit missing.\n",
                      striAsUnquotedCStri(stri), shift););
      raise_error(RANGE_ERROR);
      result = NULL;
    } else if (unlikely(stri->size - mostSignificantDigitPos >
                        MAX_MEMSIZETYPE / (memSizeType) shift)) {
      raise_error(MEMORY_ERROR);
      result = NULL;
    } else {
      base = (unsigned int) 1 << shift;
      /* Compute the number of bits necessary: */
      bits_necessary = (stri->size - mostSignificantDigitPos) * (memSizeType) shift;
      /* printf("bits_necessary: " FMT_U_MEM "\n", bits_necessary); */
      /* Compute the number of bigDigits: */
      result_size = (bits_necessary - 1) / BIGDIGIT_SIZE + 1;
      if ((bits_necessary & BIGDIGIT_SIZE_MASK) == 0) {
        digit = stri->mem[mostSignificantDigitPos];
        if (digit >= '0' && digit <= 'z') {
          digitval = digit_value[digit - (strElemType) '0'];
          if (digitval < base &&
              (digitval >> (shift - 1) & 1) == 1) {
            /* The highest bit of the most significant digit is set. */
            result_size++;
          } /* if */
        } /* if */
      } /* if */
      /* printf("result_size: " FMT_U_MEM "\n", result_size); */
      if (unlikely(!ALLOC_BIG(result, result_size))) {
        raise_error(MEMORY_ERROR);
      } else {
        okay = TRUE;
        bigDigit = 0;
        bigDigitPos = 0;
        bigDigitShift = 0;
        for (charPos = stri->size; charPos > mostSignificantDigitPos && okay; charPos--) {
          digit = stri->mem[charPos - 1];
          if (likely(digit >= '0' && digit <= 'z')) {
            digitval = digit_value[digit - (strElemType) '0'];
            if (likely(digitval < base)) {
              bigDigit |= (doubleBigDigitType) digitval << bigDigitShift;
            } else {
              okay = FALSE;
            } /* if */
          } else {
            okay = FALSE;
          } /* if */
          bigDigitShift += shift;
          if (bigDigitShift >= BIGDIGIT_SIZE) {
            /* printf("result->bigdigits[" FMT_U_MEM "] = " F_X_DIG(08) "\n",
               bigDigitPos, (bigDigitType) (bigDigit & BIGDIGIT_MASK)); */
            result->bigdigits[bigDigitPos] = (bigDigitType) (bigDigit & BIGDIGIT_MASK);
            bigDigitPos++;
            bigDigit >>= BIGDIGIT_SIZE;
            bigDigitShift -= BIGDIGIT_SIZE;
          } /* if */
        } /* for */
        if (unlikely(!okay)) {
          FREE_BIG(result, result_size);
          logError(printf("bigParseBasedPow2(\"%s\", %u): "
                          "Illegal digit.\n",
                          striAsUnquotedCStri(stri), shift););
          raise_error(RANGE_ERROR);
          result = NULL;
        } else {
          result->size = result_size;
          while (bigDigitPos < result_size) {
            /* printf("result->bigdigits[" FMT_U_MEM "] = " F_X_DIG(08) "\n",
               bigDigitPos, (bigDigitType) (bigDigit & BIGDIGIT_MASK)); */
            result->bigdigits[bigDigitPos] = (bigDigitType) (bigDigit & BIGDIGIT_MASK);
            bigDigitPos++;
            bigDigit >>= BIGDIGIT_SIZE;
          } /* while */
          if (negative) {
            negate_positive_big(result);
          } /* if */
          result = normalize(result);
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigParseBasedPow2 --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigParseBasedPow2 */



/**
 *  Convert a numeric string, with a specified radix, to a 'bigInteger'.
 *  The numeric string must contain the representation of an integer
 *  in the specified radix. It consists of an optional + or - sign,
 *  followed by a sequence of digits in the specified radix. Digit values
 *  from 10 upward can be encoded with upper or lower case letters.
 *  E.g.: 10 can be encoded with A or a, 11 with B or b, etc. Other
 *  characters as well as leading or trailing whitespace characters
 *  are not allowed.
 *  @param stri Numeric string with integer in the specified radix.
 *  @param base Radix of the integer in the 'stri' parameter.
 *  @return the 'bigInteger' result of the conversion.
 *  @exception RANGE_ERROR If base < 2 or base > 36 holds or
 *             the string does not contain an integer
 *             literal with the specified base.
 *  @exception MEMORY_ERROR  Not enough memory to represent the result.
 */
static bigIntType bigParseBased2To36 (const const_striType stri, unsigned int base)

  {
    boolType okay;
    boolType negative;
    memSizeType position = 0;
    uint8Type based_digit_size;
    uint8Type based_digits_in_bigdigit;
    bigDigitType power_of_base_in_bigdigit;
    memSizeType limit;
    strElemType digit;
    unsigned int digitval;
    bigDigitType bigDigit;
    memSizeType result_size;
    bigIntType result;

  /* bigParseBased2To36 */
    logFunction(printf("bigParseBased2To36(\"%s\", %u)\n",
                       striAsUnquotedCStri(stri), base););
    if (likely(stri->size != 0)) {
      if (stri->mem[0] == ((strElemType) '-')) {
        negative = TRUE;
        position++;
      } else {
        if (stri->mem[0] == ((strElemType) '+')) {
          position++;
        } /* if */
        negative = FALSE;
      } /* if */
    } /* if */
    /* printf("position: " FMT_U_MEM "\n", position); */
    if (unlikely(position >= stri->size)) {
      logError(printf("bigParseBased2To36(\"%s\", %u): "
                      "Digit missing.\n",
                      striAsUnquotedCStri(stri), base););
      raise_error(RANGE_ERROR);
      result = NULL;
    } else if (unlikely(stri->size > MAX_MEMSIZETYPE / 6)) {
      raise_error(MEMORY_ERROR);
      result = NULL;
    } else {
      based_digit_size = (uint8Type) (uint8MostSignificantBit((uint8Type) (base - 1)) + 1);
      /* Estimate the number of bits necessary: */
      result_size = stri->size * (memSizeType) based_digit_size;
      /* Compute the number of bigDigits: */
      result_size = result_size / BIGDIGIT_SIZE + 1;
      if (unlikely(!ALLOC_BIG(result, result_size))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = 1;
        result->bigdigits[0] = 0;
        okay = TRUE;
        based_digits_in_bigdigit = radixDigitsInBigdigit[base - 2];
        power_of_base_in_bigdigit = powerOfRadixInBigdigit[base - 2];
        limit = (stri->size - position - 1) % based_digits_in_bigdigit + position + 1;
        do {
          bigDigit = 0;
          while (position < limit && okay) {
            digit = stri->mem[position];
            if (likely(digit >= '0' && digit <= 'z')) {
              digitval = digit_value[digit - (strElemType) '0'];
              if (likely(digitval < base)) {
                bigDigit = (bigDigitType) base * bigDigit + digitval;
              } else {
                okay = FALSE;
              } /* if */
            } else {
              okay = FALSE;
            } /* if */
            position++;
          } /* while */
          uBigMultiplyAndAdd(result, power_of_base_in_bigdigit, (doubleBigDigitType) bigDigit);
          limit += based_digits_in_bigdigit;
        } while (position < stri->size && okay);
        if (likely(okay)) {
          memset(&result->bigdigits[result->size], 0,
                 (size_t) (result_size - result->size) * sizeof(bigDigitType));
          result->size = result_size;
          if (negative) {
            negate_positive_big(result);
          } /* if */
          result = normalize(result);
        } else {
          FREE_BIG(result, result_size);
          logError(printf("bigParseBased2To36(\"%s\", %u): "
                          "Illegal digit.\n",
                          striAsUnquotedCStri(stri), base););
          raise_error(RANGE_ERROR);
          result = NULL;
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigParseBased2To36 --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigParseBased2To36 */



/**
 *  Computes base ** (2 ** exponent) to be used as conversion divisor.
 *  The function uses a cache to avoid a recomputation.
 *  The result is used by binaryToStri and binaryRadix2To36 as
 *  divisor. The functions binaryToStri and binaryRadix2To36 use
 *  the binary algorithm to convert a bigInteger to a string.
 *  @return base ** (2 ** exponent).
 */
static bigIntType getConversionDivisor (unsigned int base, unsigned int exponent)

  {
    bigIntType *divisorCache;
    unsigned int size;
    unsigned int pos;
    bigIntType divisor;

  /* getConversionDivisor */
    logFunction(printf("getConversionDivisor(%u, %u)\n", base, exponent););
    divisorCache = conversionDivisorCache[base];
    size = conversionDivisorCacheSize[base];
    if (exponent < size) {
      divisor = divisorCache[exponent];
    } else {
      divisorCache = (bigIntType *) realloc(divisorCache,
          (exponent + 1) * sizeof(bigIntType));
      if (unlikely(divisorCache == NULL)) {
        raise_error(MEMORY_ERROR);
        divisor = NULL;
      } else {
        if (size == 0) {
          divisorCache[0] = bigFromUInt32(base);
          size = 1;
        } /* if */
        for (pos = size; pos <= exponent; ++pos) {
          divisorCache[pos] = bigSquare(divisorCache[pos - 1]);
        } /* for */
        conversionDivisorCache[base] = divisorCache;
        conversionDivisorCacheSize[base] = exponent + 1;
        divisor = divisorCache[exponent];
      } /* if */
    } /* if */
    logFunction(printf("getConversionDivisor --> %s\n", bigHexCStri(divisor)););
    return divisor;
  } /* getConversionDivisor */



static memSizeType basicToStri (const bigIntType unsignedBig,
    striType buffer, memSizeType pos)

  {
    bigDigitType digit;
    int digit_pos;

  /* basicToStri */
    logFunction(printf("basicToStri(%s, *, " FMT_U_MEM ")\n",
                       bigHexCStri(unsignedBig), pos););
    do {
      digit = uBigDivideByPowerOf10(unsignedBig);
      /* printf("unsignedBig->size=" FMT_U_MEM ", digit=" FMT_U_DIG "\n",
         unsignedBig->size, digit); */
      if (unsignedBig->bigdigits[unsignedBig->size - 1] == 0) {
        unsignedBig->size--;
      } /* if */
      if (unsignedBig->size > 1 || unsignedBig->bigdigits[0] != 0) {
        for (digit_pos = DECIMAL_DIGITS_IN_BIGDIGIT;
            digit_pos != 0; digit_pos--) {
          buffer->mem[pos] = '0' + digit % 10;
          digit /= 10;
          pos--;
        } /* for */
      } else {
        do {
          buffer->mem[pos] = '0' + digit % 10;
          digit /= 10;
          pos--;
        } while (digit != 0);
      } /* if */
    } while (unsignedBig->size > 1 || unsignedBig->bigdigits[0] != 0);
    logFunction(printf("basicToStri --> " FMT_U_MEM "\n", pos););
    return pos;
  } /* basicToStri */



static memSizeType binaryToStri (bigIntType unsignedBig, striType buffer,
    unsigned int exponent, boolType zeroPad, memSizeType pos)

  {
    bigIntType divisor;
    bigIntType quotient;
    bigIntType remainder;
    memSizeType endPos;

  /* binaryToStri */
    logFunction(printf("binaryToStri(%s, *, %u, %d, " FMT_U_MEM ")\n",
                       bigHexCStri(unsignedBig), exponent, zeroPad, pos););
    if (exponent > 8) {
      exponent--;
      divisor = getConversionDivisor(10, exponent);
      if (divisor != NULL) {
        quotient = bigDivRem(unsignedBig, divisor, &remainder);
        if (quotient != NULL) {
          if (zeroPad || (quotient->size > 1 || quotient->bigdigits[0] != 0)) {
            pos = binaryToStri(remainder, buffer, exponent, TRUE, pos);
            pos = binaryToStri(quotient, buffer, exponent, zeroPad, pos);
          } else {
            pos = binaryToStri(remainder, buffer, exponent, FALSE, pos);
          } /* if */
          FREE_BIG(remainder, remainder->size);
          FREE_BIG(quotient, quotient->size);
        } /* if */
      } /* if */
    } else {
      endPos = pos;
      pos = basicToStri(unsignedBig, buffer, pos);
      if (zeroPad) {
        /* printf(FMT_U_MEM " " FMT_U_MEM " " FMT_U_MEM
               " insert " FMT_U_MEM " zero digits.\n",
               pos, endPos, (memSizeType) 1 << exponent,
               pos - (endPos - ((memSizeType) 1 << exponent))); */
        endPos -= (memSizeType) 1 << exponent;
        while (pos > endPos) {
          buffer->mem[pos] = '0';
          pos--;
        } /* while */
      } /* if */
    } /* if */
    logFunction(printf("binaryToStri --> " FMT_U_MEM "\n", pos););
    return pos;
  } /* binaryToStri */



static memSizeType basicRadix2To36 (const bigIntType unsignedBig,
    striType buffer, unsigned int base, const const_ustriType digits,
    memSizeType pos)

  {
    bigDigitType divisor_digit;
    uint8Type digits_in_bigdigit;
    bigDigitType digit;
    int digit_pos;

  /* basicRadix2To36 */
    logFunction(printf("basicRadix2To36(%s, *, %u, *, " FMT_U_MEM ")\n",
                       bigHexCStri(unsignedBig), base, pos););
    divisor_digit = powerOfRadixInBigdigit[base - 2];
    /* printf("divisor_digit: " FMT_U_DIG "\n", divisor_digit); */
    digits_in_bigdigit = radixDigitsInBigdigit[base - 2];
    /* printf("digits_in_bigdigit: %hd\n", digits_in_bigdigit); */
    do {
      digit = uBigDivideByDigit(unsignedBig, divisor_digit);
      /* printf("unsignedBig->size=" FMT_U_MEM ", digit=" FMT_U_DIG "\n",
         unsignedBig->size, digit); */
      if (unsignedBig->bigdigits[unsignedBig->size - 1] == 0) {
        unsignedBig->size--;
      } /* if */
      if (unsignedBig->size > 1 || unsignedBig->bigdigits[0] != 0) {
        for (digit_pos = digits_in_bigdigit;
            digit_pos != 0; digit_pos--) {
          buffer->mem[pos] = (strElemType) (digits[digit % base]);
          digit /= base;
          pos--;
        } /* for */
      } else {
        do {
          buffer->mem[pos] = (strElemType) (digits[digit % base]);
          digit /= base;
          pos--;
        } while (digit != 0);
      } /* if */
    } while (unsignedBig->size > 1 || unsignedBig->bigdigits[0] != 0);
    logFunction(printf("basicRadix2To36 --> " FMT_U_MEM "\n", pos););
    return pos;
  } /* basicRadix2To36 */



static memSizeType binaryRadix2To36 (bigIntType unsignedBig,
    striType buffer, unsigned int base, const const_ustriType digits,
    unsigned int exponent, boolType zeroPad, memSizeType pos)

  {
    bigIntType divisor;
    bigIntType quotient;
    bigIntType remainder;
    memSizeType endPos;

  /* binaryRadix2To36 */
    logFunction(printf("binaryRadix2To36(%s, *, %u, *, %u, %u, "
                       FMT_U_MEM ")\n", bigHexCStri(unsignedBig),
                       base, exponent, zeroPad, pos););
    if (exponent > 8) {
      exponent--;
      divisor = getConversionDivisor(base, exponent);
      if (divisor != NULL) {
        quotient = bigDivRem(unsignedBig, divisor, &remainder);
        if (quotient != NULL) {
          if (zeroPad || (quotient->size > 1 || quotient->bigdigits[0] != 0)) {
            pos = binaryRadix2To36(remainder, buffer, base, digits,
                                  exponent, TRUE, pos);
            pos = binaryRadix2To36(quotient, buffer, base, digits,
                                  exponent, zeroPad, pos);
          } else {
            pos = binaryRadix2To36(remainder, buffer, base, digits,
                                  exponent, FALSE, pos);
          } /* if */
          FREE_BIG(remainder, remainder->size);
          FREE_BIG(quotient, quotient->size);
        } /* if */
      } /* if */
    } else {
      endPos = pos;
      pos = basicRadix2To36(unsignedBig, buffer, base, digits, pos);
      if (zeroPad) {
        /* printf(FMT_U_MEM " " FMT_U_MEM " " FMT_U_MEM
               " insert " FMT_U_MEM " zero digits.\n",
               pos, endPos, (memSizeType) 1 << exponent,
               pos - (endPos - ((memSizeType) 1 << exponent))); */
        endPos -= (memSizeType) 1 << exponent;
        while (pos > endPos) {
          buffer->mem[pos] = '0';
          pos--;
        } /* while */
      } /* if */
    } /* if */
    logFunction(printf("binaryRadix2To36 --> " FMT_U_MEM "\n", pos););
    return pos;
  } /* binaryRadix2To36 */



/**
 *  Convert a big integer number to a string using a radix.
 *  The conversion uses the numeral system with the specified base.
 *  The base is a power of two and it is specified indirectly with
 *  shift and mask. Digit values from 10 upward are encoded with
 *  letters.
 *  @param big1 BigInteger number to be converted.
 *  @param shift Logarithm (log2) of the base (=number of bits in mask).
 *  @param mask Mask to get the bits of a digit (equivalent to base-1).
 *  @param upperCase Decides about the letter case.
 *  @return the string result of the conversion.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
static striType bigRadixPow2 (const const_bigIntType big1, unsigned int shift,
    bigDigitType mask, boolType upperCase)

  {
    const_bigIntType unsigned_big;
    memSizeType unsigned_size;
    doubleBigDigitType unsigned_digit;
    boolType negative;
    unsigned int most_significant;
    unsigned int digit_shift;
    memSizeType digit_index;
    const_ustriType digits;
    memSizeType pos;
    memSizeType result_size;
    striType result;

  /* bigRadixPow2 */
    logFunction(printf("bigRadixPow2(%s, %u, " FMT_X_DIG ", %d)\n",
                       bigHexCStri(big1), shift, mask, upperCase););
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    if (negative) {
      unsigned_big = alloc_positive_copy_of_negative_big(big1);
    } else {
      unsigned_big = big1;
    } /* if */
    if (unlikely(unsigned_big == NULL)) {
      raise_error(MEMORY_ERROR);
      result = NULL;
    } else {
      unsigned_size = unsigned_big->size;
      /* Unsigned_size is reduced to avoid a leading zero digit.        */
      /* Except for the value 0 unsigned_big has no leading zero digit. */
      while (unsigned_size > 1 && unsigned_big->bigdigits[unsigned_size - 1] == 0) {
        unsigned_size--;
      } /* while */
      if (unlikely((MAX_STRI_LEN <= (MAX_MEMSIZETYPE - 1) / shift +
                                    (unsigned int) negative + 1 &&
                   unsigned_size > ((MAX_STRI_LEN - (unsigned int) negative - 1) *
                                shift + 1) / BIGDIGIT_SIZE) ||
                   unsigned_size > MAX_MEMSIZETYPE / BIGDIGIT_SIZE)) {
        if (unsigned_big != big1) {
          FREE_BIG(unsigned_big, unsigned_big->size);
        } /* if */
        raise_error(MEMORY_ERROR);
        result = NULL;
      } else {
        if (unsigned_size == 1 && unsigned_big->bigdigits[0] == 0) {
          /* The size of zero is always 1. */
          result_size = 1;
        } else {
          /* The size of the result is computed by computing */
          /* the number of radix digits plus one optional    */
          /* character for the sign.                         */
          result_size = (unsigned_size * BIGDIGIT_SIZE - 1) / shift + (unsigned int) negative + 1;
          most_significant = (unsigned int)
              digitMostSignificantBit(unsigned_big->bigdigits[unsigned_size - 1]);
          digit_shift = (unsigned int) (BIGDIGIT_SIZE - (unsigned_size * BIGDIGIT_SIZE) % shift);
          if (most_significant < digit_shift) {
            /* Reduce result_size because of leading zero digits. */
            result_size -= (digit_shift - most_significant - 1) / shift;
            if (digit_shift != BIGDIGIT_SIZE) {
              result_size--;
            } /* if */
          } /* if */
        } /* if */
        /* printf("result_size: " FMT_U_MEM "\n", result_size); */
        if (unlikely(!ALLOC_STRI_SIZE_OK(result, result_size))) {
          if (unsigned_big != big1) {
            FREE_BIG(unsigned_big, unsigned_big->size);
          } /* if */
          raise_error(MEMORY_ERROR);
          result = NULL;
        } else {
          digits = digitTable[upperCase];
          pos = result_size;
          unsigned_digit = unsigned_big->bigdigits[0];
          digit_index = 0;
          digit_shift = 0;
          do {
            while (digit_shift <= BIGDIGIT_SIZE - shift && pos > (memSizeType) negative) {
              pos--;
              /* printf("A result->mem[" FMT_U_MEM "] = %c\n", pos,
                  digits[(unsigned_digit >> digit_shift) & mask]); */
              result->mem[pos] = (strElemType) (digits[(unsigned_digit >> digit_shift) & mask]);
              digit_shift += shift;
            } /* while */
            digit_index++;
            if (digit_index < unsigned_size) {
              if (digit_shift == BIGDIGIT_SIZE) {
                unsigned_digit = unsigned_big->bigdigits[digit_index];
                digit_shift = 0;
              } else {
                unsigned_digit >>= digit_shift;
                unsigned_digit |=
                    unsigned_big->bigdigits[digit_index] << (BIGDIGIT_SIZE - digit_shift);
                if (pos > (memSizeType) negative) {
                  pos--;
                  /* printf("B result->mem[" FMT_U_MEM "] = %c\n", pos,
                      digits[unsigned_digit & mask]); */
                  result->mem[pos] = (strElemType) (digits[unsigned_digit & mask]);
                  unsigned_digit = unsigned_big->bigdigits[digit_index];
                  digit_shift += shift - BIGDIGIT_SIZE;
                } /* if */
              } /* if */
            } else if (digit_shift != BIGDIGIT_SIZE && pos > (memSizeType) negative) {
              pos--;
              /* printf("C result->mem[" FMT_U_MEM "] = %c\n", pos,
                  digits[(unsigned_digit >> digit_shift) & mask]); */
              result->mem[pos] = (strElemType) (digits[(unsigned_digit >> digit_shift) & mask]);
            } /* if */
          } while (digit_index < unsigned_size && pos > (memSizeType) negative);
          if (negative) {
            pos--;
            /* printf("result->mem[" FMT_U_MEM "] = -\n", pos); */
            result->mem[pos] = (strElemType) '-';
          } /* if */
          result->size = result_size;
        } /* if */
      } /* if */
      if (unsigned_big != big1) {
        FREE_BIG(unsigned_big, unsigned_big->size);
      } /* if */
    } /* if */
    logFunction(printf("bigRadixPow2 --> \"%s\"\n", striAsUnquotedCStri(result)););
    return result;
  } /* bigRadixPow2 */



/**
 *  Convert a big integer number to a string using a radix.
 *  The conversion uses the numeral system with the given base.
 *  Digit values from 10 upward are encoded with letters.
 *  For negative numbers a minus sign is prepended.
 *  @param big1 BigInteger number to be converted.
 *  @param base Base of numeral system (base >= 2 and base <= 36 holds).
 *  @param upperCase Decides about the letter case.
 *  @return the string result of the conversion.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
static striType bigRadix2To36 (const const_bigIntType big1, unsigned int base,
    boolType upperCase)

  {
    unsigned int estimate_shift;
    bigIntType unsigned_big;
    boolType negative;
    memSizeType pos;
    memSizeType result_size;
    memSizeType final_result_size;
    striType resized_result;
    striType result;

  /* bigRadix2To36 */
    logFunction(printf("bigRadix2To36(%s, %u, %d)\n",
                       bigHexCStri(big1), base, upperCase););
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    /* A power of two that is less or equal than the base is */
    /* used to estimate the size of the result.              */
    estimate_shift = (unsigned int) uint8MostSignificantBit((uint8Type) base);
    if (unlikely((MAX_STRI_LEN <= (MAX_MEMSIZETYPE - 1) / estimate_shift +
                                  (unsigned int) negative + 1 &&
                 big1->size > ((MAX_STRI_LEN - (unsigned int) negative - 1) *
                               estimate_shift + 1) / BIGDIGIT_SIZE) ||
                 big1->size > MAX_MEMSIZETYPE / BIGDIGIT_SIZE)) {
      raise_error(MEMORY_ERROR);
      result = NULL;
    } else {
      /* The size of the result is computed by computing the     */
      /* number of radix digits plus one character for the sign. */
      result_size = (big1->size * BIGDIGIT_SIZE - 1) / estimate_shift + (unsigned int) negative + 1;
      /* printf("result_size: " FMT_U_MEM "\n", result_size); */
      if (unlikely(!ALLOC_STRI_SIZE_OK(result, result_size))) {
        raise_error(MEMORY_ERROR);
        result = NULL;
      } else {
        if (negative) {
          unsigned_big = alloc_positive_copy_of_negative_big(big1);
        } else if (likely(ALLOC_BIG_SIZE_OK(unsigned_big, big1->size))) {
          unsigned_big->size = big1->size;
          memcpy(unsigned_big->bigdigits, big1->bigdigits,
                 (size_t) big1->size * sizeof(bigDigitType));
        } /* if */
        if (unlikely(unsigned_big == NULL)) {
          FREE_STRI(result, result_size);
          raise_error(MEMORY_ERROR);
          result = NULL;
        } else {
          /* pos = basicRadix2To36(unsigned_big, result, base,
                                digitTable[upperCase], result_size - 1); */
          pos = binaryRadix2To36(unsigned_big, result, base,
                                 digitTable[upperCase], (unsigned int)
                                 memSizeMostSignificantBit(result_size) + 1,
                                 FALSE, result_size - 1);
          FREE_BIG(unsigned_big, big1->size);
          pos++;
          if (negative) {
            final_result_size = result_size - pos + 1;
            result->mem[0] = '-';
            memmove(&result->mem[1], &result->mem[pos],
                    (result_size - pos) * sizeof(strElemType));
          } else {
            final_result_size = result_size - pos;
            memmove(&result->mem[0], &result->mem[pos],
                    (result_size - pos) * sizeof(strElemType));
          } /* if */
          result->size = final_result_size;
          if (final_result_size < result_size) {
            REALLOC_STRI_SIZE_SMALLER(resized_result, result, result_size, final_result_size);
            if (unlikely(resized_result == NULL)) {
              FREE_STRI(result, result_size);
              raise_error(MEMORY_ERROR);
              result = NULL;
            } else {
              result = resized_result;
              COUNT3_STRI(result_size, final_result_size);
            } /* if */
          } /* if */
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigRadix2To36 --> \"%s\"\n", striAsUnquotedCStri(result)););
    return result;
  } /* bigRadix2To36 */



/**
 *  Shifts the big integer big1 to the left by lshift bits.
 *  Bits which are shifted out at the left of big1 are lost.
 *  At the right of big1 zero bits are shifted in. The function
 *  is called for 0 < lshift < BIGDIGIT_SIZE.
 */
static void uBigLShift (const bigIntType big1, const unsigned int lshift)

  {
    doubleBigDigitType carry = 0;
    memSizeType pos = 0;

  /* uBigLShift */
    do {
      carry |= ((doubleBigDigitType) big1->bigdigits[pos]) << lshift;
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big1->size);
  } /* uBigLShift */



/**
 *  Shifts the big integer big1 to the right by rshift bits.
 *  Bits which are shifted out at the right of big1 are lost.
 *  At the left of big1 zero bits are shifted in. The function
 *  is called for 0 < rshift < BIGDIGIT_SIZE.
 */
static void uBigRShift (const bigIntType big1, const unsigned int rshift)

  {
    unsigned int lshift = BIGDIGIT_SIZE - rshift;
    bigDigitType low_digit;
    bigDigitType high_digit = 0;
    memSizeType pos;

  /* uBigRShift */
    for (pos = big1->size - 1; pos != 0; pos--) {
      low_digit = big1->bigdigits[pos];
      big1->bigdigits[pos] = (bigDigitType)
          (((low_digit >> rshift) | (high_digit << lshift)) & BIGDIGIT_MASK);
      high_digit = low_digit;
    } /* for */
    low_digit = big1->bigdigits[0];
    big1->bigdigits[0] = (bigDigitType)
        (((low_digit >> rshift) | (high_digit << lshift)) & BIGDIGIT_MASK);
  } /* uBigRShift */



/**
 *  Increments an unsigned big integer by 1.
 *  This function does overflow silently if big1 contains
 *  not enough digits.
 */
static void uBigIncr (const bigIntType big1)

  {
    memSizeType pos = 0;

  /* uBigIncr */
    if (unlikely(big1->bigdigits[pos] == BIGDIGIT_MASK)) {
      if (big1->size == 1) {
        big1->bigdigits[pos] = 0;
        pos++;
      } else {
        do {
          big1->bigdigits[pos] = 0;
          pos++;
        } while (big1->bigdigits[pos] == BIGDIGIT_MASK);
        /* memset(big1->bigdigits, 0, pos * sizeof(bigDigitType)); */
      } /* if */
    } /* if */
    if (pos < big1->size) {
      big1->bigdigits[pos]++;
    } /* if */
  } /* uBigIncr */



/**
 *  Decrements an unsigned big integer by 1.
 *  This function does overflow silently if big1 contains
 *  not enough digits. The function works correctly if there
 *  are leading zereo digits.
 */
static void uBigDecr (const bigIntType big1)

  {
    memSizeType pos = 0;

  /* uBigDecr */
    if (unlikely(big1->bigdigits[pos] == 0)) {
      do {
        big1->bigdigits[pos] = BIGDIGIT_MASK;
        pos++;
      } while (pos < big1->size && big1->bigdigits[pos] == 0);
    } /* if */
    if (pos < big1->size) {
      big1->bigdigits[pos]--;
    } /* if */
  } /* uBigDecr */



/**
 *  Computes the quotient of an integer division of dividend by one
 *  divisor_digit for nonnegative big integers. The divisor_digit
 *  must not be zero.
 */
static void uBigDiv1 (const const_bigIntType dividend,
    const bigDigitType divisor_digit, const bigIntType quotient)

  {
    memSizeType pos;
    doubleBigDigitType carry = 0;

  /* uBigDiv1 */
    pos = dividend->size;
    do {
      pos--;
      carry <<= BIGDIGIT_SIZE;
      carry += dividend->bigdigits[pos];
      quotient->bigdigits[pos] = (bigDigitType) ((carry / divisor_digit) & BIGDIGIT_MASK);
      carry %= divisor_digit;
    } while (pos > 0);
  } /* uBigDiv1 */



/**
 *  Computes an integer division of dividend by one divisor_digit
 *  for signed big integers. The memory for the quotient is requested
 *  and the normalized quotient is returned. This function handles
 *  also the special case of a division by zero.
 *  @return the quotient of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
static bigIntType bigDiv1 (const_bigIntType dividend, bigDigitType divisor_digit)

  {
    boolType negative = FALSE;
    bigIntType dividend_help = NULL;
    bigIntType quotient;

  /* bigDiv1 */
    if (unlikely(divisor_digit == 0)) {
      logError(printf("bigDiv1(%s, " FMT_U_DIG "): Division by zero.\n",
                      bigHexCStri(dividend), divisor_digit););
      raise_error(NUMERIC_ERROR);
      return NULL;
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(quotient, dividend->size + 1))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        quotient->size = dividend->size + 1;
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          negative = TRUE;
          dividend_help = alloc_positive_copy_of_negative_big(dividend);
          dividend = dividend_help;
          if (unlikely(dividend_help == NULL)) {
            FREE_BIG(quotient, quotient->size);
            raise_error(MEMORY_ERROR);
            return NULL;
          } /* if */
        } /* if */
        quotient->bigdigits[quotient->size - 1] = 0;
        if (IS_NEGATIVE(divisor_digit)) {
          negative = !negative;
          /* The unsigned value is negated to avoid a signed integer */
          /* overflow if the smallest signed integer is negated.     */
          divisor_digit = -divisor_digit;
        } /* if */
        uBigDiv1(dividend, divisor_digit, quotient);
        if (negative) {
          negate_positive_big(quotient);
        } /* if */
        quotient = normalize(quotient);
        if (dividend_help != NULL) {
          FREE_BIG(dividend_help, dividend_help->size);
        } /* if */
        return quotient;
      } /* if */
    } /* if */
  } /* bigDiv1 */



/**
 *  Computes an integer division of dividend by divisor for signed big
 *  integers if dividend has less digits than divisor. The memory for
 *  the quotient is requested and the normalized quotient is returned. Normally
 *  dividend->size < divisor->size implies abs(dividend) < abs(divisor).
 *  If abs(dividend) < abs(divisor) holds the quotient is 0. The cases
 *  dividend->size < divisor->size and abs(dividend) = abs(divisor) are if
 *  dividend->size + 1 == divisor->size and dividend = 0x8000 (0x80000000...)
 *  and divisor = 0x00008000 (0x000080000000...). In this cases the
 *  quotient is -1. In all other cases the quotient is 0.
 *  @return the quotient of the integer division.
 */
static bigIntType bigDivSizeLess (const const_bigIntType dividend,
    const const_bigIntType divisor)

  {
    memSizeType pos;
    bigIntType quotient;

  /* bigDivSizeLess */
    if (unlikely(!ALLOC_BIG_SIZE_OK(quotient, 1))) {
      raise_error(MEMORY_ERROR);
      return NULL;
    } else {
      quotient->size = 1;
      if (unlikely(dividend->size + 1 == divisor->size &&
                   dividend->bigdigits[dividend->size - 1] == BIGDIGIT_SIGN &&
                   divisor->bigdigits[divisor->size - 1] == 0 &&
                   divisor->bigdigits[divisor->size - 2] == BIGDIGIT_SIGN)) {
        quotient->bigdigits[0] = BIGDIGIT_MASK;
        pos = dividend->size - 1;
        while (pos > 0) {
          pos--;
          if (likely(dividend->bigdigits[pos] != 0 || divisor->bigdigits[pos] != 0)) {
            quotient->bigdigits[0] = 0;
            pos = 0;
          } /* if */
        } /* while */
      } else {
        quotient->bigdigits[0] = 0;
      } /* if */
      return quotient;
    } /* if */
  } /* bigDivSizeLess */



/**
 *  Multiplies big2 with multiplier and subtracts the product from
 *  big1 at the digit position pos1 of big1. Big1, big2 and
 *  multiplier are nonnegative big integer values.
 *  The algorithm tries to save computations. Therefore
 *  there are checks for mult_carry != 0 and sbtr_carry == 0.
 */
static bigDigitType uBigMultSub (const bigIntType big1, const const_bigIntType big2,
    const bigDigitType multiplier, const memSizeType pos1)

  {
    memSizeType pos = 0;
    doubleBigDigitType mult_carry = 0;
    doubleBigDigitType sbtr_carry = 1;

  /* uBigMultSub */
    do {
      mult_carry += (doubleBigDigitType) big2->bigdigits[pos] * multiplier;
      sbtr_carry += big1->bigdigits[pos1 + pos] + (~mult_carry & BIGDIGIT_MASK);
      big1->bigdigits[pos1 + pos] = (bigDigitType) (sbtr_carry & BIGDIGIT_MASK);
      mult_carry >>= BIGDIGIT_SIZE;
      sbtr_carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big2->size);
    for (pos += pos1; mult_carry != 0 && pos < big1->size; pos++) {
      sbtr_carry += big1->bigdigits[pos] + (~mult_carry & BIGDIGIT_MASK);
      big1->bigdigits[pos] = (bigDigitType) (sbtr_carry & BIGDIGIT_MASK);
      mult_carry >>= BIGDIGIT_SIZE;
      sbtr_carry >>= BIGDIGIT_SIZE;
    } /* for */
    for (; sbtr_carry == 0 && pos < big1->size; pos++) {
      sbtr_carry = (doubleBigDigitType) big1->bigdigits[pos] + BIGDIGIT_MASK;
      big1->bigdigits[pos] = (bigDigitType) (sbtr_carry & BIGDIGIT_MASK);
      sbtr_carry >>= BIGDIGIT_SIZE;
    } /* for */
    return (bigDigitType) (sbtr_carry & BIGDIGIT_MASK);
  } /* uBigMultSub */



/**
 *  Adds big2 to big1 at the digit position pos1. Big1 and big2
 *  are nonnegative big integer values. The size of big1 must be
 *  greater or equal the size of big2. The final carry is ignored.
 */
static void uBigAddTo (const bigIntType big1, const const_bigIntType big2,
    const memSizeType pos1)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 0;

  /* uBigAddTo */
    do {
      carry += (doubleBigDigitType) big1->bigdigits[pos1 + pos] + big2->bigdigits[pos];
      big1->bigdigits[pos1 + pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big2->size);
    for (pos += pos1; pos < big1->size; pos++) {
      carry += big1->bigdigits[pos];
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
    } /* for */
  } /* uBigAddTo */



/**
 *  Computes quotient and remainder of an integer division of dividend by
 *  divisor for nonnegative big integers. The remainder is delivered in
 *  dividend. There are several preconditions for this function. Divisor
 *  must have at least 2 digits and dividend must have at least one
 *  digit more than divisor. If dividend and divisor have the same length in
 *  digits nothing is done. The most significant bit of divisor must be
 *  set. The most significant digit of dividend must be less than the
 *  most significant digit of divisor. The computations to meet this
 *  predonditions are done outside this function. The special cases
 *  with a one digit divisor or a dividend with less digits than divisor are
 *  handled in other functions. This algorithm based on the algorithm
 *  from D.E. Knuth described in "The art of computer programming"
 *  volume 2 (Seminumerical algorithms).
 */
static void uBigDiv (const bigIntType dividend, const const_bigIntType divisor,
    const bigIntType quotient)

  {
    memSizeType pos1;
    doubleBigDigitType twodigits;
    doubleBigDigitType remainder;
    bigDigitType quotientdigit;
    bigDigitType sbtr_carry;

  /* uBigDiv */
    for (pos1 = dividend->size - 1; pos1 >= divisor->size; pos1--) {
      twodigits = (((doubleBigDigitType) dividend->bigdigits[pos1]) << BIGDIGIT_SIZE) |
          dividend->bigdigits[pos1 - 1];
      if (unlikely(dividend->bigdigits[pos1] == divisor->bigdigits[divisor->size - 1])) {
        quotientdigit = BIGDIGIT_MASK;
      } else {
        quotientdigit = (bigDigitType) (twodigits / divisor->bigdigits[divisor->size - 1]);
      } /* if */
      remainder = twodigits - (doubleBigDigitType) quotientdigit *
          divisor->bigdigits[divisor->size - 1];
      while (remainder <= BIGDIGIT_MASK &&
          (doubleBigDigitType) divisor->bigdigits[divisor->size - 2] * quotientdigit >
          (remainder << BIGDIGIT_SIZE | dividend->bigdigits[pos1 - 2])) {
        quotientdigit--;
        remainder = twodigits - (doubleBigDigitType) quotientdigit *
            divisor->bigdigits[divisor->size - 1];
      } /* while */
      sbtr_carry = uBigMultSub(dividend, divisor, quotientdigit, pos1 - divisor->size);
      if (sbtr_carry == 0) {
        uBigAddTo(dividend, divisor, pos1 - divisor->size);
        quotientdigit--;
      } /* if */
      quotient->bigdigits[pos1 - divisor->size] = quotientdigit;
    } /* for */
  } /* uBigDiv */



/**
 *  Computes quotient and remainder of an integer division of dividend
 *  by one divisor_digit for nonnegative big integers. The divisor_digit
 *  must not be zero. The remainder of the division is returned.
 */
static bigDigitType uBigDivRem1 (const const_bigIntType dividend,
    const bigDigitType divisor_digit, const bigIntType quotient)

  {
    memSizeType pos;
    doubleBigDigitType carry = 0;

  /* uBigDivRem1 */
    pos = dividend->size;
    do {
      pos--;
      carry <<= BIGDIGIT_SIZE;
      carry += dividend->bigdigits[pos];
      quotient->bigdigits[pos] = (bigDigitType) ((carry / divisor_digit) & BIGDIGIT_MASK);
      carry %= divisor_digit;
    } while (pos > 0);
    return (bigDigitType) carry;
  } /* uBigDivRem1 */


/**
 *  Computes quotient and remainder of the integer division dividend
 *  by one divisor_digit for signed big integers. The memory for the
 *  quotient is requested and the normalized quotient is returned.
 *  The memory for the remainder is requested and the normalized
 *  remainder is assigned to *remainder. This function handles also
 *  the special case of a division by zero.
 *  @return the quotient of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
static bigIntType bigDivRem1 (const_bigIntType dividend, bigDigitType divisor_digit,
    bigIntType *remainder)

  {
    boolType quotientNegative = FALSE;
    boolType remainderNegative = FALSE;
    bigIntType dividend_help = NULL;
    bigIntType quotient;

  /* bigDivRem1 */
    if (unlikely(divisor_digit == 0)) {
      logError(printf("bigDivRem1(%s, " FMT_U_DIG "): Division by zero.\n",
                      bigHexCStri(dividend), divisor_digit););
      *remainder = NULL;
      raise_error(NUMERIC_ERROR);
      return NULL;
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(quotient, dividend->size + 1))) {
        *remainder = NULL;
        raise_error(MEMORY_ERROR);
        return NULL;
      } else if (unlikely(!ALLOC_BIG_SIZE_OK(*remainder, 1))) {
        FREE_BIG(quotient, quotient->size);
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        quotient->size = dividend->size + 1;
        (*remainder)->size = 1;
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          quotientNegative = TRUE;
          remainderNegative = TRUE;
          dividend_help = alloc_positive_copy_of_negative_big(dividend);
          dividend = dividend_help;
          if (unlikely(dividend_help == NULL)) {
            FREE_BIG(quotient, quotient->size);
            FREE_BIG(*remainder, (*remainder)->size);
            *remainder = NULL;
            raise_error(MEMORY_ERROR);
            return NULL;
          } /* if */
        } /* if */
        quotient->bigdigits[quotient->size - 1] = 0;
        if (IS_NEGATIVE(divisor_digit)) {
          quotientNegative = !quotientNegative;
          /* The unsigned value is negated to avoid a signed integer */
          /* overflow if the smallest signed integer is negated.     */
          divisor_digit = -divisor_digit;
        } /* if */
        (*remainder)->bigdigits[0] = uBigDivRem1(dividend, divisor_digit, quotient);
        if (quotientNegative) {
          negate_positive_big(quotient);
        } /* if */
        quotient = normalize(quotient);
        if (remainderNegative) {
          negate_positive_big(*remainder);
        } /* if */
        if (dividend_help != NULL) {
          FREE_BIG(dividend_help, dividend_help->size);
        } /* if */
        return quotient;
      } /* if */
    } /* if */
  } /* bigDivRem1 */



/**
 *  Computes quotient and remainder of the integer division of dividend
 *  by divisor for signed big integers if dividend has less digits than
 *  divisor. The memory for the quotient is requested and the normalized
 *  quotient is returned. The memory for the remainder is requested and
 *  the normalized remainder is assigned to *remainder. Normally
 *  dividend->size < divisor->size implies abs(dividend) < abs(divisor).
 *  If abs(dividend) < abs(divisor) holds the quotient is 0 and the
 *  remainder is dividend. The cases
 *  dividend->size < divisor->size and abs(dividend) = abs(divisor) are if
 *  dividend->size + 1 == divisor->size and dividend = 0x8000 (0x80000000...)
 *  and divisor = 0x00008000 (0x000080000000...). In this cases the
 *  quotient is -1 and the remainder is 0. In all other cases the quotient
 *  is 0 and the remainder is dividend.
 *  @return the quotient of the integer division.
 */
static bigIntType bigDivRemSizeLess (const const_bigIntType dividend,
    const const_bigIntType divisor, bigIntType *remainder)

  {
    memSizeType pos;
    boolType remainderIs0;
    bigIntType quotient;

  /* bigDivRemSizeLess */
    if (unlikely(!ALLOC_BIG_SIZE_OK(quotient, 1))) {
      *remainder = NULL;
      raise_error(MEMORY_ERROR);
    } else {
      quotient->size = 1;
      if (unlikely(dividend->size + 1 == divisor->size &&
                   dividend->bigdigits[dividend->size - 1] == BIGDIGIT_SIGN &&
                   divisor->bigdigits[divisor->size - 1] == 0 &&
                   divisor->bigdigits[divisor->size - 2] == BIGDIGIT_SIGN)) {
        remainderIs0 = TRUE;
        pos = dividend->size - 1;
        while (pos > 0) {
          pos--;
          if (likely(dividend->bigdigits[pos] != 0 || divisor->bigdigits[pos] != 0)) {
            remainderIs0 = FALSE;
            pos = 0;
          } /* if */
        } /* while */
      } else {
        remainderIs0 = FALSE;
      } /* if */
      if (remainderIs0) {
        if (unlikely(!ALLOC_BIG_SIZE_OK(*remainder, 1))) {
          FREE_BIG(quotient, 1);
          raise_error(MEMORY_ERROR);
          quotient = NULL;
        } else {
          (*remainder)->size = 1;
          (*remainder)->bigdigits[0] = 0;
          quotient->bigdigits[0] = BIGDIGIT_MASK;
        } /* if */
      } else {
        if (unlikely(!ALLOC_BIG_SIZE_OK(*remainder, dividend->size))) {
          FREE_BIG(quotient, 1);
          raise_error(MEMORY_ERROR);
          quotient = NULL;
        } else {
          (*remainder)->size = dividend->size;
          memcpy((*remainder)->bigdigits, dividend->bigdigits,
                 (size_t) dividend->size * sizeof(bigDigitType));
          quotient->bigdigits[0] = 0;
        } /* if */
      } /* if */
    } /* if */
    return quotient;
  } /* bigDivRemSizeLess */



/**
 *  Computes the remainder of an integer division of dividend by
 *  one divisor_digit for nonnegative big integers. The divisor_digit must
 *  not be zero.
 */
static bigDigitType uBigRem1 (const const_bigIntType dividend,
    const bigDigitType divisor_digit)

  {
    memSizeType pos;
    doubleBigDigitType carry = 0;

  /* uBigRem1 */
    pos = dividend->size;
    do {
      pos--;
      carry <<= BIGDIGIT_SIZE;
      carry += dividend->bigdigits[pos];
      carry %= divisor_digit;
    } while (pos > 0);
    return (bigDigitType) carry;
  } /* uBigRem1 */



/**
 *  Computes the remainder of the integer division dividend by one
 *  divisor_digit for signed big integers. The memory for the
 *  remainder is requested and the normalized remainder is
 *  returned. This function handles also the special case of a
 *  division by zero.
 *  @return the remainder of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
static bigIntType bigRem1 (const_bigIntType dividend, bigDigitType divisor_digit)

  {
    boolType negative = FALSE;
    bigIntType dividend_help = NULL;
    bigIntType remainder;

  /* bigRem1 */
    if (unlikely(divisor_digit == 0)) {
      logError(printf("bigRem1(%s, " FMT_U_DIG "): Division by zero.\n",
                      bigHexCStri(dividend), divisor_digit););
      raise_error(NUMERIC_ERROR);
      return NULL;
    } else {
      if (unlikely(!ALLOC_BIG_SIZE_OK(remainder, 1))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        remainder->size = 1;
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          negative = TRUE;
          dividend_help = alloc_positive_copy_of_negative_big(dividend);
          dividend = dividend_help;
          if (unlikely(dividend_help == NULL)) {
            FREE_BIG(remainder, remainder->size);
            raise_error(MEMORY_ERROR);
            return NULL;
          } /* if */
        } /* if */
        if (IS_NEGATIVE(divisor_digit)) {
          /* The unsigned value is negated to avoid a signed integer */
          /* overflow if the smallest signed integer is negated.     */
          divisor_digit = -divisor_digit;
        } /* if */
        remainder->bigdigits[0] = uBigRem1(dividend, divisor_digit);
        if (negative) {
          negate_positive_big(remainder);
        } /* if */
        if (dividend_help != NULL) {
          FREE_BIG(dividend_help, dividend_help->size);
        } /* if */
        return remainder;
      } /* if */
    } /* if */
  } /* bigRem1 */



/**
 *  Computes an integer modulo division of dividend by one
 *  divisor_digit for signed big integers. The memory for the
 *  quotient is requested and the normalized quotient is returned.
 *  This function handles also the special case of a division by
 *  zero.
 *  @return the quotient of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
static bigIntType bigMDiv1 (const_bigIntType dividend, bigDigitType divisor_digit)

  {
    boolType negative = FALSE;
    bigIntType dividend_help = NULL;
    bigDigitType remainder;
    bigIntType quotient;

  /* bigMDiv1 */
    if (unlikely(divisor_digit == 0)) {
      logError(printf("bigMDiv1(%s, " FMT_U_DIG "): Division by zero.\n",
                      bigHexCStri(dividend), divisor_digit););
      raise_error(NUMERIC_ERROR);
      return NULL;
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(quotient, dividend->size + 1))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        quotient->size = dividend->size + 1;
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          negative = TRUE;
          dividend_help = alloc_positive_copy_of_negative_big(dividend);
          dividend = dividend_help;
          if (unlikely(dividend_help == NULL)) {
            FREE_BIG(quotient, quotient->size);
            raise_error(MEMORY_ERROR);
            return NULL;
          } /* if */
        } /* if */
        quotient->bigdigits[quotient->size - 1] = 0;
        if (IS_NEGATIVE(divisor_digit)) {
          negative = !negative;
          /* The unsigned value is negated to avoid a signed integer */
          /* overflow if the smallest signed integer is negated.     */
          divisor_digit = -divisor_digit;
        } /* if */
        remainder = uBigDivRem1(dividend, divisor_digit, quotient);
        if (negative) {
          if (remainder != 0) {
            uBigIncr(quotient);
          } /* if */
          negate_positive_big(quotient);
        } /* if */
        quotient = normalize(quotient);
        if (dividend_help != NULL) {
          FREE_BIG(dividend_help, dividend_help->size);
        } /* if */
        return quotient;
      } /* if */
    } /* if */
  } /* bigMDiv1 */



/**
 *  Computes a modulo integer division of dividend by divisor for signed
 *  big integers if dividend has less digits than divisor. The memory for
 *  the quotient is requested and the normalized quotient is returned.
 *  If the dividend is zero the quotient is always zero. Otherwise if
 *  the signs of dividend and divisor differ the quotient is -1.
 *  In all other cases the quotient is zero.
 *  @return the quotient of the integer division.
 */
static bigIntType bigMDivSizeLess (const const_bigIntType dividend,
    const const_bigIntType divisor)

  {
    bigIntType quotient;

  /* bigMDivSizeLess */
    logFunction(printf("bigMDivSizeLess(%s,", bigHexCStri(dividend));
                printf("%s)\n", bigHexCStri(divisor)););
    if (unlikely(!ALLOC_BIG_SIZE_OK(quotient, 1))) {
      raise_error(MEMORY_ERROR);
    } else {
      quotient->size = 1;
      if ((dividend->size == 1 && dividend->bigdigits[0] == 0) ||
          IS_NEGATIVE(dividend->bigdigits[dividend->size - 1]) ==
          IS_NEGATIVE(divisor->bigdigits[divisor->size - 1])) {
        quotient->bigdigits[0] = 0;
      } else {
        quotient->bigdigits[0] = BIGDIGIT_MASK;
      } /* if */
    } /* if */
    logFunction(printf("bigMDivSizeLess --> %s\n", bigHexCStri(quotient)););
    return quotient;
  } /* bigMDivSizeLess */



/**
 *  Computes the modulo of the integer division dividend by one
 *  digit for signed big integers. The memory for the modulo is
 *  requested and the normalized modulo is returned. This function
 *  handles also the special case of a division by zero.
 */
static bigIntType bigMod1 (const const_bigIntType dividend, const bigDigitType divisor_digit)

  {
    bigIntType modulo;

  /* bigMod1 */
    modulo = bigRem1(dividend, divisor_digit);
    if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1]) != IS_NEGATIVE(divisor_digit) &&
        modulo != NULL && modulo->bigdigits[0] != 0) {
      modulo->bigdigits[0] += divisor_digit;
    } /* if */
    return modulo;
  } /* bigMod1 */



/**
 *  Computes the remainder of the integer division dividend by divisor for
 *  signed big integers if dividend has less digits than divisor. The memory
 *  for the remainder is requested and the normalized remainder is returned.
 *  Normally dividend->size < divisor->size implies abs(dividend) < abs(divisor).
 *  If abs(dividend) < abs(divisor) holds the remainder is dividend. The cases
 *  dividend->size < divisor->size and abs(dividend) = abs(divisor) are if
 *  dividend->size + 1 == divisor->size and dividend = 0x8000 (0x80000000...)
 *  and divisor = 0x00008000 (0x000080000000...). In this cases the
 *  remainder is 0. In all other cases the remainder is dividend.
 */
static bigIntType bigRemSizeLess (const const_bigIntType dividend,
    const const_bigIntType divisor)

  {
    memSizeType pos;
    boolType remainderIs0;
    bigIntType remainder;

  /* bigRemSizeLess */
    if (dividend->size + 1 == divisor->size &&
        dividend->bigdigits[dividend->size - 1] == BIGDIGIT_SIGN &&
        divisor->bigdigits[divisor->size - 1] == 0 &&
        divisor->bigdigits[divisor->size - 2] == BIGDIGIT_SIGN) {
      remainderIs0 = TRUE;
      for (pos = 0; pos < dividend->size - 1; pos++) {
        if (dividend->bigdigits[pos] != 0 || divisor->bigdigits[pos] != 0) {
          remainderIs0 = FALSE;
        } /* if */
      } /* for */
    } else {
      remainderIs0 = FALSE;
    } /* if */
    if (remainderIs0) {
      if (unlikely(!ALLOC_BIG_SIZE_OK(remainder, 1))) {
        raise_error(MEMORY_ERROR);
      } else {
        remainder->size = 1;
        remainder->bigdigits[0] = 0;
      } /* if */
    } else {
      if (unlikely(!ALLOC_BIG_SIZE_OK(remainder, dividend->size))) {
        raise_error(MEMORY_ERROR);
      } else {
        remainder->size = dividend->size;
        memcpy(remainder->bigdigits, dividend->bigdigits,
               (size_t) dividend->size * sizeof(bigDigitType));
      } /* if */
    } /* if */
    return remainder;
  } /* bigRemSizeLess */



/**
 *  Adds big2 to big1 at the digit position pos1. Big1 and big2
 *  are signed big integer values. The size of big1 must be
 *  greater or equal the size of big2.
 */
static void bigAddTo (const bigIntType big1, const const_bigIntType big2)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 0;
    doubleBigDigitType big2_sign;

  /* bigAddTo */
    do {
      carry += (doubleBigDigitType) big1->bigdigits[pos] + big2->bigdigits[pos];
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big2->size);
    big2_sign = IS_NEGATIVE(big2->bigdigits[pos - 1]) ? BIGDIGIT_MASK : 0;
    for (; pos < big1->size; pos++) {
      carry += big1->bigdigits[pos] + big2_sign;
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
    } /* for */
  } /* bigAddTo */



/**
 *  Computes the modulo of the integer division dividend by divisor for
 *  signed big integers if dividend has less digits than divisor. The memory
 *  for the modulo is requested and the normalized modulo is returned.
 *  There are two cases: If the modulo division (see bigMDivSizeLess() )
 *  would compute a quotient of zero the modulo is equal to the dividend.
 *  In all other cases the quotient would be -1 and the modulo is computed
 *  as divisor + dividend.
 *  @return the modulo of the integer division.
 */
static bigIntType bigModSizeLess (const const_bigIntType dividend,
    const const_bigIntType divisor)

  {
    bigIntType modulo;

  /* bigModSizeLess */
    logFunction(printf("bigModSizeLess(%s,", bigHexCStri(dividend));
                printf("%s)\n", bigHexCStri(divisor)););
    if ((dividend->size == 1 && dividend->bigdigits[0] == 0) ||
        IS_NEGATIVE(dividend->bigdigits[dividend->size - 1]) ==
        IS_NEGATIVE(divisor->bigdigits[divisor->size - 1])) {
      /* The quotient is zero. */
      if (unlikely(!ALLOC_BIG_SIZE_OK(modulo, dividend->size))) {
        raise_error(MEMORY_ERROR);
      } else {
        modulo->size = dividend->size;
        memcpy(modulo->bigdigits, dividend->bigdigits,
               (size_t) dividend->size * sizeof(bigDigitType));
      } /* if */
    } else {
      /* The quotient is -1. */
      if (unlikely(!ALLOC_BIG_SIZE_OK(modulo, divisor->size))) {
        raise_error(MEMORY_ERROR);
      } else {
        modulo->size = divisor->size;
        memcpy(modulo->bigdigits, divisor->bigdigits,
               (size_t) divisor->size * sizeof(bigDigitType));
        bigAddTo(modulo, dividend);
        modulo = normalize(modulo);
      } /* if */
    } /* if */
    logFunction(printf("bigModSizeLess --> %s\n", bigHexCStri(quotient)););
    return modulo;
  } /* bigModSizeLess */



/**
 *  Computes the remainder of an integer division of dividend by divisor
 *  for nonnegative big integers. The remainder is delivered in
 *  dividend. There are several preconditions for this function. Divisor
 *  must have at least 2 digits and dividend must have at least one
 *  digit more than divisor. If dividend and divisor have the same length in
 *  digits nothing is done. The most significant bit of divisor must be
 *  set. The most significant digit of dividend must be less than the
 *  most significant digit of divisor. The computations to meet this
 *  predonditions are done outside this function. The special cases
 *  with a one digit divisor or a dividend with less digits than divisor are
 *  handled in other functions. This algorithm based on the algorithm
 *  from D.E. Knuth described in "The art of computer programming"
 *  volume 2 (Seminumerical algorithms).
 */
static void uBigRem (const bigIntType dividend, const const_bigIntType divisor)

  {
    memSizeType pos1;
    doubleBigDigitType twodigits;
    doubleBigDigitType remainder;
    bigDigitType quotientdigit;
    bigDigitType sbtr_carry;

  /* uBigRem */
    for (pos1 = dividend->size - 1; pos1 >= divisor->size; pos1--) {
      twodigits = (((doubleBigDigitType) dividend->bigdigits[pos1]) << BIGDIGIT_SIZE) |
          dividend->bigdigits[pos1 - 1];
      if (unlikely(dividend->bigdigits[pos1] == divisor->bigdigits[divisor->size - 1])) {
        quotientdigit = BIGDIGIT_MASK;
      } else {
        quotientdigit = (bigDigitType) (twodigits / divisor->bigdigits[divisor->size - 1]);
      } /* if */
      remainder = twodigits - (doubleBigDigitType) quotientdigit *
          divisor->bigdigits[divisor->size - 1];
      while (remainder <= BIGDIGIT_MASK &&
          (doubleBigDigitType) divisor->bigdigits[divisor->size - 2] * quotientdigit >
          (remainder << BIGDIGIT_SIZE | dividend->bigdigits[pos1 - 2])) {
        quotientdigit--;
        remainder = twodigits - (doubleBigDigitType) quotientdigit *
            divisor->bigdigits[divisor->size - 1];
      } /* while */
      sbtr_carry = uBigMultSub(dividend, divisor, quotientdigit, pos1 - divisor->size);
      if (sbtr_carry == 0) {
        uBigAddTo(dividend, divisor, pos1 - divisor->size);
      } /* if */
    } /* for */
  } /* uBigRem */



static void uBigDigitAdd (const bigDigitType *const big1, const memSizeType size1,
    const bigDigitType *const big2, const memSizeType size2, bigDigitType *const result)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 0;

  /* uBigDigitAdd */
    do {
      carry += (doubleBigDigitType) big1[pos] + big2[pos];
      result[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < size2);
    for (; pos < size1; pos++) {
      carry += big1[pos];
      result[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
    } /* for */
    result[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
  } /* uBigDigitAdd */



static void uBigDigitSbtrFrom (bigDigitType *const big1, const memSizeType size1,
    const bigDigitType *const big2, const memSizeType size2)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 1;

  /* uBigDigitSbtrFrom */
    do {
      carry += (doubleBigDigitType) big1[pos] +
          (~big2[pos] & BIGDIGIT_MASK);
      big1[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < size2);
    for (; carry == 0 && pos < size1; pos++) {
      carry = (doubleBigDigitType) big1[pos] + BIGDIGIT_MASK;
      big1[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
    } /* for */
  } /* uBigDigitSbtrFrom */



static void uBigDigitAddTo (bigDigitType *const big1,  const memSizeType size1,
    const bigDigitType *const big2, const memSizeType size2)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 0;

  /* uBigDigitAddTo */
    do {
      carry += (doubleBigDigitType) big1[pos] + big2[pos];
      big1[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < size2);
    for (; carry != 0 && pos < size1; pos++) {
      carry += big1[pos];
      big1[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
    } /* for */
  } /* uBigDigitAddTo */



#ifdef OUT_OF_ORDER
static void uBigDigitMult (const bigDigitType *const factor1,
    const bigDigitType *const factor2, const memSizeType size,
    bigDigitType *const product)

  {
    memSizeType pos1;
    memSizeType pos2;
    doubleBigDigitType carry;
    doubleBigDigitType carry2 = 0;
    doubleBigDigitType prod;

  /* uBigDigitMult */
    carry = (doubleBigDigitType) factor1[0] * factor2[0];
    product[0] = (bigDigitType) (carry & BIGDIGIT_MASK);
    carry >>= BIGDIGIT_SIZE;
    for (pos1 = 1; pos1 < size; pos1++) {
      pos2 = 0;
      do {
        prod = (doubleBigDigitType) factor1[pos2] * factor2[pos1 - pos2];
        if (unlikely(carry > (doubleBigDigitType) ~prod)) {
          carry2++;
        } /* if */
        carry += prod;
        pos2++;
      } while (pos2 <= pos1);
      product[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      carry |= (carry2 & BIGDIGIT_MASK) << BIGDIGIT_SIZE;
      carry2 >>= BIGDIGIT_SIZE;
    } /* for */
    for (; pos1 < size + size - 1; pos1++) {
      pos2 = pos1 - size + 1;
      do {
        prod = (doubleBigDigitType) factor1[pos2] * factor2[pos1 - pos2];
        if (unlikely(carry > (doubleBigDigitType) ~prod)) {
          carry2++;
        } /* if */
        carry += prod;
        pos2++;
      } while (pos2 < size);
      product[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      carry |= (carry2 & BIGDIGIT_MASK) << BIGDIGIT_SIZE;
      carry2 >>= BIGDIGIT_SIZE;
    } /* for */
    product[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
  } /* uBigDigitMult */
#endif



static void uBigDigitMult (const bigDigitType *const factor1,
    const bigDigitType *const factor2, const memSizeType size,
    bigDigitType *const product)

  {
    memSizeType pos1;
    memSizeType pos2 = 0;
    doubleBigDigitType carry = 0;

  /* uBigDigitMult */
    do {
      carry += (doubleBigDigitType) factor1[0] * factor2[pos2];
      product[pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos2++;
    } while (pos2 < size);
    product[size] = (bigDigitType) (carry & BIGDIGIT_MASK);
    for (pos1 = 1; pos1 < size; pos1++) {
      carry = 0;
      pos2 = 0;
      do {
        carry += (doubleBigDigitType) product[pos1 + pos2] +
            (doubleBigDigitType) factor1[pos1] * factor2[pos2];
        product[pos1 + pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos2++;
      } while (pos2 < size);
      product[pos1 + size] = (bigDigitType) (carry & BIGDIGIT_MASK);
    } /* for */
  } /* uBigDigitMult */



static void uBigKaratsubaMult (const bigDigitType *const factor1,
    const bigDigitType *const factor2, const memSizeType size,
    bigDigitType *const product, bigDigitType *const temp)

  {
    memSizeType sizeLo;
    memSizeType sizeHi;

  /* uBigKaratsubaMult */
    /* printf("uBigKaratsubaMult: size=" FMT_U_MEM "\n", size); */
    if (size < KARATSUBA_MULT_THRESHOLD) {
      uBigDigitMult(factor1, factor2, size, product);
    } else {
      sizeHi = size >> 1;
      sizeLo = size - sizeHi;
      uBigDigitAdd(factor1, sizeLo, &factor1[sizeLo], sizeHi, product);
      uBigDigitAdd(factor2, sizeLo, &factor2[sizeLo], sizeHi, &product[size]);
      uBigKaratsubaMult(product, &product[size], sizeLo + 1, temp, &temp[(sizeLo + 1) << 1]);
      uBigKaratsubaMult(factor1, factor2, sizeLo, product, &temp[(sizeLo + 1) << 1]);
      uBigKaratsubaMult(&factor1[sizeLo], &factor2[sizeLo], sizeHi, &product[sizeLo << 1],
                        &temp[(sizeLo + 1) << 1]);
      uBigDigitSbtrFrom(temp, (sizeLo + 1) << 1, product, sizeLo << 1);
      uBigDigitSbtrFrom(temp, (sizeLo + 1) << 1, &product[sizeLo << 1], sizeHi << 1);
      uBigDigitAddTo(&product[sizeLo], sizeLo + (sizeHi << 1), temp, (sizeLo + 1) << 1);
    } /* if */
  } /* uBigKaratsubaMult */



static void uBigDigitSquare (const bigDigitType *const big1,
    const memSizeType size, bigDigitType *const square)

  {
    memSizeType pos1;
    memSizeType pos2;
    doubleBigDigitType carry;
    doubleBigDigitType product;
    bigDigitType digit;

  /* uBigDigitSquare */
    digit = big1[0];
    carry = (doubleBigDigitType) digit * digit;
    square[0] = (bigDigitType) (carry & BIGDIGIT_MASK);
    carry >>= BIGDIGIT_SIZE;
    if (size == 1) {
      square[1] = (bigDigitType) (carry);
    } else {
      for (pos2 = 1; pos2 < size; pos2++) {
        product = (doubleBigDigitType) digit * big1[pos2];
        carry += (product << 1) & BIGDIGIT_MASK;
        square[pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        carry += product >> (BIGDIGIT_SIZE - 1);
      } /* for */
      square[pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
      square[pos2 + 1] = (bigDigitType) (carry >> BIGDIGIT_SIZE);
      for (pos1 = 1; pos1 < size; pos1++) {
        digit = big1[pos1];
        carry = (doubleBigDigitType) square[pos1 << 1] +
            (doubleBigDigitType) digit * digit;
        square[pos1 << 1] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        for (pos2 = pos1 + 1; pos2 < size; pos2++) {
          product = (doubleBigDigitType) digit * big1[pos2];
          carry += (doubleBigDigitType) square[pos1 + pos2] +
              ((product << 1) & BIGDIGIT_MASK);
          square[pos1 + pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
          carry += product >> (BIGDIGIT_SIZE - 1);
        } /* for */
        carry += (doubleBigDigitType) square[pos1 + pos2];
        square[pos1 + pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
        if (pos1 < size - 1) {
          square[pos1 + pos2 + 1] = (bigDigitType) (carry >> BIGDIGIT_SIZE);
        } /* if */
      } /* for */
    } /* if */
  } /* uBigDigitSquare */



static void uBigKaratsubaSquare (const bigDigitType *const big1,
    const memSizeType size, bigDigitType *const square, bigDigitType *const temp)

  {
    memSizeType sizeLo;
    memSizeType sizeHi;

  /* uBigKaratsubaSquare */
    /* printf("uBigKaratsubaSquare: size=" FMT_U_MEM "\n", size);); */
    if (size < KARATSUBA_SQUARE_THRESHOLD) {
      uBigDigitSquare(big1, size, square);
    } else {
      sizeHi = size >> 1;
      sizeLo = size - sizeHi;
      uBigDigitAdd(big1, sizeLo, &big1[sizeLo], sizeHi, square);
      uBigKaratsubaSquare(square, sizeLo + 1, temp, &temp[(sizeLo + 1) << 1]);
      uBigKaratsubaSquare(big1, sizeLo, square, &temp[(sizeLo + 1) << 1]);
      uBigKaratsubaSquare(&big1[sizeLo], sizeHi, &square[sizeLo << 1], &temp[(sizeLo + 1) << 1]);
      uBigDigitSbtrFrom(temp, (sizeLo + 1) << 1, square, sizeLo << 1);
      uBigDigitSbtrFrom(temp, (sizeLo + 1) << 1, &square[sizeLo << 1], sizeHi << 1);
      uBigDigitAddTo(&square[sizeLo], sizeLo + (sizeHi << 1), temp, (sizeLo + 1) << 1);
    } /* if */
  } /* uBigKaratsubaSquare */


static void uBigMultPositiveWithDigit (const const_bigIntType factor1,
    const bigDigitType factor2_digit, const bigIntType product)

  {
    memSizeType pos;
    doubleBigDigitType mult_carry;

  /* uBigMultPositiveWithDigit */
    mult_carry = (doubleBigDigitType) factor1->bigdigits[0] * factor2_digit;
    product->bigdigits[0] = (bigDigitType) (mult_carry & BIGDIGIT_MASK);
    mult_carry >>= BIGDIGIT_SIZE;
    for (pos = 1; pos < factor1->size; pos++) {
      mult_carry += (doubleBigDigitType) factor1->bigdigits[pos] * factor2_digit;
      product->bigdigits[pos] = (bigDigitType) (mult_carry & BIGDIGIT_MASK);
      mult_carry >>= BIGDIGIT_SIZE;
    } /* for */
    product->bigdigits[pos] = (bigDigitType) (mult_carry & BIGDIGIT_MASK);
  } /* uBigMultPositiveWithDigit */



static void uBigMultNegativeWithDigit (const const_bigIntType factor1,
    const bigDigitType factor2_digit, const bigIntType product)

  {
    memSizeType pos;
    doubleBigDigitType negate_carry = 1;
    doubleBigDigitType mult_carry;
    doubleBigDigitType product_carry = 1;

  /* uBigMultNegativeWithDigit */
    negate_carry += ~factor1->bigdigits[0] & BIGDIGIT_MASK;
    mult_carry = (negate_carry & BIGDIGIT_MASK) * factor2_digit;
    product_carry += ~mult_carry & BIGDIGIT_MASK;
    product->bigdigits[0] = (bigDigitType) (product_carry & BIGDIGIT_MASK);
    negate_carry >>= BIGDIGIT_SIZE;
    mult_carry >>= BIGDIGIT_SIZE;
    product_carry >>= BIGDIGIT_SIZE;
    for (pos = 1; pos < factor1->size; pos++) {
      negate_carry += ~factor1->bigdigits[pos] & BIGDIGIT_MASK;
      mult_carry += (negate_carry & BIGDIGIT_MASK) * factor2_digit;
      product_carry += ~mult_carry & BIGDIGIT_MASK;
      product->bigdigits[pos] = (bigDigitType) (product_carry & BIGDIGIT_MASK);
      negate_carry >>= BIGDIGIT_SIZE;
      mult_carry >>= BIGDIGIT_SIZE;
      product_carry >>= BIGDIGIT_SIZE;
    } /* for */
    product_carry += ~mult_carry & BIGDIGIT_MASK;
    product->bigdigits[pos] = (bigDigitType) (product_carry & BIGDIGIT_MASK);
  } /* uBigMultNegativeWithDigit */



static void uBigMultPositiveWithNegatedDigit (const const_bigIntType factor1,
    const bigDigitType factor2_digit, const bigIntType product)

  {
    memSizeType pos;
    doubleBigDigitType mult_carry;
    doubleBigDigitType product_carry = 1;

  /* uBigMultPositiveWithNegatedDigit */
    mult_carry = (doubleBigDigitType) factor1->bigdigits[0] * factor2_digit;
    product_carry += ~mult_carry & BIGDIGIT_MASK;
    product->bigdigits[0] = (bigDigitType) (product_carry & BIGDIGIT_MASK);
    mult_carry >>= BIGDIGIT_SIZE;
    product_carry >>= BIGDIGIT_SIZE;
    for (pos = 1; pos < factor1->size; pos++) {
      mult_carry += (doubleBigDigitType) factor1->bigdigits[pos] * factor2_digit;
      product_carry += ~mult_carry & BIGDIGIT_MASK;
      product->bigdigits[pos] = (bigDigitType) (product_carry & BIGDIGIT_MASK);
      mult_carry >>= BIGDIGIT_SIZE;
      product_carry >>= BIGDIGIT_SIZE;
    } /* for */
    product_carry += ~mult_carry & BIGDIGIT_MASK;
    product->bigdigits[pos] = (bigDigitType) (product_carry & BIGDIGIT_MASK);
  } /* uBigMultPositiveWithNegatedDigit */



static void uBigMultNegativeWithNegatedDigit (const const_bigIntType factor1,
    const bigDigitType factor2_digit, const bigIntType product)

  {
    memSizeType pos;
    doubleBigDigitType negate_carry = 1;
    doubleBigDigitType mult_carry;

  /* uBigMultNegativeWithNegatedDigit */
    negate_carry += ~factor1->bigdigits[0] & BIGDIGIT_MASK;
    mult_carry = (negate_carry & BIGDIGIT_MASK) * factor2_digit;
    product->bigdigits[0] = (bigDigitType) (mult_carry & BIGDIGIT_MASK);
    negate_carry >>= BIGDIGIT_SIZE;
    mult_carry >>= BIGDIGIT_SIZE;
    for (pos = 1; pos < factor1->size; pos++) {
      negate_carry += ~factor1->bigdigits[pos] & BIGDIGIT_MASK;
      mult_carry += (negate_carry & BIGDIGIT_MASK) * factor2_digit;
      product->bigdigits[pos] = (bigDigitType) (mult_carry & BIGDIGIT_MASK);
      negate_carry >>= BIGDIGIT_SIZE;
      mult_carry >>= BIGDIGIT_SIZE;
    } /* for */
    product->bigdigits[pos] = (bigDigitType) (mult_carry & BIGDIGIT_MASK);
  } /* uBigMultNegativeWithNegatedDigit */



#ifdef OUT_OF_ORDER
static void uBigMult (const_bigIntType factor1, const_bigIntType factor2,
    const bigIntType product)

  {
    const_bigIntType help_big;
    memSizeType pos1;
    memSizeType pos2;
    doubleBigDigitType carry;
    doubleBigDigitType carry2 = 0;
    doubleBigDigitType prod;

  /* uBigMult */
    if (factor2->size > factor1->size) {
      help_big = factor1;
      factor1 = factor2;
      factor2 = help_big;
    } /* if */
    carry = (doubleBigDigitType) factor1->bigdigits[0] * factor2->bigdigits[0];
    product->bigdigits[0] = (bigDigitType) (carry & BIGDIGIT_MASK);
    carry >>= BIGDIGIT_SIZE;
    if (factor2->size == 1) {
      for (pos1 = 1; pos1 < factor1->size; pos1++) {
        carry += (doubleBigDigitType) factor1->bigdigits[pos1] * factor2->bigdigits[0];
        product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
      } /* for */
    } else {
      for (pos1 = 1; pos1 < factor2->size; pos1++) {
        pos2 = 0;
        do {
          prod = (doubleBigDigitType) factor1->bigdigits[pos2] * factor2->bigdigits[pos1 - pos2];
          if (unlikely(carry > (doubleBigDigitType) ~prod)) {
            carry2++;
          } /* if */
          carry += prod;
          pos2++;
        } while (pos2 <= pos1);
        product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        carry |= (carry2 & BIGDIGIT_MASK) << BIGDIGIT_SIZE;
        carry2 >>= BIGDIGIT_SIZE;
      } /* for */
      for (; pos1 < factor1->size; pos1++) {
        pos2 = pos1 - factor2->size + 1;
        do {
          prod = (doubleBigDigitType) factor1->bigdigits[pos2] * factor2->bigdigits[pos1 - pos2];
          if (unlikely(carry > (doubleBigDigitType) ~prod)) {
            carry2++;
          } /* if */
          carry += prod;
          pos2++;
        } while (pos2 <= pos1);
        product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        carry |= (carry2 & BIGDIGIT_MASK) << BIGDIGIT_SIZE;
        carry2 >>= BIGDIGIT_SIZE;
      } /* for */
      for (; pos1 < factor1->size + factor2->size - 1; pos1++) {
        pos2 = pos1 - factor2->size + 1;
        do {
          prod = (doubleBigDigitType) factor1->bigdigits[pos2] * factor2->bigdigits[pos1 - pos2];
          if (unlikely(carry > (doubleBigDigitType) ~prod)) {
            carry2++;
          } /* if */
          carry += prod;
          pos2++;
        } while (pos2 < factor1->size);
        product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        carry |= (carry2 & BIGDIGIT_MASK) << BIGDIGIT_SIZE;
        carry2 >>= BIGDIGIT_SIZE;
      } /* for */
    } /* if */
    product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
  } /* uBigMult */
#endif



#ifdef OUT_OF_ORDER
static void uBigMult (const const_bigIntType factor1, const const_bigIntType factor2,
    const bigIntType product)

  {
    memSizeType pos1;
    memSizeType pos2;
    memSizeType pos3;
    doubleBigDigitType carry;
    doubleBigDigitType carry2 = 0;
    doubleBigDigitType prod;

  /* uBigMult */
    carry = (doubleBigDigitType) factor1->bigdigits[0] * factor2->bigdigits[0];
    product->bigdigits[0] = (bigDigitType) (carry & BIGDIGIT_MASK);
    carry >>= BIGDIGIT_SIZE;
    for (pos1 = 1; pos1 < factor1->size + factor2->size - 1; pos1++) {
      if (pos1 < factor2->size) {
        pos2 = 0;
      } else {
        pos2 = pos1 - factor2->size + 1;
      } /* if */
      if (pos1 < factor1->size) {
        pos3 = pos1 + 1;
      } else {
        pos3 = factor1->size;
      } /* if */
      do {
        prod = (doubleBigDigitType) factor1->bigdigits[pos2] * factor2->bigdigits[pos1 - pos2];
        /* To avoid overflows of carry + prod it is necessary     */
        /* to check if carry + prod > DOUBLEBIGDIGIT_MASK which   */
        /* is equivalent to carry > DOUBLEBIGDIGIT_MASK - prod.   */
        /* A subtraction can be replaced by adding the negated    */
        /* value: carry > DOUBLEBIGDIGIT_MASK + ~prod + 1. This   */
        /* can be simplified to carry > ~prod.                    */
        if (unlikely(carry > (doubleBigDigitType) ~prod)) {
          carry2++;
        } /* if */
        carry += prod;
        pos2++;
      } while (pos2 < pos3);
      product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      carry |= (carry2 & BIGDIGIT_MASK) << BIGDIGIT_SIZE;
      carry2 >>= BIGDIGIT_SIZE;
    } /* for */
    product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
  } /* uBigMult */
#endif



static void uBigMult (const const_bigIntType factor1, const const_bigIntType factor2,
    const bigIntType product)

  {
    memSizeType pos1 = 0;
    memSizeType pos2;
    doubleBigDigitType carry = 0;

  /* uBigMult */
    do {
      carry += (doubleBigDigitType) factor1->bigdigits[pos1] * factor2->bigdigits[0];
      product->bigdigits[pos1] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos1++;
    } while (pos1 < factor1->size);
    product->bigdigits[factor1->size] = (bigDigitType) (carry & BIGDIGIT_MASK);
    for (pos2 = 1; pos2 < factor2->size; pos2++) {
      carry = 0;
      pos1 = 0;
      do {
        carry += (doubleBigDigitType) product->bigdigits[pos1 + pos2] +
            (doubleBigDigitType) factor1->bigdigits[pos1] * factor2->bigdigits[pos2];
        product->bigdigits[pos1 + pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos1++;
      } while (pos1 < factor1->size);
      product->bigdigits[factor1->size + pos2] = (bigDigitType) (carry & BIGDIGIT_MASK);
    } /* for */
  } /* uBigMult */



static void bigMultAssign1 (bigIntType *const big_variable, bigDigitType factor_digit)

  {
    const_bigIntType big1;
    boolType negative = FALSE;
    const_bigIntType big1_help = NULL;
    memSizeType pos;
    doubleBigDigitType carry = 0;
    bigIntType product;

  /* bigMultAssign1 */
    big1 = *big_variable;
    if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
      negative = TRUE;
      big1_help = alloc_positive_copy_of_negative_big(big1);
      big1 = big1_help;
      if (unlikely(big1_help == NULL)) {
        raise_error(MEMORY_ERROR);
        return;
      } /* if */
    } /* if */
    if (IS_NEGATIVE(factor_digit)) {
      negative = !negative;
      /* The unsigned value is negated to avoid a signed integer */
      /* overflow if the smallest signed integer is negated.     */
      factor_digit = -factor_digit;
    } /* if */
    if (unlikely(!ALLOC_BIG(product, big1->size + 1))) {
      raise_error(MEMORY_ERROR);
    } else {
      for (pos = 0; pos < big1->size; pos++) {
        carry += (doubleBigDigitType) big1->bigdigits[pos] * factor_digit;
        product->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
      } /* for */
      product->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      product->size = big1->size + 1;
      if (negative) {
        negate_positive_big(product);
      } /* if */
      product = normalize(product);
      FREE_BIG(*big_variable, (*big_variable)->size);
      *big_variable = product;
    } /* if */
    if (big1_help != NULL) {
      FREE_BIG(big1_help, big1_help->size);
    } /* if */
  } /* bigMultAssign1 */



/**
 *  Multiply two unsigned big integers with the Karatsuba multiplication.
 *  @return the product, and NULL if there is not enough memory.
 */
static bigIntType uBigMultK (const_bigIntType factor1, const_bigIntType factor2,
    const boolType negative)

  {
    const_bigIntType help_big;
    bigIntType factor2_help;
    bigIntType temp;
    bigIntType product;

  /* uBigMultK */
    logFunction(printf("uBigMultK(size= " FMT_U_MEM ", size=" FMT_U_MEM ", *)\n",
                       factor1->size, factor2->size););
    if (factor2->size > factor1->size) {
      help_big = factor1;
      factor1 = factor2;
      factor2 = help_big;
    } /* if */
    if (factor1->size >= KARATSUBA_MULT_THRESHOLD &&
        factor2->size >= KARATSUBA_MULT_THRESHOLD) {
      if (factor2->size << 1 <= factor1->size) {
        if (unlikely(!ALLOC_BIG_SIZE_OK(factor2_help, factor1->size - (factor1->size >> 1)))) {
          product = NULL;
        } else {
          factor2_help->size = factor1->size - (factor1->size >> 1);
          memcpy(factor2_help->bigdigits, factor2->bigdigits,
                 (size_t) factor2->size * sizeof(bigDigitType));
          memset(&factor2_help->bigdigits[factor2->size], 0,
                 (size_t) (factor2_help->size - factor2->size) * sizeof(bigDigitType));
          factor2 = factor2_help;
          if (likely(ALLOC_BIG(product, (factor1->size >> 1) + (factor2->size << 1)))) {
            product->size = (factor1->size >> 1) + (factor2->size << 1);
            if (unlikely(!ALLOC_BIG(temp, factor1->size << 2))) {
              FREE_BIG(product, (factor1->size >> 1) + (factor2->size << 1));
              product = NULL;
            } else {
              uBigKaratsubaMult(factor1->bigdigits, factor2->bigdigits,
                                factor1->size >> 1, product->bigdigits, temp->bigdigits);
              uBigKaratsubaMult(&factor1->bigdigits[factor1->size >> 1], factor2->bigdigits,
                                factor2->size, temp->bigdigits,
                                &temp->bigdigits[factor2->size << 1]);
              memset(&product->bigdigits[(factor1->size >> 1) << 1], 0,
                     (size_t) (product->size - ((factor1->size >> 1) << 1)) * sizeof(bigDigitType));
              uBigDigitAddTo(&product->bigdigits[factor1->size >> 1],
                             product->size - (factor1->size >> 1),
                             temp->bigdigits, factor2->size << 1);
              if (negative) {
                negate_positive_big(product);
              } /* if */
              product = normalize(product);
              FREE_BIG(temp, factor1->size << 2);
            } /* if */
          } /* if */
          FREE_BIG(factor2_help, factor1->size - (factor1->size >> 1));
        } /* if */
      } else {
        if (unlikely(!ALLOC_BIG_SIZE_OK(factor2_help, factor1->size))) {
          product = NULL;
        } else {
          factor2_help->size = factor1->size;
          memcpy(factor2_help->bigdigits, factor2->bigdigits,
                 (size_t) factor2->size * sizeof(bigDigitType));
          memset(&factor2_help->bigdigits[factor2->size], 0,
                 (size_t) (factor2_help->size - factor2->size) * sizeof(bigDigitType));
          factor2 = factor2_help;
          if (likely(ALLOC_BIG(product, factor1->size << 1))) {
            if (unlikely(!ALLOC_BIG(temp, factor1->size << 2))) {
              FREE_BIG(product, factor1->size << 1);
              product = NULL;
            } else {
              uBigKaratsubaMult(factor1->bigdigits, factor2->bigdigits,
                  factor1->size, product->bigdigits, temp->bigdigits);
              product->size = factor1->size << 1;
              if (negative) {
                negate_positive_big(product);
              } /* if */
              product = normalize(product);
              FREE_BIG(temp, factor1->size << 2);
            } /* if */
          } /* if */
          FREE_BIG(factor2_help, factor1->size);
        } /* if */
      } /* if */
    } else {
      if (likely(ALLOC_BIG(product, factor1->size + factor2->size))) {
        product->size = factor1->size + factor2->size;
        uBigMult(factor1, factor2, product);
        if (negative) {
          negate_positive_big(product);
        } /* if */
        product = normalize(product);
      } /* if */
    } /* if */
    logFunction(printf("uBigMultK -> size= " FMT_U_MEM "\n", product->size););
    return product;
  } /* uBigMultK */



/**
 *  Square an unsigned big integer with the Karatsuba multiplication.
 *  @return the square, and NULL if there is not enough memory.
 */
static bigIntType uBigSquareK (const_bigIntType big1)

  {
    bigIntType temp;
    bigIntType square;

  /* uBigSquareK */
    logFunction(printf("uBigSquareK(size= " FMT_U_MEM ")\n",
                       big1->size););
    if (big1->size >= KARATSUBA_SQUARE_THRESHOLD) {
      if (likely(ALLOC_BIG(square, big1->size << 1))) {
        if (unlikely(!ALLOC_BIG(temp, big1->size << 2))) {
          FREE_BIG(square, big1->size << 1);
          square = NULL;
        } else {
          uBigKaratsubaSquare(big1->bigdigits, big1->size,
              square->bigdigits, temp->bigdigits);
          square->size = big1->size << 1;
          square = normalize(square);
          FREE_BIG(temp, big1->size << 2);
        } /* if */
      } /* if */
    } else {
      if (likely(ALLOC_BIG(square, big1->size + big1->size))) {
        square->size = big1->size + big1->size;
        uBigDigitSquare(big1->bigdigits, big1->size, square->bigdigits);
        square = normalize(square);
      } /* if */
    } /* if */
    logFunction(printf("uBigSquareK -> size= " FMT_U_MEM "\n", square->size););
    return square;
  } /* uBigSquareK */



/**
 *  Computes base to the power of exponent for signed big integers.
 *  It is assumed that the exponent and base both are >= 1.
 *  The result variable is set to base or 1 depending on the
 *  rightmost bit of the exponent. After that the base is
 *  squared in a loop and every time the corresponding bit of
 *  the exponent is set the current square is multiplied
 *  with the result variable. This reduces the number of square
 *  operations to ld(exponent).
 */
static bigIntType bigIPowN (const bigDigitType base, intType exponent)

  {
    bigIntType square;
    bigIntType big_help;
    bigIntType power;

  /* bigIPowN */
    logFunction(printf("bigIPowN(" FMT_U_DIG ", " FMT_D ")\n",
                       base, exponent););
    if (unlikely(!ALLOC_BIG_SIZE_OK(square, 1))) {
      raise_error(MEMORY_ERROR);
      power = NULL;
    } else if (unlikely(!ALLOC_BIG_SIZE_OK(power, 1))) {
      FREE_BIG(square, 1);
      raise_error(MEMORY_ERROR);
    } else {
      square->size = 1;
      square->bigdigits[0] = base;
      power->size = 1;
      if (exponent & 1) {
        power->bigdigits[0] = base;
      } else {
        power->bigdigits[0] = 1;
      } /* if */
      exponent >>= 1;
      while (exponent != 0 && square != NULL && power != NULL) {
        big_help = square;
        square = uBigSquareK(square);
        FREE_BIG(big_help, big_help->size);
        if (square != NULL) {
          if (exponent & 1) {
            big_help = power;
            power = uBigMultK(power, square, FALSE);
            FREE_BIG(big_help, big_help->size);
          } /* if */
          exponent >>= 1;
        } /* if */
      } /* while */
      if (unlikely(square == NULL)) {
        if (power != NULL) {
          FREE_BIG(power, power->size);
        } /* if */
        raise_error(MEMORY_ERROR);
        power = NULL;
      } else {
        FREE_BIG(square, square->size);
        if (unlikely(power == NULL)) {
          raise_error(MEMORY_ERROR);
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigIPowN --> power->size=" FMT_U_MEM "\n",
                       power != NULL ? power->size : 0););
    return power;
  } /* bigIPowN */



/**
 *  Computes base to the power of exponent for signed big integers.
 *  It is assumed that the exponent is >= 1.
 *  The function recognizes the special case of base with a value
 *  of a power of two. In this case the function bigLog2BaseIPow is
 *  used.
 */
static bigIntType bigIPow1 (bigDigitType base, intType exponent)

  {
    boolType negative;
    unsigned int bit_size;
    bigIntType power;

  /* bigIPow1 */
    logFunction(printf("bigIPow1(" FMT_D_DIG ", " FMT_D ")\n",
                       base, exponent););
    if (base == 0) {
      if (unlikely(!ALLOC_BIG_SIZE_OK(power, 1))) {
        raise_error(MEMORY_ERROR);
        power = NULL;
      } else {
        power->size = 1;
        power->bigdigits[0] = 0;
      } /* if */
    } else {
      if (IS_NEGATIVE(base)) {
        /* The unsigned value is negated to avoid a signed integer */
        /* overflow if the smallest signed integer is negated.     */
        base = -base;
        negative = (boolType) (exponent & 1);
      } else {
        negative = FALSE;
      } /* if */
      bit_size = (unsigned int) (digitMostSignificantBit(base) + 1);
      if (base == (bigDigitType) (1 << (bit_size - 1))) {
        power = bigLog2BaseIPow((intType) (bit_size - 1), exponent);
        if (power != NULL) {
          if (negative) {
            negate_positive_big(power);
            power = normalize(power);
          } /* if */
        } /* if */
      } else {
        power = bigIPowN(base, exponent);
        if (power != NULL) {
          if (negative) {
            negate_positive_big(power);
          } /* if */
          power = normalize(power);
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigIPow1 --> power->size=" FMT_U_MEM "\n",
                       power != NULL ? power->size : 0););
    return power;
  } /* bigIPow1 */



static int uBigIsNot0 (const const_bigIntType big)

  {
    memSizeType pos = 0;

  /* uBigIsNot0 */
    do {
      if (big->bigdigits[pos] != 0) {
        return TRUE;
      } /* if */
      pos++;
    } while (pos < big->size);
    return FALSE;
  } /* uBigIsNot0 */



/**
 *  Compute the absolute value of a 'bigInteger' number.
 *  @return the absolute value.
 *  @exception MEMORY_ERROR Not enough memory to create the result.
 */
bigIntType bigAbs (const const_bigIntType big1)

  {
    memSizeType pos;
    doubleBigDigitType carry = 1;
    memSizeType absoluteValue_size;
    bigIntType resized_absoluteValue;
    bigIntType absoluteValue;

  /* bigAbs */
    logFunction(printf("bigAbs(%s)\n", bigHexCStri(big1)););
    if (unlikely(!ALLOC_BIG_SIZE_OK(absoluteValue, big1->size))) {
      raise_error(MEMORY_ERROR);
    } else {
      absoluteValue->size = big1->size;
      if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
        pos = 0;
        do {
          carry += ~big1->bigdigits[pos] & BIGDIGIT_MASK;
          absoluteValue->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
          pos++;
        } while (pos < big1->size);
        if (IS_NEGATIVE(absoluteValue->bigdigits[pos - 1])) {
          absoluteValue_size = absoluteValue->size + 1;
          REALLOC_BIG_CHECK_SIZE(resized_absoluteValue, absoluteValue,
                                 big1->size, absoluteValue_size);
          if (unlikely(resized_absoluteValue == NULL)) {
            FREE_BIG(absoluteValue, big1->size);
            raise_error(MEMORY_ERROR);
            absoluteValue = NULL;
          } else {
            absoluteValue = resized_absoluteValue;
            COUNT3_BIG(big1->size, absoluteValue->size);
            absoluteValue->size = absoluteValue_size;
            absoluteValue->bigdigits[big1->size] = 0;
          } /* if */
        } /* if */
      } else {
        memcpy(absoluteValue->bigdigits, big1->bigdigits,
               (size_t) big1->size * sizeof(bigDigitType));
      } /* if */
    } /* if */
    logFunction(printf("bigAbs --> %s\n", bigHexCStri(absoluteValue)););
    return absoluteValue;
  } /* bigAbs */



/**
 *  Compute the absolute value of a 'bigInteger' number.
 *  Big1 is assumed to be a temporary value which is reused.
 *  @return the absolute value.
 *  @exception MEMORY_ERROR Not enough memory to create the result.
 */
bigIntType bigAbsTemp (bigIntType big1)

  {
    memSizeType pos;
    doubleBigDigitType carry = 1;
    boolType negative;
    bigIntType resized_big1;

  /* bigAbsTemp */
    logFunction(printf("bigAbsTemp(%s)\n", bigHexCStri(big1)););
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    if (negative) {
      pos = 0;
      do {
        carry += ~big1->bigdigits[pos] & BIGDIGIT_MASK;
        big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos++;
      } while (pos < big1->size);
      if (IS_NEGATIVE(big1->bigdigits[pos - 1])) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, pos, pos + 1);
        if (unlikely(resized_big1 == NULL)) {
          FREE_BIG(big1, pos);
          raise_error(MEMORY_ERROR);
          big1 = NULL;
        } else {
          big1 = resized_big1;
          COUNT3_BIG(pos, pos + 1);
          big1->size++;
          big1->bigdigits[pos] = 0;
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigAbsTemp --> %s\n", bigHexCStri(big1)););
    return big1;
  } /* bigAbsTemp */



/**
 *  Add two 'bigInteger' numbers.
 *  The function sorts the two values by size. This way there is a
 *  loop up to the shorter size and a second loop up to the longer size.
 *  @return the sum of the two numbers.
 *  @exception MEMORY_ERROR Not enough memory to create the result.
 */
bigIntType bigAdd (const_bigIntType summand1, const_bigIntType summand2)

  {
    const_bigIntType help_big;
    memSizeType pos;
    doubleBigDigitType carry = 0;
    doubleBigDigitType summand2_sign;
    bigIntType sum;

  /* bigAdd */
    logFunction(printf("bigAdd(%s,", bigHexCStri(summand1));
                printf("%s)\n", bigHexCStri(summand2)););
    if (summand2->size > summand1->size) {
      help_big = summand1;
      summand1 = summand2;
      summand2 = help_big;
    } /* if */
    if (unlikely(!ALLOC_BIG_CHECK_SIZE(sum, summand1->size + 1))) {
      raise_error(MEMORY_ERROR);
    } else {
      pos = 0;
      do {
        carry += (doubleBigDigitType) summand1->bigdigits[pos] + summand2->bigdigits[pos];
        sum->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos++;
      } while (pos < summand2->size);
      summand2_sign = IS_NEGATIVE(summand2->bigdigits[pos - 1]) ? BIGDIGIT_MASK : 0;
      for (; pos < summand1->size; pos++) {
        carry += summand1->bigdigits[pos] + summand2_sign;
        sum->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
      } /* for */
      if (IS_NEGATIVE(summand1->bigdigits[pos - 1])) {
        summand2_sign--;
      } /* if */
      sum->bigdigits[pos] = (bigDigitType) ((carry + summand2_sign) & BIGDIGIT_MASK);
      sum->size = pos + 1;
      sum = normalize(sum);
    } /* if */
    logFunction(printf("bigAdd --> %s\n", bigHexCStri(sum)););
    return sum;
  } /* bigAdd */



/**
 *  Increment a 'bigInteger' variable by a delta.
 *  Adds delta to *big_variable. The operation is done in
 *  place and *big_variable is only resized if necessary.
 *  If the size of delta is smaller than *big_variable the
 *  algorithm tries to save computations. Therefore there are
 *  checks for carry == 0 and carry != 0.
 *  In case the resizing fails the content of *big_variable
 *  is freed and *big_variable is set to NULL.
 *  @param delta The delta to be added to *big_variable.
 *  @exception MEMORY_ERROR If the resizing of *big_variable fails.
 */
void bigAddAssign (bigIntType *const big_variable, const const_bigIntType delta)

  {
    bigIntType big1;
    memSizeType pos;
    memSizeType big1_size;
    boolType delta_negative;
    doubleBigDigitType carry = 0;
    doubleBigDigitType big1_sign;
    doubleBigDigitType delta_sign;
    bigIntType resized_big1;

  /* bigAddAssign */
    logFunction(printf("bigAddAssign(%s,", bigHexCStri(*big_variable));
                printf("%s)\n", bigHexCStri(delta)););
    big1 = *big_variable;
    if (big1->size >= delta->size) {
      big1_size = big1->size;
      big1_sign = IS_NEGATIVE(big1->bigdigits[big1_size - 1]) ? BIGDIGIT_MASK : 0;
      /* It is possible that big1 == delta holds. Therefore the check */
      /* for negative delta must be done before big1 is changed.      */
      delta_negative = IS_NEGATIVE(delta->bigdigits[delta->size - 1]);
      pos = 0;
      do {
        carry += (doubleBigDigitType) big1->bigdigits[pos] + delta->bigdigits[pos];
        big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos++;
      } while (pos < delta->size);
      if (delta_negative) {
        for (; carry == 0 && pos < big1_size; pos++) {
          carry = (doubleBigDigitType) big1->bigdigits[pos] + BIGDIGIT_MASK;
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
        carry += BIGDIGIT_MASK;
      } else {
        for (; carry != 0 && pos < big1_size; pos++) {
          carry += big1->bigdigits[pos];
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
      } /* if */
      carry += big1_sign;
      carry &= BIGDIGIT_MASK;
      /* Now the only possible values for carry are 0 and BIGDIGIT_MASK. */
      if ((carry != 0 || IS_NEGATIVE(big1->bigdigits[big1_size - 1])) &&
          (carry != BIGDIGIT_MASK || !IS_NEGATIVE(big1->bigdigits[big1_size - 1]))) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, big1_size, big1_size + 1);
        if (unlikely(resized_big1 == NULL)) {
          FREE_BIG(big1, big1_size);
          *big_variable = NULL;
          raise_error(MEMORY_ERROR);
        } else {
          /* It is possible that big1 == delta holds. Since */
          /* 'delta' is not used after realloc() enlarged   */
          /* 'big1' a correction of delta is not necessary. */
          big1 = resized_big1;
          COUNT3_BIG(big1_size, big1_size + 1);
          big1->size++;
          big1->bigdigits[big1_size] = (bigDigitType) (carry);
          *big_variable = big1;
        } /* if */
      } else {
        *big_variable = normalize(big1);
      } /* if */
    } else {
      REALLOC_BIG_CHECK_SIZE(resized_big1, big1, big1->size, delta->size + 1);
      if (unlikely(resized_big1 == NULL)) {
        FREE_BIG(big1, big1->size);
        *big_variable = NULL;
        raise_error(MEMORY_ERROR);
      } else {
        big1 = resized_big1;
        COUNT3_BIG(big1->size, delta->size + 1);
        big1_sign = IS_NEGATIVE(big1->bigdigits[big1->size - 1]) ? BIGDIGIT_MASK : 0;
        pos = 0;
        do {
          carry += (doubleBigDigitType) big1->bigdigits[pos] + delta->bigdigits[pos];
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
          pos++;
        } while (pos < big1->size);
        delta_sign = IS_NEGATIVE(delta->bigdigits[delta->size - 1]) ? BIGDIGIT_MASK : 0;
        for (; pos < delta->size; pos++) {
          carry += big1_sign + delta->bigdigits[pos];
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
        carry += big1_sign + delta_sign;
        big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        big1->size = pos + 1;
        *big_variable = normalize(big1);
      } /* if */
    } /* if */
    logFunction(printf("bigAddAssign --> %s\n", bigHexCStri(*big_variable)););
  } /* bigAddAssign */



/**
 *  Increment a 'bigInteger' variable by a delta.
 *  Adds delta to *big_variable. The operation is done in
 *  place and *big_variable is only resized if necessary.
 *  In case the resizing fails the content of *big_variable
 *  is freed and *big_variable is set to NULL.
 *  @param delta The delta to be added to *big_variable.
 *         Delta must be in the range of signedBigDigitType.
 *  @exception MEMORY_ERROR If the resizing of *big_variable fails.
 */
void bigAddAssignSignedDigit (bigIntType *const big_variable, const intType delta)

  {
    bigIntType big1;
    memSizeType pos;
    memSizeType big1_size;
    doubleBigDigitType carry = 0;
    doubleBigDigitType big1_sign;
    bigIntType resized_big1;

  /* bigAddAssignSignedDigit */
    logFunction(printf("bigAddAssignSignedDigit(%s, " FMT_D ")\n",
                       bigHexCStri(*big_variable), delta););
    big1 = *big_variable;
    big1_sign = IS_NEGATIVE(big1->bigdigits[big1->size - 1]) ? BIGDIGIT_MASK : 0;
    carry += (doubleBigDigitType) big1->bigdigits[0] + (bigDigitType) (delta & BIGDIGIT_MASK);
    big1->bigdigits[0] = (bigDigitType) (carry & BIGDIGIT_MASK);
    carry >>= BIGDIGIT_SIZE;
    pos = 1;
    if (delta < 0) {
      for (; carry == 0 && pos < big1->size; pos++) {
        carry = (doubleBigDigitType) big1->bigdigits[pos] + BIGDIGIT_MASK;
        big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
      } /* for */
      carry += BIGDIGIT_MASK;
    } else {
      for (; carry != 0 && pos < big1->size; pos++) {
        carry += big1->bigdigits[pos];
        big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
      } /* for */
    } /* if */
    big1_size = big1->size;
    carry += big1_sign;
    carry &= BIGDIGIT_MASK;
    if ((carry != 0 || IS_NEGATIVE(big1->bigdigits[big1_size - 1])) &&
        (carry != BIGDIGIT_MASK || !IS_NEGATIVE(big1->bigdigits[big1_size - 1]))) {
      REALLOC_BIG_CHECK_SIZE(resized_big1, big1, big1_size, big1_size + 1);
      if (unlikely(resized_big1 == NULL)) {
        FREE_BIG(big1, big1_size);
        *big_variable = NULL;
        raise_error(MEMORY_ERROR);
      } else {
        big1 = resized_big1;
        COUNT3_BIG(big1_size, big1_size + 1);
        big1->size++;
        big1->bigdigits[big1_size] = (bigDigitType) (carry & BIGDIGIT_MASK);
        *big_variable = big1;
      } /* if */
    } else {
      *big_variable = normalize(big1);
    } /* if */
    logFunction(printf("bigAddAssignSignedDigit --> %s\n",
                       bigHexCStri(*big_variable)););
  } /* bigAddAssignSignedDigit */



/**
 *  Add two 'bigInteger' numbers.
 *  Summand1 is assumed to be a temporary value which is reused.
 *  @return the sum of the two numbers in 'summand1'.
 */
bigIntType bigAddTemp (bigIntType summand1, const const_bigIntType summand2)

  { /* bigAddTemp */
    bigAddAssign(&summand1, summand2);
    return summand1;
  } /* bigAddTemp */



bigIntType bigAnd (const_bigIntType big1, const_bigIntType big2)

  {
    const_bigIntType help_big;
    memSizeType pos;
    bigDigitType big2_sign;
    bigIntType result;

  /* bigAnd */
    logFunction(printf("bigAnd(%s,", bigHexCStri(big1));
                printf("%s)\n", bigHexCStri(big2)););
    if (big2->size > big1->size) {
      help_big = big1;
      big1 = big2;
      big2 = help_big;
    } /* if */
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, big1->size))) {
      raise_error(MEMORY_ERROR);
    } else {
      pos = 0;
      do {
        result->bigdigits[pos] = big1->bigdigits[pos] & big2->bigdigits[pos];
        pos++;
      } while (pos < big2->size);
      big2_sign = IS_NEGATIVE(big2->bigdigits[pos - 1]) ? BIGDIGIT_MASK : 0;
      for (; pos < big1->size; pos++) {
        result->bigdigits[pos] = big1->bigdigits[pos] & big2_sign;
      } /* for */
      result->size = pos;
      result = normalize(result);
    } /* if */
    logFunction(printf("bigAnd --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigAnd */



#ifdef OUT_OF_ORDER
bigIntType bigBinom (bigIntType n_number, bigIntType k_number)

  {
    bigIntType number;
    bigIntType result;

  /* bigBinom */
    if (2 * k_number > n_number) {
      k_number = n_number - k_number;
    } /* if */
    if (k_number < 0) {
      result = 0;
    } else if (k_number == 0) {
      result = 1;
    } else {
      result = n_number;
      for (number = 2; number <= k_number; number++) {
        result *= (n_number - number + 1);
        result /= number;
      } /* for */
    } /* if */
    return (intType) result;
  } /* bigBinom */
#endif



/**
 *  Number of bits in the minimum two's-complement representation.
 *  The high bits equivalent to the sign bit are not part of the
 *  minimum two's-complement representation.
 *  @return the number of bits.
 *  @exception RANGE_ERROR The result does not fit into an integer.
 */
intType bigBitLength (const const_bigIntType big1)

  {
    intType bitLength;

  /* bigBitLength */
    logFunction(printf("bigBitLength(%s)\n", bigHexCStri(big1)););
    if (unlikely(big1->size >= MAX_MEM_INDEX >> BIGDIGIT_LOG2_SIZE)) {
      logError(printf("bigBitLength(%s): "
                      "Result does not fit into an integer.\n",
                      bigHexCStri(big1)););
      raise_error(RANGE_ERROR);
      bitLength = 0;
    } else {
      bitLength = (intType) ((big1->size - 1) << BIGDIGIT_LOG2_SIZE);
      if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
        bitLength += digitMostSignificantBit(~big1->bigdigits[big1->size - 1]) + 1;
      } else {
        bitLength += digitMostSignificantBit(big1->bigdigits[big1->size - 1]) + 1;
      } /* if */
    } /* if */
    logFunction(printf("bigBitLength --> " FMT_D "\n", bitLength););
    return bitLength;
  } /* bigBitLength */



/**
 *  Compare two 'bigInteger' numbers.
 *  @return -1, 0 or 1 if the first argument is considered to be
 *          respectively less than, equal to, or greater than the
 *          second.
 */
intType bigCmp (const const_bigIntType big1, const const_bigIntType big2)

  {
    boolType big1_negative;
    boolType big2_negative;
    memSizeType pos;

  /* bigCmp */
    pos = big1->size;
    big1_negative = IS_NEGATIVE(big1->bigdigits[pos - 1]);
    big2_negative = IS_NEGATIVE(big2->bigdigits[big2->size - 1]);
    if (big1_negative != big2_negative) {
      return big1_negative ? -1 : 1;
    } else if (pos != big2->size) {
      return (pos < big2->size) != big1_negative ? -1 : 1;
    } else {
      do {
        pos--;
        if (big1->bigdigits[pos] != big2->bigdigits[pos]) {
          return big1->bigdigits[pos] < big2->bigdigits[pos] ? -1 : 1;
        } /* if */
      } while (pos > 0);
      return 0;
    } /* if */
  } /* bigCmp */



/**
 *  Reinterpret the generic parameters as bigIntType and call bigCmp.
 *  Function pointers in C programs generated by the Seed7 compiler
 *  may point to this function. This assures correct behaviour even
 *  if sizeof(genericType) != sizeof(bigIntType).
 *  @return -1, 0 or 1 if the first argument is considered to be
 *          respectively less than, equal to, or greater than the
 *          second.
 */
intType bigCmpGeneric (const genericType value1, const genericType value2)

  { /* bigCmpGeneric */
    return bigCmp(((const_rtlObjectType *) &value1)->value.bigIntValue,
                  ((const_rtlObjectType *) &value2)->value.bigIntValue);
  } /* bigCmpGeneric */



/**
 *  Compare 'big1' with the bigdigit 'number'.
 *  The range of 'number' is restricted and it is the job of the
 *  compiler to assure that 'number' is within the allowed range.
 *  @param number Number that must be in the range of
 *         signedBigDigitType.
 *  @return -1, 0 or 1 if the first argument is considered to be
 *          respectively less than, equal to, or greater than the
 *          second.
 */
intType bigCmpSignedDigit (const const_bigIntType big1, intType number)

  {
    intType signumValue;

  /* bigCmpSignedDigit */
    if (number < 0) {
      if (!IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
        signumValue = 1;
      } else if (big1->size != 1) {
        signumValue = -1;
      } else if (big1->bigdigits[0] < (bigDigitType) number) {
        signumValue = -1;
      } else {
        signumValue = big1->bigdigits[0] > (bigDigitType) number;
      } /* if */
    } else {
      if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
        signumValue = -1;
      } else if (big1->size != 1) {
        signumValue = 1;
      } else if (big1->bigdigits[0] < (bigDigitType) number) {
        signumValue = -1;
      } else {
        signumValue = big1->bigdigits[0] > (bigDigitType) number;
      } /* if */
    } /* if */
    return signumValue;
  } /* bigCmpSignedDigit */



/**
 *  Assign source to *dest.
 *  A copy function assumes that *dest contains a legal value.
 *  @exception MEMORY_ERROR Not enough memory to create dest.
 */
void bigCpy (bigIntType *const dest, const const_bigIntType source)

  {
    memSizeType new_size;
    bigIntType big_dest;

  /* bigCpy */
    big_dest = *dest;
    new_size = source->size;
    if (big_dest->size != new_size) {
      if (unlikely(!ALLOC_BIG_SIZE_OK(big_dest, new_size))) {
        raise_error(MEMORY_ERROR);
        return;
      } else {
        FREE_BIG(*dest, (*dest)->size);
        big_dest->size = new_size;
        *dest = big_dest;
      } /* if */
    } /* if */
    /* It is possible that *dest == source holds. The    */
    /* behavior of memcpy() is undefined if source and   */
    /* destination areas overlap (or are identical).     */
    /* Therefore memmove() is used instead of memcpy().  */
    memmove(big_dest->bigdigits, source->bigdigits,
            (size_t) new_size * sizeof(bigDigitType));
  } /* bigCpy */



/**
 *  Reinterpret the generic parameters as bigIntType and call bigCpy.
 *  Function pointers in C programs generated by the Seed7 compiler
 *  may point to this function. This assures correct behaviour even
 *  if sizeof(genericType) != sizeof(bigIntType).
 */
void bigCpyGeneric (genericType *const dest, const genericType source)

  { /* bigCpyGeneric */
    bigCpy(&((rtlObjectType *) dest)->value.bigIntValue,
           ((const_rtlObjectType *) &source)->value.bigIntValue);
  } /* bigCpyGeneric */



/**
 *  Return a copy of source, that can be assigned to a new destination.
 *  It is assumed that the destination of the assignment is undefined.
 *  Create functions can be used to initialize Seed7 constants.
 *  @return a copy of source.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigCreate (const const_bigIntType source)

  {
    memSizeType new_size;
    bigIntType result;

  /* bigCreate */
    new_size = source->size;
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, new_size))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = new_size;
      memcpy(result->bigdigits, source->bigdigits,
             (size_t) new_size * sizeof(bigDigitType));
    } /* if */
    return result;
  } /* bigCreate */



/**
 *  Generic Create function to be used via function pointers.
 *  Function pointers in C programs generated by the Seed7 compiler
 *  may point to this function. This assures correct behaviour even
 *  if sizeof(genericType) != sizeof(bigIntType).
 */
genericType bigCreateGeneric (const genericType source)

  {
    rtlObjectType result;

  /* bigCreateGeneric */
    INIT_GENERIC_PTR(result.value.genericValue);
    result.value.bigIntValue =
        bigCreate(((const_rtlObjectType *) &source)->value.bigIntValue);
    return result.value.genericValue;
  } /* bigCreateGeneric */



/**
 *  Decrement a 'bigInteger' variable.
 *  Decrements *big_variable by 1. The operation is done in
 *  place and *big_variable is only enlarged if necessary.
 *  In case the enlarging fails the old content of *big_variable
 *  is restored and the exception MEMORY_ERROR is raised.
 *  This ensures that bigDecr works as a transaction.
 *  @exception MEMORY_ERROR If the resizing of *big_variable fails.
 */
void bigDecr (bigIntType *const big_variable)

  {
    bigIntType big1;
    memSizeType pos;
    boolType negative;
    bigIntType resized_big1;

  /* bigDecr */
    logFunction(printf("bigDecr(%s)\n", bigHexCStri(*big_variable)););
    big1 = *big_variable;
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    pos = 0;
    if (big1->bigdigits[pos] == 0) {
      if (big1->size == 1) {
        big1->bigdigits[pos] = BIGDIGIT_MASK;
        pos++;
      } else {
        do {
          big1->bigdigits[pos] = BIGDIGIT_MASK;
          pos++;
        } while (big1->bigdigits[pos] == 0);
        /* memset(big1->bigdigits, 0xFF, pos * sizeof(bigDigitType)); */
      } /* if */
    } /* if */
    if (pos < big1->size) {
      big1->bigdigits[pos]--;
    } /* if */
    pos = big1->size;
    if (!IS_NEGATIVE(big1->bigdigits[pos - 1])) {
      if (negative) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, pos, pos + 1);
        if (unlikely(resized_big1 == NULL)) {
          /* This error situation is very unlikely, but we need to */
          /* make sure that 'big_variable' contains a legal value. */
          /* We UNDO the change done for 'big_variable' by setting */
          /* it to the old value: The highest bit is set to 1 and  */
          /* the other bits are set to 0. Note that only values    */
          /* with this pattern need an additional digit if they    */
          /* are decremented.                                      */
          pos--;
          big1->bigdigits[pos] = BIGDIGIT_SIGN;
          while (pos != 0) {
            pos--;
            big1->bigdigits[pos] = 0;
          } /* while */
          raise_error(MEMORY_ERROR);
        } else {
          big1 = resized_big1;
          COUNT3_BIG(pos, pos + 1);
          big1->size++;
          big1->bigdigits[pos] = BIGDIGIT_MASK;
          *big_variable = big1;
        } /* if */
      } else if (big1->bigdigits[pos - 1] == 0 &&
          pos >= 2 && !IS_NEGATIVE(big1->bigdigits[pos - 2])) {
        REALLOC_BIG_SIZE_OK(resized_big1, big1, pos, pos - 1);
        /* Avoid a MEMORY_ERROR in the strange case   */
        /* if a 'realloc' which shrinks memory fails. */
        if (likely(resized_big1 != NULL)) {
          big1 = resized_big1;
          *big_variable = big1;
        } /* if */
        COUNT3_BIG(pos, pos - 1);
        big1->size--;
      } /* if */
    } /* if */
    logFunction(printf("bigDecr --> %s\n", bigHexCStri(*big_variable)););
  } /* bigDecr */



/**
 *  Free the memory referred by 'old_bigint'.
 *  After bigDestr is left 'old_bigint' refers to not existing memory.
 *  The memory where 'old_bigint' is stored can be freed afterwards.
 */
void bigDestr (const const_bigIntType old_bigint)

  { /* bigDestr */
    if (old_bigint != NULL) {
      FREE_BIG(old_bigint, old_bigint->size);
    } /* if */
  } /* bigDestr */



/**
 *  Generic Destr function to be used via function pointers.
 *  Function pointers in C programs generated by the Seed7 compiler
 *  may point to this function. This assures correct behaviour even
 *  if sizeof(genericType) != sizeof(bigIntType).
 */
void bigDestrGeneric (const genericType old_value)

  { /* bigDestrGeneric */
    bigDestr(((const_rtlObjectType *) &old_value)->value.bigIntValue);
  } /* bigDestrGeneric */



/**
 *  Integer division truncated towards zero.
 *  The remainder of this division is computed with bigRem.
 *  The memory for the result is requested and the normalized
 *  result is returned. If divisor has just one digit or if
 *  dividend has less digits than divisor the bigDiv1() or
 *  bigDivSizeLess() functions are called. In the general case
 *  the absolute values of dividend and divisor are taken. Then
 *  dividend is extended by one leading zero digit. After that
 *  dividend and divisor are shifted to the left such that the
 *  most significant bit of divisor is set. This fulfills the
 *  preconditions for calling uBigDiv() which does the main
 *  work of the division.
 *  @return the quotient of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
bigIntType bigDiv (const const_bigIntType dividend, const const_bigIntType divisor)

  {
    boolType negative = FALSE;
    bigIntType dividend_help;
    bigIntType divisor_help;
    unsigned int shift;
    bigIntType quotient;

  /* bigDiv */
    logFunction(printf("bigDiv(%s, ", bigHexCStri(dividend));
                printf("%s)\n", bigHexCStri(divisor)););
    if (divisor->size == 1) {
      quotient = bigDiv1(dividend, divisor->bigdigits[0]);
    } else if (dividend->size < divisor->size) {
      quotient = bigDivSizeLess(dividend, divisor);
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(dividend_help, dividend->size + 2))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          negative = TRUE;
          positive_copy_of_negative_big(dividend_help, dividend);
        } else {
          dividend_help->size = dividend->size;
          memcpy(dividend_help->bigdigits, dividend->bigdigits,
                 (size_t) dividend->size * sizeof(bigDigitType));
        } /* if */
        dividend_help->bigdigits[dividend_help->size] = 0;
        dividend_help->size++;
      } /* if */
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(divisor_help, divisor->size + 1))) {
        FREE_BIG(dividend_help, dividend->size + 2);
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(divisor->bigdigits[divisor->size - 1])) {
          negative = !negative;
          positive_copy_of_negative_big(divisor_help, divisor);
        } else {
          divisor_help->size = divisor->size;
          memcpy(divisor_help->bigdigits, divisor->bigdigits,
                 (size_t) divisor->size * sizeof(bigDigitType));
        } /* if */
      } /* if */
      if (unlikely(!ALLOC_BIG_SIZE_OK(quotient, dividend_help->size - divisor_help->size + 1))) {
        FREE_BIG(dividend_help, dividend->size + 2);
        FREE_BIG(divisor_help, divisor->size + 1);
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        quotient->size = dividend_help->size - divisor_help->size + 1;
        quotient->bigdigits[quotient->size - 1] = 0;
        shift = (unsigned int)
            (digitMostSignificantBit(divisor_help->bigdigits[divisor_help->size - 1]) + 1);
        if (shift == 0) {
          /* The most significant digit of divisor_help is 0. Just ignore it */
          dividend_help->size--;
          divisor_help->size--;
          if (divisor_help->size == 1) {
            uBigDiv1(dividend_help, divisor_help->bigdigits[0], quotient);
          } else {
            uBigDiv(dividend_help, divisor_help, quotient);
          } /* if */
        } else {
          shift = BIGDIGIT_SIZE - shift;
          uBigLShift(dividend_help, shift);
          uBigLShift(divisor_help, shift);
          uBigDiv(dividend_help, divisor_help, quotient);
        } /* if */
        if (negative) {
          negate_positive_big(quotient);
        } /* if */
        quotient = normalize(quotient);
      } /* if */
      FREE_BIG(dividend_help, dividend->size + 2);
      FREE_BIG(divisor_help, divisor->size + 1);
    } /* if */
    logFunction(printf("bigDiv --> %s\n", bigHexCStri(quotient)););
    return quotient;
  } /* bigDiv */



/**
 *  Integer division truncated towards zero.
 *  The memory for the quotient is requested and the normalized
 *  quotient is returned. The memory for the remainder is
 *  requested and the normalized remainder is assigned to
 *  *remainderAddr. If divisor has just one digit or if
 *  dividend has less digits than divisor the bigDivRem1() or
 *  bigDivRemSizeLess() functions are called. In the general case
 *  the absolute values of dividend and divisor are taken. Then
 *  dividend is extended by one leading zero digit. After that
 *  dividend and divisor are shifted to the left such that the
 *  most significant bit of divisor is set. This fulfills the
 *  preconditions for calling uBigDiv() which does the main
 *  work of the division.
 *  @return the quotient of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
bigIntType bigDivRem (const const_bigIntType dividend, const const_bigIntType divisor,
    bigIntType *remainderAddr)

  {
    boolType quotientNegative = FALSE;
    boolType remainderNegative = FALSE;
    bigIntType divisor_help;
    unsigned int shift;
    bigIntType quotient;
    bigIntType remainder;

  /* bigDivRem */
    logFunction(printf("bigDivRem(%s, ", bigHexCStri(dividend));
                printf("%s, *)\n", bigHexCStri(divisor)););
    if (divisor->size == 1) {
      quotient = bigDivRem1(dividend, divisor->bigdigits[0], remainderAddr);
    } else if (dividend->size < divisor->size) {
      quotient = bigDivRemSizeLess(dividend, divisor, remainderAddr);
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(remainder, dividend->size + 2))) {
        *remainderAddr = NULL;
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          quotientNegative = TRUE;
          remainderNegative = TRUE;
          positive_copy_of_negative_big(remainder, dividend);
        } else {
          remainder->size = dividend->size;
          memcpy(remainder->bigdigits, dividend->bigdigits,
                 (size_t) dividend->size * sizeof(bigDigitType));
        } /* if */
        remainder->bigdigits[remainder->size] = 0;
        remainder->size++;
      } /* if */
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(divisor_help, divisor->size + 1))) {
        FREE_BIG(remainder, dividend->size + 2);
        *remainderAddr = NULL;
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(divisor->bigdigits[divisor->size - 1])) {
          quotientNegative = !quotientNegative;
          positive_copy_of_negative_big(divisor_help, divisor);
        } else {
          divisor_help->size = divisor->size;
          memcpy(divisor_help->bigdigits, divisor->bigdigits,
                 (size_t) divisor->size * sizeof(bigDigitType));
        } /* if */
      } /* if */
      if (unlikely(!ALLOC_BIG_SIZE_OK(quotient, remainder->size - divisor_help->size + 1))) {
        FREE_BIG(remainder, dividend->size + 2);
        FREE_BIG(divisor_help, divisor->size + 1);
        *remainderAddr = NULL;
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        quotient->size = remainder->size - divisor_help->size + 1;
        quotient->bigdigits[quotient->size - 1] = 0;
        shift = (unsigned int)
            (digitMostSignificantBit(divisor_help->bigdigits[divisor_help->size - 1]) + 1);
        if (shift == 0) {
          /* The most significant digit of divisor_help is 0. Just ignore it */
          remainder->size--;
          divisor_help->size--;
          if (divisor_help->size == 1) {
            remainder->bigdigits[0] = uBigDivRem1(remainder, divisor_help->bigdigits[0], quotient);
            memset(&remainder->bigdigits[1], 0,
                   (size_t) (remainder->size - 1) * sizeof(bigDigitType));
          } else {
            uBigDiv(remainder, divisor_help, quotient);
          } /* if */
          remainder->bigdigits[remainder->size] = 0;
          divisor_help->size++;
        } else {
          shift = BIGDIGIT_SIZE - shift;
          uBigLShift(remainder, shift);
          uBigLShift(divisor_help, shift);
          uBigDiv(remainder, divisor_help, quotient);
          uBigRShift(remainder, shift);
        } /* if */
        remainder->bigdigits[dividend->size + 1] = 0;
        remainder->size = dividend->size + 2;
        if (quotientNegative) {
          negate_positive_big(quotient);
        } /* if */
        quotient = normalize(quotient);
        if (remainderNegative) {
          negate_positive_big(remainder);
        } /* if */
        remainder = normalize(remainder);
      } /* if */
      FREE_BIG(divisor_help, divisor->size + 1);
      *remainderAddr = remainder;
    } /* if */
    logFunction(printf("bigDivRem --> %s", bigHexCStri(quotient));
                printf(" (%s)\n", bigHexCStri(*remainderAddr)););
    return quotient;
  } /* bigDivRem */



/**
 *  Check if two 'bigInteger' numbers are equal.
 *  @return TRUE if both numbers are equal,
 *          FALSE otherwise.
 */
boolType bigEq (const const_bigIntType big1, const const_bigIntType big2)

  { /* bigEq */
    if (big1->size == big2->size &&
      memcmp(big1->bigdigits, big2->bigdigits,
          (size_t) big1->size * sizeof(bigDigitType)) == 0) {
      return TRUE;
    } else {
      return FALSE;
    } /* if */
  } /* bigEq */



/**
 *  Check if 'big1' is equal to the bigdigit 'number'.
 *  The range of 'number' is restricted and it is the job of the
 *  compiler to assure that 'number' is within the allowed range.
 *  @param number Number that must be in the range of
 *         signedBigDigitType.
 *  @return TRUE if 'big1' and 'number' are equal,
 *          FALSE otherwise.
 */
boolType bigEqSignedDigit (const const_bigIntType big1, intType number)

  { /* bigEqSignedDigit */
    return big1->size == 1 && big1->bigdigits[0] == (bigDigitType) number;
  } /* bigEqSignedDigit */



/**
 *  Convert a byte buffer (interpreted as big-endian) to a bigInteger.
 *  @param size Size of the byte buffer to be converted (in bytes).
 *  @param buffer Byte buffer to be converted. The bytes are interpreted
 *         as binary big-endian representation with a base of 256.
 *  @param isSigned Defines if 'buffer' is interpreted as signed value.
 *         If 'isSigned' is TRUE the twos-complement representation
 *         is used. In this case the result is negative if the most
 *         significant byte (the first byte) has an ordinal > BYTE_MAX (=127).
 *  @return a bigInteger created from the big-endian bytes.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigFromByteBufferBe (const memSizeType size,
    const const_ustriType buffer, const boolType isSigned)

  {
    memSizeType byteIndex;
    memSizeType pos;
    memSizeType num_bigdigits;
    memSizeType result_size;
    ucharType buffer2[BIGDIGIT_SIZE >> 3];
    bigIntType result;

  /* bigFromByteBufferBe */
    logFunction(printf("bigFromByteBufferBe(" FMT_U_MEM ", 0x" FMT_X_MEM ", %d)\n",
                       size, (memSizeType) buffer, isSigned););
    if (size == 0) {
      num_bigdigits = 0;
      result_size = 1;
    } else {
      num_bigdigits = (size + (BIGDIGIT_SIZE >> 3) - 1) / (BIGDIGIT_SIZE >> 3);
      result_size = num_bigdigits;
      if (!isSigned && size % (BIGDIGIT_SIZE >> 3) == 0 && buffer[0] > BYTE_MAX) {
        /* The number is unsigned, but highest bit is one: */
        /* A leading zero bigdigit must be added.          */
        result_size++;
      } /* if */
    } /* if */
    if (unlikely(!ALLOC_BIG(result, result_size))) {
      raise_error(MEMORY_ERROR);
      return NULL;
    } else {
      result->size = result_size;
      if (num_bigdigits == 0) {
        result->bigdigits[0] = (bigDigitType) 0;
      } else {
        byteIndex = size;
        for (pos = 0; pos < num_bigdigits - 1; pos++) {
#if BIGDIGIT_SIZE == 8
          result->bigdigits[pos] =  (bigDigitType) buffer[byteIndex - 1];
          byteIndex--;
#elif BIGDIGIT_SIZE == 16
          result->bigdigits[pos] = ((bigDigitType) buffer[byteIndex - 2]) <<  8 |
                                    (bigDigitType) buffer[byteIndex - 1];
          byteIndex -= 2;
#elif BIGDIGIT_SIZE == 32
          result->bigdigits[pos] = ((bigDigitType) buffer[byteIndex - 4]) << 24 |
                                   ((bigDigitType) buffer[byteIndex - 3]) << 16 |
                                   ((bigDigitType) buffer[byteIndex - 2]) <<  8 |
                                    (bigDigitType) buffer[byteIndex - 1];
          byteIndex -= 4;
#endif
        } /* for */
        memcpy(&buffer2[(BIGDIGIT_SIZE >> 3) - byteIndex], buffer, byteIndex);
        if (isSigned && buffer[0] > BYTE_MAX) {
          memset(buffer2, 0xFF, (BIGDIGIT_SIZE >> 3) - byteIndex);
        } else {
          memset(buffer2, 0, (BIGDIGIT_SIZE >> 3) - byteIndex);
        } /* if */
#if BIGDIGIT_SIZE == 8
        result->bigdigits[pos] =  (bigDigitType) buffer2[0];
#elif BIGDIGIT_SIZE == 16
        result->bigdigits[pos] = ((bigDigitType) buffer2[0]) <<  8 |
                                  (bigDigitType) buffer2[1];
#elif BIGDIGIT_SIZE == 32
        result->bigdigits[pos] = ((bigDigitType) buffer2[0]) << 24 |
                                 ((bigDigitType) buffer2[1]) << 16 |
                                 ((bigDigitType) buffer2[2]) <<  8 |
                                  (bigDigitType) buffer2[3];
#endif
        if (num_bigdigits != result_size) {
          /* The number is unsigned, but highest bit is one: */
          /* A leading zero bigdigit must be added.          */
          result->bigdigits[num_bigdigits] = (bigDigitType) 0;
        } /* if */
      } /* if */
    } /* if */
    result = normalize(result);
    logFunction(printf("bigFromByteBufferBe --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigFromByteBufferBe */



/**
 *  Convert a byte buffer (interpreted as little-endian) to a bigInteger.
 *  @param size Size of the byte buffer to be converted (in bytes).
 *  @param buffer Byte buffer to be converted. The bytes are interpreted
 *         as binary little-endian representation with a base of 256.
 *  @param isSigned Defines if 'buffer' is interpreted as signed value.
 *         If 'isSigned' is TRUE the twos-complement representation
 *         is used. In this case the result is negative if the most
 *         significant byte (the last byte) has an ordinal > BYTE_MAX (=127).
 *  @return a bigInteger created from the little-endian bytes.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigFromByteBufferLe (const memSizeType size,
    const const_ustriType buffer, const boolType isSigned)

  {
    memSizeType byteIndex;
    memSizeType pos;
    memSizeType num_bigdigits;
    memSizeType result_size;
    ucharType buffer2[BIGDIGIT_SIZE >> 3];
    bigIntType result;

  /* bigFromByteBufferLe */
    logFunction(printf("bigFromByteBufferLe(" FMT_U_MEM ", 0x" FMT_X_MEM ", %d)\n",
                       size, (memSizeType) buffer, isSigned););
    if (size == 0) {
      num_bigdigits = 0;
      result_size = 1;
    } else {
      num_bigdigits = (size + (BIGDIGIT_SIZE >> 3) - 1) / (BIGDIGIT_SIZE >> 3);
      result_size = num_bigdigits;
      if (!isSigned && buffer[size - 1] > BYTE_MAX) {
        /* The number is unsigned, but highest bit is one: */
        /* A leading zero bigdigit must be added.          */
        result_size++;
      } /* if */
    } /* if */
    if (unlikely(!ALLOC_BIG(result, result_size))) {
      raise_error(MEMORY_ERROR);
      return NULL;
    } else {
      result->size = result_size;
      if (num_bigdigits == 0) {
        result->bigdigits[0] = (bigDigitType) 0;
      } else {
        byteIndex = 0;
        for (pos = 0; pos < num_bigdigits - 1; pos++) {
#if BIGDIGIT_SIZE == 8
          result->bigdigits[pos] =  (bigDigitType) buffer[byteIndex];
          byteIndex++;
#elif BIGDIGIT_SIZE == 16
          result->bigdigits[pos] = ((bigDigitType) buffer[byteIndex + 1]) <<  8 |
                                    (bigDigitType) buffer[byteIndex];
          byteIndex += 2;
#elif BIGDIGIT_SIZE == 32
          result->bigdigits[pos] = ((bigDigitType) buffer[byteIndex + 3]) << 24 |
                                   ((bigDigitType) buffer[byteIndex + 2]) << 16 |
                                   ((bigDigitType) buffer[byteIndex + 1]) <<  8 |
                                    (bigDigitType) buffer[byteIndex];
          byteIndex += 4;
#endif
        } /* for */
        memcpy(buffer2, &buffer[byteIndex], size - byteIndex);
        if (isSigned && buffer[size - 1] > BYTE_MAX) {
          memset(&buffer2[size - byteIndex], 0xFF, (BIGDIGIT_SIZE >> 3) - (size - byteIndex));
        } else {
          memset(&buffer2[size - byteIndex], 0, (BIGDIGIT_SIZE >> 3) - (size - byteIndex));
        } /* if */
#if BIGDIGIT_SIZE == 8
        result->bigdigits[pos] =  (bigDigitType) buffer2[0];
#elif BIGDIGIT_SIZE == 16
        result->bigdigits[pos] = ((bigDigitType) buffer2[1]) <<  8 |
                                  (bigDigitType) buffer2[0];
#elif BIGDIGIT_SIZE == 32
        result->bigdigits[pos] = ((bigDigitType) buffer2[3]) << 24 |
                                 ((bigDigitType) buffer2[2]) << 16 |
                                 ((bigDigitType) buffer2[1]) <<  8 |
                                  (bigDigitType) buffer2[0];
#endif
        if (num_bigdigits != result_size) {
          /* The number is unsigned, but highest bit is one: */
          /* A leading zero bigdigit must be added.          */
          result->bigdigits[num_bigdigits] = (bigDigitType) 0;
        } /* if */
      } /* if */
    } /* if */
    result = normalize(result);
    logFunction(printf("bigFromByteBufferLe --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigFromByteBufferLe */



/**
 *  Convert a bstring (interpreted as big-endian) to a bigInteger.
 *  @param bstri Bstring to be converted. The bytes are interpreted
 *         as binary big-endian representation with a base of 256.
 *  @param isSigned Defines if 'bstri' is interpreted as signed value.
 *         If 'isSigned' is TRUE the twos-complement representation
 *         is used. In this case the result is negative if the most
 *         significant byte (the first byte) has an ordinal > BYTE_MAX (=127).
 *  @return a bigInteger created from the big-endian bytes.
 */
bigIntType bigFromBStriBe (const const_bstriType bstri, const boolType isSigned)

  { /* bigFromBStriBe */
    logFunction(printf("bigFromBStriBe(\"%s\", %d)\n",
                       bstriAsUnquotedCStri(bstri), isSigned););
    return bigFromByteBufferBe(bstri->size, bstri->mem, isSigned);
  } /* bigFromBStriBe */



/**
 *  Convert a bstring (interpreted as little-endian) to a bigInteger.
 *  @param bstri Bstring to be converted. The bytes are interpreted
 *         as binary little-endian representation with a base of 256.
 *  @param isSigned Defines if 'bstri' is interpreted as signed value.
 *         If 'isSigned' is TRUE the twos-complement representation
 *         is used. In this case the result is negative if the most
 *         significant byte (the last byte) has an ordinal > BYTE_MAX (=127).
 *  @return a bigInteger created from the little-endian bytes.
 */
bigIntType bigFromBStriLe (const const_bstriType bstri, const boolType isSigned)

  { /* bigFromBStriLe */
    logFunction(printf("bigFromBStriLe(\"%s\", %d)\n",
                       bstriAsUnquotedCStri(bstri), isSigned););
    return bigFromByteBufferLe(bstri->size, bstri->mem, isSigned);
  } /* bigFromBStriLe */



/**
 *  Convert an int32Type number to 'bigInteger'.
 *  @return the bigInteger result of the conversion.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigFromInt32 (int32Type number)

  {
    memSizeType result_size;
    bigIntType result;

  /* bigFromInt32 */
    logFunction(printf("bigFromInt32(" FMT_D32 ")\n", number););
#if BIGDIGIT_SIZE < 32
    result_size = sizeof(int32Type) / (BIGDIGIT_SIZE >> 3);
#else
    result_size = 1;
#endif
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = result_size;
#if BIGDIGIT_SIZE <= 32
      result->bigdigits[0] = (bigDigitType) (((uint32Type) number) & BIGDIGIT_MASK);
#if BIGDIGIT_SIZE < 32
      {
        memSizeType pos;

        for (pos = 1; pos < result_size; pos++) {
          number >>= BIGDIGIT_SIZE;
          result->bigdigits[pos] = (bigDigitType) (((uint32Type) number) & BIGDIGIT_MASK);
        } /* for */
      }
#endif
#else
      if (number < 0) {
        result->bigdigits[0] = (bigDigitType) ((uint32Type) number) | (BIGDIGIT_MASK ^ 0xFFFFFFFF);
      } else {
        result->bigdigits[0] = (bigDigitType) ((uint32Type) number);
      } /* if */
#endif
#if BIGDIGIT_SIZE < 32
      result = normalize(result);
#endif
    } /* if */
    logFunction(printf("bigFromInt32 --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigFromInt32 */



#ifdef INT64TYPE
/**
 *  Convert an int64Type number to 'bigInteger'.
 *  @return the bigInteger result of the conversion.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigFromInt64 (int64Type number)

  {
    memSizeType pos;
    memSizeType result_size;
    bigIntType result;

  /* bigFromInt64 */
    logFunction(printf("bigFromInt64(" FMT_D64 ")\n", number););
    result_size = sizeof(int64Type) / (BIGDIGIT_SIZE >> 3);
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = result_size;
      for (pos = 0; pos < result_size; pos++) {
        result->bigdigits[pos] = (bigDigitType) (number & BIGDIGIT_MASK);
        number >>= BIGDIGIT_SIZE;
      } /* for */
      result = normalize(result);
    } /* if */
    logFunction(printf("bigFromInt64 --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigFromInt64 */
#endif



/**
 *  Convert an uint32Type number to 'bigInteger'.
 *  @return the bigInteger result of the conversion.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigFromUInt32 (uint32Type number)

  {
    memSizeType result_size;
    bigIntType result;

  /* bigFromUInt32 */
    logFunction(printf("bigFromUInt32(" FMT_U32 ")\n", number););
#if BIGDIGIT_SIZE == 32
    if (number > UINT32_SUFFIX(2147483647)) {
      result_size = 2;
    } else {
      result_size = 1;
    } /* if */
#elif BIGDIGIT_SIZE == 16
    if (number > UINT32_SUFFIX(2147483647)) {
      result_size = 3;
    } else if (number > UINT32_SUFFIX(32767)) {
      result_size = 2;
    } else {
      result_size = 1;
    } /* if */
#elif BIGDIGIT_SIZE == 8
    if (number > UINT32_SUFFIX(2147483647)) {
      result_size = 5;
    } else if (number > UINT32_SUFFIX(8388607)) {
      result_size = 4;
    } else if (number > UINT32_SUFFIX(32767)) {
      result_size = 3;
    } else if (number > UINT32_SUFFIX(127)) {
      result_size = 2;
    } else {
      result_size = 1;
    } /* if */
#endif
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = result_size;
      if (result_size == sizeof(uint32Type) / (BIGDIGIT_SIZE >> 3) + 1) {
        result_size--;
        result->bigdigits[result_size] = (bigDigitType) 0;
      } /* if */
      result->bigdigits[0] = (bigDigitType) (number & BIGDIGIT_MASK);
#if BIGDIGIT_SIZE < 32
      {
        memSizeType pos;

        for (pos = 1; pos < result_size; pos++) {
          number >>= BIGDIGIT_SIZE;
          result->bigdigits[pos] = (bigDigitType) (number & BIGDIGIT_MASK);
        } /* for */
      }
#endif
    } /* if */
    logFunction(printf("bigFromUInt32 --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigFromUInt32 */



#ifdef INT64TYPE
/**
 *  Convert an uint64Type number to 'bigInteger'.
 *  @return the bigInteger result of the conversion.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigFromUInt64 (uint64Type number)

  {
    memSizeType pos;
    memSizeType result_size;
    bigIntType result;

  /* bigFromUInt64 */
    logFunction(printf("bigFromUInt64(" FMT_U64 ")\n", number););
#if BIGDIGIT_SIZE == 32
    if (number > UINT64_SUFFIX(9223372036854775807)) {
      result_size = 3;
    } else if (number > UINT64_SUFFIX(2147483647)) {
      result_size = 2;
    } else {
      result_size = 1;
    } /* if */
#elif BIGDIGIT_SIZE == 16
    if (number > UINT64_SUFFIX(9223372036854775807)) {
      result_size = 5;
    } else if (number > UINT64_SUFFIX(140737488355327)) {
      result_size = 4;
    } else if (number > UINT64_SUFFIX(2147483647)) {
      result_size = 3;
    } else if (number > UINT64_SUFFIX(32767)) {
      result_size = 2;
    } else {
      result_size = 1;
    } /* if */
#elif BIGDIGIT_SIZE == 8
    if (number > UINT64_SUFFIX(9223372036854775807)) {
      result_size = 9;
    } else if (number > UINT64_SUFFIX(36028797018963967)) {
      result_size = 8;
    } else if (number > UINT64_SUFFIX(140737488355327)) {
      result_size = 7;
    } else if (number > UINT64_SUFFIX(549755813887)) {
      result_size = 6;
    } else if (number > UINT64_SUFFIX(2147483647)) {
      result_size = 5;
    } else if (number > UINT64_SUFFIX(8388607)) {
      result_size = 4;
    } else if (number > UINT64_SUFFIX(32767)) {
      result_size = 3;
    } else if (number > UINT64_SUFFIX(127)) {
      result_size = 2;
    } else {
      result_size = 1;
    } /* if */
#endif
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = result_size;
      if (result_size == sizeof(uint64Type) / (BIGDIGIT_SIZE >> 3) + 1) {
        result_size--;
        result->bigdigits[result_size] = (bigDigitType) 0;
      } /* if */
      result->bigdigits[0] = (bigDigitType) (number & BIGDIGIT_MASK);
      for (pos = 1; pos < result_size; pos++) {
        number >>= BIGDIGIT_SIZE;
        result->bigdigits[pos] = (bigDigitType) (number & BIGDIGIT_MASK);
      } /* for */
    } /* if */
    logFunction(printf("bigFromUInt64 --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigFromUInt64 */
#endif



/**
 *  Compute the greatest common divisor of two 'bigInteger' numbers.
 *  @return the greatest common divisor of the two numbers.
 *          The greatest common divisor is positive or zero.
 */
bigIntType bigGcd (const const_bigIntType big1,
    const const_bigIntType big2)

  {
    bigIntType big1_help;
    bigIntType big2_help;
    intType lowestSetBitA;
    intType shift;
    bigIntType help_big;
    bigIntType gcd;

  /* bigGcd */
    logFunction(printf("bigGcd(%s,", bigHexCStri(big1));
                printf("%s)\n", bigHexCStri(big2)););
    if (big1->size == 1 && big1->bigdigits[0] == 0) {
      gcd = bigAbs(big2);
    } else if (big2->size == 1 && big2->bigdigits[0] == 0) {
      gcd = bigAbs(big1);
    } else if (unlikely((big1_help = bigAbs(big1)) == NULL)) {
      /* An exception was raised in bigAbs(). */
      gcd = NULL;
    } else if (unlikely((big2_help = bigAbs(big2)) == NULL)) {
      /* An exception was raised in bigAbs(). */
      bigDestr(big1_help);
      gcd = NULL;
    } else {
      if ((big1_help->size > big2_help->size &&
          big1_help->size - big2_help->size > 10) ||
          (big1_help->size < big2_help->size &&
          big2_help->size - big1_help->size > 10)) {
        while (big1_help->size != 1 || big1_help->bigdigits[0] != 0) {
          help_big = bigRem(big2_help, big1_help);
          bigDestr(big2_help);
          big2_help = big1_help;
          big1_help = help_big;
        } /* while */
        gcd = big2_help;
        bigDestr(big1_help);
      } else {
        lowestSetBitA = bigLowestSetBit(big1_help);
        shift = bigLowestSetBit(big2_help);
        if (lowestSetBitA < shift) {
          shift = lowestSetBitA;
        } /* if */
        bigRShiftAssign(&big1_help, lowestSetBitA);
        do {
          bigRShiftAssign(&big2_help, bigLowestSetBit(big2_help));
          if (bigCmp(big1_help, big2_help) < 0) {
            bigSbtrAssign(&(big2_help), big1_help);
          } else {
            help_big = bigSbtr(big1_help, big2_help);
            bigDestr(big1_help);
            big1_help = big2_help;
            big2_help = help_big;
          } /* if */
        } while (big2_help->size != 1 || big2_help->bigdigits[0] != 0);
        bigLShiftAssign(&big1_help, shift);
        gcd = big1_help;
        bigDestr(big2_help);
      } /* if */
    } /* if */
    logFunction(printf("bigGcd -->%s\n", bigHexCStri(gcd)););
    return gcd;
  } /* bigGcd */



/**
 *  Compute the hash value of a 'bigInteger' number.
 *  @return the hash value.
 */
intType bigHashCode (const const_bigIntType big1)

  {
    intType hashCode;

  /* bigHashCode */
    hashCode = (intType)
        (big1->bigdigits[0] << 5 ^ big1->size << 3 ^ big1->bigdigits[big1->size - 1]);
    return hashCode;
  } /* bigHashCode */



/**
 *  Increment a 'bigInteger' variable.
 *  Increments *big_variable by 1. The operation is done in
 *  place and *big_variable is only enlarged if necessary.
 *  In case the enlarging fails the old content of *big_variable
 *  is restored and the exception MEMORY_ERROR is raised.
 *  This ensures that bigIncr works as a transaction.
 *  @exception MEMORY_ERROR If the resizing of *big_variable fails.
 */
void bigIncr (bigIntType *const big_variable)

  {
    bigIntType big1;
    memSizeType pos = 0;
    boolType negative;
    bigIntType resized_big1;

  /* bigIncr */
    logFunction(printf("bigIncr(%s)\n", bigHexCStri(*big_variable)););
    big1 = *big_variable;
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    if (big1->bigdigits[pos] == BIGDIGIT_MASK) {
      if (big1->size == 1) {
        big1->bigdigits[pos] = 0;
        pos++;
      } else {
        do {
          big1->bigdigits[pos] = 0;
          pos++;
        } while (big1->bigdigits[pos] == BIGDIGIT_MASK);
        /* memset(big1->bigdigits, 0, pos * sizeof(bigDigitType)); */
      } /* if */
    } /* if */
    if (pos < big1->size) {
      big1->bigdigits[pos]++;
    } /* if */
    pos = big1->size;
    if (IS_NEGATIVE(big1->bigdigits[pos - 1])) {
      if (!negative) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, pos, pos + 1);
        if (unlikely(resized_big1 == NULL)) {
          /* This error situation is very unlikely, but we need to */
          /* make sure that 'big_variable' contains a legal value. */
          /* We UNDO the change done for 'big_variable' by setting */
          /* it to the old value: The highest bit is set to 0 and  */
          /* the other bits are set to 1. Note that only values    */
          /* with this pattern need an additional digit if they    */
          /* are incremented.                                      */
          pos--;
          big1->bigdigits[pos] = BIGDIGIT_MASK ^ BIGDIGIT_SIGN;
          while (pos != 0) {
            pos--;
            big1->bigdigits[pos] = BIGDIGIT_MASK;
          } /* while */
          raise_error(MEMORY_ERROR);
        } else {
          big1 = resized_big1;
          COUNT3_BIG(pos, pos + 1);
          big1->size++;
          big1->bigdigits[pos] = 0;
          *big_variable = big1;
        } /* if */
      } else if (big1->bigdigits[pos - 1] == BIGDIGIT_MASK &&
          pos >= 2 && IS_NEGATIVE(big1->bigdigits[pos - 2])) {
        REALLOC_BIG_SIZE_OK(resized_big1, big1, pos, pos - 1);
        /* Avoid a MEMORY_ERROR in the strange case   */
        /* if a 'realloc' which shrinks memory fails. */
        if (likely(resized_big1 != NULL)) {
          big1 = resized_big1;
          *big_variable = big1;
        } /* if */
        COUNT3_BIG(pos, pos - 1);
        big1->size--;
      } /* if */
    } /* if */
    logFunction(printf("bigIncr --> %s\n", bigHexCStri(*big_variable)););
  } /* bigIncr */



/**
 *  Compute the exponentiation of a 'bigInteger' base with an integer exponent.
 *  The result variable is set to base or 1 depending on the
 *  rightmost bit of the exponent. After that the base is
 *  squared in a loop and every time the corresponding bit of
 *  the exponent is set the current square is multiplied
 *  with the result variable. This reduces the number of square
 *  operations to ld(exponent).
 *  @return the result of the exponentiation.
 *  @exception NUMERIC_ERROR If the exponent is negative.
 */
bigIntType bigIPow (const const_bigIntType base, intType exponent)

  {
    boolType negative = FALSE;
    bigIntType square;
    bigIntType big_help;
    bigIntType power;

  /* bigIPow */
    logFunction(printf("bigIPow(%s, " FMT_D ")\n",
                       bigHexCStri(base), exponent););
    if (exponent <= 1) {
      if (exponent == 0) {
        if (unlikely(!ALLOC_BIG_SIZE_OK(power, 1))) {
          raise_error(MEMORY_ERROR);
        } else {
          power->size = 1;
          power->bigdigits[0] = 1;
        } /* if */
      } else if (exponent == 1) {
        power = bigCreate(base);
      } else {
        logError(printf("bigIPow(%s, " FMT_D "): "
                        "Exponent is negative.\n",
                        bigHexCStri(base), exponent););
        raise_error(NUMERIC_ERROR);
        power = NULL;
      } /* if */
    } else if (base->size == 1) {
      power = bigIPow1(base->bigdigits[0], exponent);
    } else if (unlikely(!ALLOC_BIG_CHECK_SIZE(square, base->size + 1))) {
      raise_error(MEMORY_ERROR);
      power = NULL;
    } else if (unlikely(!ALLOC_BIG_CHECK_SIZE(power, base->size + 1))) {
      FREE_BIG(square, base->size + 1);
      raise_error(MEMORY_ERROR);
    } else {
      if (IS_NEGATIVE(base->bigdigits[base->size - 1])) {
        negative = TRUE;
        positive_copy_of_negative_big(square, base);
      } else {
        square->size = base->size;
        memcpy(square->bigdigits, base->bigdigits,
               (size_t) base->size * sizeof(bigDigitType));
      } /* if */
      if (exponent & 1) {
        power->size = square->size;
        memcpy(power->bigdigits, square->bigdigits,
               (size_t) square->size * sizeof(bigDigitType));
      } else {
        negative = FALSE;
        power->size = 1;
        power->bigdigits[0] = 1;
      } /* if */
      exponent >>= 1;
      while (exponent != 0 && square != NULL && power != NULL) {
        big_help = square;
        square = uBigSquareK(square);
        FREE_BIG(big_help, big_help->size);
        if (square != NULL) {
          if (exponent & 1) {
            big_help = power;
            power = uBigMultK(power, square, FALSE);
            FREE_BIG(big_help, big_help->size);
          } /* if */
          exponent >>= 1;
        } /* if */
      } /* while */
      if (unlikely(square == NULL)) {
        if (power != NULL) {
          FREE_BIG(power, power->size);
        } /* if */
        raise_error(MEMORY_ERROR);
        power = NULL;
      } else {
        FREE_BIG(square, square->size);
        if (unlikely(power == NULL)) {
          raise_error(MEMORY_ERROR);
        } else {
          if (negative) {
            negate_positive_big(power);
          } /* if */
          power = normalize(power);
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigIPow --> %s (size=" FMT_U_MEM ")\n",
                       bigHexCStri(power), power != NULL ? power->size : 0););
    return power;
  } /* bigIPow */



/**
 *  Compute the exponentiation of a bigdigit base with an integer exponent.
 *  @param base Base that must be in the range of signedBigDigitType.
 *  @return the result of the exponentiation.
 *  @exception NUMERIC_ERROR If the exponent is negative.
 */
bigIntType bigIPowSignedDigit (intType base, intType exponent)

  {
    bigIntType power;

  /* bigIPowSignedDigit */
    logFunction(printf("bigIPowSignedDigit(" FMT_D ", " FMT_D ")\n",
                       base, exponent););
    if (exponent <= 1) {
      if (unlikely(exponent < 0)) {
        logError(printf("bigIPowSignedDigit(" FMT_D ", " FMT_D "): "
                        "Exponent is negative.\n",
                        base, exponent););
        raise_error(NUMERIC_ERROR);
        power = NULL;
      } else {
        if (unlikely(!ALLOC_BIG_SIZE_OK(power, 1))) {
          raise_error(MEMORY_ERROR);
        } else {
          power->size = 1;
          power->bigdigits[0] = exponent == 1 ? (bigDigitType) base : 1;
        } /* if */
      } /* if */
    } else {
      power = bigIPow1((bigDigitType) base, exponent);
    } /* if */
    logFunction(printf("bigIPowSignedDigit --> %s (size=" FMT_U_MEM ")\n",
                       bigHexCStri(power), power != NULL ? power->size : 0););
    return power;
  } /* bigIPowSignedDigit */



/**
 *  Compute the truncated base 10 logarithm of a 'bigInteger' number.
 *  The definition of 'log10' is extended by defining log10(0) = -1_.
 *  @return the truncated base 10 logarithm.
 *  @exception NUMERIC_ERROR The number is negative.
 */
bigIntType bigLog10 (const const_bigIntType big1)

  {
    bigIntType unsigned_big;
    bigIntType powerOf10;
    bigDigitType digit;
    memSizeType largeDecimalBlockCount;
    memSizeType decimalBlockCount;
    bigIntType logarithm;

  /* bigLog10 */
    logFunction(printf("bigLog10(%s)\n", bigHexCStri(big1)););
    if (unlikely(IS_NEGATIVE(big1->bigdigits[big1->size - 1]))) {
      logError(printf("bigLog10(%s): Number is negative.\n",
                      bigHexCStri(big1)););
      raise_error(NUMERIC_ERROR);
      logarithm = NULL;
    } else if (big1->size == 1 && big1->bigdigits[0] == 0) {
      if (unlikely(!ALLOC_BIG_SIZE_OK(logarithm, 1))) {
        raise_error(MEMORY_ERROR);
      } else {
        logarithm->size = 1;
        logarithm->bigdigits[0] = BIGDIGIT_MASK;
      } /* if */
    } else {
      if (unlikely(!ALLOC_BIG_SIZE_OK(unsigned_big, big1->size))) {
        raise_error(MEMORY_ERROR);
        logarithm = NULL;
      } else {
        unsigned_big->size = big1->size;
        memcpy(unsigned_big->bigdigits, big1->bigdigits,
               (size_t) big1->size * sizeof(bigDigitType));
        decimalBlockCount = 0;
        if (unsigned_big->size > 2) {
          if (unsigned_big->size - 1 <= MAX_MEM_INDEX) {
            decimalBlockCount = unsigned_big->size - 1;
          } else {
            decimalBlockCount = MAX_MEM_INDEX;
          } /* if */
          powerOf10 = bigIPow1(POWER_OF_10_IN_BIGDIGIT, (intType) (decimalBlockCount));
          unsigned_big = bigMDiv(unsigned_big, powerOf10);
          bigDestr(powerOf10);
        } /* if */
        largeDecimalBlockCount = 0;
        while (unsigned_big->size > 2) {
          uBigRShift(unsigned_big, QUINARY_DIGITS_IN_BIGDIGIT);
          if (unsigned_big->bigdigits[unsigned_big->size - 1] == 0) {
            unsigned_big->size--;
          } /* if */
          uBigDivideByPowerOf5(unsigned_big);
          if (unsigned_big->bigdigits[unsigned_big->size - 1] == 0) {
            unsigned_big->size--;
          } /* if */
          largeDecimalBlockCount++;
        } /* while */
        while (unsigned_big->size > 1 ||
               unsigned_big->bigdigits[0] >= POWER_OF_10_IN_BIGDIGIT) {
          (void) uBigDivideByPowerOf10(unsigned_big);
          /* printf("unsigned_big->size=" FMT_U_MEM ", digit=" FMT_U_DIG "\n",
             unsigned_big->size, digit); */
          if (unsigned_big->bigdigits[unsigned_big->size - 1] == 0) {
            unsigned_big->size--;
          } /* if */
          decimalBlockCount++;
        } /* while */
        digit = unsigned_big->bigdigits[0];
        FREE_BIG(unsigned_big, big1->size + 1);
#if POINTER_SIZE == 32
        logarithm = bigFromUInt32(decimalBlockCount);
#elif POINTER_SIZE == 64
        logarithm = bigFromUInt64(decimalBlockCount);
#endif
        if (logarithm != NULL) {
          bigMultAssign1(&logarithm, DECIMAL_DIGITS_IN_BIGDIGIT);
#if BIGDIGIT_SIZE < 32
          {
            bigIntType numDigits = bigFromUInt32(
                largeDecimalBlockCount * QUINARY_DIGITS_IN_BIGDIGIT);
            bigAddAssign(&logarithm, numDigits);
            bigDestr(numDigits);
          }
#else
          bigAddAssignSignedDigit(&logarithm,
              (intType) (largeDecimalBlockCount * QUINARY_DIGITS_IN_BIGDIGIT));
#endif
          /* printf("digit: " FMT_U_DIG "\n", digit); */
          digit /= 10;
          while (digit != 0) {
            bigIncr(&logarithm);
            digit /= 10;
          } /* while */
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigLog10 --> %s\n", bigHexCStri(logarithm)););
    return logarithm;
  } /* bigLog10 */



/**
 *  Compute the truncated base 2 logarithm of a 'bigInteger' number.
 *  The definition of 'log2' is extended by defining log2(0) = -1_.
 *  @return the truncated base 2 logarithm.
 *  @exception NUMERIC_ERROR The number is negative.
 */
bigIntType bigLog2 (const const_bigIntType big1)

  {
    memSizeType number;
    memSizeType pos;
    intType bigdigit_log2;
    memSizeType logarithm_size;
    bigIntType logarithm;

  /* bigLog2 */
    logFunction(printf("bigLog2(%s)\n", bigHexCStri(big1)););
    if (unlikely(IS_NEGATIVE(big1->bigdigits[big1->size - 1]))) {
      logError(printf("bigLog2(%s): Number is negative.\n",
                      bigHexCStri(big1)););
      raise_error(NUMERIC_ERROR);
      logarithm = NULL;
    } else {
      /* The logarithm_size is incremented by one to take the space */
      /* needed for the shift by BIGDIGIT_LOG2_SIZE into account.   */
      logarithm_size = sizeof(memSizeType) / (BIGDIGIT_SIZE >> 3) + 1;
      if (unlikely(!ALLOC_BIG_SIZE_OK(logarithm, logarithm_size))) {
        raise_error(MEMORY_ERROR);
      } else {
        logarithm->size = logarithm_size;
        number = big1->size - 1;
        logarithm->bigdigits[0] = (bigDigitType) (number & BIGDIGIT_MASK);
        for (pos = 1; pos < logarithm_size; pos++) {
          /* POINTER_SIZE is equal to sizeof(memSizeType) << 3 */
#if POINTER_SIZE > BIGDIGIT_SIZE
          /* The number does not fit into one bigdigit */
          number >>= BIGDIGIT_SIZE;
          logarithm->bigdigits[pos] = (bigDigitType) (number & BIGDIGIT_MASK);
#else
          /* The number fits into one bigdigit */
          logarithm->bigdigits[pos] = 0;
#endif
        } /* for */
        uBigLShift(logarithm, BIGDIGIT_LOG2_SIZE);
        bigdigit_log2 = digitMostSignificantBit(big1->bigdigits[big1->size - 1]);
        if (bigdigit_log2 == -1) {
          uBigDecr(logarithm);
        } else {
          logarithm->bigdigits[0] |= (bigDigitType) bigdigit_log2;
        } /* if */
        logarithm = normalize(logarithm);
      } /* if */
    } /* if */
    logFunction(printf("bigLog2 --> %s\n", bigHexCStri(logarithm)););
    return logarithm;
  } /* bigLog2 */



/**
 *  Create a number from the lower bits of big1.
 *  This corresponds to the modulo if the dividend is a power of two:
 *   bigLowerBits(big1, bits)  corresponds to  big1 mod (2_ ** bits)
 *  @param bits Number of lower bits to select from big1.
 *  @return a number in the range 0 .. pred(2_ ** bits).
 *  @exception NUMERIC_ERROR The number of bits is negative.
 */
bigIntType bigLowerBits (const const_bigIntType big1, const intType bits)

  {
    memSizeType big1_size;
    memSizeType pos;
    int bit_pos;
    boolType add_sign_digit = FALSE;
    bigDigitType digit_mask;
    memSizeType idx;
    memSizeType result_size;
    bigIntType result;

  /* bigLowerBits */
    logFunction(printf("bigLowerBits(%s, " FMT_D ")\n",
                       bigHexCStri(big1), bits););
    if (unlikely(bits <= 0)) {
      if (unlikely(bits != 0)) {
        logError(printf("bigLowerBits(%s, " FMT_D "): "
                        "Number of bits is negative.\n",
                        bigHexCStri(big1), bits););
        raise_error(NUMERIC_ERROR);
        result = NULL;
      } else {
        if (unlikely(!ALLOC_BIG_SIZE_OK(result, 1))) {
          raise_error(MEMORY_ERROR);
        } else {
          result->size = 1;
          result->bigdigits[0] = (bigDigitType) 0;
        } /* if */
      } /* if */
    } else {
      big1_size = big1->size;
      pos = (memSizeType) (bits - 1) >> BIGDIGIT_LOG2_SIZE;
      if (pos >= big1_size) {
        if (IS_NEGATIVE(big1->bigdigits[big1_size - 1])) {
          result_size = pos + 1;
          bit_pos = (int) ((bits - 1) & BIGDIGIT_SIZE_MASK);
          digit_mask = BIGDIGIT_MASK >> (BIGDIGIT_SIZE - bit_pos - 1);
          if (bit_pos == BIGDIGIT_SIZE_MASK) {
            add_sign_digit = TRUE;
            result_size++;
          } /* if */
        } else {
          result_size = big1_size;
          digit_mask = BIGDIGIT_MASK;
        } /* if */
      } else {
        result_size = pos + 1;
        bit_pos = (int) ((bits - 1) & BIGDIGIT_SIZE_MASK);
        digit_mask = BIGDIGIT_MASK >> (BIGDIGIT_SIZE - bit_pos - 1);
        if (bit_pos == BIGDIGIT_SIZE_MASK && IS_NEGATIVE(big1->bigdigits[pos])) {
          add_sign_digit = TRUE;
          result_size++;
        } /* if */
      } /* if */
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(result, result_size))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = result_size;
        idx = result_size - 1;
        if (add_sign_digit) {
          result->bigdigits[idx] = (bigDigitType) 0;
          idx--;
        } /* if */
        if (idx >= big1_size) {
          result->bigdigits[idx] = digit_mask;
          while (idx > big1_size) {
            idx--;
            result->bigdigits[idx] = BIGDIGIT_MASK;
          } /* while */
        } else {
          /* printf("mask = " F_X_DIG(08) "\n", digit_mask); */
          result->bigdigits[idx] = big1->bigdigits[idx] & digit_mask;
        } /* if */
        memcpy(result->bigdigits, big1->bigdigits,
               (size_t) idx * sizeof(bigDigitType));
      } /* if */
    } /* if */
    result = normalize(result);
    logFunction(printf("bigLowerBits --> %s (size=" FMT_U_MEM ")\n",
                       bigHexCStri(result), result->size););
    return result;
  } /* bigLowerBits */



/**
 *  Create a number from the lower bits of big1.
 *  Big1 is assumed to be a temporary value which is reused.
 *  This corresponds to the modulo if the dividend is a power of two:
 *   bigLowerBits(big1, bits)  corresponds to  big1 mod (2_ ** bits)
 *  @param bits Number of lower bits to select from big1.
 *  @return a number in the range 0 .. pred(2_ ** bits).
 *  @exception NUMERIC_ERROR The number of bits is negative.
 */
bigIntType bigLowerBitsTemp (const bigIntType big1, const intType bits)

  {
    memSizeType big1_size;
    memSizeType pos;
    int bit_pos;
    boolType add_sign_digit = FALSE;
    bigDigitType digit_mask;
    memSizeType idx;
    memSizeType result_size;
    bigIntType result;

  /* bigLowerBitsTemp */
    logFunction(printf("bigLowerBitsTemp(%s, " FMT_D ")\n",
                       bigHexCStri(big1), bits););
    big1_size = big1->size;
    if (unlikely(bits <= 0)) {
      FREE_BIG(big1, big1_size);
      if (unlikely(bits != 0)) {
        logError(printf("bigLowerBitsTemp(%s, " FMT_D "): "
                        "Number of bits is negative.\n",
                        bigHexCStri(big1), bits););
        raise_error(NUMERIC_ERROR);
        result = NULL;
      } else {
        if (unlikely(!ALLOC_BIG_SIZE_OK(result, 1))) {
          raise_error(MEMORY_ERROR);
        } else {
          result->size = 1;
          result->bigdigits[0] = (bigDigitType) 0;
        } /* if */
      } /* if */
    } else {
      pos = (memSizeType) (bits - 1) >> BIGDIGIT_LOG2_SIZE;
      if (pos >= big1_size) {
        if (IS_NEGATIVE(big1->bigdigits[big1_size - 1])) {
          result_size = pos + 1;
          bit_pos = (int) ((bits - 1) & BIGDIGIT_SIZE_MASK);
          digit_mask = BIGDIGIT_MASK >> (BIGDIGIT_SIZE - bit_pos - 1);
          if (bit_pos == BIGDIGIT_SIZE_MASK) {
            add_sign_digit = TRUE;
            result_size++;
          } /* if */
        } else {
          result_size = big1_size;
          digit_mask = BIGDIGIT_MASK;
        } /* if */
      } else {
        result_size = pos + 1;
        bit_pos = (int) ((bits - 1) & BIGDIGIT_SIZE_MASK);
        digit_mask = BIGDIGIT_MASK >> (BIGDIGIT_SIZE - bit_pos - 1);
        if (bit_pos == BIGDIGIT_SIZE_MASK && IS_NEGATIVE(big1->bigdigits[pos])) {
          add_sign_digit = TRUE;
          result_size++;
        } /* if */
      } /* if */
      if (big1_size != result_size) {
        REALLOC_BIG_CHECK_SIZE(result, big1, big1_size, result_size);
      } else {
        result = big1;
      } /* if */
      if (unlikely(result == NULL)) {
        FREE_BIG(big1, big1_size);
        raise_error(MEMORY_ERROR);
      } else {
        COUNT3_BIG(big1_size, result_size);
        result->size = result_size;
        idx = result_size - 1;
        if (add_sign_digit) {
          result->bigdigits[idx] = (bigDigitType) 0;
          idx--;
        } /* if */
        if (idx >= big1_size) {
          result->bigdigits[idx] = digit_mask;
          while (idx > big1_size) {
            idx--;
            result->bigdigits[idx] = BIGDIGIT_MASK;
          } /* while */
        } else {
          /* printf("mask = " F_X_DIG(08) "\n", digit_mask); */
          result->bigdigits[idx] = result->bigdigits[idx] & digit_mask;
        } /* if */
      } /* if */
    } /* if */
    result = normalize(result);
    logFunction(printf("bigLowerBitsTemp --> %s (size=" FMT_U_MEM ")\n",
                       bigHexCStri(result), result->size););
    return result;
  } /* bigLowerBitsTemp */



uint64Type bigLowerBits64 (const const_bigIntType big1)

  {
    memSizeType pos;
    uint64Type result;

  /* bigLowerBits64 */
    logFunction(printf("bigLowerBits64(%s)\n", bigHexCStri(big1)););
    pos = big1->size - 1;
    if (pos >= sizeof(uint64Type) / (BIGDIGIT_SIZE >> 3)) {
      pos = sizeof(uint64Type) / (BIGDIGIT_SIZE >> 3) - 1;
    } /* if */
    result = (uint64Type) big1->bigdigits[pos];
#if BIGDIGIT_SIZE < 64
    while (pos > 0) {
      pos--;
      result <<= BIGDIGIT_SIZE;
      result |= (uint64Type) big1->bigdigits[pos];
    } /* while */
#endif
    logFunction(printf("bigLowerBits64(%s) --> " FMT_U64 "\n",
                       bigHexCStri(big1), result););
    return result;
  } /* bigLowerBits64 */



/**
 *  Index of the lowest-order one bit.
 *  For A <> 0 this is equal to the number of lowest-order zero bits.
 *  @return the number of lowest-order zero bits or -1 for lowestSetBit(0).
 *  @exception RANGE_ERROR The result does not fit into an integer.
 */
intType bigLowestSetBit (const const_bigIntType big1)

  {
    memSizeType big1_size;
    memSizeType pos = 0;
    intType result;

  /* bigLowestSetBit */
    logFunction(printf("bigLowestSetBit(%s)\n", bigHexCStri(big1)););
    big1_size = big1->size;
    while (pos < big1_size && big1->bigdigits[pos] == 0) {
      pos++;
    } /* while */
    if (pos < big1_size) {
      result = digitLeastSignificantBit(big1->bigdigits[pos]);
      if (unlikely(pos > (memSizeType) (MAX_MEM_INDEX - result) >> BIGDIGIT_LOG2_SIZE)) {
        logError(printf("bigLowestSetBit(%s): "
                        "Result does not fit into an integer.\n",
                        bigHexCStri(big1)););
        raise_error(RANGE_ERROR);
        result = 0;
      } else {
        result += (intType) (pos << BIGDIGIT_LOG2_SIZE);
      } /* if */
    } else {
      result = -1;
    } /* if */
    logFunction(printf("bigLowestSetBit --> " FMT_D "\n", result););
    return result;
  } /* bigLowestSetBit */



/**
 *  Shift a 'bigInteger' number left by lshift bits.
 *  If lshift is negative a right shift is done instead.
 *  A << B is equivalent to A * 2_ ** B if B >= 0 holds.
 *  A << B is equivalent to A mdiv 2_ ** -B if B < 0 holds.
 *  @return the left shifted number.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigLShift (const const_bigIntType big1, const intType lshift)

  {
    unsigned int digit_rshift;
    unsigned int digit_lshift;
    bigDigitType digit_mask;
    bigDigitType low_digit;
    bigDigitType high_digit;
    const bigDigitType *source_digits;
    bigDigitType *dest_digits;
    memSizeType size_reduction;
    memSizeType pos;
    memSizeType result_size;
    bigIntType result;

  /* bigLShift */
    logFunction(printf("bigLShift(%s, " FMT_D ")\n",
                       bigHexCStri(big1), lshift););
    if (unlikely(lshift < 0)) {
      if (unlikely(TWOS_COMPLEMENT_INTTYPE && lshift == INTTYPE_MIN)) {
        result = bigRShift(big1, INTTYPE_MAX);
        if (result != NULL) {
          bigRShiftAssign(&result, 1);
        } /* if */
      } else {
        result = bigRShift(big1, -lshift);
      } /* if */
    } else if (unlikely(big1->size == 1 && big1->bigdigits[0] == 0)) {
      if (unlikely(!ALLOC_BIG_SIZE_OK(result, 1))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = 1;
        result->bigdigits[0] = 0;
      } /* if */
    } else if ((lshift & BIGDIGIT_SIZE_MASK) == 0) {
      if (unlikely((uintType) lshift >> BIGDIGIT_LOG2_SIZE > MAX_BIG_LEN - big1->size)) {
        raise_error(MEMORY_ERROR);
        result = NULL;
      } else {
        result_size = big1->size + (memSizeType) ((uintType) lshift >> BIGDIGIT_LOG2_SIZE);
        if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
          raise_error(MEMORY_ERROR);
        } else {
          result->size = result_size;
          memcpy(&result->bigdigits[lshift >> BIGDIGIT_LOG2_SIZE], big1->bigdigits,
                 (size_t) big1->size * sizeof(bigDigitType));
          memset(result->bigdigits, 0,
                 (memSizeType) ((uintType) lshift >> BIGDIGIT_LOG2_SIZE) * sizeof(bigDigitType));
        } /* if */
      } /* if */
    } else if (unlikely(((uintType) lshift >> BIGDIGIT_LOG2_SIZE) + 1 > MAX_BIG_LEN - big1->size)) {
      raise_error(MEMORY_ERROR);
      result = NULL;
    } else {
      result_size = big1->size + (memSizeType) ((uintType) lshift >> BIGDIGIT_LOG2_SIZE) + 1;
      digit_lshift = (unsigned int) ((uintType) lshift & BIGDIGIT_SIZE_MASK);
      digit_rshift = BIGDIGIT_SIZE - digit_lshift;
      size_reduction = 0;
      low_digit = big1->bigdigits[big1->size - 1];
      if (IS_NEGATIVE(low_digit)) {
        digit_mask = (BIGDIGIT_MASK << (digit_rshift - 1)) & BIGDIGIT_MASK;
        if ((low_digit & digit_mask) == digit_mask) {
          result_size--;
          size_reduction = 1;
        } else {
          low_digit = BIGDIGIT_MASK;
        } /* if */
      } else {
        if (low_digit >> (digit_rshift - 1) == 0) {
          result_size--;
          size_reduction = 1;
        } else {
          low_digit = 0;
        } /* if */
      } /* if */
      if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = result_size;
        dest_digits = &result->bigdigits[result_size];
        if (size_reduction) {
          source_digits = &big1->bigdigits[big1->size - 1];
        } else {
          source_digits = &big1->bigdigits[big1->size];
        } /* if */
        high_digit = (low_digit << digit_lshift) & BIGDIGIT_MASK;
        for (pos = big1->size - size_reduction; pos != 0; pos--) {
          low_digit = *--source_digits;
          *--dest_digits = high_digit | (low_digit >> digit_rshift);
          high_digit = (low_digit << digit_lshift) & BIGDIGIT_MASK;
        } /* for */
        *--dest_digits = high_digit;
        if (dest_digits > result->bigdigits) {
          memset(result->bigdigits, 0,
                 (memSizeType) (dest_digits - result->bigdigits) * sizeof(bigDigitType));
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigLShift --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigLShift */



/**
 *  Shift a number left by lshift bits and assign the result back to number.
 *  If lshift is negative a right shift is done instead.
 *  @exception MEMORY_ERROR Not enough memory to represent the new value.
 */
void bigLShiftAssign (bigIntType *const big_variable, intType lshift)

  {
    bigIntType big1;
    unsigned int digit_rshift;
    unsigned int digit_lshift;
    bigDigitType digit_mask;
    bigDigitType low_digit;
    bigDigitType high_digit;
    const bigDigitType *source_digits;
    bigDigitType *dest_digits;
    memSizeType size_reduction;
    memSizeType pos;
    memSizeType result_size;
    bigIntType result;

  /* bigLShiftAssign */
    logFunction(printf("bigLShiftAssign(%s, " FMT_D ")\n",
                       bigHexCStri(*big_variable), lshift););
    if (unlikely(lshift < 0)) {
      if (unlikely(TWOS_COMPLEMENT_INTTYPE && lshift == INTTYPE_MIN)) {
        bigRShiftAssign(big_variable, INTTYPE_MAX);
        bigRShiftAssign(big_variable, 1);
      } else {
        bigRShiftAssign(big_variable, -lshift);
      } /* if */
    } else if (likely(lshift != 0)) {
      big1 = *big_variable;
      if (big1->size == 1 && big1->bigdigits[0] == 0) {
        if (unlikely(!ALLOC_BIG_SIZE_OK(result, 1))) {
          raise_error(MEMORY_ERROR);
        } else {
          result->size = 1;
          result->bigdigits[0] = 0;
          *big_variable = result;
          FREE_BIG(big1, big1->size);
        } /* if */
      } else if ((lshift & BIGDIGIT_SIZE_MASK) == 0) {
        if (unlikely((uintType) lshift >> BIGDIGIT_LOG2_SIZE > MAX_BIG_LEN - big1->size)) {
          raise_error(MEMORY_ERROR);
        } else {
          result_size = big1->size + (memSizeType) ((uintType) lshift >> BIGDIGIT_LOG2_SIZE);
          if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
            raise_error(MEMORY_ERROR);
          } else {
            result->size = result_size;
            memcpy(&result->bigdigits[lshift >> BIGDIGIT_LOG2_SIZE], big1->bigdigits,
                   (size_t) big1->size * sizeof(bigDigitType));
            memset(result->bigdigits, 0,
                   (memSizeType) ((uintType) lshift >> BIGDIGIT_LOG2_SIZE) * sizeof(bigDigitType));
            *big_variable = result;
            FREE_BIG(big1, big1->size);
          } /* if */
        } /* if */
      } else if (unlikely(((uintType) lshift >> BIGDIGIT_LOG2_SIZE) + 1 > MAX_BIG_LEN - big1->size)) {
        raise_error(MEMORY_ERROR);
      } else {
        result_size = big1->size + (memSizeType) ((uintType) lshift >> BIGDIGIT_LOG2_SIZE) + 1;
        digit_lshift = (unsigned int) ((uintType) lshift & BIGDIGIT_SIZE_MASK);
        digit_rshift = BIGDIGIT_SIZE - digit_lshift;
        size_reduction = 0;
        low_digit = big1->bigdigits[big1->size - 1];
        if (IS_NEGATIVE(low_digit)) {
          digit_mask = (BIGDIGIT_MASK << (digit_rshift - 1)) & BIGDIGIT_MASK;
          if ((low_digit & digit_mask) == digit_mask) {
            result_size--;
            size_reduction = 1;
          } else {
            low_digit = BIGDIGIT_MASK;
          } /* if */
        } else {
          if (low_digit >> (digit_rshift - 1) == 0) {
            result_size--;
            size_reduction = 1;
          } else {
            low_digit = 0;
          } /* if */
        } /* if */
        if (result_size != big1->size) {
          if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
            raise_error(MEMORY_ERROR);
          } /* if */
        } else {
          result = big1;
        } /* if */
        if (result != NULL) {
          result->size = result_size;
          dest_digits = &result->bigdigits[result_size];
          if (size_reduction) {
            source_digits = &big1->bigdigits[big1->size - 1];
          } else {
            source_digits = &big1->bigdigits[big1->size];
          } /* if */
          high_digit = (low_digit << digit_lshift) & BIGDIGIT_MASK;
          for (pos = big1->size - size_reduction; pos != 0; pos--) {
            low_digit = *--source_digits;
            *--dest_digits = high_digit | (low_digit >> digit_rshift);
            high_digit = (low_digit << digit_lshift) & BIGDIGIT_MASK;
          } /* for */
          *--dest_digits = high_digit;
          if (dest_digits > result->bigdigits) {
            memset(result->bigdigits, 0,
                   (memSizeType) (dest_digits - result->bigdigits) * sizeof(bigDigitType));
          } /* if */
          if (result != big1) {
            *big_variable = result;
            FREE_BIG(big1, big1->size);
          } /* if */
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigLShiftAssign --> %s\n", bigHexCStri(*big_variable)););
  } /* bigLShiftAssign */



/**
 *  Shift one left by 'lshift' bits.
 *  If 'lshift' is positive or zero this corresponds to
 *  the computation of a power of two:
 *   bigLShiftOne(lshift)  corresponds to  2_ ** lshift
 *  If 'lshift' is negative the result is zero.
 *  @return one shifted left by 'lshift'.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigLShiftOne (const intType lshift)

  {
    memSizeType result_size;
    int bit_pos;
    bigIntType result;

  /* bigLShiftOne */
    logFunction(printf("bigLShiftOne(" FMT_D ")\n", lshift););
    if (unlikely(lshift < 0)) {
      if (unlikely(!ALLOC_BIG_SIZE_OK(result, 1))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = 1;
        result->bigdigits[0] = 0;
      } /* if */
    } else if (unlikely((((uintType) lshift + 1) >> BIGDIGIT_LOG2_SIZE) + 1 > MAX_BIG_LEN)) {
      raise_error(MEMORY_ERROR);
      result = NULL;
    } else {
      result_size = (memSizeType) (((uintType) lshift + 1) >> BIGDIGIT_LOG2_SIZE) + 1;
      if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = result_size;
        bit_pos = (int) (lshift & BIGDIGIT_SIZE_MASK);
        if (bit_pos == BIGDIGIT_SIZE_MASK) {
          memset(result->bigdigits, 0, (result_size - 2) * sizeof(bigDigitType));
          result->bigdigits[result_size - 2] = ((bigDigitType) 1) << bit_pos;
          result->bigdigits[result_size - 1] = 0;
        } else {
          memset(result->bigdigits, 0, (result_size - 1) * sizeof(bigDigitType));
          result->bigdigits[result_size - 1] = ((bigDigitType) 1) << bit_pos;
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigLShiftOne --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigLShiftOne */



/**
 *  Exponentiation if the base is a power of two.
 *  @param log2base Logarithm of the actual base ( =log2(base) )
 *  @return (2 ** log2base) ** exponent
 *  @exception NUMERIC_ERROR If log2base or exponent is negative.
 */
bigIntType bigLog2BaseIPow (const intType log2base, const intType exponent)

  {
    uintType high_shift;
    uintType low_shift;
    bigIntType power;

  /* bigLog2BaseIPow */
    logFunction(printf("bigLog2BaseIPow(" FMT_D ", " FMT_D ")\n",
                       log2base, exponent););
    if (unlikely(log2base < 0 || exponent < 0)) {
      logError(printf("bigLog2BaseIPow(" FMT_D ", " FMT_D "): "
                      "Log2base or exponent is negative.\n",
                      log2base, exponent););
      raise_error(NUMERIC_ERROR);
      power = NULL;
    } else if (likely(log2base == 1)) {
      power = bigLShiftOne(exponent);
    } else if (log2base <= 10 && exponent <= MAX_DIV_10) {
      power = bigLShiftOne(log2base * exponent);
    } else {
      low_shift = uintMult((uintType) log2base, (uintType) exponent, &high_shift);
      if (unlikely(high_shift != 0 || (intType) low_shift < 0)) {
        raise_error(MEMORY_ERROR);
        power = NULL;
      } else {
        power = bigLShiftOne((intType) low_shift);
      } /* if */
    } /* if */
    logFunction(printf("bigLog2BaseIPow --> %s\n", bigHexCStri(power)););
    return power;
  } /* bigLog2BaseIPow */



/**
 *  Integer division truncated towards negative infinity.
 *  The modulo (remainder) of this division is computed with bigMod.
 *  Therefore this division is called modulo division (MDiv).
 *  The memory for the result is requested and the normalized result
 *  is returned. If divisor has just one digit or if dividend
 *  has less digits than divisor the functions bigMDiv1() or
 *  bigMDivSizeLess() are called. In the general case the absolute
 *  values of dividend and divisor are taken. Then dividend is
 *  extended by one leading zero digit. After that dividend and divisor
 *  are shifted to the left such that the most significant bit
 *  of divisor is set. This fulfills the preconditions for calling
 *  uBigDiv() which does the main work of the division.
 *  @return the quotient of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
bigIntType bigMDiv (const const_bigIntType dividend, const const_bigIntType divisor)

  {
    boolType negative = FALSE;
    bigIntType dividend_help;
    bigIntType divisor_help;
    unsigned int shift;
    bigDigitType mdiv1_remainder = 0;
    bigIntType quotient;

  /* bigMDiv */
    logFunction(printf("bigMDiv(%s,", bigHexCStri(dividend));
                printf("%s)\n", bigHexCStri(divisor)););
    if (divisor->size == 1) {
      quotient = bigMDiv1(dividend, divisor->bigdigits[0]);
    } else if (dividend->size < divisor->size) {
      quotient = bigMDivSizeLess(dividend, divisor);
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(dividend_help, dividend->size + 2))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          negative = TRUE;
          positive_copy_of_negative_big(dividend_help, dividend);
        } else {
          dividend_help->size = dividend->size;
          memcpy(dividend_help->bigdigits, dividend->bigdigits,
                 (size_t) dividend->size * sizeof(bigDigitType));
        } /* if */
        dividend_help->bigdigits[dividend_help->size] = 0;
        dividend_help->size++;
      } /* if */
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(divisor_help, divisor->size + 1))) {
        FREE_BIG(dividend_help, dividend->size + 2);
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(divisor->bigdigits[divisor->size - 1])) {
          negative = !negative;
          positive_copy_of_negative_big(divisor_help, divisor);
        } else {
          divisor_help->size = divisor->size;
          memcpy(divisor_help->bigdigits, divisor->bigdigits,
                 (size_t) divisor->size * sizeof(bigDigitType));
        } /* if */
      } /* if */
      if (unlikely(!ALLOC_BIG_SIZE_OK(quotient, dividend_help->size - divisor_help->size + 1))) {
        FREE_BIG(dividend_help, dividend->size + 2);
        FREE_BIG(divisor_help, divisor->size + 1);
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        quotient->size = dividend_help->size - divisor_help->size + 1;
        quotient->bigdigits[quotient->size - 1] = 0;
        shift = (unsigned int)
            (digitMostSignificantBit(divisor_help->bigdigits[divisor_help->size - 1]) + 1);
        if (shift == 0) {
          /* The most significant digit of divisor_help is 0. Just ignore it */
          dividend_help->size--;
          divisor_help->size--;
          if (divisor_help->size == 1) {
            mdiv1_remainder = uBigDivRem1(dividend_help, divisor_help->bigdigits[0], quotient);
          } else {
            uBigDiv(dividend_help, divisor_help, quotient);
          } /* if */
        } else {
          shift = BIGDIGIT_SIZE - shift;
          uBigLShift(dividend_help, shift);
          uBigLShift(divisor_help, shift);
          uBigDiv(dividend_help, divisor_help, quotient);
        } /* if */
        if (negative) {
          if ((divisor_help->size == 1 && mdiv1_remainder != 0) ||
              (divisor_help->size != 1 && uBigIsNot0(dividend_help))) {
            uBigIncr(quotient);
          } /* if */
          negate_positive_big(quotient);
        } /* if */
        quotient = normalize(quotient);
      } /* if */
      FREE_BIG(dividend_help, dividend->size + 2);
      FREE_BIG(divisor_help, divisor->size + 1);
    } /* if */
    logFunction(printf("bigMDiv --> %s\n", bigHexCStri(quotient)););
    return quotient;
  } /* bigMDiv */



/**
 *  Compute the modulo (remainder) of the integer division bigMDiv.
 *  The modulo has the same sign as the divisor. The memory for the result
 *  is requested and the normalized result is returned. If divisor has
 *  just one digit or if dividend has less digits than divisor the
 *  functions bigMod1() or bigModSizeLess() are called. In the general case
 *  the absolute values of dividend and divisor are taken. Then dividend is
 *  extended by one leading zero digit. After that dividend and divisor
 *  are shifted to the left such that the most significant bit
 *  of divisor is set. This fulfills the preconditions for calling
 *  uBigRem() which does the main work of the division. Afterwards
 *  the result must be shifted to the right to get the remainder.
 *  If dividend and divisor have the same sign the modulo has the same
 *  value as the remainder. If the remainder is zero the modulo
 *  is also zero. If the signs of dividend and divisor are different the
 *  modulo is computed from the remainder by adding dividend.
 *  @return the modulo of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
bigIntType bigMod (const const_bigIntType dividend, const const_bigIntType divisor)

  {
    boolType negative1 = FALSE;
    boolType negative2 = FALSE;
    bigIntType divisor_help;
    unsigned int shift;
    bigIntType modulo;

  /* bigMod */
    logFunction(printf("bigMod(%s,", bigHexCStri(dividend));
                printf("%s)\n", bigHexCStri(divisor)););
    if (divisor->size == 1) {
      modulo = bigMod1(dividend, divisor->bigdigits[0]);
    } else if (dividend->size < divisor->size) {
      modulo = bigModSizeLess(dividend, divisor);
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(modulo, dividend->size + 2))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          negative1 = TRUE;
          positive_copy_of_negative_big(modulo, dividend);
        } else {
          modulo->size = dividend->size;
          memcpy(modulo->bigdigits, dividend->bigdigits,
                 (size_t) dividend->size * sizeof(bigDigitType));
        } /* if */
        modulo->bigdigits[modulo->size] = 0;
        modulo->size++;
      } /* if */
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(divisor_help, divisor->size + 1))) {
        FREE_BIG(modulo,  dividend->size + 2);
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(divisor->bigdigits[divisor->size - 1])) {
          negative2 = TRUE;
          positive_copy_of_negative_big(divisor_help, divisor);
        } else {
          divisor_help->size = divisor->size;
          memcpy(divisor_help->bigdigits, divisor->bigdigits,
                 (size_t) divisor->size * sizeof(bigDigitType));
        } /* if */
      } /* if */
      shift = (unsigned int)
          (digitMostSignificantBit(divisor_help->bigdigits[divisor_help->size - 1]) + 1);
      if (shift == 0) {
        /* The most significant digit of divisor_help is 0. Just ignore it */
        modulo->size--;
        divisor_help->size--;
        if (divisor_help->size == 1) {
          modulo->bigdigits[0] = uBigRem1(modulo, divisor_help->bigdigits[0]);
          memset(&modulo->bigdigits[1], 0,
                 (size_t) (modulo->size - 1) * sizeof(bigDigitType));
        } else {
          uBigRem(modulo, divisor_help);
        } /* if */
        modulo->bigdigits[modulo->size] = 0;
        divisor_help->size++;
      } else {
        shift = BIGDIGIT_SIZE - shift;
        uBigLShift(modulo, shift);
        uBigLShift(divisor_help, shift);
        uBigRem(modulo, divisor_help);
        uBigRShift(modulo, shift);
      } /* if */
      modulo->bigdigits[dividend->size + 1] = 0;
      modulo->size = dividend->size + 2;
      if (negative1) {
        if (negative2) {
          negate_positive_big(modulo);
        } else {
          if (uBigIsNot0(modulo)) {
            negate_positive_big(modulo);
            bigAddTo(modulo, divisor);
          } /* if */
        } /* if */
      } else {
        if (negative2) {
          if (uBigIsNot0(modulo)) {
            bigAddTo(modulo, divisor);
          } /* if */
        } /* if */
      } /* if */
      modulo = normalize(modulo);
      FREE_BIG(divisor_help, divisor->size + 1);
    } /* if */
    logFunction(printf("bigMod --> %s\n", bigHexCStri(modulo)););
    return modulo;
  } /* bigMod */



/**
 *  Multiply two 'bigInteger' numbers.
 *  @return the product of the two numbers.
 */
bigIntType bigMult (const_bigIntType factor1, const_bigIntType factor2)

  {
    boolType negative = FALSE;
    bigIntType factor1_help = NULL;
    bigIntType factor2_help = NULL;
    bigIntType product;

  /* bigMult */
    logFunction(printf("bigMult(%s,", bigHexCStri(factor1));
                printf("%s)\n", bigHexCStri(factor2)););
    if (IS_NEGATIVE(factor1->bigdigits[factor1->size - 1])) {
      negative = TRUE;
      factor1_help = alloc_positive_copy_of_negative_big(factor1);
      factor1 = factor1_help;
      if (unlikely(factor1_help == NULL)) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } /* if */
    } /* if */
    if (IS_NEGATIVE(factor2->bigdigits[factor2->size - 1])) {
      negative = !negative;
      factor2_help = alloc_positive_copy_of_negative_big(factor2);
      factor2 = factor2_help;
      if (unlikely(factor2_help == NULL)) {
        if (factor1_help != NULL) {
          FREE_BIG(factor1_help, factor1_help->size);
        } /* if */
        raise_error(MEMORY_ERROR);
        return NULL;
      } /* if */
    } /* if */
    /* printf("bigMult(" FMT_U_MEM ", " FMT_U_MEM ")\n",
        factor1->size, factor2->size); */
    product = uBigMultK(factor1, factor2, negative);
    if (factor1_help != NULL) {
      FREE_BIG(factor1_help, factor1_help->size);
    } /* if */
    if (factor2_help != NULL) {
      FREE_BIG(factor2_help, factor2_help->size);
    } /* if */
    if (unlikely(product == NULL)) {
      raise_error(MEMORY_ERROR);
    } /* if */
    logFunction(printf("bigMult --> %s\n", bigHexCStri(product)););
    return product;
  } /* bigMult */



/**
 *  Multiply a 'bigInteger' number by a factor and assign the result back to number.
 */
void bigMultAssign (bigIntType *const big_variable, const_bigIntType factor)

  {
    bigIntType product;

  /* bigMultAssign */
    logFunction(printf("bigMultAssign(%s,", bigHexCStri(*big_variable));
                printf("%s)\n", bigHexCStri(factor)););
    if (factor->size == 1) {
      bigMultAssign1(big_variable, factor->bigdigits[0]);
    } else {
      product = bigMult(*big_variable, factor);
      FREE_BIG(*big_variable, (*big_variable)->size);
      *big_variable = product;
    } /* if */
    logFunction(printf("bigMultAssign --> %s\n", bigHexCStri(*big_variable)););
  } /* bigMultAssign */



/**
 *  Multiply factor1 with the bigdigit factor2.
 *  The range of factor2 is restricted and it is the job of the
 *  compiler to assure that factor2 is within the allowed range.
 *  @param factor2 Multiplication factor that must be
 *         in the range of signedBigDigitType.
 *  @return the product of factor1 * factor2.
 */
bigIntType bigMultSignedDigit (const_bigIntType factor1, intType factor2)

  {
    bigIntType product;

  /* bigMultSignedDigit */
    logFunction(printf("bigMultSignedDigit(%s, " FMT_D ")\n",
                       bigHexCStri(factor1), factor2););
    if (unlikely(!ALLOC_BIG_CHECK_SIZE(product, factor1->size + 1))) {
      raise_error(MEMORY_ERROR);
    } else {
      product->size = factor1->size + 1;
      if (factor2 < 0) {
        if (IS_NEGATIVE(factor1->bigdigits[factor1->size - 1])) {
          uBigMultNegativeWithNegatedDigit(factor1, (bigDigitType) -factor2 & BIGDIGIT_MASK, product);
        } else {
          uBigMultPositiveWithNegatedDigit(factor1, (bigDigitType) -factor2 & BIGDIGIT_MASK, product);
        } /* if */
      } else {
        if (IS_NEGATIVE(factor1->bigdigits[factor1->size - 1])) {
          uBigMultNegativeWithDigit(factor1, (bigDigitType) factor2, product);
        } else {
          uBigMultPositiveWithDigit(factor1, (bigDigitType) factor2, product);
        } /* if */
      } /* if */
      product = normalize(product);
    } /* if */
    logFunction(printf("bigMultSignedDigit --> %s\n", bigHexCStri(product)););
    return product;
  } /* bigMultSignedDigit */



/**
 *  Minus sign, negate a 'bigInteger' number.
 *  @return the negated value of the number.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigNegate (const const_bigIntType big1)

  {
    memSizeType pos;
    doubleBigDigitType carry = 1;
    bigIntType resized_negatedValue;
    bigIntType negatedValue;

  /* bigNegate */
    logFunction(printf("bigNegate(%s)\n", bigHexCStri(big1)););
    if (unlikely(!ALLOC_BIG_SIZE_OK(negatedValue, big1->size))) {
      raise_error(MEMORY_ERROR);
    } else {
      negatedValue->size = big1->size;
      pos = 0;
      do {
        carry += ~big1->bigdigits[pos] & BIGDIGIT_MASK;
        negatedValue->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos++;
      } while (pos < big1->size);
      if (IS_NEGATIVE(negatedValue->bigdigits[pos - 1])) {
        if (IS_NEGATIVE(big1->bigdigits[pos - 1])) {
          REALLOC_BIG_CHECK_SIZE(resized_negatedValue, negatedValue, pos, pos + 1);
          if (unlikely(resized_negatedValue == NULL)) {
            FREE_BIG(negatedValue, pos);
            raise_error(MEMORY_ERROR);
            negatedValue = NULL;
          } else {
            negatedValue = resized_negatedValue;
            COUNT3_BIG(pos, pos + 1);
            negatedValue->size++;
            negatedValue->bigdigits[pos] = 0;
          } /* if */
        } else if (negatedValue->bigdigits[pos - 1] == BIGDIGIT_MASK &&
            pos >= 2 && IS_NEGATIVE(negatedValue->bigdigits[pos - 2])) {
          REALLOC_BIG_SIZE_OK(resized_negatedValue, negatedValue, pos, pos - 1);
          /* Avoid a MEMORY_ERROR in the strange case   */
          /* if a 'realloc' which shrinks memory fails. */
          if (likely(resized_negatedValue != NULL)) {
            negatedValue = resized_negatedValue;
          } /* if */
          COUNT3_BIG(pos, pos - 1);
          negatedValue->size--;
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigNegate --> %s\n", bigHexCStri(negatedValue)););
    return negatedValue;
  } /* bigNegate */



/**
 *  Minus sign, negate a 'bigInteger' number.
 *  Big1 is assumed to be a temporary value which is reused.
 *  @return the negated value of the number.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigNegateTemp (bigIntType big1)

  {
    memSizeType pos = 0;
    doubleBigDigitType carry = 1;
    boolType negative;
    bigIntType resized_big1;

  /* bigNegateTemp */
    logFunction(printf("bigNegateTemp(%s)\n", bigHexCStri(big1)););
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    do {
      carry += ~big1->bigdigits[pos] & BIGDIGIT_MASK;
      big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
      carry >>= BIGDIGIT_SIZE;
      pos++;
    } while (pos < big1->size);
    if (IS_NEGATIVE(big1->bigdigits[pos - 1])) {
      if (negative) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, pos, pos + 1);
        if (unlikely(resized_big1 == NULL)) {
          FREE_BIG(big1, pos);
          raise_error(MEMORY_ERROR);
          big1 = NULL;
        } else {
          big1 = resized_big1;
          COUNT3_BIG(pos, pos + 1);
          big1->size++;
          big1->bigdigits[pos] = 0;
        } /* if */
      } else if (big1->bigdigits[pos - 1] == BIGDIGIT_MASK &&
          pos >= 2 && IS_NEGATIVE(big1->bigdigits[pos - 2])) {
        REALLOC_BIG_SIZE_OK(resized_big1, big1, pos, pos - 1);
        /* Avoid a MEMORY_ERROR in the strange case   */
        /* if a 'realloc' which shrinks memory fails. */
        if (likely(resized_big1 != NULL)) {
          big1 = resized_big1;
        } /* if */
        COUNT3_BIG(pos, pos - 1);
        big1->size--;
      } /* if */
    } /* if */
    logFunction(printf("bigNegateTemp --> %s\n", bigHexCStri(big1)););
    return big1;
  } /* bigNegateTemp */



/**
 *  Determine if a 'bigInteger' number is odd.
 *  @return TRUE if the number is odd,
 *          FALSE otherwise.
 */
boolType bigOdd (const const_bigIntType big1)

  { /* bigOdd */
    return (boolType) (big1->bigdigits[0] & 1);
  } /* bigOdd */



bigIntType bigOr (const_bigIntType big1, const_bigIntType big2)

  {
    const_bigIntType help_big;
    memSizeType pos;
    bigDigitType big2_sign;
    bigIntType result;

  /* bigOr */
    logFunction(printf("bigOr(%s,", bigHexCStri(big1));
                printf("%s)\n", bigHexCStri(big2)););
    if (big2->size > big1->size) {
      help_big = big1;
      big1 = big2;
      big2 = help_big;
    } /* if */
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, big1->size))) {
      raise_error(MEMORY_ERROR);
    } else {
      pos = 0;
      do {
        result->bigdigits[pos] = big1->bigdigits[pos] | big2->bigdigits[pos];
        pos++;
      } while (pos < big2->size);
      big2_sign = IS_NEGATIVE(big2->bigdigits[pos - 1]) ? BIGDIGIT_MASK : 0;
      for (; pos < big1->size; pos++) {
        result->bigdigits[pos] = big1->bigdigits[pos] | big2_sign;
      } /* for */
      result->size = pos;
      result = normalize(result);
    } /* if */
    logFunction(printf("bigOr --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigOr */



/**
 *  Convert a string to a 'bigInteger' number.
 *  The string must contain an integer literal consisting of an
 *  optional + or - sign, followed by a sequence of digits. Other
 *  characters as well as leading or trailing whitespace characters are
 *  not allowed. The sequence of digits is taken to be decimal.
 *  @return the 'bigInteger' result of the conversion.
 *  @exception RANGE_ERROR If the string is empty or does not contain
 *             an integer literal.
 *  @exception MEMORY_ERROR  Not enough memory to represent the result.
 */
bigIntType bigParse (const const_striType stri)

  {
    memSizeType result_size;
    boolType okay;
    boolType negative;
    memSizeType position = 0;
    memSizeType limit;
    bigDigitType bigDigit;
    bigIntType result;

  /* bigParse */
    logFunction(printf("bigParse(\"%s\")\n", striAsUnquotedCStri(stri)););
    if (likely(stri->size != 0)) {
      if (stri->mem[0] == ((strElemType) '-')) {
        negative = TRUE;
        position++;
      } else {
        if (stri->mem[0] == ((strElemType) '+')) {
          position++;
        } /* if */
        negative = FALSE;
      } /* if */
    } /* if */
    if (unlikely(position >= stri->size)) {
      logError(printf("bigParse(\"%s\"): "
                      "Digit missing.\n",
                      striAsUnquotedCStri(stri)););
      raise_error(RANGE_ERROR);
      result = NULL;
    } else {
      result_size = (stri->size - 1) / DECIMAL_DIGITS_IN_BIGDIGIT + 1;
      if (unlikely(!ALLOC_BIG(result, result_size))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = 1;
        result->bigdigits[0] = 0;
        okay = TRUE;
        limit = (stri->size - position - 1) % DECIMAL_DIGITS_IN_BIGDIGIT + position + 1;
        do {
          bigDigit = 0;
          while (position < limit && okay) {
            if (likely(stri->mem[position] >= ((strElemType) '0') &&
                       stri->mem[position] <= ((strElemType) '9'))) {
              bigDigit = (bigDigitType) 10 * bigDigit +
                  (bigDigitType) stri->mem[position] - (bigDigitType) '0';
            } else {
              okay = FALSE;
            } /* if */
            position++;
          } /* while */
          uBigMultByPowerOf10AndAdd(result, (doubleBigDigitType) bigDigit);
          limit += DECIMAL_DIGITS_IN_BIGDIGIT;
        } while (position < stri->size && okay);
        if (likely(okay)) {
          memset(&result->bigdigits[result->size], 0,
                 (size_t) (result_size - result->size) * sizeof(bigDigitType));
          result->size = result_size;
          if (negative) {
            negate_positive_big(result);
          } /* if */
          result = normalize(result);
        } else {
          FREE_BIG(result, result_size);
          logError(printf("bigParse(\"%s\"): "
                          "Illegal digit.\n",
                          striAsUnquotedCStri(stri)););
          raise_error(RANGE_ERROR);
          result = NULL;
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigParse --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigParse */



/**
 *  Convert a numeric string, with a specified radix, to a 'bigInteger'.
 *  The numeric string must contain the representation of an integer
 *  in the specified radix. It consists of an optional + or - sign,
 *  followed by a sequence of digits in the specified radix. Digit values
 *  from 10 upward can be encoded with upper or lower case letters.
 *  E.g.: 10 can be encoded with A or a, 11 with B or b, etc. Other
 *  characters as well as leading or trailing whitespace characters
 *  are not allowed.
 *  @param stri Numeric string with integer in the specified radix.
 *  @param base Radix of the integer in the 'stri' parameter.
 *  @return the 'bigInteger' result of the conversion.
 *  @exception RANGE_ERROR If base < 2 or base > 36 holds or
 *             the string does not contain an integer
 *             literal with the specified base.
 *  @exception MEMORY_ERROR  Not enough memory to represent the result.
 */
bigIntType bigParseBased (const const_striType stri, intType base)

  {
    bigIntType result;

  /* bigParseBased */
    logFunction(printf("bigParseBased(\"%s\", " FMT_D ")\n",
                       striAsUnquotedCStri(stri), base););
    switch (castIntTypeForSwitch(base)) {
      /* Cases sorted by probability. */
      case 16: result = bigParseBasedPow2(stri, 4); break;
      case  8: result = bigParseBasedPow2(stri, 3); break;
      case 10: result = bigParse(stri);             break;
      case  2: result = bigParseBasedPow2(stri, 1); break;
      case  4: result = bigParseBasedPow2(stri, 2); break;
      case 32: result = bigParseBasedPow2(stri, 5); break;
      default:
        if (unlikely(base < 2 || base > 36)) {
          logError(printf("bigParseBased(\"%s\", " FMT_D "): "
                          "Base not in allowed range.\n",
                          striAsUnquotedCStri(stri), base););
          raise_error(RANGE_ERROR);
          result = NULL;
        } else {
          result = bigParseBased2To36(stri, (unsigned int) base);
        } /* if */
        break;
    } /* switch */
    logFunction(printf("bigParseBased --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigParseBased */



/**
 *  Predecessor of a 'bigInteger' number.
 *  pred(A) is equivalent to A-1 .
 *  @return big1 - 1 .
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigPred (const const_bigIntType big1)

  {
    memSizeType pos;
    bigIntType resized_predecessor;
    bigIntType predecessor;

  /* bigPred */
    logFunction(printf("bigPred(%s)\n", bigHexCStri(big1)););
    if (unlikely(!ALLOC_BIG_SIZE_OK(predecessor, big1->size))) {
      raise_error(MEMORY_ERROR);
    } else {
      predecessor->size = big1->size;
      pos = 0;
      if (big1->bigdigits[pos] == 0) {
        if (big1->size == 1) {
          predecessor->bigdigits[pos] = BIGDIGIT_MASK;
          pos++;
        } else {
          do {
            predecessor->bigdigits[pos] = BIGDIGIT_MASK;
            pos++;
          } while (big1->bigdigits[pos] == 0);
          /* memset(predecessor->bigdigits, 0xFF, pos * sizeof(bigDigitType)); */
        } /* if */
      } /* if */
      if (pos < big1->size) {
        predecessor->bigdigits[pos] = big1->bigdigits[pos] - 1;
        pos++;
        memcpy(&predecessor->bigdigits[pos], &big1->bigdigits[pos],
               (big1->size - pos) * sizeof(bigDigitType));
        pos = big1->size;
        /* while (pos < big1->size) {
          predecessor->bigdigits[pos] = big1->bigdigits[pos];
          pos++;
        } ** while */
      } /* if */
      if (!IS_NEGATIVE(predecessor->bigdigits[pos - 1])) {
        if (IS_NEGATIVE(big1->bigdigits[pos - 1])) {
          REALLOC_BIG_CHECK_SIZE(resized_predecessor, predecessor, pos, pos + 1);
          if (unlikely(resized_predecessor == NULL)) {
            FREE_BIG(predecessor, pos);
            raise_error(MEMORY_ERROR);
            predecessor = NULL;
          } else {
            predecessor = resized_predecessor;
            COUNT3_BIG(pos, pos + 1);
            predecessor->size++;
            predecessor->bigdigits[pos] = BIGDIGIT_MASK;
          } /* if */
        } else if (predecessor->bigdigits[pos - 1] == 0 &&
            pos >= 2 && !IS_NEGATIVE(predecessor->bigdigits[pos - 2])) {
          REALLOC_BIG_SIZE_OK(resized_predecessor, predecessor, pos, pos - 1);
          /* Avoid a MEMORY_ERROR in the strange case   */
          /* if a 'realloc' which shrinks memory fails. */
          if (likely(resized_predecessor != NULL)) {
            predecessor = resized_predecessor;
          } /* if */
          COUNT3_BIG(pos, pos - 1);
          predecessor->size--;
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigPred --> %s\n", bigHexCStri(predecessor)););
    return predecessor;
  } /* bigPred */



/**
 *  Returns a signed big integer decremented by 1.
 *  Big1 is assumed to be a temporary value which is reused.
 */
bigIntType bigPredTemp (bigIntType big1)

  {
    memSizeType pos = 0;
    boolType negative;
    bigIntType resized_big1;

  /* bigPredTemp */
    logFunction(printf("bigPredTemp(%s)\n", bigHexCStri(big1)););
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    if (big1->bigdigits[pos] == 0) {
      if (big1->size == 1) {
        big1->bigdigits[pos] = BIGDIGIT_MASK;
        pos++;
      } else {
        do {
          big1->bigdigits[pos] = BIGDIGIT_MASK;
          pos++;
        } while (big1->bigdigits[pos] == 0);
        /* memset(big1->bigdigits, 0xFF, pos * sizeof(bigDigitType)); */
      } /* if */
    } /* if */
    if (pos < big1->size) {
      big1->bigdigits[pos]--;
    } /* if */
    pos = big1->size;
    if (!IS_NEGATIVE(big1->bigdigits[pos - 1])) {
      if (negative) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, pos, pos + 1);
        if (unlikely(resized_big1 == NULL)) {
          FREE_BIG(big1, big1->size);
          raise_error(MEMORY_ERROR);
          big1 = NULL;
        } else {
          big1 = resized_big1;
          COUNT3_BIG(pos, pos + 1);
          big1->size++;
          big1->bigdigits[pos] = BIGDIGIT_MASK;
        } /* if */
      } else if (big1->bigdigits[pos - 1] == 0 &&
          pos >= 2 && !IS_NEGATIVE(big1->bigdigits[pos - 2])) {
        REALLOC_BIG_SIZE_OK(resized_big1, big1, pos, pos - 1);
        /* Avoid a MEMORY_ERROR in the strange case   */
        /* if a 'realloc' which shrinks memory fails. */
        if (likely(resized_big1 != NULL)) {
          big1 = resized_big1;
        } /* if */
        COUNT3_BIG(pos, pos - 1);
        big1->size--;
      } /* if */
    } /* if */
    logFunction(printf("bigPredTemp --> %s\n", bigHexCStri(big1)););
    return big1;
  } /* bigPredTemp */



/**
 *  Convert a big integer number to a string using a radix.
 *  The conversion uses the numeral system with the given base.
 *  Digit values from 10 upward are encoded with letters.
 *  For negative numbers a minus sign is prepended.
 *  @param big1 BigInteger number to be converted.
 *  @param upperCase Decides about the letter case.
 *  @return the string result of the conversion.
 *  @exception RANGE_ERROR If base < 2 or base > 36 holds.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
striType bigRadix (const const_bigIntType big1, intType base,
    boolType upperCase)

  {
    striType result;

  /* bigRadix */
    logFunction(printf("bigRadix(%s, " FMT_D ", %d)\n",
                       bigHexCStri(big1), base, upperCase););
    switch (castIntTypeForSwitch(base)) {
      /* Cases sorted by probability. */
      case 16: result = bigRadixPow2(big1, 4,  0xf, upperCase); break;
      case  8: result = bigRadixPow2(big1, 3,  0x7, upperCase); break;
      case 10: result = bigStr(big1);                           break;
      case  2: result = bigRadixPow2(big1, 1,  0x1, upperCase); break;
      case  4: result = bigRadixPow2(big1, 2,  0x3, upperCase); break;
      case 32: result = bigRadixPow2(big1, 5, 0x1f, upperCase); break;
      default:
        if (unlikely(base < 2 || base > 36)) {
          logError(printf("bigRadix((%s, " FMT_D ", %d): "
                          "Base not in allowed range.\n",
                          bigHexCStri(big1), base, upperCase););
          raise_error(RANGE_ERROR);
          result = NULL;
        } else {
          result = bigRadix2To36(big1, (unsigned int) base, upperCase);
        } /* if */
        break;
    } /* switch */
    logFunction(printf("bigRadix --> \"%s\"\n", striAsUnquotedCStri(result)););
    return result;
  } /* bigRadix */



/**
 *  Compute pseudo-random number in the range [low, high].
 *  The random values are uniform distributed. The memory for
 *  the result is requested and the normalized result is returned.
 *  @return a random number such that low <= rand(low, high) and
 *          rand(low, high) <= high holds.
 *  @exception RANGE_ERROR The range is empty (low > high holds).
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigRand (const const_bigIntType low,
    const const_bigIntType high)

  {
    bigIntType scale_limit;
    int usedBits;
    bigDigitType mask;
    memSizeType pos;
    doubleBigDigitType random_number = 0;
    memSizeType randomNumber_size;
    bigIntType randomNumber;

  /* bigRand */
    logFunction(printf("bigRand(%s, %s)\n", bigHexCStri(low), bigHexCStri(high)););
    if (unlikely(bigCmp(low, high) > 0)) {
      logError(printf("bigRand(%s, %s): "
                      "The range is empty (low > high holds).\n",
                      bigHexCStri(low), bigHexCStri(high)););
      raise_error(RANGE_ERROR);
      randomNumber = NULL;
    } else {
      scale_limit = bigSbtr(high, low);
      if (low->size > scale_limit->size) {
        randomNumber_size = low->size + 1;
      } else {
        randomNumber_size = scale_limit->size + 1;
      } /* if */
      if (unlikely(!ALLOC_BIG(randomNumber, randomNumber_size))) {
        raise_error(MEMORY_ERROR);
        randomNumber = NULL;
      } else {
        memset(&randomNumber->bigdigits[scale_limit->size], 0,
               (size_t) (randomNumber_size - scale_limit->size) * sizeof(bigDigitType));
        randomNumber->size = scale_limit->size;
        usedBits = digitMostSignificantBit(scale_limit->bigdigits[scale_limit->size - 1]) + 1;
        if (usedBits == 0) {
          mask = 0;
        } else {
          mask = ((bigDigitType) BIGDIGIT_MASK) >> (BIGDIGIT_SIZE - (memSizeType) (usedBits));
        } /* if */
        do {
          pos = 0;
          do {
            if (random_number == 0) {
              random_number = uintRand();
            } /* if */
            randomNumber->bigdigits[pos] = (bigDigitType) (random_number & BIGDIGIT_MASK);
            random_number >>= BIGDIGIT_SIZE;
            pos++;
          } while (pos < scale_limit->size);
          randomNumber->bigdigits[pos - 1] &= mask;
        } while (bigCmp(randomNumber, scale_limit) > 0);
        randomNumber->size = randomNumber_size;
        bigAddTo(randomNumber, low);
        randomNumber = normalize(randomNumber);
        FREE_BIG(scale_limit, scale_limit->size);
      } /* if */
    } /* if */
    logFunction(printf("bigRand --> %s\n", bigHexCStri(randomNumber)););
    return randomNumber;
  } /* bigRand */



/**
 *  Compute the remainder of the integer division bigDiv.
 *  The remainder has the same sign as the dividend. The memory for the result
 *  is requested and the normalized result is returned. If divisor has
 *  just one digit or if dividend has less digits than divisor the
 *  functions bigRem1() or bigRemSizeLess() are called. In the general case
 *  the absolute values of dividend and divisor are taken. Then dividend is
 *  extended by one leading zero digit. After that dividend and divisor
 *  are shifted to the left such that the most significant bit
 *  of divisor is set. This fulfills the preconditions for calling
 *  uBigRem() which does the main work of the division. Afterwards
 *  the result must be shifted to the right to get the remainder.
 *  @return the remainder of the integer division.
 *  @exception NUMERIC_ERROR If a division by zero occurs.
 */
bigIntType bigRem (const const_bigIntType dividend, const const_bigIntType divisor)

  {
    boolType negative = FALSE;
    bigIntType divisor_help;
    unsigned int shift;
    bigIntType remainder;

  /* bigRem */
    logFunction(printf("bigRem(%s, ", bigHexCStri(dividend));
                printf("%s)\n", bigHexCStri(divisor)););
    if (divisor->size == 1) {
      remainder = bigRem1(dividend, divisor->bigdigits[0]);
    } else if (dividend->size < divisor->size) {
      remainder = bigRemSizeLess(dividend, divisor);
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(remainder, dividend->size + 2))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(dividend->bigdigits[dividend->size - 1])) {
          negative = TRUE;
          positive_copy_of_negative_big(remainder, dividend);
        } else {
          remainder->size = dividend->size;
          memcpy(remainder->bigdigits, dividend->bigdigits,
                 (size_t) dividend->size * sizeof(bigDigitType));
        } /* if */
        remainder->bigdigits[remainder->size] = 0;
        remainder->size++;
      } /* if */
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(divisor_help, divisor->size + 1))) {
        FREE_BIG(remainder, dividend->size + 2);
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        if (IS_NEGATIVE(divisor->bigdigits[divisor->size - 1])) {
          positive_copy_of_negative_big(divisor_help, divisor);
        } else {
          divisor_help->size = divisor->size;
          memcpy(divisor_help->bigdigits, divisor->bigdigits,
                 (size_t) divisor->size * sizeof(bigDigitType));
        } /* if */
      } /* if */
      shift = (unsigned int)
          (digitMostSignificantBit(divisor_help->bigdigits[divisor_help->size - 1]) + 1);
      if (shift == 0) {
        /* The most significant digit of divisor_help is 0. Just ignore it */
        remainder->size--;
        divisor_help->size--;
        if (divisor_help->size == 1) {
          remainder->bigdigits[0] = uBigRem1(remainder, divisor_help->bigdigits[0]);
          memset(&remainder->bigdigits[1], 0,
                 (size_t) (remainder->size - 1) * sizeof(bigDigitType));
        } else {
          uBigRem(remainder, divisor_help);
        } /* if */
        remainder->bigdigits[remainder->size] = 0;
        divisor_help->size++;
      } else {
        shift = BIGDIGIT_SIZE - shift;
        uBigLShift(remainder, shift);
        uBigLShift(divisor_help, shift);
        uBigRem(remainder, divisor_help);
        uBigRShift(remainder, shift);
      } /* if */
      remainder->bigdigits[dividend->size + 1] = 0;
      remainder->size = dividend->size + 2;
      if (negative) {
        negate_positive_big(remainder);
      } /* if */
      remainder = normalize(remainder);
      FREE_BIG(divisor_help, divisor->size + 1);
    } /* if */
    logFunction(printf("bigRem --> %s\n", bigHexCStri(remainder)););
    return remainder;
  } /* bigRem */



/**
 *  Shift a 'bigInteger' number right by rshift bits.
 *  If rshift is negative a left shift is done instead.
 *  A >> B is equivalent to A mdiv 2_ ** B if B >= 0 holds.
 *  A >> B is equivalent to A * 2_ ** -B if B < 0 holds.
 *  @return the right shifted number.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigRShift (const const_bigIntType big1, const intType rshift)

  {
    memSizeType size_reduction;
    unsigned int digit_rshift;
    unsigned int digit_lshift;
    bigDigitType digit_mask;
    bigDigitType low_digit;
    bigDigitType high_digit;
    const bigDigitType *source_digits;
    bigDigitType *dest_digits;
    memSizeType pos;
    memSizeType result_size;
    bigIntType result;

  /* bigRShift */
    logFunction(printf("bigRShift(%s, " FMT_D ")\n",
                       bigHexCStri(big1), rshift););
    if (unlikely(rshift < 0)) {
      if (unlikely(TWOS_COMPLEMENT_INTTYPE && rshift == INTTYPE_MIN)) {
        result = bigLShift(big1, INTTYPE_MAX);
        if (result != NULL) {
          bigLShiftAssign(&result, 1);
        } /* if */
      } else {
        result = bigLShift(big1, -rshift);
      } /* if */
    } else if (big1->size <= (uintType) rshift >> BIGDIGIT_LOG2_SIZE) {
      if (unlikely(!ALLOC_BIG_SIZE_OK(result, 1))) {
        raise_error(MEMORY_ERROR);
      } else {
        result->size = 1;
        if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
          result->bigdigits[0] = BIGDIGIT_MASK;
        } else {
          result->bigdigits[0] = 0;
        } /* if */
      } /* if */
    } else {
      size_reduction = (memSizeType) ((uintType) rshift >> BIGDIGIT_LOG2_SIZE);
      result_size = big1->size - size_reduction;
      if ((rshift & BIGDIGIT_SIZE_MASK) == 0) {
        if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
          raise_error(MEMORY_ERROR);
        } else {
          result->size = result_size;
          memcpy(result->bigdigits, &big1->bigdigits[size_reduction],
                 (size_t) result_size * sizeof(bigDigitType));
        } /* if */
      } else {
        digit_rshift = (unsigned int) ((uintType) rshift & BIGDIGIT_SIZE_MASK);
        digit_lshift = BIGDIGIT_SIZE - digit_rshift;
        if (result_size > 1) {
          high_digit = big1->bigdigits[big1->size - 1];
          if (IS_NEGATIVE(high_digit)) {
            digit_mask = (BIGDIGIT_MASK << (digit_rshift - 1)) & BIGDIGIT_MASK;
            if ((digit_rshift == 1 && high_digit == BIGDIGIT_MASK) ||
                (high_digit & digit_mask) == digit_mask) {
              result_size--;
            } /* if */
          } else {
            if ((digit_rshift == 1 && high_digit == 0) ||
                high_digit >> (digit_rshift - 1) == 0) {
              result_size--;
            } /* if */
          } /* if */
        } /* if */
        if (unlikely(!ALLOC_BIG_SIZE_OK(result, result_size))) {
          raise_error(MEMORY_ERROR);
        } else {
          result->size = result_size;
          source_digits = &big1->bigdigits[size_reduction];
          dest_digits = result->bigdigits;
          high_digit = *source_digits++;
          low_digit = high_digit >> digit_rshift;
          for (pos = big1->size - size_reduction - 1; pos != 0; pos--) {
            high_digit = *source_digits++;
            *dest_digits++ = low_digit | ((high_digit << digit_lshift) & BIGDIGIT_MASK);
            low_digit = high_digit >> digit_rshift;
          } /* for */
          if ((memSizeType) (dest_digits - result->bigdigits) < result_size) {
            if (IS_NEGATIVE(high_digit)) {
              *dest_digits = low_digit | ((BIGDIGIT_MASK << digit_lshift) & BIGDIGIT_MASK);
            } else {
              *dest_digits = low_digit;
            } /* if */
          } /* if */
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigRShift --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigRShift */



/**
 *  Shift a number right by rshift bits and assign the result back to number.
 *  If rshift is negative a left shift is done instead.
 *  @exception MEMORY_ERROR Not enough memory to represent the new value.
 */
void bigRShiftAssign (bigIntType *const big_variable, intType rshift)

  {
    bigIntType big1;
    memSizeType size_reduction;
    unsigned int digit_rshift;
    unsigned int digit_lshift;
    bigDigitType low_digit;
    bigDigitType high_digit;
    const bigDigitType *source_digits;
    bigDigitType *dest_digits;
    bigIntType resized_big1;
    memSizeType pos;
    memSizeType big1_size;

  /* bigRShiftAssign */
    logFunction(printf("bigRShiftAssign(%s, " FMT_D ")\n",
                       bigHexCStri(*big_variable), rshift););
    if (unlikely(rshift < 0)) {
      if (unlikely(TWOS_COMPLEMENT_INTTYPE && rshift == INTTYPE_MIN)) {
        bigLShiftAssign(big_variable, INTTYPE_MAX);
        bigLShiftAssign(big_variable, 1);
      } else {
        bigLShiftAssign(big_variable, -rshift);
      } /* if */
    } else {
      big1 = *big_variable;
      if (big1->size <= (uintType) rshift >> BIGDIGIT_LOG2_SIZE) {
        if (unlikely(!ALLOC_BIG_SIZE_OK(*big_variable, 1))) {
          raise_error(MEMORY_ERROR);
        } else {
          (*big_variable)->size = 1;
          if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
            (*big_variable)->bigdigits[0] = BIGDIGIT_MASK;
          } else {
            (*big_variable)->bigdigits[0] = 0;
          } /* if */
          FREE_BIG(big1, big1->size);
        } /* if */
      } else {
        size_reduction = (memSizeType) ((uintType) rshift >> BIGDIGIT_LOG2_SIZE);
        if ((rshift & BIGDIGIT_SIZE_MASK) == 0) {
          if (rshift != 0) {
            big1_size = big1->size;
            memmove(big1->bigdigits, &big1->bigdigits[size_reduction],
                    (size_t) (big1_size - size_reduction) * sizeof(bigDigitType));
            REALLOC_BIG_SIZE_OK(resized_big1, big1, big1_size, big1_size - size_reduction);
            /* Avoid a MEMORY_ERROR in the strange case   */
            /* if a 'realloc' which shrinks memory fails. */
            if (likely(resized_big1 != NULL)) {
              big1 = resized_big1;
              *big_variable = big1;
            } /* if */
            COUNT3_BIG(big1_size, big1_size - size_reduction);
            big1->size -= size_reduction;
          } /* if */
        } else {
          digit_rshift = (unsigned int) ((uintType) rshift & BIGDIGIT_SIZE_MASK);
          digit_lshift = BIGDIGIT_SIZE - digit_rshift;
          source_digits = &big1->bigdigits[size_reduction];
          dest_digits = big1->bigdigits;
          high_digit = *source_digits++;
          low_digit = high_digit >> digit_rshift;
          for (pos = big1->size - size_reduction - 1; pos != 0; pos--) {
            high_digit = *source_digits++;
            *dest_digits++ = low_digit | ((high_digit << digit_lshift) & BIGDIGIT_MASK);
            low_digit = high_digit >> digit_rshift;
          } /* for */
          if (IS_NEGATIVE(high_digit)) {
            *dest_digits = low_digit | ((BIGDIGIT_MASK << digit_lshift) & BIGDIGIT_MASK);
            if (*dest_digits == BIGDIGIT_MASK) {
              if (size_reduction == 0) {
                *big_variable = normalize(big1);
              } else {
                pos = big1->size - size_reduction;
                if (pos >= 2 && IS_NEGATIVE(big1->bigdigits[pos - 2])) {
                  pos--;
                } /* if */
                REALLOC_BIG_SIZE_OK(resized_big1, big1, big1->size, pos);
                /* Avoid a MEMORY_ERROR in the strange case   */
                /* if a 'realloc' which shrinks memory fails. */
                if (likely(resized_big1 != NULL)) {
                  big1 = resized_big1;
                  *big_variable = big1;
                } /* if */
                COUNT3_BIG(big1->size, pos);
                big1->size = pos;
                size_reduction = 0;
              } /* if */
            } /* if */
          } else {
            *dest_digits = low_digit;
            if (low_digit == 0) {
              if (size_reduction == 0) {
                *big_variable = normalize(big1);
              } else {
                pos = big1->size - size_reduction;
                if (pos >= 2 && !IS_NEGATIVE(big1->bigdigits[pos - 2])) {
                  pos--;
                } /* if */
                REALLOC_BIG_SIZE_OK(resized_big1, big1, big1->size, pos);
                /* Avoid a MEMORY_ERROR in the strange case   */
                /* if a 'realloc' which shrinks memory fails. */
                if (likely(resized_big1 != NULL)) {
                  big1 = resized_big1;
                  *big_variable = big1;
                } /* if */
                COUNT3_BIG(big1->size, pos);
                big1->size = pos;
                size_reduction = 0;
              } /* if */
            } /* if */
          } /* if */
          if (size_reduction != 0) {
            big1_size = big1->size;
            REALLOC_BIG_SIZE_OK(resized_big1, big1, big1_size, big1_size - size_reduction);
            /* Avoid a MEMORY_ERROR in the strange case   */
            /* if a 'realloc' which shrinks memory fails. */
            if (likely(resized_big1 != NULL)) {
              big1 = resized_big1;
              *big_variable = big1;
            } /* if */
            COUNT3_BIG(big1_size, big1_size - size_reduction);
            big1->size -= size_reduction;
          } /* if */
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigRShiftAssign --> %s\n", bigHexCStri(*big_variable)););
  } /* bigRShiftAssign */



/**
 *  Compute the subtraction of two 'bigInteger' numbers.
 *  @return the difference of the two numbers.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigSbtr (const const_bigIntType minuend, const const_bigIntType subtrahend)

  {
    memSizeType pos;
    doubleBigDigitType carry = 1;
    doubleBigDigitType minuend_sign;
    doubleBigDigitType subtrahend_sign;
    bigIntType difference;

  /* bigSbtr */
    logFunction(printf("bigSbtr(%s,", bigHexCStri(minuend));
                printf("%s)\n", bigHexCStri(subtrahend)););
    if (minuend->size >= subtrahend->size) {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(difference, minuend->size + 1))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        pos = 0;
        do {
          carry += (doubleBigDigitType) minuend->bigdigits[pos] +
              (~subtrahend->bigdigits[pos] & BIGDIGIT_MASK);
          difference->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
          pos++;
        } while (pos < subtrahend->size);
        subtrahend_sign = IS_NEGATIVE(subtrahend->bigdigits[pos - 1]) ? 0 : BIGDIGIT_MASK;
        for (; pos < minuend->size; pos++) {
          carry += minuend->bigdigits[pos] + subtrahend_sign;
          difference->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
        if (IS_NEGATIVE(minuend->bigdigits[pos - 1])) {
          subtrahend_sign--;
        } /* if */
        difference->bigdigits[pos] = (bigDigitType) ((carry + subtrahend_sign) & BIGDIGIT_MASK);
        difference->size = pos + 1;
        difference = normalize(difference);
      } /* if */
    } else {
      if (unlikely(!ALLOC_BIG_CHECK_SIZE(difference, subtrahend->size + 1))) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } else {
        pos = 0;
        do {
          carry += (doubleBigDigitType) minuend->bigdigits[pos] +
              (~subtrahend->bigdigits[pos] & BIGDIGIT_MASK);
          difference->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
          pos++;
        } while (pos < minuend->size);
        minuend_sign = IS_NEGATIVE(minuend->bigdigits[pos - 1]) ? BIGDIGIT_MASK : 0;
        for (; pos < subtrahend->size; pos++) {
          carry += minuend_sign + (~subtrahend->bigdigits[pos] & BIGDIGIT_MASK);
          difference->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
        subtrahend_sign = IS_NEGATIVE(subtrahend->bigdigits[pos - 1]) ? 0 : BIGDIGIT_MASK;
        if (IS_NEGATIVE(minuend->bigdigits[minuend->size - 1])) {
          subtrahend_sign--;
        } /* if */
        difference->bigdigits[pos] = (bigDigitType) ((carry + subtrahend_sign) & BIGDIGIT_MASK);
        difference->size = pos + 1;
        difference = normalize(difference);
      } /* if */
    } /* if */
    logFunction(printf("bigSbtr --> %s\n", bigHexCStri(difference)););
    return difference;
  } /* bigSbtr */



/**
 *  Decrement a 'bigInteger' variable by a delta.
 *  Subtracts delta from *big_variable. The operation is done in
 *  place and *big_variable is only resized if necessary.
 *  If the size of delta is smaller than *big_variable the
 *  algorithm tries to save computations. Therefore there are
 *  checks for carry != 0 and carry == 0.
 *  In case the resizing fails the content of *big_variable
 *  is freed and *big_variable is set to NULL.
 *  @param delta The delta to be subtracted from *big_variable.
 *  @exception MEMORY_ERROR If the resizing of *big_variable fails.
 */
void bigSbtrAssign (bigIntType *const big_variable, const const_bigIntType delta)

  {
    bigIntType big1;
    memSizeType pos;
    memSizeType big1_size;
    boolType delta_negative;
    doubleBigDigitType carry = 1;
    doubleBigDigitType big1_sign;
    doubleBigDigitType delta_sign;
    bigIntType resized_big1;

  /* bigSbtrAssign */
    logFunction(printf("bigSbtrAssign(%s,", bigHexCStri(*big_variable));
                printf("%s)\n", bigHexCStri(delta)););
    big1 = *big_variable;
    if (big1->size >= delta->size) {
      big1_size = big1->size;
      big1_sign = IS_NEGATIVE(big1->bigdigits[big1_size - 1]) ? BIGDIGIT_MASK : 0;
      /* It is possible that big1 == delta holds. Therefore the check */
      /* for negative delta must be done before big1 is changed.      */
      delta_negative = IS_NEGATIVE(delta->bigdigits[delta->size - 1]);
      pos = 0;
      do {
        carry += (doubleBigDigitType) big1->bigdigits[pos] +
            (~delta->bigdigits[pos] & BIGDIGIT_MASK);
        big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        carry >>= BIGDIGIT_SIZE;
        pos++;
      } while (pos < delta->size);
      if (delta_negative) {
        for (; carry != 0 && pos < big1_size; pos++) {
          carry += big1->bigdigits[pos];
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
      } else {
        for (; carry == 0 && pos < big1_size; pos++) {
          carry = (doubleBigDigitType) big1->bigdigits[pos] + BIGDIGIT_MASK;
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
        carry += BIGDIGIT_MASK;
      } /* if */
      carry += big1_sign;
      carry &= BIGDIGIT_MASK;
      /* Now the only possible values for carry are 0 and BIGDIGIT_MASK. */
      if ((carry != 0 || IS_NEGATIVE(big1->bigdigits[big1_size - 1])) &&
          (carry != BIGDIGIT_MASK || !IS_NEGATIVE(big1->bigdigits[big1_size - 1]))) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, big1_size, big1_size + 1);
        if (unlikely(resized_big1 == NULL)) {
          FREE_BIG(big1, big1_size);
          *big_variable = NULL;
          raise_error(MEMORY_ERROR);
        } else {
          /* It is possible that big1 == delta holds. Since */
          /* 'delta' is not used after realloc() enlarged   */
          /* 'big1' a correction of delta is not necessary. */
          big1 = resized_big1;
          COUNT3_BIG(big1_size, big1_size + 1);
          big1->size++;
          big1->bigdigits[big1_size] = (bigDigitType) (carry);
          *big_variable = big1;
        } /* if */
      } else {
        *big_variable = normalize(big1);
      } /* if */
    } else {
      REALLOC_BIG_CHECK_SIZE(resized_big1, big1, big1->size, delta->size + 1);
      if (unlikely(resized_big1 == NULL)) {
        FREE_BIG(big1, big1->size);
        *big_variable = NULL;
        raise_error(MEMORY_ERROR);
      } else {
        big1 = resized_big1;
        COUNT3_BIG(big1->size, delta->size + 1);
        big1_sign = IS_NEGATIVE(big1->bigdigits[big1->size - 1]) ? BIGDIGIT_MASK : 0;
        pos = 0;
        do {
          carry += (doubleBigDigitType) big1->bigdigits[pos] +
              (~delta->bigdigits[pos] & BIGDIGIT_MASK);
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
          pos++;
        } while (pos < big1->size);
        delta_sign = IS_NEGATIVE(delta->bigdigits[delta->size - 1]) ? 0 : BIGDIGIT_MASK;
        for (; pos < delta->size; pos++) {
          carry += big1_sign + (~delta->bigdigits[pos] & BIGDIGIT_MASK);
          big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
          carry >>= BIGDIGIT_SIZE;
        } /* for */
        carry += big1_sign + delta_sign;
        big1->bigdigits[pos] = (bigDigitType) (carry & BIGDIGIT_MASK);
        big1->size = pos + 1;
        *big_variable = normalize(big1);
      } /* if */
    } /* if */
    logFunction(printf("bigSbtrAssign --> %s\n", bigHexCStri(*big_variable)););
  } /* bigSbtrAssign */



/**
 *  Compute the subtraction of two 'bigInteger' numbers.
 *  Minuend is assumed to be a temporary value which is reused.
 *  @return the difference of the two numbers in 'minuend'.
 */
bigIntType bigSbtrTemp (bigIntType minuend, const_bigIntType subtrahend)

  { /* bigSbtrTemp */
    bigSbtrAssign(&minuend, subtrahend);
    return minuend;
  } /* bigSbtrTemp */



/**
 *  Compute the square of a 'bigInteger'.
 *  This function is used by the compiler to optimize
 *  multiplication and exponentiation operations.
 *  @return the square of big1.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigSquare (const_bigIntType big1)

  {
    bigIntType big1_help = NULL;
    bigIntType square;

  /* bigSquare */
    logFunction(printf("bigSquare(%s)\n", bigHexCStri(big1)););
    if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
      big1_help = alloc_positive_copy_of_negative_big(big1);
      big1 = big1_help;
      if (unlikely(big1_help == NULL)) {
        raise_error(MEMORY_ERROR);
        return NULL;
      } /* if */
    } /* if */
    /* printf("bigSquare(" FMT_U_MEM ")\n", big1->size); */
    square = uBigSquareK(big1);
    if (big1_help != NULL) {
      FREE_BIG(big1_help, big1_help->size);
    } /* if */
    if (unlikely(square == NULL)) {
      raise_error(MEMORY_ERROR);
    } /* if */
    logFunction(printf("bigSquare --> %s\n", bigHexCStri(square)););
    return square;
  } /* bigSquare */



/**
 *  Convert a 'bigInteger' number to a string.
 *  The number is converted to a string with decimal representation.
 *  For negative numbers a minus sign is prepended.
 *  @return the string result of the conversion.
 *  @exception MEMORY_ERROR  Not enough memory to represent the result.
 */
striType bigStr (const const_bigIntType big1)

  {
    bigIntType unsigned_big;
    memSizeType pos;
    memSizeType result_size;
    memSizeType final_result_size;
    striType resized_result;
    striType result;

  /* bigStr */
    logFunction(printf("bigStr(%s)\n", bigHexCStri(big1)););
    if (unlikely((MAX_STRI_LEN <= (MAX_MEMSIZETYPE - 1) / OCTAL_DIGIT_BITS + 2 &&
                 big1->size > ((MAX_STRI_LEN - 2) * OCTAL_DIGIT_BITS + 1) / BIGDIGIT_SIZE) ||
                 big1->size > MAX_MEMSIZETYPE / BIGDIGIT_SIZE)) {
      raise_error(MEMORY_ERROR);
      result = NULL;
    } else {
      /* The size of the result is estimated by computing the    */
      /* number of octal digits plus one character for the sign. */
      result_size = (big1->size * BIGDIGIT_SIZE - 1) / OCTAL_DIGIT_BITS + 2;
      if (unlikely(!ALLOC_STRI_SIZE_OK(result, result_size))) {
        raise_error(MEMORY_ERROR);
        result = NULL;
      } else {
        if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
          unsigned_big = alloc_positive_copy_of_negative_big(big1);
        } else if (likely(ALLOC_BIG_SIZE_OK(unsigned_big, big1->size))) {
          unsigned_big->size = big1->size;
          memcpy(unsigned_big->bigdigits, big1->bigdigits,
                 (size_t) big1->size * sizeof(bigDigitType));
        } /* if */
        if (unlikely(unsigned_big == NULL)) {
          FREE_STRI(result, result_size);
          raise_error(MEMORY_ERROR);
          result = NULL;
        } else {
          /* pos = basicToStri(unsigned_big, result, result_size - 1); */
          pos = binaryToStri(unsigned_big, result, (unsigned int)
                             memSizeMostSignificantBit(result_size) + 1,
                             FALSE, result_size - 1);
          FREE_BIG(unsigned_big, big1->size);
          pos++;
          if (IS_NEGATIVE(big1->bigdigits[big1->size - 1])) {
            final_result_size = result_size - pos + 1;
            result->mem[0] = '-';
            memmove(&result->mem[1], &result->mem[pos],
                    (result_size - pos) * sizeof(strElemType));
          } else {
            final_result_size = result_size - pos;
            memmove(&result->mem[0], &result->mem[pos],
                    (result_size - pos) * sizeof(strElemType));
          } /* if */
          result->size = final_result_size;
          if (final_result_size < result_size) {
            REALLOC_STRI_SIZE_SMALLER(resized_result, result, result_size, final_result_size);
            if (unlikely(resized_result == NULL)) {
              FREE_STRI(result, result_size);
              raise_error(MEMORY_ERROR);
              result = NULL;
            } else {
              result = resized_result;
              COUNT3_STRI(result_size, final_result_size);
            } /* if */
          } /* if */
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigStr --> \"%s\"\n", striAsUnquotedCStri(result)););
    return result;
  } /* bigStr */



/**
 *  Successor of a 'bigInteger' number.
 *  succ(A) is equivalent to A+1 .
 *  @return big1 + 1 .
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bigIntType bigSucc (const const_bigIntType big1)

  {
    memSizeType pos;
    bigIntType resized_successor;
    bigIntType successor;

  /* bigSucc */
    logFunction(printf("bigSucc(%s)\n", bigHexCStri(big1)););
    if (unlikely(!ALLOC_BIG_SIZE_OK(successor, big1->size))) {
      raise_error(MEMORY_ERROR);
    } else {
      successor->size = big1->size;
      pos = 0;
      if (big1->bigdigits[pos] == BIGDIGIT_MASK) {
        if (big1->size == 1) {
          successor->bigdigits[pos] = 0;
          pos++;
        } else {
          do {
            successor->bigdigits[pos] = 0;
            pos++;
          } while (big1->bigdigits[pos] == BIGDIGIT_MASK);
          /* memset(successor->bigdigits, 0, pos * sizeof(bigDigitType)); */
        } /* if */
      } /* if */
      if (pos < big1->size) {
        successor->bigdigits[pos] = big1->bigdigits[pos] + 1;
        pos++;
        memcpy(&successor->bigdigits[pos], &big1->bigdigits[pos],
               (big1->size - pos) * sizeof(bigDigitType));
        pos = big1->size;
        /* while (pos < big1->size) {
          successor->bigdigits[pos] = big1->bigdigits[pos];
          pos++;
        } ** while */
      } /* if */
      if (IS_NEGATIVE(successor->bigdigits[pos - 1])) {
        if (!IS_NEGATIVE(big1->bigdigits[pos - 1])) {
          REALLOC_BIG_CHECK_SIZE(resized_successor, successor, pos, pos + 1);
          if (unlikely(resized_successor == NULL)) {
            FREE_BIG(successor, pos);
            raise_error(MEMORY_ERROR);
            successor = NULL;
          } else {
            successor = resized_successor;
            COUNT3_BIG(pos, pos + 1);
            successor->size++;
            successor->bigdigits[pos] = 0;
          } /* if */
        } else if (successor->bigdigits[pos - 1] == BIGDIGIT_MASK &&
            pos >= 2 && IS_NEGATIVE(successor->bigdigits[pos - 2])) {
          /* Avoid a MEMORY_ERROR in the strange case   */
          /* if a 'realloc' which shrinks memory fails. */
          REALLOC_BIG_SIZE_OK(resized_successor, successor, pos, pos - 1);
          if (likely(resized_successor != NULL)) {
            successor = resized_successor;
          } /* if */
          COUNT3_BIG(pos, pos - 1);
          successor->size--;
        } /* if */
      } /* if */
    } /* if */
    logFunction(printf("bigSucc --> %s\n", bigHexCStri(successor)););
    return successor;
  } /* bigSucc */



/**
 *  Successor of a 'bigInteger' number.
 *  Big1 is assumed to be a temporary value which is reused.
 *  @return big1 + 1 .
 */
bigIntType bigSuccTemp (bigIntType big1)

  {
    memSizeType pos = 0;
    boolType negative;
    bigIntType resized_big1;

  /* bigSuccTemp */
    logFunction(printf("bigSuccTemp(%s)\n", bigHexCStri(big1)););
    negative = IS_NEGATIVE(big1->bigdigits[big1->size - 1]);
    if (big1->bigdigits[pos] == BIGDIGIT_MASK) {
      if (big1->size == 1) {
        big1->bigdigits[pos] = 0;
        pos++;
      } else {
        do {
          big1->bigdigits[pos] = 0;
          pos++;
        } while (big1->bigdigits[pos] == BIGDIGIT_MASK);
        /* memset(big1->bigdigits, 0, pos * sizeof(bigDigitType)); */
      } /* if */
    } /* if */
    if (pos < big1->size) {
      big1->bigdigits[pos]++;
    } /* if */
    pos = big1->size;
    if (IS_NEGATIVE(big1->bigdigits[pos - 1])) {
      if (!negative) {
        REALLOC_BIG_CHECK_SIZE(resized_big1, big1, pos, pos + 1);
        if (unlikely(resized_big1 == NULL)) {
          FREE_BIG(big1, big1->size);
          raise_error(MEMORY_ERROR);
          big1 = NULL;
        } else {
          big1 = resized_big1;
          COUNT3_BIG(pos, pos + 1);
          big1->size++;
          big1->bigdigits[pos] = 0;
        } /* if */
      } else if (big1->bigdigits[pos - 1] == BIGDIGIT_MASK &&
          pos >= 2 && IS_NEGATIVE(big1->bigdigits[pos - 2])) {
        REALLOC_BIG_SIZE_OK(resized_big1, big1, pos, pos - 1);
        /* Avoid a MEMORY_ERROR in the strange case   */
        /* if a 'realloc' which shrinks memory fails. */
        if (likely(resized_big1 != NULL)) {
          big1 = resized_big1;
        } /* if */
        COUNT3_BIG(pos, pos - 1);
        big1->size--;
      } /* if */
    } /* if */
    logFunction(printf("bigSuccTemp --> %s\n", bigHexCStri(big1)););
    return big1;
  } /* bigSuccTemp */



/**
 *  Convert a 'bigInteger' into a big-endian 'bstring'.
 *  The result uses binary representation with a base of 256.
 *  @param big1 BigInteger number to be converted.
 *  @param isSigned Determines the signedness of the result.
 *         If 'isSigned' is TRUE the result is encoded with the
 *         twos-complement representation. In this case a negative
 *         'big1' is converted to a result where the most significant
 *         byte (the first byte) has an ordinal > BYTE_MAX (=127).
 *  @return a bstring with the big-endian representation.
 *  @exception RANGE_ERROR If 'big1' is negative and 'isSigned' is FALSE.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bstriType bigToBStriBe (const const_bigIntType big1, const boolType isSigned)

  {
    memSizeType pos;
    int byteNum;
    bigDigitType digit;
    memSizeType charIndex;
    memSizeType result_size;
    bstriType result;

  /* bigToBStriBe */
    logFunction(printf("bigToBStriBe(%s, %d)\n", bigHexCStri(big1), isSigned););
    /* The expression computing result_size does not overflow           */
    /* because the number of bytes in a bigInteger fits in memSizeType. */
    result_size = big1->size * (BIGDIGIT_SIZE >> 3);
    pos = big1->size - 1;
    digit = big1->bigdigits[pos];
    byteNum = (BIGDIGIT_SIZE >> 3) - 1;
    if (isSigned) {
      if (IS_NEGATIVE(digit)) {
        while (byteNum > 0 && (digit >> byteNum * CHAR_BIT & 0xFF) == UBYTE_MAX) {
          result_size--;
          byteNum--;
        } /* while */
        if (byteNum < 3 && (digit >> byteNum * CHAR_BIT & 0xFF) <= BYTE_MAX) {
          result_size++;
          byteNum++;
        } /* if */
      } else {
        while (byteNum > 0 && (digit >> byteNum * CHAR_BIT & 0xFF) == 0) {
          result_size--;
          byteNum--;
        } /* while */
        if (byteNum < 3 && (digit >> byteNum * CHAR_BIT & 0xFF) > BYTE_MAX) {
          result_size++;
          byteNum++;
        } /* if */
      } /* if */
    } else {
      if (unlikely(IS_NEGATIVE(digit))) {
        logError(printf("bigToBStriBe(%s, %d): "
                        "Number is negative and 'isSigned' is FALSE.\n",
                        bigHexCStri(big1), isSigned););
        raise_error(RANGE_ERROR);
        return NULL;
      } else {
        if (digit == 0 && pos > 0) {
          result_size -= (BIGDIGIT_SIZE >> 3);
          pos--;
          digit = big1->bigdigits[pos];
        } /* if */
        while (byteNum > 0 && (digit >> byteNum * CHAR_BIT & 0xFF) == 0) {
          result_size--;
          byteNum--;
        } /* while */
      } /* if */
    } /* if */
    if (unlikely(!ALLOC_BSTRI_CHECK_SIZE(result, result_size))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = result_size;
      charIndex = 0;
      for (; byteNum >= 0; byteNum--) {
        result->mem[charIndex] = (ucharType) (digit >> byteNum * CHAR_BIT & 0xFF);
        charIndex++;
      } /* for */
      while (pos > 0) {
        pos--;
        digit = big1->bigdigits[pos];
        for (byteNum = (BIGDIGIT_SIZE >> 3) - 1; byteNum >= 0; byteNum--) {
          result->mem[charIndex] = (ucharType) (digit >> byteNum * CHAR_BIT & 0xFF);
          charIndex++;
        } /* for */
      } /* while */
    } /* if */
    logFunction(printf("bigToBStriBe --> \"%s\"\n",
                       bstriAsUnquotedCStri(result)););
    return result;
  } /* bigToBStriBe */



/**
 *  Convert a 'bigInteger' into a little-endian 'bstring'.
 *  The result uses binary representation with a base of 256.
 *  @param big1 BigInteger number to be converted.
 *  @param isSigned Determines the signedness of the result.
 *         If 'isSigned' is TRUE the result is encoded with the
 *         twos-complement representation. In this case a negative
 *         'big1' is converted to a result where the most significant
 *         byte (the last byte) has an ordinal > BYTE_MAX (=127).
 *  @return a bstring with the little-endian representation.
 *  @exception RANGE_ERROR If 'big1' is negative and 'isSigned' is FALSE.
 *  @exception MEMORY_ERROR Not enough memory to represent the result.
 */
bstriType bigToBStriLe (const const_bigIntType big1, const boolType isSigned)

  {
    memSizeType pos;
    int byteNum;
    bigDigitType digit;
    memSizeType charIndex;
    memSizeType result_size;
    bstriType result;

  /* bigToBStriLe */
    logFunction(printf("bigToBStriLe(%s, %d)\n", bigHexCStri(big1), isSigned););
    /* The expression computing result_size does not overflow           */
    /* because the number of bytes in a bigInteger fits in memSizeType. */
    result_size = big1->size * (BIGDIGIT_SIZE >> 3);
    pos = big1->size - 1;
    digit = big1->bigdigits[pos];
    byteNum = (BIGDIGIT_SIZE >> 3) - 1;
    if (isSigned) {
      if (IS_NEGATIVE(digit)) {
        while (byteNum > 0 && (digit >> byteNum * CHAR_BIT & 0xFF) == UBYTE_MAX) {
          result_size--;
          byteNum--;
        } /* while */
        if (byteNum < 3 && (digit >> byteNum * CHAR_BIT & 0xFF) <= BYTE_MAX) {
          result_size++;
          byteNum++;
        } /* if */
      } else {
        while (byteNum > 0 && (digit >> byteNum * CHAR_BIT & 0xFF) == 0) {
          result_size--;
          byteNum--;
        } /* while */
        if (byteNum < 3 && (digit >> byteNum * CHAR_BIT & 0xFF) > BYTE_MAX) {
          result_size++;
          byteNum++;
        } /* if */
      } /* if */
    } else {
      if (unlikely(IS_NEGATIVE(digit))) {
        logError(printf("bigToBStriLe(%s, %d): "
                        "Number is negative and 'isSigned' is FALSE.\n",
                        bigHexCStri(big1), isSigned););
        raise_error(RANGE_ERROR);
        return NULL;
      } else {
        if (digit == 0 && pos > 0) {
          result_size -= (BIGDIGIT_SIZE >> 3);
          pos--;
          digit = big1->bigdigits[pos];
        } /* if */
        while (byteNum > 0 && (digit >> byteNum * CHAR_BIT & 0xFF) == 0) {
          result_size--;
          byteNum--;
        } /* while */
      } /* if */
    } /* if */
    if (unlikely(!ALLOC_BSTRI_CHECK_SIZE(result, result_size))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = result_size;
      charIndex = result_size - 1;
      for (; byteNum >= 0; byteNum--) {
        result->mem[charIndex] = (ucharType) (digit >> byteNum * CHAR_BIT & 0xFF);
        charIndex--;
      } /* for */
      while (pos > 0) {
        pos--;
        digit = big1->bigdigits[pos];
        for (byteNum = (BIGDIGIT_SIZE >> 3) - 1; byteNum >= 0; byteNum--) {
          result->mem[charIndex] = (ucharType) (digit >> byteNum * CHAR_BIT & 0xFF);
          charIndex--;
        } /* for */
      } /* while */
    } /* if */
    logFunction(printf("bigToBStriLe -->\"%s\"\n",
                       bstriAsUnquotedCStri(result)););
    return result;
  } /* bigToBStriLe */



/**
 *  Convert a 'bigInteger' to an 'int16Type' number.
 *  @return the int16Type result of the conversion.
 *  @param err_info Unchanged if the function succeeds or
 *                  RANGE_ERROR The number is too small or too big
 *                  to fit into a int16Type value.
 */
int16Type bigToInt16 (const const_bigIntType big1, errInfoType *err_info)

  {
    memSizeType pos;
    int32Type result;

  /* bigToInt16 */
    logFunction(printf("bigToInt16(%s)\n", bigHexCStri(big1)););
#if BIGDIGIT_SIZE > 16
    if (unlikely(big1->size > 1)) {
#else
    if (unlikely(big1->size > sizeof(int16Type) / (BIGDIGIT_SIZE >> 3))) {
#endif
      logError(printf("bigToInt16(%s): Number too big or too small.\n",
                      bigHexCStri(big1)););
      *err_info = RANGE_ERROR;
      result = 0;
    } else {
      pos = big1->size - 1;
      result = (int32Type) (signedBigDigitType) big1->bigdigits[pos];
#if BIGDIGIT_SIZE > 16
      if (unlikely(result < INT16TYPE_MIN || result > INT16TYPE_MAX)) {
        logError(printf("bigToInt16(%s): Number too big or too small.\n",
                        bigHexCStri(big1)););
        *err_info = RANGE_ERROR;
        result = 0;
      } /* if */
#elif BIGDIGIT_SIZE < 16
      while (pos > 0) {
        pos--;
        result <<= BIGDIGIT_SIZE;
        result |= (int16Type) big1->bigdigits[pos];
      } /* while */
#endif
    } /* if */
    logFunction(printf("bigToInt16 --> " FMT_D32 "\n", result););
    return (int16Type) result;
  } /* bigToInt16 */



/**
 *  Convert a 'bigInteger' to an 'int32Type' number.
 *  @return the int32Type result of the conversion.
 *  @param big1 BigInteger to be converted.
 *  @param err_info Only used if err_info is not NULL.
 *                  Unchanged if the function succeeds or
 *                  RANGE_ERROR The number is too small or too big
 *                  to fit into a int32Type value.
 *  @exception RANGE_ERROR If err_info is NULL and the number is
 *             too small or too big to fit into a int32Type value.
 */
int32Type bigToInt32 (const const_bigIntType big1, errInfoType *err_info)

  {
    memSizeType pos;
    int32Type result;

  /* bigToInt32 */
    logFunction(printf("bigToInt32(%s)\n", bigHexCStri(big1)););
    /* Assume that BIGDIGIT_SIZE <= 32 holds. */
    if (unlikely(big1->size > sizeof(int32Type) / (BIGDIGIT_SIZE >> 3))) {
      logError(printf("bigToInt32(%s): Number too big or too small.\n",
                      bigHexCStri(big1)););
      if (err_info == NULL) {
        raise_error(RANGE_ERROR);
      } else {
        *err_info = RANGE_ERROR;
      } /* if */
      result = 0;
    } else {
      pos = big1->size - 1;
      result = (int32Type) (signedBigDigitType) big1->bigdigits[pos];
#if BIGDIGIT_SIZE < 32
      while (pos > 0) {
        pos--;
        result <<= BIGDIGIT_SIZE;
        result |= (int32Type) big1->bigdigits[pos];
      } /* while */
#endif
    } /* if */
    logFunction(printf("bigToInt32 --> " FMT_D32 "\n", result););
    return result;
  } /* bigToInt32 */



#ifdef INT64TYPE
/**
 *  Convert a 'bigInteger' to an 'int64Type' number.
 *  @return the int64Type result of the conversion.
 *  @param big1 BigInteger to be converted.
 *  @param err_info Only used if err_info is not NULL.
 *                  Unchanged if the function succeeds or
 *                  RANGE_ERROR The number is too small or too big
 *                  to fit into a int64Type value.
 *  @exception RANGE_ERROR If err_info is NULL and the number is
 *             too small or too big to fit into a int64Type value.
 */
int64Type bigToInt64 (const const_bigIntType big1, errInfoType *err_info)

  {
    memSizeType pos;
    int64Type result;

  /* bigToInt64 */
    logFunction(printf("bigToInt64(%s)\n", bigHexCStri(big1)););
    /* Assume that BIGDIGIT_SIZE <= 32 holds. */
    if (unlikely(big1->size > sizeof(int64Type) / (BIGDIGIT_SIZE >> 3))) {
      logError(printf("bigToInt64(%s): Number too big or too small.\n",
                      bigHexCStri(big1)););
      if (err_info == NULL) {
        raise_error(RANGE_ERROR);
      } else {
        *err_info = RANGE_ERROR;
      } /* if */
      result = 0;
    } else {
      pos = big1->size - 1;
      result = (int64Type) (signedBigDigitType) big1->bigdigits[pos];
#if BIGDIGIT_SIZE < 64
      while (pos > 0) {
        pos--;
        result <<= BIGDIGIT_SIZE;
        result |= (int64Type) big1->bigdigits[pos];
      } /* while */
#endif
    } /* if */
    logFunction(printf("bigToInt64 --> " FMT_D64 "\n", result););
    return result;
  } /* bigToInt64 */



/**
 *  Convert a 'bigInteger' to an 'uint64Type' number.
 *  @return the uint64Type result of the conversion.
 *  @exception RANGE_ERROR The number is negative or too big to fit
 *             into a uint64Type value.
 */
uint64Type bigToUInt64 (const const_bigIntType big1)

  {
    memSizeType pos;
    uint64Type result;

  /* bigToUInt64 */
    logFunction(printf("bigToUInt64(%s)\n", bigHexCStri(big1)););
    pos = big1->size - 1;
    if (unlikely(IS_NEGATIVE(big1->bigdigits[pos]))) {
      logError(printf("bigToUInt64(%s): Number is negative.\n",
                      bigHexCStri(big1)););
      raise_error(RANGE_ERROR);
      result = 0;
    } else {
      /* Assume that BIGDIGIT_SIZE <= 32 holds. */
      if (big1->bigdigits[pos] == 0 && pos > 0) {
        pos--;
      } /* if */
      if (unlikely(pos >= sizeof(uint64Type) / (BIGDIGIT_SIZE >> 3))) {
        logError(printf("bigToUInt64(%s): Number too big.\n",
                        bigHexCStri(big1)););
        raise_error(RANGE_ERROR);
        result = 0;
      } else {
        result = (uint64Type) big1->bigdigits[pos];
#if BIGDIGIT_SIZE < 64
        while (pos > 0) {
          pos--;
          result <<= BIGDIGIT_SIZE;
          result |= (uint64Type) big1->bigdigits[pos];
        } /* while */
#endif
      } /* if */
    } /* if */
    logFunction(printf("bigToUInt64(%s) --> " FMT_U64 "\n",
                       bigHexCStri(big1), result););
    return result;
  } /* bigToUInt64 */
#endif



bigIntType bigXor (const_bigIntType big1, const_bigIntType big2)

  {
    const_bigIntType help_big;
    memSizeType pos;
    bigDigitType big2_sign;
    bigIntType result;

  /* bigXor */
    logFunction(printf("bigXor(%s,", bigHexCStri(big1));
                printf("%s)\n", bigHexCStri(big2)););
    if (big2->size > big1->size) {
      help_big = big1;
      big1 = big2;
      big2 = help_big;
    } /* if */
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, big1->size))) {
      raise_error(MEMORY_ERROR);
    } else {
      pos = 0;
      do {
        result->bigdigits[pos] = big1->bigdigits[pos] ^ big2->bigdigits[pos];
        pos++;
      } while (pos < big2->size);
      big2_sign = IS_NEGATIVE(big2->bigdigits[pos - 1]) ? BIGDIGIT_MASK : 0;
      for (; pos < big1->size; pos++) {
        result->bigdigits[pos] = big1->bigdigits[pos] ^ big2_sign;
      } /* for */
      result->size = pos;
      result = normalize(result);
    } /* if */
    logFunction(printf("bigXor --> %s\n", bigHexCStri(result)););
    return result;
  } /* bigXor */



bigIntType bigZero (void)

  {
    bigIntType result;

  /* bigZero */
    if (unlikely(!ALLOC_BIG_SIZE_OK(result, 1))) {
      raise_error(MEMORY_ERROR);
    } else {
      result->size = 1;
      result->bigdigits[0] = 0;
    } /* if */
    return result;
  } /* bigZero */

#endif