认识达内从这里开始

我们在上期的文章中给大家简单分享了关于个性化推荐的数据分析的重要性以及操作步骤，今天我们就一起来了解和学习一下，都有哪些数据分析算法是需要我们掌握的。希望通过对本文的阅读，大家对大数据数据算法能够有更多的认识。

1、背景

工作中遇到过需要进行极大数据的存储和运算的场景，当时使用Python解决了这个问题，在Python中，整数没有位数限制，使用起来很方便。但是当程序主体使用C/C++实现时，就比较麻烦。所以考虑实现一个大数类，用于大数的存储和运算，后面生成静态库，需要的时候直接调用。

2、算法设计

(1)存储

大数一般都是以整数队列的形式存储，取一个较大的进制S，队列中的每一个值，相当于一位。假设数组长度为N(0为低位，n-1为高位)，则数组表示的值value=A0+A1*S+A2*S2+...+An-1*Sn-1。例如“1234567890000”在数组中存储形式为567890000,1234。以下大数的运算全部基于此方式。

(2)比较运算

两个大数比较的方法是：优先比较位数，位数大者为大，位数小者为小;如果位数相等，则依次从高位向低位比较，当前位大的为大，当前位小的为小;如果每一位都相等，则两者相等。

(3)加法运算

大数的加减乘运算都与十进制运算的手算方法相同，区别在于后者是10进制，而前者是S进制。加法计算时，A和B由低位到高位依次求和，需考虑进位。

对于A(a0a1a2...an-1)+B(b0b1b2...bm-1)，并假设N≥M，则计算过程如下(注意取值范围)：

注意：

A、B位数可能不相等，因此需要分两部分进行加和;

两次循环结束，需要考虑进位是否为零;

(4)减法运算

对于A(a0a1a2...an-1)-B(b0b1b2...bm-1)，并假设A≥B(不考虑负数)，一定有N≥M，则计算过程如下：

注意：

A、B位数可能不相等，因此需要分两部分求差值;

减法运算可能会导致差值的若干个高位是无意义的零值，因此需额外的去零操作;

(5)乘法运算

在计算十进制数123*45时，先计算123*5=615，然后计算123*4=492，终结果是615+492*10=5535。

大数乘法的计算过程与此相同：对于A(a0a1a2...an-1)*B(b0b1b2...bm-1)，并假设N≥M(被乘数位数不小于乘数时，效率高)，对于B中的每一位bi，计算其与A的乘积，并在后面补上i个零，将结果累加，即为A与B的乘积。

(6)除法运算

除法运算是四则运算中复杂的运算，常用的方法是使用多次减法来模拟除法。简单的方法是被除数不断减去除数，直到结果为负，减的次数即为商，当然这种方法效率太低。

网上提供了一些优化方法，例如，在被除数减除数的过程中，被除数每次减去除数的10N倍，以加速被除数衰减过程。

这里采用的方法与上述方法原理相似，以23456除以123为例，在进行竖式计算时：以234除以123，得1，余111，以1115除以123，得9，余8，以86除以123，得0，余86，则23456除以123的结果是190。

上述过程是为了将未知位数的两个大数相除，转换为多次位数相近的两个数相除，即被除数多比除数多1位。算法的核心是上述过程中的234除以124、1115除以123、86除以123，如何得到商和余数。

以下提出一种收敛算法：

先，对于A(a0a1a2...an-1)/B(b0b1b2...bm-1)，一定有A(a0a1a2...an-1)/B(b0b1b2...bm-1)≤A(aiai+1...an-1)/B(bibi+1...bm-1)，其中0≤i≤n-1且0≤i≤m-1。

所以，可以通过取A、B的高两位或一位来预估A、B相除的结果，且预估值≥实际值，并以预估值更新A，多次迭代，直到A

1轮：C0=A0/B，求得预估值V0，有V0>=C0，设V0-C0=C1，B*V0-A0=A1，则

2轮：C1=A1/B，求得预估值V1，有V1>=C1，设V1-C1=C2，B*V1-A1=A2，则

3轮：C2=A2/B，求得预估值V2，有V2>=C2，设V2-C2=C3，B*V2-A2=A3，则

......

x轮：Cx-1=Ax-1/B，此时Ax-1

通过以上过程，可以推导出：C0=V0-V1+V2-...+/-Vx-1

举例(进制S取10亿)：

A0=86,517999162,161442275,630671648,031880106,681829550,207222443

B=92,784489371,679693896,011626721,067864399,494212548

1轮：V0=86,517999162/92=940413034

A1=B*V0-A0=737743996,000612337,308902736,003021973,147110937,498328189

2轮：V1=737743996,000612337/92,784489371=7951156

A2=B*V1-A1=0(实际值是个负值，直接取0)

此时A2

因为误差问题，算法值比实际值大1或与实际值相等，所以算法的终结果需要向下微调。

作者：rmthy

来源：博客园

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。