Adventures with Computers
Archive for the ‘Math’ Category.
I have my exam in CPT tomorrow — Thomas and I have been practicing all day and it have really helped. So I now feel pretty confident that I know what I need to know about commitment schemes, zero-knowledge interactive proof systems and arguments, Σ-protocols, electronic voting, electronic cash, and secure multiparty computations. That was the six exam topics :-)
By the way, I believe Rune is still accepting bets in the Exam Game…
Browsing the access logs of my site is always fun — you never know what you’re gonna find! For example, it appears that people come to my site looking for information about the Microsoft formula (equation) editor.
How strange, for I haven’t been using this clumsy thing in at least 7 years! These days I wouldn’t consider using anything but [LaTeX][] which gives you vastly superious results when typesetting complex formulae.
The example on the right is taken from my old school paper on Mersenne Primes (in Danish), and it shows that if 2p − 1 is a prime, then p must be a prime too, for if p = rs then we have just seen that 2s − 1 divides 2p − 1! Before you ask or look in the source of this page… the inline math was done by hand using ordinary [XHTML][] entities and tags. No fancy [MathML][] markup here! It’s not that I don’t want to, I just haven’t looked that much at MathML yet.
With no less than 7,816,230 digits this is the largest explicit known prime. The Great Internet Mersenne Prime Search (GIMPS) announced today that the 42nd Mersenne prime has been found. Congratulations!
Ahh, there’s just a single day left until the Easter holidays start, and
I’m only having three hours tomorrow accourding to my schedule!
Not that I’ve been studying all that much the last couple of days… I sat
down yesterday and tried to make the Turing Machine that would take an
input tape with “aaaaaa#aaaaaaaaa” and turn it into “aaa“.
In other words: calculate the greatest common divisor of m and n
represented by the input a^m#a^n. In the above case, the greatest
common divisor of 6 and 9 is 3 if I’m not mistaken.
It turned out that Turing Machines are extremely annoying to program! Even the simplest operation gets enormously complicated. Somehow I managed to sit up all night trying to get things to work — I just kept tweeking and changing my program, hoping to catch that finaly special case that ruined the result. Amazingly I didn’t get that tired, it’s as if you reach a point and from then on you can carry on. But I still have a bad feeling that I’m going to get really tired soon…
I used a rather nice program called gturing to test my program, which you can find here. The comments are in Danish, sorry about that, but I used the program in a Danish hand-in exercise and when I rewrote things this morning I changed the English comments into Danish ones so that they would be easier to use in the report. I believe that the program now handles all correct input correctly. Correct input is input that matches the RegularExpression “a^m#a^n”.
The program also handles cases like “#“, “aaa#“, and
“#aaa“. With the first input the machine calculates gcd(0, 0) =
0, the two other inputs represent gcd(3, 0) = gcd(0, 3) = 3. The reason
why gcd(0, 0) = 0 is, that gcd(m, n) is defined as the unique
whole number d that satisfies
Div(d) = Div(m) intersect Div(n)
where Div(n) = { d in N | d divides n }. Here we have that Div(0) = N, that is, all natural numbers divide 0 — take a natural number and multiply it with 0 to see for your self. So we look for a number d that satisfies that Div(d) = N. The only number that has this property is 0 itself, so this means that gcd(0, 0) = 0.
I had my exam in Algebra yesterday, and it went fairly well. I could answer most of the questions, except the most difficult ones. I solved most of the questions in two and a half hour, but then got stuck in the last three subquestions. I just sat and starred at them for the remaining one and a half hour, but it didn’t help… It was quite annoying, and even more so when the exam finished, and I talked with Thomas Mølhave, Mikkel Krøigård and others from my class who had solved them :-/ As it is almost always the case with algebra, the solutions were fairly simple once you’ve seen them — they would fit into only a couple of lines for each subquestion.
So, I don’t really know what to expect of this exam, I guess my grade will be around 10 or perhaps 9 which is a very good grade, but still I feel that I should have been able to answer the last few questions too. The reason this bothers me is, that I can follow the arguments when someone presents them to me, but I’m having difficulities making the arguments myself. It’s not that I don’t understand the math or that I dislike working with this kind of math, it just that I don’t have the necessary routine to recognize the solution to the questions.
And now we’re getting close to the core of the problem: I don’t have the necessary routine because I haven’t spend enough time this semester solving the weekly algebra problems gives to us by our lecturer. All the way through school and high school (the Danish gymnasium) I’ve been able to get really good grades without having to work real hard, so I’ve continued that line at University of Aarhus, believing that I would somehow automatically do good… It’s a real shame if this doesn’t hold true :-)
But there’s nothing to do about all this now, I’ll have to look forward to the next exam, which will be in DAIMI:dPaSS.