Plurk.com is hiring

Are you good at Python programming? Are you a Javascript master?

As a developer of Plurk.com, here I want to say it loudly – We’re hiring!

For more details, please reference to:

Help Spark a Social Revolution – Plurk Opens Taiwan Office and is Hiring Worldwide!

And here are the list of jobs on inside jobboard:

Python/Javascript Ninja Extraordinaire

Mobile Engineer

Schmoozy Plurkinista/Plurkster & Community Evangelist

Plurk Business Development/Sales Manager

L33T Systems H@x0R, Optimizer & Log Lord

Plurk Product Manager, Chief Motivation Officer and Delegator

Posted in English Articles, Python | Tagged , , , , | 2 Comments

Zero-downtime service migration

When I am running my website, now.in, I did encounter a trouble.  That is, when there is a bug in the production server, then I need to restart them.  Sounds fine, right? Just to restart a server.  Yes, for most of web HTTP servers, they are stateless,  it is fine to restart them whenever you want, but not true for now.in, they are audio streaming servers.  Here s a server stats diagram shows the problem:

You can see there are some gaps in the plot, that’s caused by server restarting.  Of course, for users, that would definitely be bad experience.  Thus, I’m thinking how to solve this problem recently.  Before we go into the design, let’s look the reasons for restarting server first.

  • To deploy new version of program
  • To fix bugs
  • The process is using to much memory
  • To reload environment, ulimit -n for example (the limit count of file descriptor under unix-like environment)
  • To migrate from host A to host B

For simply employe new version of program, we can use reload function of Python to reload modules.  But there is some problems, reload function only rerun the module, those created instances are still there, it might work if the change is minor.  On the other hand,  reloading can’t solve memory usage problem, process environment change problem.  And here comes the final reason, to migrate service from host A to B.  Indeed, it is difficult not to make any down time for such migration, and there is little chance to do such migration, therefore, we’ll only focus on migration in same host.

The idea

The biggest challenge is, how to migrate those working connections?  My idea is simple, create a new process, and transfer those connection to the new process, and shut the old one down.  Following diagrams show my method.

The Master is a process which is charge for managing migration and receiving command from other process.  And the process A is for running service.

Before we perform the migration, the Manager startup process B, and wait it says it’s readly.

When process B said “Hey! I’m ready”, then manager tell process A to send the connection state descriptor to process B.  Process B receive the state, and take over the service.

Finally, process B took over the service, then master tells process A “You are fired.” and the process A rolls itself out.

That’s it, the service was migrated, and there is no down time.

The problem – socket transfer

The idea sounds good, right? But still, we have some technical problem to solve.  It is “How to transfer socket (file descriptor) from one process to another?”.  To solve this problem, I have some study, and eventually I know two methods to achieve the goal.

Child process

For most of unix-like OS, child processes inherit file descriptors from their parent.  Of course we can use this feature to migrate our service, but however, it got its limitation.  You can only transfer file descriptors to child process.

Sendmsg

Another way to achieve same goal is, to use sendmsg through a unix domain socket to send the file descriptors.  With sendmsg, you can transfer file descriptors to almost any processes you like, that’s much flexible.

A simple implementation

To simplify the example, we only implement process A and process B here, it is quite enough for two process to complete the migration.  Before we go into the details, there is another problem to solve, which is sendmsg is not a standard function in Python.  Fortunately, there is a third party library named sendmsg provides this function.  To install sendmsg, it is easy, just type

easy_install sendmsg

And here you are.  Okay, following are the two programs.

a.py

import os
import socket
import sendmsg
import struct

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind(('', 5566))
s.listen(1)
conn, addr = s.accept()
conn.send('Hello, process %d is servingn' % os.getpid())
print 'Accept inet connection', conn

us = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM)
us.bind(('mig.sock'))
us.listen(1)
uconn, addr = us.accept()
print 'Accept unix connection', uconn

payload = struct.pack('i', conn.fileno())
sendmsg.sendmsg(
    uconn.fileno(), '', 0, (socket.SOL_SOCKET, sendmsg.SCM_RIGHTS, payload))
print 'Sent socket', conn.fileno()
print 'Done.'

b.py

import os
import socket
import sendmsg
import struct

us = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM)
us.connect(('mig.sock'))
print 'Make unix connection', us

result = sendmsg.recvmsg(us.fileno())
identifier, flags, [(level, type, data)] = result
print identifier, flags, [(level, type, data)]
fd = struct.unpack('i', data)[0]
print 'Get fd', fd

conn = socket.fromfd(fd, socket.AF_INET, socket.SOCK_STREAM)
os.close(fd)
conn.send('Hello, process %d is servingn' % os.getpid())
raw_input()

The flow is simple, the a.py accept an inet socket and open an unix domain socket, wait b.py to take over the service.  And here we runs b.py, it connects to a.py, receives the fd of socket and takes over providing service.

The result

As the result shows, there is not down time between the service migration.

It is very useful to employ this technique in server programs.  You can even migrate service from Python server to a C/C++ server, or vice versa.  Also, to keep the memory usage low, you can also migrate the service to same program periodically.  I will try to employ this technique in my servers to achieve zero down time migration.  If you are interesting in this technique, have a try, it is fun and useful 🙂

Posted in English Articles, Python, Unix-Like, 分享 | Tagged , , , , | 1 Comment

無停機服務遷移

一直以來在營運now.in都有一個令人困擾的問題,就是每當伺服器更新或是出現問題時,就得關掉重開,雖然說大部份的伺服器我在設計上都做成重開也沒有關係,但有少部份一但重啟就會造成使用者斷線,參考下面這張伺服器狀態的圖

圖中被切斷的山峰都是伺服器重啟的時候,無疑的這對使用者來說是不好的體驗,對於一般網頁HTTP這類stateless的伺服器來說重啟是無所謂,但串流伺服器就不一樣,因此最近我在思考如何解決這樣的問題,首先想到的是伺服器重開的原因,不外乎有幾種

  • 部署新版的程式
  • 為了修正BUG
  • 記憶體用量過高
  • 重新讀取執行環境,例如ulimit -n,也就是檔案數量的限制大小
  • 從主機A移到主機B

以Python的伺服器來說,如果只是單單只是為了部署新版的程式,Python有個reload函數可以重讀整個module,因此可以設個管理用的後門用來重載模組,但是這樣做有個問題,就是已經產生的instance還是一樣,其實說穿了等於是重新執行那個module,如果只是簡單的改版還好,但複雜的改版就可能牽扯到太多因素難以透過這樣來更新,而除此之外,很多重開的因素像是記憶體用量過高,或著執行的環境參數改變,這些都無可避免的一定得建新的process,至於從A主機移到B主機,基本上是難以避免的一定得重啟伺服器,除非有某個前端的伺服器保持連線,後端的伺服器進行交移工作才有可能,而主機轉移的狀況其實很少出現,因此這篇文章要探討的是如何辦到同一臺機器內的服務轉移

方法

最大的問題就在於,連線中的socket該如保持住連線,最簡單的想法就是建立新的process,將目前的連線交給新的process,新的process接手完所有的連線開始運作後舊的process就能終止了,當然所謂的連線還包函了服務的狀態,我們在者裡稱之為 CSD (Connection State Descriptor),大致想法如下面圖片所示

首先Process A是正在運行的process,而Manager是負責控制遷移的process

此時Manager啟動了要負責接手的Process B

接著Manager通知A將連線狀態傳送給Process B,B接手後繼續提供服務,並且告知接收完成

在確定B能夠接手服務並且正確執行後,這時Manager就能將A中止,走到這裡服務就算是完整地移交了,中間沒有任何間斷

技術層面問題 – Socket的轉移

這樣的做法理論上看起來確實可行沒錯,但是最主要有技術上的問題得解決,就是如何將socket,或著是file descriptor轉移到另一個process,在我找過相關的資料後知道目前有兩個方法

child process

這個方法主要是因為child process在生成後會繼承parent process的file descriptor,但是缺點就是只限於child process,如果我們想將服務移交給另一個完整的獨立process這個方法就會行不通,因此使用上會有很多限制

sendmsg

另一個方法就是unix domain的socket有提供一個函數叫sendmsg,可以將file descriptor轉移到任何process,這樣一來實用性就比child process高很多,於是我決定採用此方法

簡易的實作

在這樣的轉移架構設計,Manager主要目的是要能夠對外有個統一個process能溝通,如果不需要的話其實兩個process就能達成服務轉移,為了實作簡單因此這個例子只用了兩個process進行轉移

還有另一個問題是Python標準函式庫裡沒有sendmsg,不過幸好有第三方函式庫已經準備好,就叫做sendmsg,安裝也很簡單,只要打

easy_install sendmsg

就可以了,接下來就是兩個範例程式

a.py:

import os
import socket
import sendmsg
import struct

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind(('', 5566))
s.listen(1)
conn, addr = s.accept()
conn.send('Hello, process %d is servingn' % os.getpid())
print 'Accept inet connection', conn

us = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM)
us.bind(('mig.sock'))
us.listen(1)
uconn, addr = us.accept()
print 'Accept unix connection', uconn

payload = struct.pack('i', conn.fileno())
sendmsg.sendmsg(
    uconn.fileno(), '', 0, (socket.SOL_SOCKET, sendmsg.SCM_RIGHTS, payload))
print 'Sent socket', conn.fileno()
print 'Done.'

b.py

import os
import socket
import sendmsg
import struct

us = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM)
us.connect(('mig.sock'))
print 'Make unix connection', us

result = sendmsg.recvmsg(us.fileno())
identifier, flags, [(level, type, data)] = result
print identifier, flags, [(level, type, data)]
fd = struct.unpack('i', data)[0]
print 'Get fd', fd

conn = socket.fromfd(fd, socket.AF_INET, socket.SOCK_STREAM)
os.close(fd)
conn.send('Hello, process %d is servingn' % os.getpid())
raw_input()

大致上的流程很簡單,首先a.py接收一個inet的連線,接著就開一個unix socket,等待b.py上線,然後把服務透過sendmsg轉移給b.py

執行結果

由執行結果我們可以看見,原本的連線是由process A提供的,然後轉交給process B,中間沒有任何中斷

有了這樣的技術基礎和想法,接著就剩下的是細節,基本上連線的狀態盡量以抽象的方式提供,如此一來任何程式只要能夠處理連線狀態就能夠接手,甚至可以由Python寫的伺服器轉移到由C/C++寫的伺服器,這些都可以辦到,中間服務都不會有間斷,而且也可以像HTTP伺服器一樣,處理到一定的量自動開新的process轉移給自己,如此一來可以保持低記憶體用量,有相當多的好處,未來我會試著將伺服器以這樣的想法改寫,應該就能做到無停機更新,有興趣的話也可以自己試試看

Posted in Python, 中文文章, 分享 | Tagged , , , , , , , | 7 Comments

Mr.DJ 2.0.3 Mac OS X版發佈

Mr.DJ 2.0.3 Mac OS X版正式發佈

截圖

Mr.DJ 2.0.3 Mac OS X版

下載頁面

Posted in Uncategorized, 中文文章 | Tagged , , , , | 3 Comments

無用 – 更改Linux SSH登入歡迎畫面為新世紀福音戰士裡的Nerv的logo

不要問我這有什麼用,只是純好玩,如果你的ssh沒有用utf8編碼的話可能會看到亂碼,以下是看起來的效果

做法

做法很簡單,修改/etc/motd檔即可,如果你想要這個Nerv logo,可以下載這個motd.txt然後解開後覆蓋原本的motd即可

Logo作者

Logo作者為ptt的cfi697,而原始版本因為字型寬度的問題我修正了一下

Posted in 中文文章, 無用 | Tagged , , , | 3 Comments

嘴砲談雲端 – 介紹用雲端除錯網頁的雲端技術: Browserling

有試著想開發支援所有主流瀏覽器的朋有們肯定都會遇過像我在 How hateful it is to develop a web application which runs correctly with different browsers? 所提到的情況,為了確定網頁在各種版本的瀏覽器,特別是那該死的IE系列都能正常顯示和執行,這樣的畫面出現是很平常的事

在這張圖中我分别用了兩個VirtualBox給IE7和IE6,如果連IE5要加進來右是另一個,只是IE5太古老雖然還是可能有人在用,但我已經懶得測了。

當然,安裝所有的瀏覽器是一個解決方法,包括使用VirtualBox之類的虛擬化技術來安裝萬惡的IE系列,但畢竟還是很麻煩,來自拉脫維亞 (老實說我也不知道這是什麼樣的地方 XD) 的Peteris Krumins,有趣的是Peteris他唸的是物理系,他和來自美國的James Halliday創作了一個基於雲端的解決方案,叫Browserling,裡面用的技術是之前我在 Open the browser, and here comes the computing power 所提到的,他們共同開發的技術,這個技術最有趣的地方是可以透過網頁來遠端操作電腦,雖然這不是什麼很創新的技術,但結合虛擬化的技術,將運算能力變成像流水一樣,網頁一開服務即到的型式,這就是它的潛力。

扯到雲端

在台灣一個很有趣的現像就是,當某種新東西很新奇、在未來會有不錯的應用,總會有一堆門外漢跟著朗朗上口地四處吹噓這些名詞,說穿了不過就只是趕流行,前陣子流行的是奈米,什麼都要冠上奈米,這樣做價格似乎就可以翻幾成,也有Web2.0之類的,甚至台灣還有人搶著推出Web3.0,說是要把網頁變成P2P的型式,當然是以失敗收場,而現在只不過是把流行的口號改成雲端而已,什麼都要冠上雲端,打開電視偶爾也會看見一些名嘴吹噓著雲端巴啦巴啦…,其實當發現一堆門外漢也在跟著人云亦云時就說明了這已經是在炒作了,哪天在路邊看見”雲端雞排”也請不要意外 XD

何謂雲端

每個人對雲端都有一套解釋,對我來說,雲端不外乎就只是將計算資源、資料儲存等等能力變成像自來水那樣,接上名為網際網路的大水管,打開電腦即可存取,這樣的概念其實早就有了,更早之前甚至有人提出更激進的想法,要將使用者這端完全只剩下客戶端的能力就夠了,剩的東西都由雲端的能力提供,但是也是沒有成功,或許是環境不夠成熟,而我個人認為使用者端的能力也是需要的,網路頻寬再怎麼進展,要即時所有東西都由遠端提供還是有困難的

台灣的現況

就台灣的環境來看,台灣軟體產業規模不足,人才都被硬體產業吸走,教育也以偏理論導向,實務部份相對很弱,網路頻寬也因為被隴斷更是奇貴無比,又位於地震帶上,不利於建資料中心,我只能說一個

但是就高階應用的層面還是有機會,純軟體服務產業最有趣的地方就是,它不需要什麼12吋晶元廠、上千萬上億元的設備,需要的只是人才、電腦、一條網路線,這樣就可以做到任何事情,電腦和網路在現在已經是隨手可得,剩下的就是人才,人才才是這樣產業裡最重要的資產,這說明了競爭是公平的,只要有能力就算只是幾個人躲在車庫裡一樣能在網路上打下一片江山

或許你會問,那像資料中心那類基礎建設怎麼辦? 其實這個問題本身就被雲端給解決了,因為雲端的概念就如我所說的,是透過網路來提供服務,你不需要自己建一個資料中心才能提供服務,你可以使用別人提供的基礎建設在上面提供更高價值的服務,一個好的例子像是Dropbox,它提供了雲端的儲存服務,只要安裝它的軟體,把檔案拖進料夾,剩的它會自動幫你傳到資料中心並且自動同步,它本身是透過Amazon S3的儲存服務來存放檔案,談到Dropbox,很有趣的是ASUS的電腦也有贈送類似的加值服務,叫ASUS WebStorage

近來,像這Amazon S3、EC2等等的基礎建設已經日漸成熟,所以現在要提供網路服務已經不像以前所有東西都得自己建置,自己買硬體、自己建資料中心,這些東西都將由雲端來提供,成本已經降很低,後繼者要做的就是要想出更高價值的高階整合應用服務並且用現有的這些基礎建設實作出來,可惜的這部份是台灣比較缺乏的能力

Browserling

久沒有寫文章就會想打一下嘴砲,扯遠了,這一是個標準的高階雲端運用 Browserling (http://browserling.com),它所要解決的問題就是上面所提到的,開發網頁時需要安裝各種瀏覽器來測試網頁,而這些都改由他們的雲端來提供,這是他們的介紹影片

他們提供了有限時間的免費使用,有興趣可以玩看看

雖然像這樣的服務其實還不太成熟,需求其實也有限,反應速度也有點差強人意,但是算是很有趣的應用,我個人覺得台灣的產業如果只是爭幾毛錢的硬體毛利,個人覺得不如多花一點心力在於這類高價值的應用服務,硬體有的摩爾定律,與其說是定律,不如說是詛咒,因為有了這條定律似乎不照著做就表示了硬體的極限到了,硬體再怎麼發展也會有物理上的限制,從近來的CPU設計就可以發現,都是朝多核心發展,連手機都有了雙核心的CPU,但其實多核心不代表效能就會立即提升,如果沒有軟體的配合是很難有顯著的改善,再者,有再強的運算能力硬體沒有軟體的功能事實上也沒有什麼用處

就像我所說的,這類的應用並不需要什麼上百億的投資,需要的就是創意 + 能力 + 執行力,像Browserling這樣的服務就只是兩個人合作之下的產品,台灣的開發者們可以多試著嘗試創造這類的服務,會失敗是必然的,但我想有了失敗的經驗,朝著這個方向走多少還是有機會成功

站在使用者的角度想

台灣常見的程式設計師都有個壞毛病,就是只顧著自己想怎樣使用軟體,想著要有強大的功能,但從來都沒有想過使用者到底會怎樣使用,台灣到處隨處可見糟糕到極點的可用性設計,看網頁的表單就知道了,一堆網頁不知道哪裡學來的風氣,總喜歡把一堆五四三的欄位加到會員註冊的表單裡,什麼已婚未婚、年收入多少,從來都沒想過使用者到底是怎樣的感覺,一個實際本身的體驗就是,最近一直收到中華電信的廣告簡訊騷擾,終於受不了想要停掉廣告簡訊,網路上找到的方法寫說要先註冊emome的會員才能取消,你一定想不到裡面有一個必填欄位是什麼,答案是

血型

我的媽呀… 中華電信你們非知道我的血型不可是要做什麼!? 難道我哪如果天貧血暈倒你們要提供緊急手機定位輸血服務嗎? 這就是台灣的現況,台灣或許有技術可以做到某個功能,但就使用者經驗這方面真的還是很糟糕,常常會聽到某些人說 XXX也可以做到那個,標準的想法就是只在乎可不可以做到,從來都沒想過做到這些所需要付出什麼

另一個沒有站在使用者角度思考的失敗實例

還有一個很好的例子就是之前提到跟人家趕流行的Web3.0,可以參考這篇 吳昇老師的Web 3.0為何很特別 或 吳昇老師的 web3.0,雖然它的概念挺有趣的,大意是說Web2.0大多東西傳到那些網站像是Youtube,結果使用者本身一無所有,內容都被服務提供者綁架,透過他們建置的系統,使用者可以將那些內容放在本地端以P2P的方式分享出去,剛出來時我就有說這東西100%不會成功,為什麼不會成功? 很簡單的從使用者的角度來想就知道了,身為使用者我會很在意這些內容是否在本機端嗎? 完全沒有,使用者最在意的只是好不好用,能不能達到我的需要,說使用者的資料被綁架只是被迫害妄想式的想法而已,將原本的系統換成P2P內容留在本機,使用者到底得到了什麼? 什麼都沒有,這就是標準的只用自己的想法思考事情,而不站在使用者角度想的後果,當時還在網路上跟人爭論過,還有人覺得要愛用國貨之類的,說真的,這樣做只會讓爛東西也能生存下去,就好像為了支持國片去看朱延平導的爛片一樣,只會讓他們更爛而已

Linux or Windows?

還有另一種常見的情況是覺得Linux比Windows好之類的想法,我得坦白說我自己也曾有類似的想法,我使用Windows也用Linux跑server,但站在使用者的角度想就會發現,要使用者學那些東西是不可能的事情,說穿了兩種是導向不同的東西,就vim來說它是人去學機器,很難學,但一但學會用起來會很有效率,而另一種可能是Word,這就是以機器來貼近人的例子,撇開要不要錢的問題,一般的使用者肯定是選Word而不是vim + latex之類的鬼東西來寫文件。

站在使用者的角度多想一分鐘,使用者會更喜歡你一些

對於使用者經驗的認知,我得說大部份技術出身的人很多都沒這樣的觀念,我自己以前也是這樣,身為開發者,站在使用者的角度多想一分鐘,使用者會更喜歡你或你的軟體一些

總結

其實本來一開始只是想簡單地解紹Browserling,不小心就嘴砲了一堆,以上只是個人的小小想法,參考看看就好,不過我真的挺希望可以看見台灣軟體產業有所發展,最近在發展自己網站的過程中學到不少東西,有空的話可能會嘴砲幾篇來分享一下我的心得

Posted in 中文文章, 作品, 嘴砲 | Tagged , , , , | 1 Comment

Logy – a central logging system for Python

I’m glad to announce my new open source project:Logy. Logy is a simple lightweight central logging system for Python. When do you need a central logging system?  Well, when you have many servers online, and they are running different python application, you will want to have a central logging system for making sure everything is going fine.  And you might ask, why not just use email for error reports? Well, following screenshot explains:

I use email as error logging report, but however, as you can see if there is something wrong with my servers in same time, network outage for instance, there will be so many error report mails come in my mailbox like crazy.  Therefore think a central log might be a good idea, then I decide to develop a simple central logging system for my own servers.  Here is a screenshot of the Logy web page.

It categorizes your logging records by IP address automatically, and also, you can set a application name for different applications which are running in same box.  And one important feature is, it is base on Flask 🙂

It is super easy to write records to Logy, here is an example:

import logging

import ex_loghandlers

rootLogger = logging.getLogger('')
rootLogger.setLevel(logging.DEBUG)

sream_handler = logging.StreamHandler()
# set up the http handler which writes records to Logy server
http_handler = ex_loghandlers.ExHTTPHandler(host='localhost:5000',
                                            url='/sink/TEST/myapp',
                                            method='POST')
rootLogger.addHandler(sream_handler)
rootLogger.addHandler(http_handler)

logger1 = logging.getLogger('myapp.area1')
logger2 = logging.getLogger('myapp.area2')

logger1.debug('Quick zephyrs blow, vexing daft Jim.')
logger1.info('How quickly daft jumping zebras vex.')
logger2.warning('Jail zesty vixen who grabbed pay from quack.')
logger2.error('The five boxing wizards jump quickly.')

try:
    raise Exception("Boom")
except:
    logger1.fatal("Huston, we've got a problem", exc_info=True)

logger1.info('Everything goes fine, now.')

You need to install my module named ex_loghandlers before you can run this script, it contains an ExHTTPHandler which provides extra information for Logy.

Here are some more information of Logy:

PyPi page: http://pypi.python.org/pypi/logy

Bitbucket: https://bitbucket.org/victorlin/logy/src

Posted in English Articles, 分享 | Tagged , , | 1 Comment

數學筆記: Euler’s theorem 練習前置證明

最近因為要讀密碼學相關的論文,會用到不少數論的東西,而我的個性是沒真正推導過的東西用起來總很不放心,而且我很笨,沒有平鋪直述的思路推導就很難理解,我討厭那種神來一筆,我記得以前在PTT上問過一個微積分的問題,我看到一個有三角函樹的式子被上下同乘某個三角函數得到另一個式子,我一直覺得很納悶,書上只這樣寫,我想知道的不是結果,而是思路,結果有個的同學就回答了”阿不就上下同乘X函數”,我差點沒暈倒,老兄,你不說我看書也知道是上下同乘那函數,結果對我來說只是一個點,但思路是一條路徑,沒有思路的話,數學式子對我來說也不過是幾個文字而已

雖然有些東西以前可能有想過是怎樣推導出來,但因為太少用所以很容易忘記,每次都重新想起,所以我決定將整個思路寫下來,這樣以後忘記時就不用重新看,所以主要只是給自己看的筆記,寫在紙上時間久了一樣會不見,所以想一想寫到部落格裡好了,順便練習用LaTeX編數學公式,可能會對某些人有幫助,但我突然腦殘想錯的機會不小,所以讀者請自重囉

今天要證的是,若m為質數,w為任一與m互質之整數,則

w^{m-1} \equiv 1 \pmod{m}

主要證明是參考

數論在密碼上的應用 (第 2 頁)

這雖然不是Euler定理,但我覺得對之後證明很有用,太少接觸所以先從簡單的開始

一開始由該網頁所提到的方式,拆開成多項式來看

(1+1+1+ \cdots +1)^m

接著就得先從多項式定理複習起

(a+b)^n

其實可以被視為是

(a+b)*(a+b)* \cdots *(a+b)

如果把每一個垂直列開來,就會發現其實

(a+b) \newline (a+b) \newline \centering \cdots \newline (a+b)

我們可以把這樣展開的式子,視為從上到下每行挑一個的連乘,因為要從2個選擇中挑n次,這樣所有的組合可能為

2^n

但是我們比較在意的是某些組合出現的次數,我們可能會想知道n個a出現幾次,也就是它的系數,而這要算出不同可能情況的系數又扯到了排列組合,複習一下排列組合的思路,如果我們有ABC三個東西要排列

ABC

最直觀的想法就是,先關注在ABC三個東西所佔的地方,直接先把它們當成位置來看

 \Box \Box \Box

先從最左邊的位置開始,此時我們手裡有ABC三種選擇,接著來到第二個位置,前面已經挑走了一個選擇,所以我們只剩兩個,接著最後一格,挑剩下的就只有一種選擇,所以可能的選擇有

3*2*1

種,也就是

3!

接著來考慮重覆的部份,先一樣當成都不同來看,可能性展開有這麼多6種

ABC \newline ACB \newline BAC \newline BCA \newline CAB \newline CBA

在此時,我們被告知B和C其實是同一種

  A\underline{BC} \newline  A\underline{CB} \newline  \underline{B}A\underline{C} \newline  \underline{BC}A \newline  \underline{C}A\underline{B} \newline  \underline{CB}A

把B和C都替換成X來看

  AXX \newline  AXX \newline  XAX \newline  XXA \newline  XAX \newline  XXA

我們會發現其實原本的可能性數量其實重覆了一次,所以應該除以二,而二這個數字其實就是B和C排列的可能性,由此我們可以知道,當N個東西任意排列,其可能情況是

  N!

而當我們被告知,這裡面其實有a個東西是一樣的,那麼我們就將重覆的情況除掉

  \frac {N!} {a!}

當我們又被告知,裡面有b個東西是一樣的,此時我們又可以去掉重覆的,得到的結果就是

  \frac {N!} {a!b!}

但是,理所當然的,裡面不一樣的東西數量加起來不可能會大於N,有了基本的排列公式複習,我們回到二項式定理

  (a+b)^k

利用我們剛才排列的公式,我們知道個個系數其實是

  \frac {k!} {k!} a^k+  \frac {k!} {(k-1)!1!} a^{k-1} b+  \frac {k!} {(k-2)!2!} a^{k-2} b^2+  \cdots

  \frac {k!} {(k-2)!2!} a^{k-2} b^2

來解釋的話,因為有k-2個相同的a和2個相同的b,所以k!要除掉相同的部份,有了這個部份我們可以回到先前把w拆成1來看的部份

  w^m=(1+1+1+ \cdots +1)^m

在這裡,我們把每個1都當做不一樣的數來看待,套用多項式公式我們會發現裡面有w項的

  1^m+1^m+1^m+ \cdots +1^m

每項都是1,加總起來是w,而剩下的部份,形式像這樣

  \frac {m!} {(m-1)!1!}1^{m-1}1+\frac {m!} {(m-2)!2!}1^{m-2}1^2+ \cdots

這些數全都因為包含m為因數可以被m整除,在此有個疑點就是,那為什麼分子就不可能把m給除掉,剩下的不會是m-1之類的嗎? 原因很簡單,因為m是質數記得嗎? 以這一項來看

  \frac {m!} {(m-2)!2!}1^{m-2}1^2+ \cdots

m!的很多項都會被消掉,像這個會被消成

  \frac {m(m-1)} {2!}

下面的2!會是(m-1)或m的因數,但是因為m是質數,除了它自己以外只有1是因數,因此不管下面放些什麼,m總會是這些項目的系數中的一部份,得到這結論後,我們就能將之前的式子兩邊同除m,這樣除了w以外的項目都會被整除,得到

  w^m \equiv w \pmod m

這時離我們目標不遠了,兩邊同除w

  w^{m-1} \equiv 1 \pmod m

就證出來了,最後有個疑問,就是w為什麼得和m互質,因為在倒數第二個式子,如果它們不互質,w一除m就會被變成其它的數

to read Haitian Creole translation of this web page (by Web Geek Science)

Posted in 中文文章, 數學筆記 | Tagged , | 3 Comments

Po translate – automatic translation tool for .PO files

It is kinda hateful to translate .PO files from Traditional-Chinese to Simplified-Chinese, most of the meanings are identical but different in simplified word or traditional word.  It is not a very difficult to translate.  But however, it is still an hateful job to do that manually.  For this reason, I wrote a tool which uses Google translate API to translate .PO files automatically.  It is quite easy to install

easy_install po_translate

It is also very easy to use, too.

po_translate input.po output.po zh-TW zh-CN

Of course, you can replace zh-TW and zh-CN to the source and destination language you like, e.g. English to Chinese, if the result is acceptable to you 🙂

Posted in English Articles, Python, 分享 | Tagged , , , , , , | 1 Comment

Po translate 自動化翻譯工具

之前有寫一個 PO檔自動繁簡轉換程式,但是因為沒有把它傳到PyPi上,所以要到處copy貼上很麻煩,為了方便使用,我把它打包並且傳到了PyPi,以MIT License開放源始碼,不過只是一個很簡單的程式而已,我想應該沒有多少人會想改些什麼,但是當然有人有興趣的話,歡迎修改

這個程式主要是用來解決繁體中文的.PO檔和簡體之間的互換問題,因為翻譯完繁體中文,基本上和簡體沒有太大差別,用Google translate轉成簡體就可以,但是手工作起來很煩,這種事情當然是交給程式執行

安裝方法很簡單

easy_install po_translate

使用也很簡單

po_translate input.po output.po zh-TW zh-CN

像這樣就能輕鬆的透過Google translate把繁中的.PO檔轉成簡中的

相關連結

PyPi的連結

Bitbucket的Repo

Posted in Python, 中文文章, 分享 | Tagged , , , , , , , , , , , , | 1 Comment