January 01, 2005

Euclid's algorithm

Today I worked on making the code generated by my translator a little less verbose. My strategy was to try and reconstruct the original C# expressions by analyzing the stack operations carried out by the IL assembly. This turned out to be quite straightforward. The main complication was aliasing. Unlike Java byte-code, MSIL byte-code permits variables to be aliased. I worked around this by only attempting to transform stack operations back into expressions between places where aliasing might occur.

For fun, I implemented Euclid's algorithm in C# and translated it to C++. Euclid's algorithm is one of the oldest formally described algorithms. It was originally described in "Elements" around 400BC, before the invention of algebra. Does that mean computer science predates mathematics? It was described in terms of geometric constructions. 2400 years later it is still in widespread use.

Anyway, this was my implementation:
static uint GCD(uint a, uint b)

if (b == 0)
return a;
return GCD(b, a % b);
And my C# to C++ translators output:

UInt32 GCD(UInt32 a, UInt32 b)

Int si0;
UInt32 CS_36_1_36_0000;
Int8 CS_36_4_36_0001;
CS_36_4_36_0001 = Int(Int(Int(b) == Int(0)) == Int(0));
if (Int(CS_36_4_36_0001)) goto L15;
CS_36_1_36_0000 = Int(a);
goto L27;
L15: si0 = ::Test1::Program::GCD((UInt32) Int(b),
(UInt32) Int(UInt(a) % UInt(b)));
CS_36_1_36_0000 = Int(si0);
goto L27;
L27: return Int(CS_36_1_36_0000);
Much less verbose! And there are still some improvements I can make. Here is the x86 disassembly of the compiled translation:

PUBLIC	?GCD@Program@Test1@@YAIII@Z

; Function compile flags: /Ogty
; COMDAT ?GCD@Program@Test1@@YAIII@Z
_a$ = 8
_b$ = 12
; Line 48
mov ecx, DWORD PTR _b$[esp-4]
test ecx, ecx
; Line 52
mov eax, DWORD PTR _a$[esp-4]
je SHORT $L27$1362
xor edx, edx
div ecx
mov DWORD PTR _b$[esp-4], edx
mov DWORD PTR _a$[esp-4], ecx
jmp ?GCD@Program@Test1@@YAIII@Z
; Line 57
ret 0
?GCD@Program@Test1@@YAIII@Z ENDP
So it seems that, by using C++ as an intermediate language, C# programs can be compiled into quite reasonable native code. Notice that the C++ compiler was able to apply the tail recursion optimization.

Euclid was actually a mathematician himself who amongst other things introduced the first proof of Pythagoras' theorem who lived a hundred of so years before. But then isn't computer science just a subset of mathematics anyway? I've always considered it to be.
Yes, I was joking. ;)
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?