### 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

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:

*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)And my C# to C++ translators output:

{

if (b == 0)

{

return a;

}

else

{

return GCD(b, a % b);

}

}

UInt32 GCD(UInt32 a, UInt32 b)Much less verbose! And there are still some improvements I can make. Here is the x86 disassembly of the compiled translation:

{

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);

}

}

PUBLIC ?GCD@Program@Test1@@YAIII@ZSo 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.

; Function compile flags: /Ogty

; COMDAT ?GCD@Program@Test1@@YAIII@Z

_TEXT SEGMENT

_a$ = 8

_b$ = 12

?GCD@Program@Test1@@YAIII@Z PROC NEAR

; Line 48

mov ecx, DWORD PTR _b$[esp-4]

test ecx, ecx

; Line 52

mov eax, DWORD PTR _a$[esp-4]

$L15$1360:

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

$L27$1362:

; Line 57

ret 0

?GCD@Program@Test1@@YAIII@Z ENDP

_TEXT ENDS

Comments:

<< Home

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.

Post a Comment
<< Home