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();
}