2014 微積分小考考卷

2014 期中小考

醫學系的課程內容與其他系有很大的差異,因此考試排程也不同。目前尚未撰寫醫學系的詳解。

本文還在施工中。

導函數

牙醫系第 2 題

Use the definition of the derivative given that to find the derivative of f(x) = cos(x).

本題同去年的第 2 題,只是用詞不同。

其他系第 2 題

given that to find the derivative of f(x) = x3 + 7x.

代入題目給的定義。

對於記得一些乘法公式的學生來說,同次項相減算起來比較快。

(x + h)3x3 = 3x2h + 3xh2 + h3

(x + h)3 + 7(x + h) − (x3 + 7x) = (3x2 + 7)h + 3xh2 + h3

牙醫系第 5 題

Logarithmic differentiation. Let and find f′(x)

對數微分法

乘法法則

導數

第 3 題

Given , find f′(3).

切線與法線

牙醫系第 4 題

Find the equation of the tangent line of the family of curves y3 + xy = sec(xy2) + c at (1, 1).

Hint

我們將這個曲線族對 x 隱微分,即在 (1, 1) 附近將 y 視為 x 的函數。

3y2y′ + y + xy′ = sec(xy2) tan(xy2) (y2 + 2xyy′)

(3y2 + x) y′ + y = sec(xy2) tan(xy2) (y2 + 2xyy′)

代入 (1, 1) 以求取切線斜率。

4y′ + 1 = sec 1 tan 1 (1 + 2y′)

cos2 1 (4y′ + 1) = sin 1 (2y′ + 1)

cos2 1 − sin 1= (2 sin 1 − 4 cos2 1) y

所以切線方程為

其他系第 4 題

Find the equation of the normal line of the family of curves y3 + xy = xy2 + c at (3/16, 2).

我們將這個曲線族對 x 隱微分

3y2y′ + y + xy′ = y2 + 2xyy

(3y2 − 2xy + x) y′ = y2y

代入 (3/16, 2) 以求取切線斜率。

(12 − 9/16) y′ = 2

y′ = 32/183

所以法線斜率為 -183/32,而法線方程為

應用題

牙醫系第 6 題

Electron speed. An electron with a whose mass of is 9.1 × 10-31 kg and a charge of is -1.6 × 10-19 C travels in a circular path with no loss of energy in a magnetic field of 0.05 T that is orthogonal to the path of the electron. If the radius of the path is 0.002 m, what is the speed of the electron?

磁力提供電子繞圈的向心力。

mv2 / r = q |v × B|

其中 m 為質量,v 為速度,q 為電量,B 為磁場;向量以粗體表示,而純量(包括向量的量值)則否。因為速度與磁場垂直,所以

|v × B| = vB

此時本題由向量問題簡化為純量問題。

mv2 / r = qvB

v = qrB / m

代入題目的數據。

v = (1.6 × 10-19 C) (0.002 m) (0.05 T) / (9.1 × 10-31 kg)

v ≈ 1.76 × 107 m/s

其他系第 6 題

In the late 1830s, French physiologist Jean Poiseuille discovered the formula we use today to predict how much the radius of a particular clogged artery decreases the normal volume of flow. His formula,

V = kr4

says that volume of fluid flowing through a small pipe or tube in a unit of time at a fixed pressure is a constant times the fourth power of the tube’s radius r. How dose does a 10% decrease in r affect V?

官方解法

由題意知

Δr = 0.05r

我們利用

得出

ΔV ≈ 0.2kr4 = 0.2V

V 增加 20%

直接解法

設原有的半徑為 r0,原有的體積為 V0

V0 = kr04

因為半徑增加 5%,即

r = 1.05r0

所以

V = k (1.05r0)4 = 1.054 V0

體積增加 21.550625%

線性回歸

其他系第 1 題

In a study of 12 subjects, a clinical researcher obtained these data relating the ages of a subject pool (in years) to that of their systolic blood pressure (in mmHg):

No. Age (years) BPsystolic (mmHg)
125120
237139
320118
449150
527125
623115
734146
856170
924128
1036137
1122126
1242148
試算表
x y x2 xy
25120 6253000
3713913695143
20118 4002360
4915024017350
27125 7293375
23115 5292645
3414611564964
5617031369520
24128 5763072
3613712964932
22126 4842772
4214817646216
39516221446555349

考卷掃描

2014 微積分小考考卷
2014 微積分小考考卷,300 dpi.

在 C++98 模擬 enum class

使用巢狀類別 (nested class) 可以達到類似的效果。因為我們不需要這些類別的實例 (instance),所以只需要宣告 (declaration),不需要定義 (definition)。

struct Color
{
	class Red;
	class Green;
	class Blue;
};

template <typename ColorType>
struct hex;

template <>
struct hex<Color::Red>
{ enum { value = 0xff0000 }; };

template <>
struct hex<Color::Green>
{ enum { value = 0x00ff00 }; };

template <>
struct hex<Color::Blue>
{ enum { value = 0x0000ff }; };

位元處理大全

本文翻譯、改寫自 Sean Eron AndersonBit Twiddling Hacks 一文。為了方便直接把代碼貼到程式裡,我盡量把長的算式寫成函數,短的算式就只列出。

本文在計算運算量時,一個 C 運算子計作一次運算。中途指派 (intermediate assignments) 因為不須寫入 RAM,所以不計。當然,這樣的計量方法只是機器指令數與 CPU 時間的估計值。所有的指令都假設消耗相同時間,與實況不符,但近來 CPU 的確朝這個方向發展。有許多微擾也決定了系統執行程式會跑得多快,像是快取大小、記憶體頻寬指令集等。倒頭來,評測 (benchmarking) 才是判斷某方法是否比另一方法快的正途,所以請把以下的手法視為在你的目標架構上的評測單元。

基本運算

本章主要探討符號、大小相關的議題,並在分支很慢的硬體上尋找替代方案。

計算數的符號

(v > 0) - (v < 0)

雖然本文是位元處理大全,但這個對浮點數也能奏效。

判斷兩整數是否異號

(x ^ y) < 0

計算整數的絕對值,不用分支

為了簡潔,這裡採用 C++函數模板

template <typename T>
T abs (T v)
{
	T mask = v < 0;
	return (v + mask) ^ mask;

//	有專利的變體
//	return (v ^ mask) - mask;
}

有些 CPU 沒有計算整數絕對值的指令,或編譯器可能無法利用它。在分支較慢的機器上,以上的函數會跑得比 v < 0 ? -v : v 快。

找出兩整數中較小的或較大的,不用分支

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))

快速骯髒版

如果你確定 xy 不會溢位,則你也可以採用以下的作法處理有號整數。為了簡潔,此處用 C++ 的寫法。對於有號整數,std::numeric_limits<T>::digits == sizeof(T) * CHAR_BIT - 1,其中 CHAR_BIT 定義在 limits.h 中。

#include <climits>
#define bitsof(T) (sizeof(T) * CHAR_BIT)

template <typename T>
T min (T x, T y)
{
	T z = x - y;
	return y + (z & (z >> std::numeric_limits<T>::digits));
}

template <typename T>
T max (T x, T y)
{
	T z = x - y;
	return x + (z & (z >> std::numeric_limits<T>::digits));
}

注意 C 並未規定負數右移的結果,所以這可能無法移植。

判斷整數是否為 2 的整數次方

如果你確定參數 v 非零,就可以用

v & (v - 1) == 0

注意當 v 是零,上述表達式仍為真。否則就得用

v && !(v & (v - 1))

符號擴展

對於 char, int 等內建類別,符號擴展是自動的。但假設你有一個有號二補數 x,只想耗費 b 位元儲存。甚者,假設你要把 x 轉成較大的 int。當 x 非負,只需要簡單的複製;但如果是負數,則負號需要擴展。例如若我們只用 4 位元儲存 −3,那麼 −3 在二進制中就是 1101。若我們有 8 位元,則 −3 在二進制中就是 11111101。在 4 位元表示中的最高位複製、填滿了目的地中多出來的、更高的 4 位。

固定寬度的符號擴展

在 C 中,固定寬度的符號擴展是平凡的,因為在 structunion 的定義當中可以指定位段 (bit field)。以下的程式把 5 位元的整數轉成 int

int x;  /* 只有最低 5 位有資料 */
int r;  /* 結果儲存在這裡 */
struct { signed int x: 5; } s;
r = s.x = x;

以下是 C++ 的模板函數,利用語言特性能以一次運算就把 b 位元的整數填滿類別 T

template <typename T, int b>
T signExtend (T x)
{
	struct { T x: b; } s;
	return s.x = x;
}

int result = signExtend <signed int, 5> (x);

變動寬度的符號擴展

有時候我們需要符號擴展,但事先不知道寬度;抑或我們用其他語言寫程式,沒有位段可用。

template <typename T>
T signExtend (T x, int b)
{
	T m = (T)1 << (b - 1);
	x &= ((T)1 << b) - 1;  // 若 x 的高位已為零可略過
	return (x ^ m) - m;
}

這需要四次運算,但當寬度是已知時,若高位已填零,則只需要二次運算。

還有另一個稍快,也不需要把高位填零,但不見得可移植的方法。

#include <climits>

template <typename T>
T signExtend (T x, int b)
{
	int m = sizeof(T) * CHAR_BIT - b;
	return (x << m) >> m;
}

移植性的問題在於 C 並未規定負數右移的結果,不過當代系統大多選擇實作算術移位。此外,若你對 limits.h 很不滿的話,可以試著寫 int m = -b,可能管用。

位元陣列

整數類別除了可以進行整數運算外,還可以當位元陣列使用。一個 n 位元的整數可以視為長度為 n 的位元陣列,其中的第 k 位就是陣列的 k 號單元。

雖然 C++ 中有 std::bitset 和 std::vector<bool>,但它們的實作仍仰賴整數。

依條件設定多個位元,不用分支

template <typename T>
T setBits (T word, T mask, bool flag)
{
	return flag ? word | mask : word & mask;
}

我們可以避免分支。但要特別注意一點,就是 flag 的類型必須是 bool,或者你要事先把所有真值轉成 1,因為我們利用了 -1 == ~0。

word ^ ((-flag ^ word) & mask)

而在超純量架構上,還有另一種算法。

(word & ~mask) | (-flag & mask)

依條件給出負值,不用分支

若你想在條件為真時拿到負值,這樣做可以避免分支。

(v ^ -fNegate) + fNegate

反之,若要在條件為假時拿到負值,就用這個。

(fDontNegate ^ (fDontNegate - 1)) * v

遮罩合併兩值

明顯的作法是

(a & ~mask) | (b & mask)

但是以下的作法可以節省一次運算。

a ^ ((a ^ b) & mask)

不過如果遮罩是常數,則兩者沒有差異。

漢明重量

漢明重量常簡稱為 popcount,是二進位整數中 1 的數量。

樸素方法

template <typename T>
int popcount (T v)
{
	int c;
	for (c = 0; v; v >>= 1)
		c += v & 1;
	return c;
}

這樸素方法每次迭代只走一位元,直到更高位的位元都為零為止。所以若輸入 1 << 31 則要迭代 32 次。

查表法

template <typename T>
int popcount (T v)
{
	static const unsigned char PopcountTable[256] =
	{
#		define B2(n) n,	 n+1,	 n+1,	 n+2
#		define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#		define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
		B6(0), B6(1), B6(1), B6(2)
	};

	unsigned char *p = reinterpret_cast<unsigned char*>(&v);
	int c = 0;

	// sizeof 在編譯期已知,編譯器能展開迴圈。
	for (int k = 0; k < sizeof(T); ++k)
		c += PopcountTable[p[k]];

	return c;
}

Brian Kernighan 計算漢明重量的方法

template <typename T>
int popcount (T v)
{
	int c;
	for (c = 0; v; ++c)
		v &= v - 1;
	return c;
}

跟樸素法相比。此方法只為已設立(為一)的位元迭代。

以 64 位元指令計算 14 位元的漢明重量

int popcount14 (unsigned int v)
{
	return (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
}

這要有 64 位元的 CPU 與快速的模除才會快,只要 3 次運算。如果要計算更多位元,可以利用位移與遮罩。

int popcount28 (unsigned long v)
{
	return popcount14(v & 0x3fff) + popcount14(v >> 14);
}

int popcount42 (unsigned long long v)
{
	return popcount28(v & 0xfffffff) + popcount14(v >> 28);
}

解說

popcount(v & 0x1111) == (v & 0x1111) % 0xf
popcount(v & 0x2222) == (v << 15 & 0x11110000UL) % 0xf
popcount(v & 0x4444) == (v << 30 & 0x111100000000ULL) % 0xf
popcount(v & 0x888) == (v << 45 & 0x111000000000000ULL) % 0xf

乍看之下好像可以求 15 位元,但別忘了除以 15 的餘數不可能是 15,所以 0x7fff 就杯具了。

平行計算漢明重量

對於 32, 64, 128 位元的整數類別 T,計算漢明重量的最佳作法如下。

#include <climits>

template <typename T>
int popcount (T v)
{
	v = v - ((v >> 1) & ~(T)0/3);
	v = (v & ~(T)0/5) + ((v >> 2) & ~(T)0/5);
	v = (v + (v >> 4)) & ~(T)0/17;
	return (T)(v * (~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT;
}

此法需要 12 次運算,與 32 位元的查表法相同,但使用較少的記憶體並避免了快取失效

解說

我們利用除法在編譯期就製造好需要的遮罩。

~0
全滿
...1111111111111111 = 0x...ffff
~0/3
偶數位為一,奇數位為零。
...0101010101010101 = 0x...5555
~0/5
4k 與 4k + 1 位為一,其他為零。
...0011001100110011 = 0x...3333
~0/17
8k 至 8k + 3 位為一,其他為零。
...0000111100001111 = 0x...0f0f
~0/255
8k 位為一,其他為零。
...0000000100000001 = 0x...0101

有興趣的人可以證明 8n 位元的 ~0 是 255 的倍數。對了,255 = 3 · 5 · 17。

奇偶性

本章所要探討的,是計算位元陣列的奇偶函數值。

樸素方法

template <typename T>
bool parity (T v)
{
	bool p = false;
	while (v)
	{
		p = !p;
		v &= v - 1;
	}
	return p;
}

這跟上述 Brian Kernighan 計算漢明重量的方法非常類似,並耗費相當的時間。

查表法

#include <stdint.h>  /* C99 */

int parity8 (uint8_t v)
{
	static const char ParityTable[256] =
	{
#		define P2(n) n, n^1, n^1, n
#		define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#		define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
		P6(0), P6(1), P6(1), P6(0)
	};
	return ParityTable[v];
}

int parity16 (uint_fast16_t v)
{
	return parity8(v ^ v >> 8);
}

int parity32 (uint_fast32_t v)
{
	return parity16(v ^ v >> 16);
}

int parity64 (uint_fast64_t v)
{
	return parity32(v ^ v >> 32);
}

利用 64 位元乘法與模除計算八位元組的奇偶性

((byte * 0x0101010101010101ULL & 0x8040201008040201ULL) % 0x1ff) & 1

這個方法只需要 4 次運算,但只對八位元組管用。

利用乘法計算奇偶性

template <typename T>
bool parity (T v)
{
	const T mask = ~(T)0/15;
	v ^= v >> 1;
	v ^= v >> 2;
	v = (v & mask) * mask;
	return (v >> sizeof(T) * CHAR_BIT - 4) & 1;
}

此法無論如何都運算 8 次。

平行計算奇偶性

(0x6996 >> ((byte ^ byte >> 4) & 0xf)) & 1

0x6996 以二進位表示為 0110 1001 1001 0110,是 4 位元的奇偶性表。

交換

沒錯,這章要談的就是大名鼎鼎的 swap。如果你有 C++ 可以用就別鬧了,快去用 std::swap

以 XOR 交換

a ^= b; b ^= a; a ^= b;

這個是不耗費額外空間進行交換的老哏了。注意 ab 不可指向同一變數,否則這個變數會變成 0。

一般來說,在現代的處理器架構上,多操作一個暫存器比這樣快多了。不過這個演算法擴展後有其他用途。

以 XOR 交換位元陣列的位元

以下的演算法可以交換連續的幾個位元。

template <typename T>
T swapBits (T v, int i, int j, int n)
{
	T x = ((v >> i) ^ (v >> j)) & ((T)1 << n) - 1;
	return v ^ ((x << i) | (x << j));
}

假設我們有 v = 001011112,要交換連續 n = 3 個位元,位於 i = 1 與 j = 5 的位置,則結果為 111000112

全文未完

給 nginx 和 php-fpm 的 AppArmor 設定檔

[同步刊載於 Github Pages.]

AppArmor 是 Ubuntu 預設的 MAC 模組。不像傳統 Unix 的 DAC,AppArmor 設定檔列出什麼是行程存取的。處於強制模式 (enforced) 的行程只能存取已列舉的路徑。處於抱怨模式 (complaining) 的行程存取未列舉的路徑會發出警告。

然而 nginxphp-fpm 沒有預設的設定檔。為了避免網頁伺服器遭駭造成系統性感染,自己的設定檔自己寫!我們有 aa-genprof 這個有用的工具完成大部份的工作,但是它還是會遺漏一些路徑,特別是 sockets。因此我把我的設定檔放上來作為他山之石。

以下是 nginx 的設定檔。

#include <tunables/global>

/usr/sbin/nginx {
    #include <abstractions/apache2-common>
    #include <abstractions/base>
    #include <abstractions/nis>

    capability dac_override,
    capability net_bind_service,
    capability setgid,
    capability setuid,

    /etc/nginx/** r,
    /etc/ssl/openssl.cnf r,
    /proc/*/auxv r,
    /run/nginx.pid rw,
    /run/nginx.pid.oldbin w,
    /run/php5-fpm.sock rw,
    /srv/www/** r,
    /usr/sbin/nginx mr,
    /var/log/nginx/* w,
}

以下是 php-fpm 的設定檔。

#include <tunables/global>

/usr/sbin/php5-fpm {
    #include <abstractions/base>
    #include <abstractions/nameservice>
    #include <abstractions/php5>

    capability kill,
    capability setgid,
    capability setuid,

    /etc/php5/** r,
    /proc/*/auxv r,
    /proc/sys/kernel/ngroups_max r,
    /run/mysqld/mysqld.sock rw,
    /run/php5-fpm.pid rw,
    /run/php5-fpm.sock w,
    /srv/www/** r,
    /srv/www/html/wp-content/** rw,
    /srv/www/html/wp-content/cache/** rwk,
    /srv/www/magento/media/** rw,
    /srv/www/magento/var/** rwk,
    /tmp/ r,
    /tmp/** rwk,
    /usr/sbin/php5-fpm mrix,
    /var/log/php5-fpm.log* w,
}