digit_vector.h

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

/*******************************************************************************
+
+  LEDA 4.5  
+
+
+  digit_vector.h
+
+
+  Copyright (c) 1995-2004
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.3 $  $Date: 2004/02/06 11:19:34 $


#ifndef DIGIT_VECTOR_H
#define DIGIT_VECTOR_H

#include <LEDA/basic.h>
#include <LEDA/numbers/digit.h>
#include <LEDA/std/string.h>

LEDA_BEGIN_NAMESPACE 

inline void vecInit(digit* a, digit_sz a_used);
inline digit* vecCopy(digit* a, const digit* b, digit_sz count);
void vecFill(digit* a, digit_sz a_used,digit d);
inline digit_sz vecLength(digit* x, digit_sz x_used);
inline void vecIncrement(digit* a, digit_sz a_used);
inline void vecDecrement(digit* a, digit_sz a_used);



inline void vecDecrement(digit* a, digit_sz a_used)
{
  digit* a_stop=a+a_used;
  while (a<a_stop&&--*a==MAX_DIGIT) a++;
}

inline void vecIncrement(digit* a, digit_sz a_used)
{
  digit* a_stop=a+a_used;
  while (a<a_stop&&++*a==0) a++;
}


inline void vecInit(digit* a, digit_sz a_used)
{
  if (a_used < 8) 
    switch(a_used) {
      case  7:*a++ = 0;
      case  6:*a++ = 0;
      case  5:*a++ = 0;
      case  4:*a++ = 0;
      case  3:*a++ = 0;
      case  2:*a++ = 0;
      case  1:*a++ = 0;
    }
  else
    memset(a,0,a_used*DIGIT_SIZE);
}


inline digit* vecCopy(digit* a, const digit* b, digit_sz count)
{
  if (count < 8) {
    switch (count) { 
      case  7:*a++ = *b++;
      case  6:*a++ = *b++;
      case  5:*a++ = *b++;
      case  4:*a++ = *b++;
      case  3:*a++ = *b++;
      case  2:*a++ = *b++;
      case  1:*a++ = *b++; 
    }
    return a;
  }
  else {
    memcpy((void* ) a, (void*)b, count*DIGIT_SIZE);
    return a+count;
  }
}


inline digit_sz vecLength(digit* x, digit_sz x_used) {
#ifdef DIGIT_CHECKS_ON
  assert (x_used>0);
  assert (x[x_used-1]!=0);
#endif
  return (x_used<<WORD_LENGTH_LOG)-digLeadingZeros(x[x_used-1]);
}




inline int vecCompare(digit* a, digit* b, digit_sz n)
{ 
  digit* ap = a + n;
  digit* bp = b + n;
  
  while(ap > a)
  { digit A = *--ap;
    digit B = *--bp;
    if (A > B) return  1;
    if (A < B) return -1;
   }
  return 0;
}


digit vecShiftLeftByBits(digit *a, digit *b, digit_sz length, digit_sz shift);
digit vecShiftLeftByBits(digit *a, digit_sz length, digit_sz shift);
digit_sz  vecShiftLeftByManyBits(digit *a,digit * b, digit_sz b_length, digit_sz shift);
digit vecShiftRightByBits(digit *a, digit *b, digit_sz length, digit_sz shift);
digit vecShiftRightByBits(digit *a, digit_sz length, digit_sz shift);
digit_sz vecShiftRightByManyBits(digit *a,digit * b, digit_sz b_length, digit_sz shift);


inline int vecCompare(digit* a, digit* b, digit_sz n);
int vecCompare(digit* a, digit_sz a_used, digit* b, digit_sz b_used);
int vecCompareNormal(digit* a, int a_used, digit* b, int b_used);



digit_sz vecAdd(digit *a, digit_sz a_used, digit *b, digit_sz b_used, digit* sum);
digit_sz vecAddTo(digit *a, digit_sz a_used, digit *b, digit_sz b_used);
digit vecAddToReturnCarry(digit *a, digit *b, digit_sz b_used);

inline digit_sz vecSignedAdd(
  digit* a, digit_sz a_used, int a_sign, digit* b, digit_sz b_used, int b_sign,
  digit* sum, int& sum_sign);


void vecSub(digit *a, digit_sz a_used, digit *b, digit_sz b_used, digit* diff);
void vecSubFrom(digit *a, digit_sz a_used, digit *b, digit_sz b_used);
digit vecSubFromReturnBorrow(digit *a, digit *b, digit_sz b_used);


inline digit_sz vecSignedAdd( digit* a, digit_sz a_used, int a_sign,
                              digit* b, digit_sz b_used, int b_sign,
                              digit* sum, int& sum_sign)
{
  digit_sz sum_used=0;
  int rel=a_used-b_used;
  if (a_sign == b_sign) { 
    if (rel>=0)  
      sum_used = vecAdd(a,a_used,b,b_used,sum); 
    else 
      sum_used = vecAdd(b,b_used,a,a_used,sum); 
    sum_sign = a_sign;
    return sum_used;
  }
  if (rel==0) {
    digit* p = a + a_used;
    digit* q = b + b_used;
    while (a_used && *--p == *--q) {
      a_used--; b_used--;
    }
    if (a_used==0) {
      sum_sign=0;
      return 0;
    }
    else
      rel = (*p > *q) ? 1 : -1;
  }
  if (rel>0) { // |a| > |b|
    vecSub(a,a_used,b,b_used,sum);
    sum_used=a_used;
    sum_sign=a_sign;
  }
  if (rel<0) { // |b| > |a|
    vecSub(b,b_used,a,a_used,sum);
    sum_used=b_used;
    sum_sign=b_sign;
  }
  digit* sp=sum+sum_used;
  while (*--sp == 0) 
    sum_used--;
  return sum_used;
}


 
digit_sz vecMul
  (digit* prod, digit* a, digit_sz a_used, digit* b, digit_sz b_used);
digit_sz vecMulSchool
  (digit *a, digit_sz a_used, digit *b, digit_sz b_used, digit* prod);
digit_sz vecMulSchoolHigh
  (digit *a, digit_sz a_used, digit *b, digit_sz b_used, digit* prod, digit_sz k);
void vecMulSchoolLow
  (digit *a, digit_sz a_used, digit *b, digit_sz b_used, digit* prod, digit_sz k);
digit_sz vecMulKara
  (digit* a, digit_sz a_used, digit* b, digit_sz b_used, digit* prod, digit_sz prod_size);


digit_sz vecSquare(digit* prod,digit* a_vec, digit_sz a_used);
digit_sz vecSquareSchool(digit *a, digit_sz a_used, digit *square);
digit_sz vecSquareKara(digit* a, digit_sz a_used, digit* prod);



digit_sz vecDiv
  (digit* quot, digit* r, digit_sz *r_used,
   digit* a, digit_sz a_used,
   digit* b, digit_sz b_used);
digit_sz vecDivByOneDigit
  (digit *a, digit_sz a_used, digit B, 
   digit* quot, digit* rem);
digit_sz vecDivSchool
  (digit* a, digit_sz a_used, digit* b, digit_sz b_used,
   digit* quot, digit* r, digit_sz* r_used);
digit_sz vecDivKara
  (digit* a, digit_sz a_used, digit* b, digit_sz b_used, 
   digit* quot, digit* r, digit_sz* r_used);




digit_sz vecModMul(digit* rem,
  digit* a_vec, digit_sz a_used,
  digit* b_vec, digit_sz b_used,
  digit* n_vec, digit_sz n_used);
digit_sz vecModMulLean(digit* rem,
  digit* a_vec, digit_sz a_used,
  digit* b_vec, digit_sz b_used,
  digit* n_vec, digit_sz n_used, digit *tmp);
digit_sz vecModSquare(digit* rem,
  digit* a_vec, digit_sz a_used,
  digit* n_vec, digit_sz n_used);
digit_sz vecModSquareLean(digit* rem,
  digit* a_vec, digit_sz a_used,
  digit* n_vec, digit_sz n_used, digit* tmp);
digit_sz vecModExp(digit *prod0,digit* a_vec, digit_sz a_used,
  digit* e_vec, digit_sz e_used,
  digit* n_vec, digit_sz n_used);



enum num_op { vecMUL=1, vecADD=2, vecSUB=3, vecSQR=4, vecDIV=5}; 

digit vecModReduce(digit* a, digit_sz a_used, int a_sign);

void vecModCheckOperation(num_op operation,
    digit* a_vec, digit_sz a_used, int a_sign, digit& a_mod,
    digit* b_vec, digit_sz b_used, int b_sign, digit& b_mod,
    digit* c_vec, digit_sz c_used, int c_sign, digit& c_mod);

void vecModCheckSquare(
    digit* a_vec, digit_sz a_used, int a_sign, digit& a_mod,
    digit* c_vec, digit_sz c_used, int c_sign, digit& c_mod);

void vecModCheckDivision(
    digit* a_vec, digit_sz a_used, int a_sign, digit& a_mod,
    digit* b_vec, digit_sz b_used, int b_sign, digit& b_mod,
    digit* c_vec, digit_sz c_used, int c_sign, digit& c_mod,
    digit* r_vec, digit_sz r_used, int r_sign, digit& r_mod);



char* vecToDecimal(digit* a, digit_sz a_used, char* str);
// digit* vecFromDecimal(digit* a, digit_sz a_used, char* str);


digit_sz vecFromDouble(double x, digit* vec, int& sign, int& exp);
digit_sz vecFromDoubleAligned
(double x, digit* vec, int& sign, int& exp, digit_sz& precision);
double vecToDouble(digit* vec, digit_sz used);


LEDA_END_NAMESPACE

#endif