一个关于数据处理的问题。

joeqi0370

请问如果我要对两个数值都超过长整形的数据进行四则运算，该怎么办？
（能说一说原理吗？）

flw

自己设计数据结构，存储超长数据，自己设计算法，实现四则运算。
提示：可以设计一种“100 进制”的数据，即：“逢百进一”，然后用一个
字节表示一位数，参考小学生做算术列竖式的方法。再参考一下 BCD 码
运算器的道理。

alun123456

上学的时候，我学过。这个算法很简单。设一数组，你想你的数据位是多长就设多长，设1000也可以，就是a[10000]，这个数组就是你计算的结果位数。
然后、你自己设计计算方法，一般是这样的，a[1],a[2]...a[n],a[1]里就只存一个个位数、依次。。。，想做 ＊ 法就，用那个数组中的b[1]...b[n] 一个一个的 * ,然后再做一个进位的。就行了。用这个东西、理论上是可以无限的。如果看不明白、说一声，我这里有源程。

雷斯林

贴一个

雷斯林

不能上载文件吗？

/*-------------------------------------------------------------------

Project:      ROHC
Module/Class: Multi-precision Arithmetic
File:         ma.c
Author:       Mark A West

Description:

This implements a simple multi-precision maths library


Copyright:
Copyright (C) 2000 Siemens, all rights reserved with exception of the rights
necessary to evaluate and test the code to produce contributions to the
standardization work of the IETF.

---------------------------------------------------------------------

Change History:

Date    Initials    Version    Change Details
----    --------    -------    --------------
Oct '00             INITIAL    Work-in-progress
                     DRAFT     For information only

Nov '00         AS                        1.0                   First Release
               
-------------------------------------------------------------------*/

/* @(#) /users/ts/redrum_disk2/maw/sccs/epic/s.ma.c 1.7 00/11/16 18:13:33 */


#include <stdio.h>;
#include <string.h>;
#include <stdlib.h>;
#include <assert.h>;

#include "ma.h"


#ifdef USE_FULL_WORD
#define MAX_CHARS (PR * 32)
typedef unsigned long long mul_unit;
const mul_unit upper_mask = 0xffffffff00000000;
const mul_unit lower_mask = 0x00000000ffffffff;
const int upper_shift = 32;
const int lower_shift = 0;
const unit const_top_bit = 0x80000000;
#else
#define MAX_CHARS (PR * 16)
typedef unsigned int mul_unit;
const mul_unit upper_mask = 0xffff0000;
const mul_unit lower_mask = 0x0000ffff;
const int upper_shift = 16;
const int lower_shift = 0;
const unit const_top_bit = 0x8000;
#endif


#define MP_ORDER(x) (x [PR - 1])
#define MP_STORE_ORDER(x) (x [PR - 1] = mp_order (x))
#define MP_SET_ORDER(x,y) (x [PR - 1] = (y))
#define MS_UNIT (PR - 2)
#define LS_UNIT (0)

#define MIN(a,b) ( ((a)<(b)) ? (a) : (b) )
#define MAX(a,b) ( ((a)>;(b)) ? (a) : (b) )

const int unit_bits = sizeof (unit) * 8;


inline void mp_zero (num_p n)
{
        (void) memset ((char*) n, 0, sizeof (unit) * PR);
}


inline void mp_load (num_p n, unit u)
{
        mp_zero (n);
        n [0] = u;
}


inline void mp_copy (num_p d, const_num_p s)
{
        (void) memcpy ((char*) d, (char*) s, sizeof (unit) * PR);
}


inline unit mp_to_int (const_num_p a)
{
        assert (MP_ORDER (a) == 0);

        return a [LS_UNIT];
}


static int mp_order (const_num_p a)
{
        int i = MS_UNIT;

        while (i >; 0 &amp;&amp; ! a)
        {
                i--;
        }

        return i;
}



static int mp_msb_index (const_num_p a)
{
        int i = MP_ORDER (a);
        unit t = a ;
        int c = i * unit_bits;

        while (t)
        {
                t >;>;= 1;
                c ++;
        }

        return c;
}


static inline int mp_test_bit (const_num_p a, int b)
{
        return ((a [b / unit_bits] >;>; (b % unit_bits)) &amp; 1);
}


static inline void mp_set_bit (num_p a, int b)
{
        a [b / unit_bits] |= 1 << (b % unit_bits);
}


static void mp_fast_shift_right (num_p a)
{
        int i;
        const unit mask = (-1 >;>; (unit_bits - 1));

        for (i = 0; i <= MP_ORDER (a); i++)
        {
                a >;>;= 1;

                a |= (a [i + 1] &amp; mask) << (unit_bits - 1);
        }
}


int mp_digits (const_num_p a)
{
        return mp_msb_index (a);
}


void mp_add (num_p a, const_num_p b)
{
        int c = 0;
        int i;
        num_t r;

    mp_zero (r);

        for (i = 0; i <= MAX (MP_ORDER (a), MP_ORDER (b)) + 1; i++)
        {
                r = a + b + c;
                c = (r < a ) ? 1 : 0;
        }

        mp_copy (a, r);

        MP_STORE_ORDER (a);

        /* check for overflow...
         */
        assert (!c);
}


void mp_sub (num_p a, const_num_p b)
{
        int c = 0;
        int i;
        num_t r;

        mp_zero (r);

        for (i = 0; i <= MP_ORDER (a); i++)
        {
                r = a - b - c;
                c = (r >; a ) ? 1 : 0;
        }

        mp_copy (a, r);

        MP_STORE_ORDER (a);

        /* check for overflow...
         */
        assert (!c);
}


int mp_comp (const_num_p a, const_num_p b)
{
        int i;
        int r = 0;

        for (i = MAX (MP_ORDER (a), MP_ORDER (b)); i >;= 0 &amp;&amp; !r; i--)
        {
                if (a >; b )
                {
                        r = 1;
                }
                else if (a < b )
                {
                        r = -1;
                }
        }

        return r;
}


void mp_shift_left (num_p a, int c)
{
        int i;
        const int unit_skip = c / unit_bits;
        const int unit_shift = c % unit_bits;
        const int mask_shift = unit_bits - unit_shift;
        const unit mask = (mask_shift < unit_bits) ? (-1 << mask_shift) : 0;

        for (i = MP_ORDER (a); i >;= 0; i--)
        {
                if (i < (MS_UNIT - unit_skip - 1))
                {
                        a [i + unit_skip + 1] |= (a &amp; mask) >;>; mask_shift;
                }

                a [i + unit_skip] = a << unit_shift;
        }

        for (i = unit_skip - 1; i >;= 0; i--)
        {
                a = 0;
        }

        MP_STORE_ORDER (a);
}


void mp_shift_right (num_p a, int c)
{
        int i;
        const int unit_skip = c / unit_bits;
        const int unit_shift = c % unit_bits;
        const int mask_shift = unit_bits - unit_shift;
        const unit mask = (mask_shift < unit_bits) ? (-1 >;>; mask_shift) : 0;

        for (i = 0; i <= MP_ORDER (a); i++)
        {
                a = a [i + unit_skip] >;>; unit_shift;

                if (i < (MS_UNIT - unit_skip - 1))
                {
                        a |= (a [i + unit_skip + 1] &amp; mask) << mask_shift;
                }
        }

        for (i = MS_UNIT - 1; i >; MS_UNIT - unit_skip - 1; i --)
                a = 0;

        MP_STORE_ORDER (a);
}


void mp_div (num_p a, const_num_p b, num_p q, num_p r)
{
        int sb = mp_msb_index (b);
        int s;

        num_t t;

        mp_zero (q);
        mp_copy (r, a);

        mp_copy (t, b);
        s = mp_msb_index (r) - sb + 1;

        if (s >; 0)
        {
                mp_shift_left (t, s);
        }

        while (mp_comp (r, b) >;= 0)
        {
                if (mp_comp (r, t) >;= 0)
                {
                        mp_sub (r, t);

                        assert (s >;= 0);

                        mp_set_bit (q, s);
                }

                mp_fast_shift_right (t);
                s --;
        }

        MP_STORE_ORDER (q);
        MP_STORE_ORDER (r);
}


void mp_mod (num_p a, const_num_p m)
{
        num_t q;
        num_t r;

        mp_div (a, m, q, r);

        mp_copy (a, r);
}


void mp_mul (num_p a, const_num_p b)
{
        int ai, bi;
        num_t r;
        mul_unit ir;

        num_t i1, i2;

        mp_zero (r);

        for (ai = 0; ai <= MP_ORDER (a); ai++)
        {
                mp_zero (i1);
                mp_zero (i2);

                for (bi = 0; bi <= MP_ORDER (b); bi++)
                {
                        ir = (mul_unit) a [ai] * (mul_unit) b [bi];

                        if (ir != 0)
                        {
                                i1 [ai + bi] = (unit) ((ir &amp; lower_mask) >;>; lower_shift);
                                i2 [ai + bi + 1] = (unit) ((ir &amp; upper_mask) >;>; upper_shift);
                        }
                }

                MP_SET_ORDER (i1, ai + bi);
                MP_SET_ORDER (i2, ai + bi + 1);

                mp_add (r, i1);
                mp_add (r, i2);
        }

        mp_copy (a, r);

        MP_STORE_ORDER (a);
}


void mp_construct (num_p a, const char* s)
{
        num_t b;
        num_t cv;
        num_t acc;
        num_t t;
        int i;

        mp_load (b, 10);
        mp_load (cv, 1);
        mp_zero (acc);

        for (i = strlen (s) - 1; i >;= 0; i--)
        {
                mp_load (t, s - '0');
                mp_mul (t, cv);
                mp_add (acc, t);
                mp_mul (cv, b);
        }

        mp_copy (a, acc);
}


void mp_dump (const_num_p a)
{
        int i = MP_ORDER (a);

        while (i >;= 0)
        {
                printf ("%04x", a );
                i--;
        }
        printf ("\n";
}


/* convert an MP number to a string - not thread safe, 'cause there's
* only 1 buffer!
*/
char *mp_tostr (const_num_p a)
{
        static char tostr_buffer [MAX_CHARS];

        num_t base;
        num_t q;
        num_t r;
        num_t t;
        num_t n0;
        int i = MAX_CHARS - 2;
        int z = 0;

        mp_load (base, 10);
        mp_zero (n0);
        mp_copy (q, a);

        tostr_buffer [MAX_CHARS - 1] = '\0';

        while (mp_comp (q, n0) != 0 &amp;&amp; i)
        {
                mp_copy (t, q);
                mp_div (t, base, q, r);

                tostr_buffer [i--] = '0' + r [0];

                z = 1;
        }

        if (! z)
        {
                tostr_buffer [i--] = '0';
        }

        return (tostr_buffer + i + 1);
}


void mp_show (const_num_p a)
{
        printf ("%s", mp_tostr (a));
}





/*-------------------------------------------------------------------

Project:      ROHC
Module/Class: Multi-precision Arithmetic
File:         ma.h
Author:       Mark A West

Description:

This defines a simple multi-precision maths library


Copyright:
Copyright (C) 2000 Siemens, all rights reserved with exception of the rights
necessary to evaluate and test the code to produce contributions to the
standardization work of the IETF.

---------------------------------------------------------------------

Change History:

Date    Initials    Version    Change Details
----    --------    -------    --------------
Oct '00             INITIAL    Work-in-progress
                     DRAFT     For information only

Nov '00         AS                        1.0                   First Release
               
-------------------------------------------------------------------*/

/* @(#) /users/ts/redrum_disk2/maw/sccs/epic/s.ma.h 1.7 00/11/16 18:13:33 */



#ifndef MULTI_PREC_H
#define MULTI_PREC_H

#define USE_FULL_WORD

#define PR 64 /* units */

#ifdef USE_FULL_WORD
typedef unsigned int unit;
#else
typedef unsigned short int unit;
#endif

typedef unit num_t [PR];
typedef unit *num_p;
typedef const unit *const_num_p;


extern inline void mp_zero (num_p n);
extern inline void mp_load (num_p n, unit u);
extern inline void mp_copy (num_p d, const_num_p s);
extern inline unit mp_to_int (const_num_p a);
int mp_digits (const_num_p a);

void mp_add (num_p a, const_num_p b);
void mp_sub (num_p a, const_num_p b);
int mp_comp (const_num_p a, const_num_p b);
void mp_shift_left (num_p a, int c);
void mp_shift_right (num_p a, int c);
void mp_div (num_p a, const_num_p b, num_p q, num_p r);
void mp_mod (num_p a, const_num_p m);
void mp_mul (num_p a, const_num_p b);
void mp_construct (num_p a, const char* s);
void mp_dump (const_num_p a);
void mp_show (const_num_p a);
char *mp_tostr (const_num_p a);

#endif

HopeCao

以前的贴子里有，找找