int_op.cpp

关于大数运算的加 减 乘 除 模 等运算 运用了libtommath库的算法

    if (right.m_acutual_len == 1)
    {

        dw_reminder=raw_div_int(tmpAns,right_buf[0],tmpAns); 
        if (right_buf != dest_buf)
        {
            
            dest = tmpAns;
            dest.m_dw_sign = dest_sign;
        }
        if (left_buf != dest_buf)
        {
            left.zero();
            left_buf[0]=dw_reminder;
            if (dw_reminder) left.m_dw_sign = old_sig_left;
        }
        right.m_dw_sign = old_sig_right;
        return 0;

    }

    if (right_buf!=dest_buf) dest.zero();
    d_factor=norm_divisor(right,right);
    
    if (d_factor!=1) raw_mul_int(tmpAns,d_factor,tmpAns);
        unsigned int ldy,sdy;

        ldy=right_buf[right.m_acutual_len-1];
        sdy=right_buf[right.m_acutual_len-2];
    
        
        for (unsigned int k=tmpAns.m_acutual_len-1;k>=right.m_acutual_len-1;k--)
        {  /* long division */
#ifdef _NOTUSEASM
            unsigned int carry_flg=0;
            unsigned int tst,ra;
            if (tmp_buf[k+1]==ldy) // guess next quotient 'digit'
            {
                attemp=DWORD_BITMASK;
                ra=ldy+tmp_buf[k];
                if (ra<ldy) carry_flg=1;
            }
            else attemp=muldvm(tmp_buf[k+1],tmp_buf[k],ldy,(int *)&ra);
           

            while (carry_flg==0)
            {
               
                tst=muldvd(sdy,attemp,(unsigned int)0,(int *)&dw_reminder);
                if (tst< ra || (tst==ra && dw_reminder<=tmp_buf[k-1])) break;
                attemp--;  /* refine guess */
                ra+=ldy;
                if (ra<ldy) carry_flg=1;
            }
#else
            __asm
            {
             push esi
             push edi
             mov ebx,tmp_buf
             mov esi,k
             shl esi,2
             add ebx,esi
             mov edx,[ebx+4]
             mov eax,[ebx]
             cmp edx,ldy
             jne tcl8
             xor edi,edi
             dec edi
             mov esi,eax
             add esi,ldy
             jc tcl12
             jmp tcl10
          tcl8:
             div DWORD PTR ldy
             mov edi,eax
             mov esi,edx
          tcl10:
             mov eax,sdy
             mul edi
             cmp edx,esi
             jb tcl12
             jne tcl11
             cmp eax,[ebx-4]
             jbe tcl12
          tcl11:
             dec edi
             add esi,ldy
             jnc tcl10
          tcl12:
             mov attemp,edi
             pop edi
             pop esi
            }
#endif
            int m=k-right.m_acutual_len+1;
            if (attemp>0)
            { /* do partial subtraction */
                borrow_flag=0;
#ifdef _NOTUSEASM
                unsigned int dig=0;
                for (unsigned int i=0;i<right.m_acutual_len;i++)
                {
                  borrow_flag=muldvd(attemp,right_buf[i],borrow_flag,(int *)&dig);

                  if (tmp_buf[m+i]<dig) borrow_flag++;
                  tmp_buf[m+i]-=dig;
                }
#else
                
                __asm
                {
                 push esi
                 push edi
                 mov ecx,right_buff_len
                 mov esi,m
                 shl esi,2
                 mov edi,attemp
                 mov ebx,tmp_buf
                 add ebx,esi
                 mov esi,right_buf
                 sub ebx,esi
                 sub ebx,4
                 push ebp
                 xor ebp,ebp

             tcl3:
                 mov eax,[esi]
                 add esi,4
                 mul edi
                 add eax,ebp
                 mov ebp,[esi+ebx]
                 adc edx,0
                 sub ebp,eax
                 adc edx,0
                 mov [esi+ebx],ebp
                 dec ecx
                 mov ebp,edx
                 jnz tcl3

                 mov eax,ebp
                 pop ebp
                 mov borrow_flag,eax
                 pop edi
                 pop esi
                }
#endif
                if (tmp_buf[k+1]<borrow_flag)
                {  /* whoops! - over did it */
                    tmp_buf[k+1]=0;
#ifdef _NOTUSEASM
                    unsigned int carry_flg=0;
                    for (unsigned int i=0;i<right.m_acutual_len;i++)
                    {  /* compensate for error ... */
                        unsigned int psum;
                        psum=tmp_buf[m+i]+right_buf[i]+carry_flg;
                        if (psum>right_buf[i]) carry_flg=0;
                        if (psum<right_buf[i]) carry_flg=1;
                        tmp_buf[m+i]=psum;
                    }
#else
                   
                    __asm
                    {
                        mov ecx, right_buff_len
                        mov esi, right_buf
                        mov edi, tmp_buf
                        mov eax, m
                        shl eax, 2
                        add edi, eax
                        xor ebx,ebx
                loop1:
                        mov eax, [esi + ebx]
                        adc [edi + ebx], eax
                        inc ebx
                        inc ebx
                        inc ebx
                        inc ebx
                        dec ecx
                        jnz loop1

                        
                    }
#endif
                    attemp--;  /* ... and adjust guess */
                }
                else tmpAns.m_p_data_arr[k+1]-=borrow_flag;
            }
            if (k==tmpAns.m_acutual_len-1 && attemp==0) tmpAns.m_acutual_len--;
            else if (right_buf!=dest_buf) dest.m_p_data_arr[m]=attemp;
        }
        if (right_buf!=dest_buf){
            /* set sign and length of result */
            

            dest.m_acutual_len = tmpAns.m_acutual_len - right.m_acutual_len + 1;
            dest.m_dw_sign = dest_sign;
        }


    tmpAns.m_acutual_len = right.m_acutual_len;

    while( dest_buf[dest.m_acutual_len-1]==0 && dest.m_acutual_len>1)dest.m_acutual_len--;
    memset(dest_buf+dest.m_acutual_len,0,sizeof(unsigned int)*(ms_u_data_arr_num-dest.m_acutual_len));
    if (left_buf!=dest_buf)
    {
  
        while(tmp_buf[tmpAns.m_acutual_len-1]==0 && tmpAns.m_acutual_len>1) tmpAns.m_acutual_len--;
        if (d_factor!=1) raw_div_int( tmpAns,d_factor,left);
        else left = tmpAns;
        if (!left.isZero()) left.m_dw_sign = old_sig_left;
    }
    if (d_factor!=1) raw_div_int(right,d_factor,right);
    right.m_dw_sign = old_sig_right;


    return 0;
}

void Integer::raw_mul_int(Integer &left, unsigned int n, Integer &dest)
{
   
    unsigned int carry_flg,pos;
    unsigned int src_buf_len,dest_buf_len;
    unsigned int * dest_buff = dest.m_p_data_arr;
    unsigned int * src_buff = left.m_p_data_arr;
    src_buf_len = left.m_acutual_len;
    dest_buf_len= dest.m_acutual_len;

    if (dest_buff != src_buff)
    {
        dest.zero();  
    }
    if (n ==0 || left.isZero() )
    {
        dest.zero();
        return;
    }
    
    
    carry_flg=0;

#ifndef _NOTUSEASM
    
    __asm{
         mov ecx,src_buf_len
         or ecx,ecx     
         je finish                //ecx > 0?
         mov ebx,n
         mov edi,dest_buff
         mov esi,src_buff
         push ebp
         xor ebp,ebp
    loop1:
         mov eax,[esi]
         add esi,4
         mul ebx
         add eax,ebp
         adc edx,0
         mov [edi],eax
         add edi,4
         mov ebp,edx
         dec ecx
         jnz loop1

         mov eax,ebp
         pop ebp
         mov carry_flg,eax
     finish: 
    }
#else
    pos=0;
    __int64 ans;
    unsigned int *dw_ans = (unsigned int *)&ans;
    for (;pos<src_buf_len;pos++)
    {
        ans=(__int64)src_buff[pos]*n+carry_flg;
        carry_flg=dw_ans[1];
        dest_buff[pos]=dw_ans[0];
    }
#endif
        if (carry_flg>0)
        {
            pos=src_buf_len;
            if (pos > ms_u_data_arr_num)
            {
                dest.m_dw_isOverflow = true;
                return;
            }
          
            dest_buff[pos]=carry_flg;
            dest.m_acutual_len = pos+1;
        }
        else dest.m_acutual_len =src_buf_len;
        dest.m_dw_sign = left.m_dw_sign;
}

unsigned int Integer::raw_div_int(Integer &left, unsigned int n, Integer &dest)
{
  
    unsigned int src_length;
    unsigned int * src_buff = left.m_p_data_arr;
    unsigned int * dest_buff = dest.m_p_data_arr;
    unsigned int src_reminder = 0;
    src_length = left.m_acutual_len;

    if (src_buff!=dest_buff) dest.zero();
 
#ifndef _NOTUSEASM
    __asm{
         mov ecx,src_length
         or ecx,ecx
         je final
         mov ebx,ecx
         shl ebx,2
         mov esi, src_buff
         add esi,ebx
         mov edi, dest_buff
         add edi,ebx
         mov ebx,n
         push ebp
         xor ebp,ebp
    loop1:
         sub esi,4
         mov edx,ebp
         mov eax,[esi]
         div ebx
         sub edi,4
         mov ebp,edx
         mov [edi],eax
         dec ecx
         jnz loop1

         mov eax,ebp
         pop ebp
         mov src_reminder,eax
     final:
                          
    }
#else
    int pos;
    __int64 tmp_ans;
    unsigned int * dw_ans = (unsigned int *)&tmp_ans;
    for (pos =(int)src_length-1;pos>=0;pos--)
    {
        dw_ans[0]=src_buff[pos];
        dw_ans[1]=src_reminder;
        dest_buff[pos]=(unsigned int)(tmp_ans/n);
        src_reminder=(unsigned int)(tmp_ans-(__int64)dest_buff*n);
    }
#endif
    dest.m_acutual_len = src_length;
    while(dest_buff[dest.m_acutual_len - 1] == 0 && dest.m_acutual_len>1) dest.m_acutual_len--;
   
    return src_reminder;
}


int Integer::norm_divisor(Integer &left, Integer &right)
{
    unsigned int norm,remainder;
    int len;
    
    if (left.m_p_data_arr!=right.m_p_data_arr) right = left;
    len=right.m_acutual_len;

    if ((remainder=right.m_p_data_arr[len-1]+1)==0) norm=1;
#ifdef _NOTUSEASM
        else norm=(unsigned int)(((__int64)1 << 32)/remainder);
#else
        else norm=muldvm((unsigned int)1,(unsigned int)0,remainder,( int *)&remainder);
#endif
    if (norm!=1) raw_mul_int(right,norm,right);
    return norm;
}


Integer& Integer::plus(Integer &dest)
{
    add_sub_director(*this,dest,0);
    return *this;
}

Integer& Integer::minus(Integer &dest)
{
    add_sub_director(*this,dest,1);
    return *this;
}

Integer& Integer::mul(const Integer &right,Integer &dest)
{
  
    raw_mul(*this,right,dest);
   
    return dest;
}

Integer& Integer::div(const Integer &right)
{
    raw_div(*this,const_cast<Integer &>(right),*this); 
    return *this;
}

Integer& Integer::mod(const Integer &right)
{
    
    raw_div(*this,const_cast<Integer &>(right),const_cast<Integer &>(right));
    return *this;
}

Integer& Integer::shift(int n)
{
    if (this->isZero() || n==0) return *this;
    int dest_len = this->m_acutual_len + n;
    int i;
    if (dest_len<=0)
    {
        this->zero();
        return *this;
    }
    if ((unsigned int)dest_len >ms_u_data_arr_num)
    {
        this->m_dw_isOverflow = true;
        dest_len = ms_u_data_arr_num;
    }

    if (n>0)
    {
        for (i=dest_len-1;i>=n;i--)
            this->m_p_data_arr[i]=this->m_p_data_arr[i-n];
        for (i=0;i<n;i++)
            this->m_p_data_arr[i]=0;
    }
    else
    {
        n=(-n);
        for (i=0;i<dest_len;i++)
            this->m_p_data_arr[i]=this->m_p_data_arr[i+n];
        for (i=0;i<n;i++)
            this->m_p_data_arr[dest_len+i]=0;
    }
    this->m_acutual_len = dest_len;
    return *this;
}