高精度计算之大数据相加

§前言

 

高精度计算是算法较为基础的一部分。

由于现有计算编程语言的数据类型限制,对于大数据的存储能力与计算能力有限。故在需要进行大数据运算时,我们采用非常规的方法代替编程语言内置的算法,来进行计算。

大数据计算的一般思路为:将大数据拆分成多个小数据,使用编辑语言能够计算的小数据进行计算,再将小数据合并成大数据。

 

§大数加法

 

从自然数的加法开始学习。

首先要解决的是数据的存储。由于C++语言的长整型存储位数有限,存储大数据会出现溢出错误,我们将大数当作一个字符串进行存储。

然后将字符串分解成可以运算的小数,按照数据运算的一般规则来进行计算处理。

最后将多个小数组合成大数表示。

 

则对于大数加法有如下步骤:

  • 存储。使用字符串存储大数,将大数从高位到低位依次存放于字符数组中。这符合数据表示习惯
  • 转换。将字符数组从低位到高位依次转换成整型数字,并按下标从大到小依次存入整型数组(即将大数据的最低位向右对齐)。这符合数据计算习惯。
  • 计算。按下标从大到小(即大数据从低位到高位),依次进行单个整型的加法运算。如果满10则向高一个进1
  • 转换并存储。按下标的从小到大,将整型数组元素依次存入字符数组。

阅读更多

初探SQLite的R-Tree

R-Tree简介:

R-Tree是一种为空间查询而生的数据结构。只要给出一个空间对象的范围,使用R-Tree就可以快速而精确的查询出你所需要的空间对象(一个精确对象或是与之叠加的一组对象)。

让你的SQLite支持R-Tree

如果你使用的SQLite是从SQLite官网上直接下载的DLL文件,那么它应该已经包含了R-Tree功能模块。如果你使用的是自己定制的SQLite库,那么你在编译的时候,就需要打开R-Tree开关了(R-Tree模块默认是禁用的)。在C模式下编译的时候,添加 SQLITE_ENABLE_RTREE 宏开关,就可以获取R-Tree模块支持了。

在SQLite中使用R-Tree

构建R-Tree结构

SQLite中的R-Tree以虚表(Virtual Table)实现,最多支持5维空间索引。在N维R-Tree中,需要给出一个64位有符号整型作为索引(同时也是主键),然后给出N维的32位浮点数的空间范围值对。例如,一维的R-Tree,需要给出三个字段:索引、最小值、最大值,二维的R-Tree,需要给出五个字段:索引、X最小值、X最大值、Y最小值、Y最值…以此类推,五维的R-Tree,有11个字段。

在SQLite中创建一个R-Tree很简单,只需要一条Sql语句就可以搞定:

格式:CREATE VIRTUAL TABLE <name> USING rtree(<column-names>);

例如:CREATE VIRTUAL TABLE demo_index USING rtree(

id,              -- Integer primary key

minX, maxX,      -- Minimum and maximum X coordinate

minY, maxY       -- Minimum and maximum Y coordinate

);

 

阅读更多