## Rotating Doughnut Using Matrix Multiplication

My copy of Escher’s artwork got some attention and quite some people asked me, “what kind of programmer are you?”, well, this Youtube video explains it well.

Actually, Joma’s video basically depicted me when in real dev mode. Upon watching this video, I couldn’t wait to re-implement it in Python. However, the initial version is basically a trans-coding of the original C code and was pretty hard to read. So here is a version that actually uses Matrix multiplication in Python (In the mean time, I still have to fix the syntax highlighter…):

``import time``import numpy as np``screen_size = 40``theta_spacing = 0.07``phi_spacing = 0.02``illumination = np.fromiter(".,-~:;=!*#\$@", dtype="<U1")``A = 1``B = 1``R1 = 1``R2 = 2``K2 = 5``K1 = screen_size * K2 * 3 / (8 * (R1 + R2))``def render_frame(A: float, B: float) -> np.ndarray:``"""``Returns a frame of the spinning 3D donut.``Based on the pseudocode from: https://www.a1k0n.net/2011/07/20/donut-math.html``"""``cos_A = np.cos(A)``sin_A = np.sin(A)``cos_B = np.cos(B)``sin_B = np.sin(B)``output = np.full((screen_size, screen_size), " ") # (40, 40)``zbuffer = np.zeros((screen_size, screen_size)) # (40, 40)``cos_phi = np.cos(phi := np.arange(0, 2 * np.pi, phi_spacing)) # (315,)``sin_phi = np.sin(phi) # (315,)``cos_theta = np.cos(theta := np.arange(0, 2 * np.pi, theta_spacing)) # (90,)``sin_theta = np.sin(theta) # (90,)``circle_x = R2 + R1 * cos_theta # (90,)``circle_y = R1 * sin_theta # (90,)``x = (np.outer(cos_B * cos_phi + sin_A * sin_B * sin_phi, circle_x) - circle_y * cos_A * sin_B).T # (90, 315)``y = (np.outer(sin_B * cos_phi - sin_A * cos_B * sin_phi, circle_x) + circle_y * cos_A * cos_B).T # (90, 315)``z = ((K2 + cos_A * np.outer(sin_phi, circle_x)) + circle_y * sin_A).T # (90, 315)``ooz = np.reciprocal(z) # Calculates 1/z``xp = (screen_size / 2 + K1 * ooz * x).astype(int) # (90, 315)``yp = (screen_size / 2 - K1 * ooz * y).astype(int) # (90, 315)``L1 = (((np.outer(cos_phi, cos_theta) * sin_B) - cos_A * np.outer(sin_phi, cos_theta)) - sin_A * sin_theta) # (315, 90)``L2 = cos_B * (cos_A * sin_theta - np.outer(sin_phi, cos_theta * sin_A)) # (315, 90)``L = np.around(((L1 + L2) * 8)).astype(int).T # (90, 315)``mask_L = L >= 0 # (90, 315)``chars = illumination[L] # (90, 315)``for i in range(90):``mask = mask_L[i] & (ooz[i] > zbuffer[xp[i], yp[i]]) # (315,)``zbuffer[xp[i], yp[i]] = np.where(mask, ooz[i], zbuffer[xp[i], yp[i]])``output[xp[i], yp[i]] = np.where(mask, chars[i], output[xp[i], yp[i]])``return output``def pprint(array: np.ndarray) -> None:``"""Pretty print the frame."""``print(*[" ".join(row) for row in array], sep="\n")``if __name__ == "__main__":``for _ in range(screen_size * screen_size):``A += theta_spacing``B += phi_spacing``# clear screen using ANSI control code``print("\x1b[H")``time.sleep(0.05)``pprint(render_frame(A, B))``

《形而上学》亚里士多德

# 2.1 埃及乘法

\$\$1a=a\$\$                                   （2.1）

\$\$(n+1)a=na+a\$\$                 （2.2）

```int multiply0(int n, int a){
if (n==1) return a;
return multiply0(n-1, a)+a;
}```

Ahmes所描述的算法，这个算法在古希腊被称为“埃及乘法”，而很多现代作者则称之为“俄罗斯农民算法”，建立在如下洞察上：

\$\$ 4a=((a+a)+a)+a=(a+a)+(a+a) \$\$

\$\$a+(b+c)=(a+b)+c \$\$

1        ♦         59
2                  118
4                  236
8        ♦        472
16                944
32      ♦      1888

\$\$41*59=(1*59)+(8*59)+(32*59)\$\$

\$\$n=n/2+n/2\$\$    说明n是偶数
\$\$n=(n-1)/2+(n-1)/2+1\$\$  说明n是奇数

odd(n) 意味着 half(n)=half(n-1)

```int multiply1(int n, int a){
if (n==1) return a;
int result=multiply1(half(n), a+a);
if (odd(n)) result=result +a;
return result;
}```

odd(x)很容易实现，测试x的最低位就可以了，half(x)则可以通过对x进行一次右移实现：

```bool odd(int n) { return n&0x1;}
int half(int n) { return n>>1; }```

multiply1需要进行多少次加法运算？每次调用这个函数，我们需要在a+a的地方进行一次加法，因为我们是不断对n取半，我们需要调用这个函数logn次。在某些时候，我们还需要在result+a的地方进行加法运算，因此加法运算的总次数为：

\$\$\#(n)=logn + v(n)-1\$\$

\$\$\#(15)=3+4-1=6\$\$

```int multiply_by_15(int a){
int b=(a+a)+a;    //b == 3*a
int c+b+b;        //c == 6*a
return (c+c)+b;   //12*a + 3*a
}```

# 2.2 改进算法

`r+na`

```int mult_acc0{int r, int n, int a) {
if (n==1) return r+a;
if (odd(n)){
return mult_acc0(r+a, half(n), a+a);
}else{
return mult_acc0(r, half(n), a+a);
}
}```

```int mult_acc1(int r, int n, int a) {
if (n==1) return r+a;
if (odd(n)) r=r+a;
return mult_acc1(r, half(n), a+a);
}```

• n=1的情况很少发生；
• 如果n是偶数，则完全没有必要判断它还是不是1.

```int mult_acc2(int r, int n, int a) {
if (odd(n)) {
r=r+a;
if (n==1) return r;
}
return mult_acc2(r, half(n), a+a);
}```

```int mult_acc3 (int r, int n, int a) {
if (odd(n)) {
r=r+a;
if (n==1) return r;
}
n=half(n);
a=a+a;
return mult_acc3(r,n,a);
}```

```int mult_acc4(int r, int n, int a) {
while (true) {
if (odd(n)) {
r=r+a;
if (n==1) return r;
}
n=half(n);
a=a+a;
}
}```

```int multiply2(int n, int a) {
if (n==1) return a;
return mult_acc4(a, n-1, a);
}```

```int multiply3(int n, int a) {
while (!odd(n)) {
a=a+a;
n=half(n);
}
if (n==1) return a;
return mult_acc4(a, n-1, a);
}```

```int multiply4(int n, int a) {
while (!odd(n)) {
a=a+a;
n=half(n);
}
if (n==1) return n;
return mult_acc4(a, half(n-1), a+a);
}```

# 2.3 本章的思考

## 通过截获gettext调用来修改WordPress的部分翻译

1. 创建一个child theme。
2. 在child theme的functions.php中加入如下代码：

[code language=”php”]
function change_attribute_line( \$translated_text, \$text, \$domain ) {
switch ( \$text ) {
\$translated_text = __( ‘低调地使用%s’);
break;
}
return \$translated_text;
}
[/code]

## Replacing WordPress translation by hooking to gettext

In a typical WordPress website, you see this line in the page footer:

This line links to WordPress website. The official Chinese translation of this line is:

“自豪地采用WordPress”

I’m using WordPress in several of my websites and I found it’s annoying: It’s a word to word translation and it’s simply not what we Chinese would say when we want to attribute something to someone. After some thinking, I think the appropriate translation should be:

“采用”emphasis the choosing of WordPress, “使用”emphasis the fact we are using WordPress right now.

The message is clear and typical Chinese: I’m a humble webmaster. All the glories go to WordPress.

So I set out to change the translation. It turned out to be rather complicated, but here’s how I finally accomplished it:

1. Create a child theme of your current theme, because you’ll have to rewrite its logic and you don’t want your effort to be overwritten by an upgrade of that theme. The procedure of creating a child theme can be found here.

[code language=”php”]
function change_attribute_line( \$translated_text, \$text, \$domain ) {
switch ( \$text ) {
\$translated_text = __( ‘低调地采用%s’);
break;
}
return \$translated_text;
}
[/code]

That’s it.

Notice that I search for \$text instead of \$translated_text. You can also search for \$translated_text. That would be:
[code language=”php”]
switch ( \$translated_text ) {
case ‘自豪地采用%s’ :
\$translated_text = __( ‘低调地使用%s’);
break;
}
return \$translated_text;
[/code]
I search for \$text because I assume (I’m not sure) search for non-unicode string will be faster.

It’s worth noting that both strings have placeholders in it. Initially I was trying to search the whole string, “Proudly powered by WordPress” or “自豪地采用WordPress” and failed. The fact that the above code works tells us, gettext() and its filters are called before the placeholders get replaced. I spent a lot of time figuring this out. It’s not mentioned in the document, nor did anyone post this on the web. This is actually the key reason why I write this post. Someone from WordPress should update the document.

## RSA illustration with not-so-small numbers – part 2

Let’s have a closer look at the encryption. During the communication, what’s been exposed are:

Alice’s public key (n=2627, e=13) , and the encrypted message.

For anyone who’s entered the world of modern cryptography from the old age, it’s tempting to try to decrypt the encrypted message using the encrypting key, the public key.

For these people, I have the below chart that shows the mapping between the plain text and the encrypted data:

x-axis is the plain-text data (sorted from 1 to 2627) and y-axis is the encrypted data(from 0 to 2626). I did the calculation using this line of script:

`~\$ for i in `seq 1 2627`; do echo "\$i^13 %2627" | bc; done > /tmp/encryption.mapping`

Below is part of this chart zoomed-in:

So you know the encrypted data, let’s say 2144, and you know the public key (n=2627, e=13). How do you find the number x such that x^13 % 2627 = 2144.

You cannot unless you compute everyone possible 1<x<2627 and then find the correct one. That’s brutal force. This is one of the basic assumption behind the security of RSA: There’s no efficient way to find x. This is called the discrete logarithm problem.

In real world scenarios, the 2 prime numbers will be so large that brutal force is simple impractical.

Then to decrypt the message, one would need the private key. The private key is the modular inverse of phi(n). However, in order to get phi(n), he has to know the factors that form n. And factoring large number is mathematically hard. That is the other assumption behind the security of RSA: There’s no efficient way to factor a large number.

As you will see in other places, these 2 assumptions are the corner stones of modern cryptography.

## RSA illustration with not-so-small numbers

Modern cryptography is difficult to understand without illustrations. One of the reason is, modern cryptography involves very large numbers that easily exceed the capacity of a standard calculator, let alone human comprehension. There are some illustrations out there using small numbers. The problem is, the numbers are too small to be convincing. So I’d like to try some no-so-small numbers here. Most of the necessary calculations can be done with GNU bc, so you can try yourself on just any GNU Linux distribution.

Let’s say Bob wants to send the below number to Alice (and make sure only Alice can decrypt the message):

520

Here’s what Alice will do first:

1. Pick up two distinct prime numbers. The numbers should be sufficiently large so that brutal force is difficult. Here we choose p=37 and q=71.
2. Calculating n=pq=37*71=2627.
3. Calculating the n‘s totient function: phi(n)=(p-1)*(q-1)=2520.
4. Pick a number e between 1 and phi(n) that is co-prime with phi(n). Here we choose 13.
5. Find number d so that e*d mod (phi(n)) =1. Here we choose 1357. This step cannot be done with bc. Intead, you can try this online calculator. Just put “modinv(13,2520)” in the text field and then press “go” you’ll get the result.

Now Alice has a public key (n=2627, e=13) and a private key (n=2627, d=1357). She can simply distribute her public key to everyone, including Bob.

Now for Bob to encrypt the message 520 to Alice, he has to encrypt the message using Alice’s public key:

`520^13 % 2627 = 2235`

Now Alice received this number 2235 from Bob. In order to decrypt this message, she do the following calculation(using her private key):

`2235^1357 % 2627 = 520`

Actually, here Bob can encrypt just any number that is less than or equal to n=2627 in this way.

Bob:

`1^13 % 2627 = 1`

Alice:

`1^1357 % 2627 = 1`

Bob:

`2^13 % 2627 = 311`

Alice:

`311^1357 % 2627 = 2`

Bob:

`3^13 % 2627 = 2361`

Alice:

`2361^1357 % 2627 = 3`

Bob:

`4^13 % 2627 = 2149`

Alice:

`2149^1357 % 2627=4`

Bob:

`137^13 % 2627 = 2431`

Alice:

`2431^1357 % 2627 = 137`

If his message is large, then he has to split his message into chunks that are smaller than n and encrypt them one by one.

Note that this only illustrates how Bob can send secrete messages to Alice. If Alice wants to send secrete messages to Bob then she has to have Bob do the same first:

1. Pick up 2 sufficiently large prime numbers;
2. Get the product of these 2 prime numbers – This is part of the keys;
3. Get the totient of this product;
4. Pick a number that is co-prime with this totient but smaller – This combined with the product is the public key;
5. Find the number that is the multiply modular inverse of this number – This combined with the product is the private key;

Then Bob sends his public key to Alice and Alice can encrypt the messages using Bob’s public key. Upon receiving the messages, Bob can decrypt the messages using his private key.

## An ugly implementation

Recently, I’ve been working on an CPropertySheet based application. It has multiple property page. Along with every property page, there’s a working thread behind the scene. I use a timer and a critical section kernel object to syncronize the working thread and the GUI update.

I tested the code with just one page, it works fine. But when I add the second page to the property sheet, the code ends up with an assert error on the SetTimer function call with the OnInitDialog funciton of the PropertySheet.

I was confused by this odd – it takes me a whole day to figure out what happened to the second property page. Finally I realized that the page would not be created till the user clicked the tab and activate the hiding page. So in OnInitDialog function, all propertypages’ m_hwnd is NULL – except for the first page, it has been activated automatically – that lead to the ASSERT error.

To solve this problem, I use a loop to activate the pages within the OnInitDialog function of propertysheet and then SetTimer. It works, but what an ugly implementation! If anyone has a neat approach, pls let me know.