Question

Number

“数字”。例如 1 2 3 4 5 3.1415。

数字做计算，例如加减乘除，统称为“算术 arithmetic”。

数字做计算，若想强调数字本身的数量多寡，可将数字重新称为“数值 numerical value”或是“值 value”。

Numerical Computation / Symbolic Computation

算术当中，一律只用实际数值，称作“数值计算”。採用数学符号，称作“符号计算”。

例如整数除法：

Numerical Computation:
1 ÷ 3 = 0.3333333333333　（使用数字，记下答案。无法完全记录。）

Symbolic Computation:
         1 
1 ÷ 3 = ———　（使用数学符号：一条横槓，代表分数，记下答案。）
         3 

例如多项式乘法：

Numerical Computation:
x = 2, y = 1
(x+1)(3y+2) = (2+1)×(3×1+2) = 3×(3×1+2) = 3×(3+2) = 3×5 = 15

Symbolic Computation:
(x+1)(3y+2) = 3xy + 2x + 3y + 2

小学谈过数值计算，中学谈过符号计算，大家应该非常熟悉。至于接下来要谈的，只有数值计算。

Number 资料结构

   name                     example      data structure
-- -----------------------  -----------  ---------------------
ℕ  natural numbers  自然数  0 1 2 3 4    ---
ℤ  integers         整数    -2 -1 0 1 2  integer        整数
ℚ  rational numbers 有理数  1/3 0.123    fraction       分数
ℝ  real numbers     实数    π e          floating-point 浮点数
ℂ  complex numbers  複数    √-1 1+2i     complex        複数

数学家将数字分类为：自然数ℕ、整数ℤ、有理数ℚ、实数ℝ、複数ℂ。

计算学家建立了对应的资料结构：整数 integer、浮点数 floating-point，又衍生：大数 big number、分数 fraction、複数 complex。注意到，由于数值计算的缘故，这些资料结构并不符合数学家的定义！

前两种资料结构暨演算法（加减乘除运算），已经制作成电路，放在中央处理器裡面。我们不必重新实作，直接在程式语言当中宣告变数、使用运算子、呼叫内建函式即可。

后三种资料结构也已经成为内建函式库，我们也不必重新实作。不过偶有例外，例如 C 和 C++就没有 big number 和 fraction。

Number Operation

     operation (noun)        operation (verb)      result (noun)
---  ----------------------  --------------------  ------------------
+    addition        加法    add           加      sum         和
−    subtraction     减法    substract     减      difference  差
×    multiplication  乘法    multiply      乘      product     积
÷    division        除法    divide        除      quotient    商
mod  modulo          模      ---           模      remainder   馀
^    exponentiation  乘方    exponentiate  乘方    power       幂
√‾   ---             开方    ---           开方    root        根
log  ---             取对数  ---           取对数  logarithm   对数
∑    summation       连加    ---           连加    sum         总和
∏    product of      连乘    ---           连乘    product     连乘积
     a sequence
!    factorial       阶乘    ---           阶乘    product     连乘积

算术当中，一种特定的计算方式，例如加法，称为“运算 operation”。

运算符号，例如+，称为“运算子 operator”。

数学家发明了许多种运算。大家应该都遇过。

Number 资料结构: Integer

整数（Integer）

C 与 C++语言当中，可以直接使用 char、short、int、long long 建立整数资料结构，再以 unsigned 调整数值范围。

切记，数值范围有固定的上下限。如果超过上下限，称做“溢位 overflow”。依照 C 程式语言规格书，整数溢位是未定义行为，可能导致当机。

此处不介绍转型规则、位元运算、型态大小、cstddef。这些不是演算法，大家自己查程式语言规格书吧。

资料结构

大家习惯使用二的补数表示法：

http://en.wikipedia.org/wiki/Two's_complement

scan

字串变整数。我没有研究。

print

整数变字串。我没有研究。

+

−

×

https://en.wikipedia.org/wiki/Multiplication_algorithm

×（Divide and Conquer）

a×b，其本质是 a 複制出 b 份，通通加起来。

如果 b 是偶数，我们将原问题分成两个小问题：b/2 份相加、b/2 份相加（一模一样，不必重算），最后两者答案相加即可。

如果 b 是奇数，则分成三个小问题：b/2 份、b/2 份、1 份，最后三者答案相加即可。

×（Double-and-Add Algorithm）

把 b 视作二进位，拆开 b 的每一个位数，从 b 的低位数处理到 b 的高位数，分别计算每一个位数与 a 的乘积，并且累加起来。

位数增加时，十进位之下是变成十倍，二进位之下则是变成两倍。随著 b 的位数逐渐增加，a 也必须逐渐翻倍。

÷

http://en.wikipedia.org/wiki/Division_algorithm

mod

^

C/C++没有次方运算子。内建函式库的 pow() 是浮点数版本而非整数版本。必须自己动手写程式。

Number 资料结构: Floating-point

浮点数（Floating-point）

C 与 C++语言当中，可以直接使用 float、double、long double 建立浮点数资料结构。切记，数值范围有固定的上下限。

资料结构

已经有标准规格，请参考 IEEE 754：

http://en.wikipedia.org/wiki/IEEE_floating_point

特殊数字

浮点数溢位，依照 IEEE 754 规格书，将产生特殊数字，而且特殊数字仍然可以用于运算！

 INF：无限大。　例如：正数除以 0、两个超大的正数相加。
-INF：负无限大。例如：负数除以 0、两个超小的负数相加。
  -0：负零。　　例如：负数乘以 0。
 NaN：非数。　　例如：无限大与零互除、负数开根号。

此处不介绍特殊数字的运算规则，请读者自行上网查询。

精确度

浮点数，位数有限。当位数过多，将剔除低位数。剔除的详细过程，请大家自行研究规格书。

有些十进位小数，换成二进位之后，是循环小数。由于位数有限，剔除低位数，使得数值变动了。

加减乘除运算，将预先比较两数的数量级谁大谁小。如果数量级太悬殊，那麽数量级较低者，将剔除低位数，才进行计算。详细计算过程，请自行研究规格书。

总而言之，浮点数的运算，要特别当心精确度问题。

scan

字串变浮点数。我没有研究。

print

http://www.zhihu.com/question/22498967

浮点数变字串，主要有两个演算法：Dragon4、Grisu3。有兴趣的读者请自行研究。

直至今日，某些演算法仍会得到错误结果。比方说，数量级很大，印成十进位，将得到奇怪的数字。

编写程式码显示浮点数，必须经过 scan 与 print 两个步骤，失真可能发生在 scan、或者 print、或者两者皆有。上例的失真应该是发生在 print。

÷

http://en.wikipedia.org/wiki/Division_algorithm

http://casdc.ee.ncku.edu.tw/class/CA/CH16.pdf

√‾

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

http://stackoverflow.com/questions/17410382/

∑（Kahan Summation Algorithm）

http://en.wikipedia.org/wiki/Kahan_summation_algorithm

加总一连串大小差异很大的浮点数，尽量保持精确。

∑（Binary Splitting）

http://en.wikipedia.org/wiki/Binary_splitting

用来加速分数运算。

!（Stirling's Formula）

http://en.wikipedia.org/wiki/Stirling's_approximation

http://en.wikipedia.org/wiki/Gamma_function

UVa 1185

延伸阅读：math.h

https://zhuanlan.zhihu.com/p/20085048

Number 资料结构: Big Number

大数（Big Number）

很大的数字，大到无法以一个简单的变数型态储存这个值。

一般来说，int 这个变数型态，记忆体大小为 32 bit，可以储存数值范围为-2^31 到 2^31 - 1 的整数，大约是 1 后面再接九个零；而 long long 这个变数型态是 64 bit 的，可以储存数值范围为-2^63 到 2^63 - 1 的整数。另外还有 unsigned 这个关键字，它能让原本的变数型态能够存入更大一点的正整数。

虽然 int、long long 的数值大小已经够用了，但是人的慾望是无止尽的，总是想让电脑能够处理更大的数字、算得更精准。于是大数的技术就这样产生了。

资料结构

要让电脑存放这麽大的数字，有个好方法就是使用阵列。

阵列有很多格子，一个格子存一个数字；只要宣告 1000 格大小的 int 阵列，就可以存 1000 位数了！至于一个 int 变数，充其量也不过十位数而已──阵列能存放的数值大小，和 int 相比之下，实在是多很多很多。

我们习惯将低位数放在索引值较小的位置，高位数放在索引值较大的位置。比如存放 680468975231245：

每个人对阵列的思考模式不一样，像这裡就是由左至右的，另外也有人觉得阵列是由右至左、由上至下、弯弯曲曲的、……。要怎麽思考都是可以的，一以贯之就好囉。

阵列右端划上横线的格子，通常我喜欢存 0 进去，这样子做运算的时候会比较方便；如果将横线的部分设成-1，在运算时会出现点麻烦，所以我不喜欢、也不建议这麽做。

scan

从字串中读取大数可以这麽做。

简单起见，假设大数绝对不是负数。领略要点之后，撰写负数版本的程式码，应该难不倒各位读者。

print

在萤幕上印出大数可以这麽做。

如果这个大数有可能是零，就得加个几行程式码。

>

比较哪个数字大。

+

这裡提供大数加法的粗略程式码，希望能一目瞭然。