Regarding Carmichael's function

Those familiar with number theory will remember that Euler's totient function, usually called phi, counts the number of inversible elements modulo m. So for example, since phi(p) = p-1, it means that with the exception of zero, all the elements of Z/pZ are inversible.

Furthermore, it is interesting to consider the multiplicative subgroup of Z/mZ --- those elements of Z/mZ that are inversible. A very important question is whether this group is cyclic, which if true would mean there is an element g the powers of which generate the whole group.

Now, Fermat's little theorem states that if p is prime and a is not zero, a^{p-1} = 1 mod p. In other words, no matter the a, raising it to the power of p - 1 gives 1. It is interesting to consider, however, the minimum possible exponent e > 0 for a given value of a which causes a^e = 1 mod p.

This value changes with a. For example, 1^1 = 1, but -1^2 = 1. Euler's phi function also gives further information: when working in Z/mZ, any such value of e, which we will call the order or the exponent of a, has to divide phi(m).

But "has to divide" does not necessarily mean "equal to". For instance, it is known that Z/pZ is cyclic: there is at least one value mod p such that its order is exactly p -1. But what about other Z/mZ rings?

Enter Carmichael's lambda function, which you can read about in Wikipedia. The interesting results are that lambda(m) divides phi(m), and that because of its method of calculation it will happen that lambda(m) will be much less than phi(m) the smoother the integer m is.

Now let's review an interesting example. If we had m = pq, the product of two different odd primes, then phi(m) = (p-1)(q-1). However, lambda(m) = (p-1) lcm (q-1), and since p and q are odd, then we have that lambda(m) <= phi(m) / 2. What does this mean? That Z/mZ is not cyclic.

But why is this? Because the maximum order in Z/mZ is, at most, half the number of inversible elements in that group. Therefore, any element with maximum order will only be able to generate half of the whole group, and therefore the group is periodic but not cyclic.

Furthermore, phi(m) and lambda(m) differ when it comes to factors of 2. For example, phi(2^k) = 2^{k-1}. But, if k > 2, lambda(2^k) = 2^{k-2}. Again, this means that when k > 2, Z/2^kZ is not cyclic due to the same argument shown above.

To show what a difference it makes, let's review one of my favorite values of m, 240. The value of phi(240) is 64, so there are 64 inversible elements modulo 240. However, despite that, lambda(240) = 4. Therefore, no inversible element modulo 240 is capable of generating more than 4 elements of the multiplicative subgroup. This can be generalized.

Theorem: the multiplicative subgroup of Z/mZ, (Z/mZ)*, is cyclic if and only if phi(m) = lambda(m).

Proof: we already know that lambda(m) divides phi(m), so we must have phi(m) >= lambda(m). First: if (Z/mZ)* is cyclic, then there is an element g such that its powers generate (Z/mZ)*. Clearly, there must be phi(m) different powers of g, and therefore its order is phi(m). Since lambda(m) is the minimum exponent such that every element in (Z/mZ)* becomes 1 when raised to powers, it follows that lambda(m) = phi(m). Conversely, assume that (Z/mZ)* is not cyclic and that nevertheless phi(m) = lambda(m). This would mean there is at least one g with the property of being a generator, against the hypothesis of (Z/mZ)* not being cyclic.

Now in reverse. If phi(m) > lambda(m), it means no generator can generate the whole group, and therefore we clearly have that (Z/mZ)* is not cyclic. If phi(m) = lambda(m), then there is at least one g in the (Z/mZ)* the powers of which generate the whole group because its order is phi(m), the amount of elements in the subgroup. This completes the proof.

Question about SUnit

Has anybody ever found the resumable varieties of assert: and deny: useful?

Assessments progress

I just finished writing the first implementation of prerequisites for Assessments, which are the equivalent of test resources in SUnit. Things are looking much better now. Something I like is that the amount of code is being kept under control. Also, by carefully designing the network of collaborating objects, what has to be done at each execution context is quite obvious and thus can be expressed in very simple terms.

So now comes that first light moment. I have to write the tests for Assessments in Assessments.

That happy feeling

Something I really enjoyed in my past life as an inhabitant of a trading floor was to interact with the users of the software I was working on. This would invariably lead to customizations, improvements and fixes directly related to the daily experience of people working next to me. I tried very hard to make them happy, and when I could do that it felt great.

And now I am seeing similar things in my current life. For example, I wrote the Hash Analysis Tool to check on the quality of hash functions, and I am hearing good things from customers. Even better: Holger Kleinsorgen wrote additional user interfaces to the Hash Analysis Tool and published them to the public repository. I just merged his work into the main branch, and did some refactoring of what I had done before so the new functionality integrates better. So now, thanks to Holger, we have the capability to quickly compare any number of hash functions against a single data set much more easily than before.

I am also working on a manual for the Hash Analysis Tool with Holger. Hopefully we will be done with it soon so it can be published.

More of the same, please!

The Chinese food place in Manhattan

So for whatever reason Hop Won came up again. It's a chinese food place in midtown Manhattan, conveniently located a few blocks from where I used to work.

It works like this. You go in, you skip the premade stuff and go directly to the cashiers. You ask for something made from scratch. And even when they are busy during lunch, with two simultaneous lines and as many as 30 orders in flight, you will be given your food to eat there or to go within 10 minutes and quite often in much less than 5.

The thing with Hop Won is that although it's cheap, the food is excellent and judged to be authentic by people who have been to, or are originally from, China. Servings are generous as well, so you can eat quite well for about $5.

So what should you get? Think of this: it's January, it's very cold, there's snow and ice everywhere. What do you ask for? Soup, for example. And indeed, for $5 you could get a huge bowl of soup complete with noodles, vegetables of various kinds, two dumplings, and your choice of meat the serving of which is quite generous as well. No more feeling cold for you.

Or you could get the food to go. Something I really enjoyed bringing to the office was a so-called wet stir fry of rice noodles, vegetables and beef. It's called wet because once the stir fry is done, they add gravy to it. They put it in the food container right from the wok, so even after the walk back and the elevator ride, it's still boiling hot by the time you can begin to eat.

Other delicious items for less than $6? Singapore style rice noodles, complete with shrimp, beef, pork and whatever else you can think of. Most of their specials, made to order of course, were under $6 as well. They are quite willing to make stuff outside the menu too --- and it's given to you just as quickly as anything else. If they were a chain, they'd make fast food places seem as slow as a block of tar oozing at the North pole.

So... are you hungry yet? The address is 139B East 45th Street in Manhattan, NY. Or, amazingly, just search for Hop Won in Google and you'll see. Also, there are a couple photos here. When they say "express", as in the front sign, they are not kidding.

Regarding Assessments

Last night I spent some time working on Assessments, the SUnit rewritten from scratch. Although there is some design work still to be done, the first light is getting close.

Something I've noticed is that implementing something like SUnit from scratch is not even nearly as easy as it seems. Although I feel that Assessments is simpler and better factored than SUnit (your subjective mileage may vary), Kent Beck's assertion that it should be possible to write it in a train ride does not appear to hold in this case.

What I find noteworthy about this is that Assessments is based on experience gained with the following previously existing projects:

• SUnit itself,
• SUnitVM (the refactored SUnit I wrote),
• SUnit Based Validation,
• SUnit Benchmarks, and
  
• the Hash Analysis Tool (a dedicated tool to test hash functions).

And so, while I thought Assessments would be a piece of cake given all that I had learned from the items above, I find that it is anything but.

The task list still has the following items.

• The test resource feature has to be redesigned and reimplemented.
• There should be an Assessments test runner.
• A way to dump results in a log file should be provided.
• The tests for Assessments should be written in itself.

And now, on to other things.

Fun with Python

So I spent some time with a friend and the Hash Analysis Tool today. In Python,

• 'osmosed' hash = 'wicking' hash

and because of that,

• 'osmosed1' hash = 'wicking1' hash

That's all very nice. However, the following two are equal

• frozenset('osmosed', 'wicking') hash
• frozenset('osmosed1', 'wicking1') hash

And it turns out that if a frozen set has elements the hashes of which are the same, and the count of elements in the frozen set is even, then the hashes of the frozen sets are equal regardless of the contents.

Fun stuff!

Exciting work environment

Now this is a place where I would like to work at...

... NOT!!!

Personal stories

As I grow older, I become aware of patterns I didn't notice before. One that has recently emerged clearly is the one about the stories of people's lives. What is peculiar about this?

It is difficult to see it when you are younger because you lack enough life experience to see it first hand and then see it in others. So it's one of those that just take time. Once you become aware of it though, it causes radical change to occur. The key observation to make is that you do not have to live your life the way you do.

At the risk of being repetitive, perhaps some paraphrasing is a good idea. Here are some restatements. Nothing and nobody can force you to live with any particular style. You are the only one responsible for the way you behave. You are free.

Now, this may seem like obvious, right? But tell me now: how many times have you heard people complaining about their lives, as if they were powerless to change things, when you know quite well all is needed is a dose of will?

So I think about people I hold dear and how they live their lives. Sometimes I almost violently disagree with how they are running their show. On one hand I know it is not up to me to go assist people who do not want help, because it is useless. I also know that it is not up to me to go assist everybody even if they do want help, because sometimes it is a bad thing to do somebody else's homework. It seems completely fair to me. I have my own life to take care of.

And yet, it is also sad to predict bad things for them, and see the predictions were more or less correct. Because after all, disagreement or not, I care.

That is the sad pattern I've come to see. In a few cases the prediction even says that, almost certainly, change is impossible for them. I wish it wasn't so for the people I think about, and yet there is nothing for me to do.

Then comes the reflection on it. A human life devoted to things that should not have been, to things that became a complete waste of time and energy, to things that sometimes the people involved knew quite well to be counterproductive. Sad, very very sad personal stories... both of the few I care about, as well as of every one of us I imagine.

Nevertheless, there is a positive side to all of this. It is the realization that you own what you do, that even in the face of great disaster you can just do what you have to do the best you can with a steady hand, that you can become free from what used to literally control you. It is available to us right now, all the time. We just have to do it.

Dare to become more than an automaton today.

Side comment about optimization

I just finished some further experiments with method lookup.

When nothing is cached, spending a bit more memory on the image results in what upon first examination looks like ~70% faster benchmark execution due to more efficient method lookup.

This is on top of the improvements I had obtained before.

Some cleanup is needed on the image side at this point, but basically it's just refactoring all the direct references to MethodDictionary into indirect references to a single direct reference. When this is done, then the actual method dictionary class can change over time.

Note that while this is indeed about messing with method dictionaries so that new strategies can be used, the new VM is quite happy about running old images.

Hopefully these speedups will hold after all is said and done. I found it extremely difficult to test the performance of Windows programs because depending on things such as whether there is a network cable attached to your computer or not, performance can swing by amounts like 20% particularly if you measure different invocations of the same VM. Therefore, the numbers above represent the result of doing the following.

1. Start up an image with no changes applied using the new VM marked as uniprocessor.
2. Measure the test case (multiple runs, take best time).
3. Perform the conversion of the image (a do-it expression).
4. Measure the test case again (multiple runs, take best time).

This is the most stable measurement procedure I could think of. This ensures exactly the same OS process runs exactly the same benchmark on exactly the same image on exactly the same memory code locations.

But in case you are wondering, the answer is yes. This is about changing how method lookup is performed. This is also about making the change on a live system. No image tracing is needed, and the conversion do-it expression takes less than one second.

Ah, my little friend... something like Smalltalk, or nothing.