N型算法
⑴ 各种排序算法的总结和比较
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
点击以下图片查看大图：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模 k："桶"的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同包含以下内容：
1、冒泡排序 2、选择排序 3、插入排序数搭 4、希尔排序 5、归并排序 6、快速排序 7、堆排序 8、计数排序 9、桶排序 10、基数排序排序算法包含的相关内容具体如下：
冒泡排序算法
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该薯亩拿数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
选择排序算法
选择排序是一种简单直观的排序算法，耐差无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
插入排序算法
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
希尔排序算法
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
归并排序算法
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
快速排序算法
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
堆排序算法
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
计数排序算法
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
桶排序算法
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
基数排序算法
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
⑵ 线性运算是数学中的一种重要算法，这种算法有什么特点
加法和数量乘法称为线性运算。
线性代数
线性代数有两类基本数学构件.一类是对象：数组；一类是这些对象进行的运算。在此基础之上可以对一系列涉及数组的数学模型进行探讨和研究，从而解决实际问题.
（一）矩阵的线性运算
矩阵的加法和数乘运算，统称为矩阵的线性运算。
矩阵加减法
⑶ 大数据常用的各种算法
我们经常谈到的所谓的 数据挖掘 是通过大量的数据集进行排序，自动化识别趋势和模式并且建立相关性的过程。那现在市面的数据公司都是通过各种各样的途径来收集海量的信息，这些信息来自于网站、公司应用、社交媒体、移动设备和不断增长的物联网。
比如我们现在每天都在使用的搜索引擎。在自然语言处理领域，有一种非常流行的算法模型，叫做词袋模型，即把一段文字看成一袋水果，这个模型就是要算出这袋水果里，有几个苹果、几个香蕉和几个梨。搜索引擎会把这些数字记下来，如果你想要苹果，它就会把有苹果的这些袋子给你。
当我们在网上买东西或是看电影时，网站会推荐一些可能符合我们偏好的商品或是电影，这个推荐有时候还挺准。事实上，这背后的算法，是在数你喜欢的电影和其他人喜欢的电影有多少个是一样的，如果你们同时喜欢的电影超过一定个数，就把其他人喜欢、但你还没看过的电影推荐给你。 搜索引擎和推荐系统 在实际生产环境中还要做很多额外的工作，但是从本质上来说，它们都是在数数。
当数据量比较小的时候，可以通过人工查阅数据。而到了大数据时代，几百TB甚至上PB的数据在分析师或者老板的报告中，就只是几个数字结论而已。 在数数的过程中，数据中存在的信息也随之被丢弃，留下的那几个数字所能代表的信息价值，不抵其真实价值之万一。 过去十年，许多公司花了大价钱，用上了物联网和云计算，收集了大量的数据，但是到头来却发现得到的收益并没有想象中那么多。
所以说我们现在正处于“ 数字化一切 ”的时代。人们的所有行为，都将以某种数字化手段转换成数据并保存下来。每到新年，各大网站、App就会给用户推送上一年的回顾报告，比如支付宝会告诉用户在过去一年里花了多少钱、在淘宝上买了多少东西、去什么地方吃过饭、花费金额超过了百分之多少的小伙伴；航旅纵横会告诉用户去年做了多少次飞机、总飞行里程是多少、去的最多的城市是哪里；同样的，最后让用户知道他的行程超过了多少小伙伴。 这些报告看起来非常酷炫，又冠以“大数据”之名，让用户以为是多么了不起的技术。
实际上，企业对于数据的使用和分析，并不比我们每年收到的年度报告更复杂。已经有30多年历史的商业智能，看起来非常酷炫，其本质依然是数数，并把数出来的结果画成图给管理者看。只是在不同的行业、场景下，同样的数字和图表会有不同的名字。即使是最近几年炙手可热的大数据处理技术，也不过是可以数更多的数，并且数的更快一些而已。
在大数据处理过程中会用到那些算法呢？
1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的较佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是较佳优先搜索的范例。
2、集束搜索(又名定向搜索，Beam Search)——较佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。
3、二分查找(Binary Search)——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。
4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。
5、Buchberger算法——一种数学算法，可将其视为针对单变量较大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。
6、数据压缩——采取特定编码方案，使用更少的字节数(或是其他信息承载单元)对信息编码的过程，又叫来源编码。
7、Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。
8、Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。
9、离散微分算法(Discrete differentiation)。
10、动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最优子架构算法
11、欧几里得算法(Euclidean algorithm)——计算两个整数的较大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。
12、期望-较大算法(Expectation-maximization algorithm，又名EM-Training)——在统计计算中，期望-较大算法在概率模型中寻找可能性较大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其较大可能估计值;第二步是较大化，较大化在第一步上求得的较大可能值来计算参数的值。
13、快速傅里叶变换(Fast Fourier transform，FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。
14、梯度下降(Gradient descent)——一种数学上的最优化算法。
15、哈希算法(Hashing)。
16、堆排序(Heaps)。
17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。
18、LLL算法(Lenstra-Lenstra-Lovasz lattice rection)——以格规约(lattice)基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统(knapsack)、有特定设置的RSA加密等等。
19、较大流量算法(Maximum flow)——该算法试图从一个流量网络中找到较大的流。它优势被定义为找到这样一个流的值。较大流问题可以看作更复杂的网络流问题的特定情况。较大流与网络中的界面有关，这就是较大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的较大流。
20、合并排序(Merge Sort)。
21、牛顿法(Newton's method)——求非线性方程(组)零点的一种重要的迭代法。
22、Q-learning学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。
23、两次筛法(Quadratic Sieve)——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。
24、RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。
25、RSA——公钥加密算法。较早的适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。
26、Schönhage-Strassen算法——在数学中，Schönhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。
27、单纯型算法(Simplex Algorithm)——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待较大化(或最小化)的固定线性函数。
28、奇异值分解(Singular value decomposition，简称SVD)——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。
29、求解线性方程组(Solving a system of linear equations)——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。
30、Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域( homogenous region)，看看它是否属于边缘，还是是一个顶点。
31、合并查找算法(Union-find)——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：
查找：判断某特定元素属于哪个组。
合并：联合或合并两个组为一个组。
32、维特比算法(Viterbi algorithm)——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。
⑷ 征求n阶乘的优化算法
这是被我初学时写的如今已我抛弃的"算法", 其实也不是什么算法, 只不过类设计一个, 而且类的实现还没有完善, 因为写到一半发现我的构思有多么垃圾我就没再写下去了, 支持4294967295位有符号和无符号整数, 你可以把UBI_SIGNED给undef了对于无符号整型可能要快一点, 我也没算过100000!有没有超过这个范围, 你要算的话自己去算下看看, 我没那个时间.
UBI意为unbounded integer
忘了说你可以去这个网站看下一个专门为理论上的"无限大"数做的的C++库:
http://www.apfloat.org/apfloat/
apfloat的意思是arbitrary precision float, 这个人写的算法很吊, 只能这样说, 2.6亿位的π只用几乎1秒多就出来了, 算100W!也不在话下, 用的大约是数论变换, 你要算法的话可以去参考下, 另:
其实the art of computer programming vol2 siminumerical algorithm有很多关于这方面的介绍的, 我曾经瞥过几眼, 但由于本人数学太烂, 看懂几乎是 impossible -_-~~. 所以也只好作罢...
我写这个烂代码计算乘法很"慢", 但计算加法还马虎, 我曾经用跌代法算Fibonacci的第10W项貌似也只用了很短的时间(感觉不长, 具体记不得了).
计算了一个1000!, 3秒左右:
1239862902
9445909974
1418278094
5573543251
2912073791
0878297308
8932076716
3650241536
0821333186
4516076535
6153071277
8114194545
3408243920
9880051954
5832036786
6848259012
3448259932
8558600301
2188525247
4228458623
5904339901
0164192106
0241866493
1399694290
986355
8633969099
2154399457
8184009699
0277534720
0000000000
0000000000
0000000000
00000000
代码:
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>
using namespace std;
#define UBI_SIGNED
class UBI
{
typedef unsigned char byte;
typedef signed char diff_byte;
typedef vector<byte> mem_type;
typedef mem_type::size_type size_type;
#define SMALL(result) result.first
#define BIG(result) result.second
typedef pair<const UBI*, const UBI*> cmp_result;
static inline byte HiByte(byte b)
{
return b >> 4;
}
static inline byte LoByte(byte b)
{
return b & 0xF;
}
static inline byte MakeByte(byte a, byte b)
{
return (a << 4) | (b & 0xF);
}
void Init(string str);
short Strcmp(const string& lhs, const string& rhs)const;
cmp_result UBICmp(const UBI& lhs, const UBI& rhs)const;
#ifndef UBI_SIGNED
void CheckVal(const string& str)const
{
if(str[0] == '-')
throw domain_error
("Try to initial or assign an negtive value" \
"to a number that is positive.");
}
#endif
public:
UBI(size_type digit = 20);
UBI(const char* c_str, size_type digit = 20);
UBI(const string& str, size_type digit = 20);
UBI(const UBI& UBI);
UBI operator + (const UBI& rhs)const;
UBI operator - (const UBI& rhs)const;
UBI operator * (const UBI& rhs)const;
UBI operator / (const UBI& rhs)const;
const UBI& operator = (const UBI& rhs);
const UBI& operator += (const UBI& rhs);
const UBI& operator -= (const UBI& rhs);
const UBI& operator *= (const UBI& rhs);
const UBI& operator /= (const UBI& rhs);
string ToString()const;
void clear();
private:
mem_type mem;
#ifdef UBI_SIGNED
bool isSigned;
bool IsSigned()const;
mutable bool mutex;
#endif
};
UBI::UBI(size_type digit)
{
#ifdef UBI_SIGNED
isSigned = false;
mutex = false;
#endif
mem.reserve(digit);
}
void UBI::Init(string str)
{
if(str[0] == '-')
str.erase(0, 1);
int i;
for(i = str.size() - 1; i-1 >= 0; i -= 2)
{
mem.push_back(MakeByte(LoByte(str[i]), LoByte(str[i-1])));
}
if(i == 0)mem.push_back(MakeByte(LoByte(str[0]), 0));
}
short UBI::Strcmp(const string& lhs, const string& rhs)const
{
if(lhs.size() > rhs.size())
return 1;
else if(lhs.size() < rhs.size())
return -1;
else if(lhs > rhs)
return 1;
else if(lhs < rhs)
return -1;
return 0;
}
UBI::cmp_result UBI::UBICmp(const UBI& lhs, const UBI& rhs)const
{
string sLhs(lhs.ToString());
string sRhs(rhs.ToString());
if(Strcmp(sLhs, sRhs) == 0)
return make_pair(&lhs, &lhs);
#ifdef UBI_SIGNED
if(sLhs[0] == '-')sLhs.erase(0, 1);
if(sRhs[0] == '-')sRhs.erase(0, 1);
#endif
const UBI* small =
Strcmp(sLhs, sRhs) == -1 ?
this : &rhs;
const UBI* big =
&rhs == small ?
this : &rhs;
return make_pair(small, big);
}
#ifdef UBI_SIGNED
bool inline UBI::IsSigned()const
{
return isSigned;
}
#endif
UBI::UBI(const char* c_str, size_type digit)
{
#ifdef UBI_SIGNED
isSigned = *c_str == '-' ? true : false;
mutex = false;
#else
CheckVal(string(c_str));
#endif
if(string(c_str).size() > digit)
mem.reserve(string(c_str).size());
else
mem.reserve(digit);
Init(string(c_str));
}
UBI::UBI(const string& str, size_type digit)
{
#ifdef UBI_SIGNED
isSigned = str[0] == '-' ? true : false;
mutex = false;
#else
CheckVal(str);
#endif
if(str.size() > digit)
mem.reserve(str.size());
else
mem.reserve(digit);
Init(str);
}
UBI::UBI(const UBI& UBI) : mem(UBI.mem)
{
#ifdef UBI_SIGNED
isSigned = UBI.isSigned;
mutex = false;
#endif
}
const UBI& UBI::operator = (const UBI& rhs)
{
if(this == &rhs)return *this;
mem.assign(rhs.mem.begin(), rhs.mem.end());
#ifdef UBN_SIGNED
isSigned = rhs.isSigned;
#endif
return *this;
}
UBI UBI::operator + (const UBI& rhs)const
{
if(mem.empty() || mem.size() == 1 && mem[0] == 0x0)
return rhs;
if(rhs.mem.empty() || rhs.mem.size() == 1 && rhs.mem[0] == 0x0)
return *this;
#ifdef UBI_SIGNED
if(!mutex)
{
if(isSigned && !rhs.isSigned || !isSigned && rhs.isSigned)
{
mutex = true;
return *this - rhs;
}
}else
mutex = false;
#endif
cmp_result result(UBICmp(*this, rhs));
byte prevHiRemain = 0;
size_type smallSize = SMALL(result)->mem.size();
UBI tempUBI;
for(size_type i = 0; i < BIG(result)->mem.size(); ++i)
{
byte tempHi =
HiByte(BIG(result)->mem[i]) +
(i < smallSize ? HiByte(SMALL(result)->mem[i]) : 0)
+ prevHiRemain;
byte tempLo =
LoByte(BIG(result)->mem[i]) +
(i < smallSize ? LoByte(SMALL(result)->mem[i]) : 0);
prevHiRemain = 0;
if(tempHi > 9)
{
tempLo += tempHi / 10;
tempHi = tempHi % 10;
}
if(tempLo > 9)
{
prevHiRemain = tempLo / 10;
tempLo = tempLo % 10;
}
tempUBI.mem.push_back(MakeByte(tempHi, tempLo));
}
if(prevHiRemain != 0)
tempUBI.mem.push_back(MakeByte(prevHiRemain, 0));
#ifdef UBI_SIGNED
tempUBI.isSigned = this->isSigned ? true : false;
#endif
return tempUBI;
}
const UBI& UBI::operator += (const UBI& rhs)
{
return *this = *this + rhs;
}
UBI UBI::operator - (const UBI& rhs)const
{
#ifdef UBI_SIGNED
if(!mutex)
{
if(!isSigned && rhs.isSigned || isSigned && !rhs.isSigned)
{
mutex = true;
return *this + rhs;
}
}else
mutex = false;
#endif
cmp_result result(UBICmp(*this, rhs));
if(SMALL(result) == BIG(result))
return UBI("0");
byte prevHiBorrow = 0;
size_type smallSize = SMALL(result)->mem.size();
UBI tempUBI;
for(size_type i = 0; i < BIG(result)->mem.size(); ++i)
{
diff_byte tempHi =
HiByte(BIG(result)->mem[i]) -
(i < smallSize ? HiByte(SMALL(result)->mem[i]) : 0)
- prevHiBorrow;
diff_byte tempLo =
LoByte(BIG(result)->mem[i]) -
(i < smallSize ? LoByte(SMALL(result)->mem[i]) : 0);
prevHiBorrow = 0;
if(tempHi < 0)
{
tempLo -= 1;
tempHi = 10 + tempHi;
}
if(tempLo < 0)
{
prevHiBorrow = 1;
tempLo += 10;
}
tempUBI.mem.push_back(MakeByte(tempHi, tempLo));
}
#ifdef UBI_SIGNED
if(this == BIG(result) && this->isSigned ||
this == SMALL(result) && !this->isSigned)
tempUBI.isSigned = true;
#endif
return tempUBI;
}
UBI UBI::operator * (const UBI& rhs)const
{
if(this->mem[mem.size()-1] == 0 || rhs.mem[rhs.mem.size()-1] == 0)
return UBI("0");
if(this->mem.size() == 1 && this->mem[0] == 0x10)
return rhs;
if(rhs.mem.size() == 1 && rhs.mem[0] == 0x10)
return *this;
cmp_result result(UBICmp(*this, rhs));
UBI tempUBI;
for(size_type i = 0, k = 0; i < SMALL(result)->mem.size(); ++i)
{
byte SmHi = HiByte(SMALL(result)->mem[i]);
byte SmLo = LoByte(SMALL(result)->mem[i]);
byte prevLoRemain = 0;
UBI Hi;
for(size_type j = 0; j < BIG(result)->mem.size(); ++j)
{
byte tempHi = SmHi * HiByte(BIG(result)->mem[j]) + prevLoRemain;
byte tempLo = SmHi * LoByte(BIG(result)->mem[j]);
prevLoRemain = 0;
if(tempHi > 9)
{
tempLo += tempHi / 10;
tempHi %= 10;
}
if(tempLo > 9)
{
prevLoRemain = tempLo / 10;
tempLo %= 10;
}
Hi.mem.push_back(MakeByte(tempHi, tempLo));
}
if(prevLoRemain != 0)
{
Hi.mem.push_back(MakeByte(prevLoRemain, 0));
prevLoRemain = 0;
}
if(k > 0)
{
string _10(Hi.ToString());
_10.resize(_10.size()+k, '0');
Hi = UBI(_10);
}
++k;
tempUBI += Hi;
UBI Lo;
for(size_type j = 0; j < BIG(result)->mem.size(); ++j)
{
byte tempHi = SmLo * HiByte(BIG(result)->mem[j]) + prevLoRemain;
byte tempLo = SmLo * LoByte(BIG(result)->mem[j]);
prevLoRemain = 0;
if(tempHi > 9)
{
tempLo += tempHi / 10;
tempHi %= 10;
}
if(tempLo > 9)
{
prevLoRemain = tempLo / 10;
tempLo %= 10;
}
Lo.mem.push_back(MakeByte(tempHi, tempLo));
}
if(prevLoRemain != 0)
{
Lo.mem.push_back(MakeByte(prevLoRemain, 0));
prevLoRemain = 0;
}
if(k > 0)
{
string _10(Lo.ToString());
_10.resize(_10.size()+k, '0');
Lo = UBI(_10);
}
++k;
tempUBI += Lo;
}
return tempUBI;
}
string UBI::ToString()const
{
if(mem.empty() || mem.size() == 1 && mem[0] == 0)
return string("0");
string temp;
temp.reserve(mem.size()*2);
#ifdef UBI_SIGNED
if(isSigned)
temp.push_back('-');
#endif
int i = mem.size()-1;
while(mem[i] == 0 && i > 0)--i;
for(; i >= 0; --i)
{
temp.push_back(LoByte(mem[i]) + '0');
temp.push_back(HiByte(mem[i]) + '0');
}
unsigned zero = temp.find_first_of("0");
#ifdef UBI_SIGNED
if(zero == 0 || temp[0] == '-' && zero == 1)
temp.erase(zero, 1);
#else
if(zero == 0)
temp.erase(zero, 1);
#endif
return temp;
}
void UBI::clear()
{
#ifdef UBI_SIGNED
isSigned = false;
#endif
mem.clear();
}
template <class T, class U>
T lexical_cast(U u)
{
stringstream sstrm;
sstrm << u;
T t;
sstrm >> t;
return t;
}
int main()
{
UBI a("1");
for(int i = 2; i <= 1000; ++i)
{
a = a * lexical_cast<string>(i);
}
cout << a.ToString();
}