Number

「數」或「數量」或「數值」或「數字」。例如1 2 3 4 5。

Large Number（Big Number）

「大數」。很大的數量。例如12345431848949513953123。

Number運算

     operation (noun)       operation (verb)     result (noun)
---  ---------------------  -------------------  -----------------
+    addition       加法    add          加      sum        和
−    subtraction    減法    subtract     減      difference 差
×    multiplication 乘法    multiply     乘      product    積
÷    division       除法    divide       除      quotient   商
mod  modulo         模      ---          模      remainder  餘
^    exponentiation 乘方    exponentiate 乘方    power      冪
√‾   ---            開方    ---          開方    root       根
log  ---            取對數  ---          取對數  logarithm  對數
∑    summation      連加    ---          連加    sum        總和
∏    ---            連乘    ---          連乘    product    連乘積

Number資料結構

要存放這麼大的數量，有個好方法——使用陣列。

陣列有很多格子，一個格子存一個數字。1000格的int陣列，可以存1000個位數！

struct BigNumber { int array[1000]; // 一格存一個數字，可以存1000個位數 bool sign; // 正負號 int length; // 位數 };

我們習慣將低位數放在索引值較小的位置，高位數放在索引值較大的位置。比如存放680468975231245：

 ₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇ ₈ ₉ ...
 _____________________________________
|5|4|2|1|3|2|5|7|9|8|6|4|0|8|6| | | | ...
 ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾

每個人對陣列的思考模式不一樣，像這裡就是由左至右的，另外也有人覺得陣列是由右至左、由上至下、彎彎曲曲的、……。要怎麼思考都是可以的，一以貫之就好囉。

陣列右端的空格，通常設成0，運算的時候比較方便。

scan

從字串中讀取大數。

void scan(char s[100], int a[100]) { int i = 100 - 1; // 大數的數字位置 int j = 0, n = strlen(s); // 字串的字元位置 while (i >= n) a[i--] = 0; // 開頭一律填零 while (i >= 0) a[i--] = s[j++] - '0'; // 字串頭尾顛倒，存入陣列 }

簡單起見，此處假設大數絕對不是負數。

print

在螢幕上印出大數。

void print(int a[100]) { int i = 100 - 1; // 大數的數字位置 while (a[i] == 0) i--; // 數字開頭的零都不印 while (i >= 0) cout << a[i--]; }

如果這個大數有可能是零，就得加個幾行程式碼。

void print(int a[100]) { int i = 100 - 1; while (i >= 0 && a[i] == 0) i--; if (i < 0) cout << '0'; else while (i >= 0) cout << a[i--]; }

comparsion <

兩個大數比較大小。

// a < b bool less_than(int a[100], int b[100]) { // 從高位數開始比，對應的位數相比較。 for (int i=100-1; i>=0; i--) if (a[i] != b[i]) // 一旦ab不一樣大，馬上回傳結果。 return a[i] < b[i]; return false; // 完全相等 }

addition +

大數加法的粗略程式碼。

// c = a + b; void add(int a[100], int b[100], int c[100]) { for (int i=0; i<100; i++) // 對應的位數相加 c[i] = a[i] + b[i]; for (int i=0; i<100-1; i++) // 一口氣進位 { c[i+1] += c[i] / 10; // 進位 c[i] %= 10; // 進位後餘下的數 } }

大數的運算有個有趣的地方，就是運算時不用立即進位，可以後來再一口氣進位。

UVa 10035

subtraction −

大數減法的粗略程式碼。

void sub(int a[100], int b[100], int c[100]) { for (int i=0; i<100; i++) c[i] = a[i] - b[i]; for (int i=0; i<100-1; i++) // 一口氣借位和補位 if (c[i] < 0) { c[i+1]--; // 借位 c[i] += 10; // 補位 } }

multiplication ×

大數乘法的粗略程式碼。我一定要強調它是粗略的。

void mul(int a[100], int b[100], int c[100]) { for (int i=0; i<100; i++) c[i] = 0; for (int i=0; i<100; i++) for (int j=0; j<100; j++) if (i+j < 100) c[i+j] += a[i] * b[j]; for (int i=0; i<100-1; i++) // 一口氣進位 { c[i+1] += c[i] / 10; c[i] %= 10; } }

大數乘以int變數，比較容易一些。

void mul(int a[100], int b, int c[100]) { for (int i=0; i<100; i++) c[i] = a[i] * b; for (int i=0; i<100-1; i++) // 一口氣進位 { c[i+1] += c[i] / 10; c[i] %= 10; } }

UVa 338 10106

division ÷

大數除法可以直接使用長除法。

void div(int a[100], int b[100], int c[100]) { int t[100]; for (int i=100-1; i>=0; i--) for (int k=9; k>0; k--) // 嘗試商數 { mul(b+i, k, t); if (!less_than(a+i, t)) { sub(a+i, t, c+i); break; } } }

商數範圍是0到9，所以必須一一嘗試。可以利用高位數相除來估計商數的範圍，便不必一一嘗試。

大數除以int變數，比較容易一些。

void div(int a[100], int b, int c[100]) { int r = 0; for (int i=100-1; i>=0; i--) { r = r * 10 + a[i]; c[i] = r / b; r %= b; } }

square root √‾

大數平方根可以直接使用直式開方法。

UVa 10023 10606

改進資料結構

 ₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇ ₈ ₉ ...
 _____________________________________
|5|4|2|1|3|2|5|7|9|8|6|4|0|8|6| | | | ...
 ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾

一格只存一個數字，有點浪費。

int的數值範圍約為10位數，一格能夠存入9位數。1000格的int陣列，從原來的1000位數，搖身一變成為9000位數。如果想要存入1000位數，僅僅需要112格。這個新想法，大幅降低空間用量，也大幅降低運算次數。

 ₀         ₁         ₂         ₃
 _________________________________
|975231245|   680468|         |   ...
 ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾

不過，如果一格存了很多位數，會對運算造成什麼影響呢？

一、進位：如果一格存了9個位數，那麼每到10⁹才能進位。

二、進位溢位：進位讓鄰格的數字增加。如果鄰格原本就有一個很大的數字，就可能產生溢位。

三、乘法溢位：乘法是兩格相乘，添加到另一格。如果兩格都存了9個位數，相乘之後至少17個位數，遠遠超過int的上限。

除此之外還要考慮除法、平方根。雖然問題重重，但是並不代表一格還是只能存一個數字。稍微存個幾位數，應該不成問題吧？這些問題就留給大家思考。

UVa 288 10220 10814 10925 748

記載數量

想要記載一個數量，最直觀的方式是：一個符號、重複數次。

♥
♦♦
☁☁☁
★★★★★★★★★★★★★★★★★★

第一個技術：分堆

一個個數，太花時間。為了節省時間，可以嘗試分堆。最常見的分堆方式，是十個一堆。如果有很多堆，那麼十堆再合成一大堆；如果有很多大堆，那麼十大堆再合成一大大堆；以此類推。

hard way:
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

easy way:
★★★★★★★★★★　　★★★★★★★★★★　　★　★
★★★★★★★★★★
★★★★★★★★★★　　★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★　　★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★

以此類推的過程，我們習慣採用固定數量，這個數量稱作「底數Base」或「基數Radix」。例如上例的底數就是十。

然而也有例外。例如時間：六十秒一分、六十分一時、二十四時一日，底數不是固定數量。

第二個技術：命名

一個個數，太花時間。為了節省時間，可以替每種數量取不一樣的名字；換句話說，用不一樣的符號代替每種數量。

長長一串數量，變成短短一個符號，人生充滿歡樂！

這些符號稱作「數字Digit」。

同時使用第一個技術和第二個技術：位數

越多符號，越難背誦。你能想像背誦一百種符號代替一百種數量嗎？符號還是少點好。

解法是同時使用第一個技術和第二個技術，令符號數量等於底數。例如底數是十，可以使用0123456789等十個符號。當數量大於等於十，十個形成一堆，記載在左邊一點的位置，變成10。當數量累積十堆，十堆形成一大堆，記載在更左邊一點的位置，變成100。這是地球上最流行的記載方式。

除了替每一種數量取名字，有些語言還會替每一種數量級取名字，讓數字之間穿插數量級符號。這是題外話。

132
英文：one hundred thirty-two      （hundred是數量級的符號）
中文：一百三十二                  （百、十是數量級的符號）

選擇底數

我們可以選擇自己喜歡的底數。底數不能是零、不能是一。底數是二，稱作「二進位」，使用01兩個符號。底數是三，稱作「三進位」，使用012三個符號。底數是十六，稱作「十六進位」，使用0123456789ABCDEF十六個符號。底數超過三十六，那麼必須額外引入一些符號，才夠用。

底數寫於數字的右下角，用括號包住。

101₍₂₎   二進位，數字是101
73F₍₁₆₎  十六進位，數字是73F

同樣的數量，使用不同的底數，往往得到不同的數字。

★★★★★★★★★★★★★★★★★★  10010₍₂₎
★★★★★★★★★★★★★★★★★★  18₍₁₀₎
★★★★★★★★★★★★★★★★★★  12₍₁₆₎

同樣的數字，使用不同的底數，往往得到不同的數量。

11₍₂₎   ★★★
11₍₁₀₎  ★★★★★★★★★★★
11₍₁₆₎  ★★★★★★★★★★★★★★★★★

選定底數，數字變數量（scan）

C語言當中的atoi()字串轉整數函式，其實就是「選定底數10，把數字變成數量」。

void number_to_value(char number[], int n, int base) { int value = 0; // 從最高位數處理到最低位數 for (int i=0; i<n; ++i) { int digit = -1; if (number[i] >= 'A' && number[i] <= 'Z') digit = number[i] - 'A'; else if (number[i] >= '0' && number[i] <= '9') digit = number[i] - '0'; // 出現異常符號 if (digit == -1 || digit >= base) return; value = value * base + digit; } // 印出數量 cout << value; }

選定底數，數量變數字（print）

void value_to_number(int value, int base) { // 便宜行事，不處理負數 if (value < 0) return; // 零 if (value == 0) {cout << '0'; return;} // 填入數字 char number[10]; int n = 0; // 位數 // 從最低位數處理到最高位數 while (value > 0) { number[n] = value % base; value /= base; n++; } // 印出數字 for (int i=n-1; i>=0; --i) cout << number[i]; }

更換底數（進制轉換）

10010₍₂₎ = ?₍₁₆₎

令數量維持相等，給定原數字、原底數、新底數，求新數字。

演算法和程式碼交給讀者思考！

UVa 343 344 355 377 389 446 448 575 594 619 636 10019 10469 10473 11005 11121

Polynomial

「多項式」。變數的各種次方、乘上倍率、通通相加。

2x³ + 0x² - 4x¹ + 8x⁰

求值（Horner's Rule）

已知x、已知係數c₀ c₁ c₂ ...，求c₀x⁰ + c₁x¹ + c₂x² + ...。

一乘一加，得到答案。不需要次方運算。時間複雜度O(N)。

2x³ + 0x² - 4x¹ + 8 = (((((2 ⋅ x) + 0) ⋅ x) - 4) ⋅ x) + 8

// n = ... + c₂x² + c₁x¹ + c₀x⁰ int evaluate(int x, vector<int>& c) { int n = 0; for (int i=c.size()-1; i>=0; i--) { n *= x; n += c[i]; } return n; }

求係數【尚無正式名稱】

已知x、已知c₀x⁰ + c₁x¹ + c₂x² + ...，求係數c₀ c₁ c₂ ...。

答案無限多種。其中一種答案是求值演算法顛倒做。

一模一除，得到答案。不需要次方運算。時間複雜度O(N)。

// n = ... + c₂x² + c₁x¹ + c₀x⁰ vector<int> coefficient(int x, int n) { vector<int> c; while (n > 0) { c.push_back(n % x); n /= x; } return c; }

一個數字可以改寫成一個多項式

10010₍₂₎ ---> 1x⁴ + 0x³ + 0x² + 1x¹ + 0x⁰ (x = 2)
18₍₁₀₎   ---> 1x¹ + 8x⁰ (x = 10)
73F₍₁₆₎　---> 7x² + 3x¹ + 15x⁰ (x = 16)

在數學家眼中，底數可以藉由多項式一以貫之。

「選定底數，數字變數量」就是「求值」。

「選定底數，數量變數字」就是「求係數」。

大數就是多項式，x代入10。大數運算就是多項式運算。

十進位、二進位、八進位、十六進位，進位制就是多項式，x代入各種底數。

luogu P5248

延伸閱讀：益智問題

以身試毒：

兩步猜出多項式的係數：

Arabic Numerals

Roman Numerals

UVa 759 11616 12397 11787

Clock

UVa 579 11677

Calendar

1752年9月曾經調整過日曆。

const char* name[] = { "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday" }; // 當天是星期幾 void weekday(int y, int m, int d) { // 1月2月看作是前一年的13月14月，方便統計。 if (m == 1 || m == 2) { m += 12; y--; } // 在1752/9/3之前，閏年機制不同。 int w = 0; if ((y < 1752) || (y == 1752 && m < 9) || (y == 1752 && m == 9 && d < 3)) w = (d + 2*m + 3*(m+1)/5 + y + y/4 + 5) % 7; else w = (d + 2*m + 3*(m+1)/5 + y + y/4 - y/100 + y/400) % 7; cout << y << "年" << m << "月" << d << "日" << name[w]; }

UVa 300 602 10070 11356

數量種類

   	operation (noun)                 	example
---	---------------------------------	-----------
ℕ  	natural numbers    自然數        	0 1 2 3 4
ℤ  	integers           整數          	-2 -1 0 1 2
ℚ  	rational numbers   有理數（分數）	1/3 0.123
𝔸  	algebraic numbers  代數數        	√2 ∛2
---	---------------------------------	-----------
ℝ  	real numbers       實數          	π e
ℂ  	complex numbers    複數          	√-1 1+2𝑖

數量與運算

1 + 2 = ☐。自然數加法運算。數一數手指就行了。

☐ + 2 = 3。自然數加法反運算。等量公理（移項）就行了。

那麼☐ + 2 = 1呢？答案不是自然數。旅途就此開始。

數量種類（基於運算）

正運算補滿數域，反運算拓展數域。

數量的基礎是自然數。自然數裝備加法得到所有自然數。整數裝備乘法得到所有整數。有理數裝備自然數乘方得到所有有理數。

數量的基礎是自然數。自然數裝備減法得到整數。整數裝備除法得到有理數。有理數裝備自然數開方得到代數數。

數量種類（基於幾何）

實數是有理數之間相鄰相連的數。用來簡化有理數的計算。

複數是代數數之間相鄰相連的數。用來簡化代數數的計算。

數量變幾何之後，數量獲得長度、角度，方便理解數量的計算。

實數數線Real Line：直角座標系。

實數　　　⇨　點
實數長度　⇨　點到原點的距離
實數加法　⇨　點的座標相加（位移）
實數乘法　⇨　點的長度相乘（縮放）、點的方位負負得正（鏡射）

複數平面Complex Plane：直角座標系、極座標系兩者合體。

複數　　　⇨　點
複數長度　⇨　從原點出發的直線距離
複數角度　⇨　從實軸出發的逆時針夾角
複數加法　⇨　點的座標相加（位移）
複數乘法　⇨　點的長度相乘（縮放）、點的角度相加（旋轉）

複數總是可以化作a+b𝑖的形式。實數a b、虛數𝑖 = √-1。

複數乘法變點的長度相乘、角度相加，使之循環繞圈，這是古人一致推薦的方式。由於很好用，從此沒有採用其他方式。

UVa 10378

程式語法

注意到，由於數值精確度的緣故，這些語法沒有完全符合數學家的定義！雖說如此，普通情況下已經足夠堪用了！

自然數：unsigned char、unsigned short、unsigned int、unsigned long long。記憶體使用量、數值範圍有所差異。

整數：char、short、int、long long。

有理數：C/C++程式語言沒有對應的語法。

代數數：C/C++程式語言沒有對應的語法。

unsigned int u = 1; // 1 int i = -1; // -1

實數：float、double、long double。

複數：complex，需要引入標頭檔。

#include <complex> float f = 0.123f; // 0.123 double d = 0.123; // 0.123 complex<float> c = 1 + 2i; // 1 + 2𝑖

函式庫

實數和複數也有專門的函式庫。GMP：任意精度運算函式庫。MPFR：實數高精度運算函式庫。MPC：複數高精度運算函式庫。

// http://www.ptt.cc/bbs/C_and_CPP/M.1379872080.A.CC9.html // 計算 sqrt(x) #include <stdio.h> #include <math.h> #include <mpfr.h> int main(int argc, char *argv[]) { mpfr_t r; unsigned long int precision, x=2; precision = ceill(10000*logl(10)/logl(2)); mpfr_init2(r, precision); mpfr_sqrt_ui(r, x, MPFR_RNDN); // <-- 重點就只有這行 mpfr_printf("%.10000Rf\n", r); mpfr_clear(r); return 0; } // http://www.ptt.cc/bbs/C_and_CPP/M.1379872080.A.CC9.html // 計算 10000! #include <stdio.h> #include <gmp.h> int main(int argc, char *argv[]) { mpz_t s; unsigned int n = 10000; mpz_init_set_ui(s, 1); for (n=1; n<=10000; n++) { // <-- 重點就只有這個迴圈 mpz_mul_ui(s, s, n); } gmp_printf("%Zd\n", s); mpz_clear(s); return 0; }