& Homework Solution

This problem is actually very straightforward, and does not require much cunning to solve. By definition, raising a number to a power is the same as multiplying the number by itself repeatedly (e.g. a^3 = a*a*a). However, polynomial expansion, a 7th grade math principle, yields a trick that can be used to compute the partial result of each multiplication (az % x) without ever computing the entire result of the exponent (a^b). A rudimentary proof of the trick:

az % x

Decompose a and z into portions which are multiples of x and portions which aren't: a = xm + n, z = xo + p
= (xm + n)(xo + p) % x

Polynomial expansion
= (x^2*mo + xmp + xno + np) % x

(y + z) % x = y % x + z % x. We have to add another % x at the end because it's possible that the sum of the remainders exceeds x.
= ((x^2*mo + xmp + xno) % x + np % x) % x

Extract common multiple
= (x(xmo + mp + no) % x + np % x) % x

xy % x = 0 by definition
= (np % x) % x

Two modulus in series are redundant
= np % x

As the result of each multiplication/modulus will always be less than x (which must fit in a word), there is no need for big numbers or for many multiplications for each step (for comparison, the most straightforward method of multiplying big numbers requires n^2 primitive multiplications, where n is the number of digits in the big numbers). Thus this algorithm is O(power) in the worst case.

This process can be further optimized by noting that a^b % x = (a^(b/c) % x)^c when b is a multiple of c. Thus divide and conquer can be used with recursion to eliminate duplicate work in the case where the exponent is a multiple of c. With this optimization, the algorithm becomes OMEGA(log power) in the best case; the example I gave in the original post was a best case scenario where the exponent was a power of two, and required only 62 multiplications and 62 divisions to solve.

Another problem in the same homework is proving much more difficult, however: write an algorithm using divide and conquer to, given an unsorted array of values, determine whether there is a single value that appears more than half as many times as the number of elements in the array; the algorithm must be generalizable such that you can only compare elements for equality - you can't tell if one element is greater or less than another (which rules out sorting and creating any kind of data structure to count them). Those multiple constraints, taken together, are really brutal for resisting solutions. I've figured out a fact of the problem that I think will be important in solving this (a condition that, if false, guarantees that such a value doesn't exist; however, if the condition is true, it's still possible a majority value doesn't exist), but I haven't quite figured out how to solve it, yet.

& Homework Fun

Got this question on a homework assignment in algorithms class, and thought it was pretty cool (or rather, the solution is pretty cool): develop an algorithm to calculate x^pow % mod, which does not use big numbers (numbers that take more than one processor word to store, and more than one processor math operation for each calculation).

Random fact: 1928374655647382910^9223372036854775808 % 4123456789 = 3021338089

In other news, posts about generally cool things will now be tagged 'squishy', rather than the previously used 'shiny'.

Logitech: At It Again

So I just spent an enjoyable period attempting to contact Logitech customer support through their Email Us link in their support site. Shortly after sending the first one, I felt inclined to send this one:

I take it you people don't like getting support requests, and do as much as you can to discourage them. There's a rather gaping bug with your support site, where it will say invalid e-mail address/password on attempt to login, tell you that the e-mail address is not in the database when you attempt to get your password sent to you, then tell you that the e-mail address is already in the database when you try to create a new account using that e-mail address. This occurred with both my primary address and backup address. I wasn't able to manage to register until I tried this one, which isn't even mine.

As you can see, this has nothing to do with the mouse I entered (that was a different support request from a few minutes ago). I just thought you might want to know that your web site makes people want to hurt you physically, and I needed to enter product info to contact you at all.

I thought I wrote about Logitech's technical incompetence a year or so back, as well, but I guess not. Maybe that was on my todo list...

Public Service Announcement

Microsoft Office 2007 Ultimate for $60 through MS special to students in eligible countries (US, CA, UK, FR, IT, SP). That's 91% off retail (not that anyone would pay that).

Buy here
Verify offer is legit here

We now return you to your regularly scheduled doldrums.

I Like It! I'll Take It!

So, I've been reading my new book, Introduction to Typology: The Unity and Diversity of Language. I've just encountered something I like a lot, and plan to use it in Caia. Let me attempt to give a very brief amount of background and explanation.

Not all languages have tense. And some languages on both sides have something called aspect. Aspect indicates some facet of time about a verb in ways that are more complicated than tense. For example, some languages conjugate the same verb (without a helper verb, which English uses) differently depending on whether the subject is starting to do something (e.g. "began to eat"), finishing something (e.g. "finished eating"), etc.

One very common class of aspect (although usually this aspect in intrinsic to the verb, and does not have multiple conjugations for the same verb) is the distinction between state, achievement, activity, and accomplishment. The state aspect indicates that the subject is maintaining some preexisting state. The achievement aspect indicates a change in state. The activity aspect indicates some act that is self-contained and does not include a change in state. Finally, the accomplishment aspect indicates that the subject has caused an action with regard to some other object.

Some examples in English, using the verb 'break' (note that English cannot perfectly distinguish these four aspects for individual verbs, so try not to get confused by the ambiguity). The state aspect: "the window is broken" (this is a little ambiguous; specifically what that says is that the window was broken before the present time, and continues to be broken). The achievement aspect: "the window broke" (also "the window was broken", but that could also indicate the state aspect). The activity aspect: "I ran to the window". The accomplishment aspect: "the ball broke the window".

As this very elegantly accounts for the active and passive voices, as well as both transitive and intransitive verbs, I'm gonna definitely use those as some of the mandatory aspects of Caia (some aspects - the most useful and common ones - and possibly tense are included in the basic conjugation of the verb, while other aspects are formed, as in English, either through phrases or extra words such as adverbs). Though I may combine the achievement and activity aspects, as I'm hard-pressed to find a verb for which activity and achievement are not mutually exclusive (note how 'break', by its very definition, could not display the activity aspect, so I had to use a different verb). And for anyone who's curious: the jury is still out on whether Caia will use tense.

Sprachbund - UPDATED

So, I'm attempting to evade work (again), and was struck by another random thought. I mentioned previously that Japanese and Korean adjectives are really intransitive verbs, which use relative clause structure to act as adjectives. I also mentioned that this seemed to be an integral part of Korean (e.g. the suffixes for adjectives and verbs are the same), while there's some evidence to the contrary in Japanese - adjectives have different suffixes, all but one of which have the form -k_, leaving the possibility that Japanese adjectives were true uninflected adjectives at one point, and had some suffix beginning in k affixed to them.

Well, there's a linguistic principle known as sprachbund. That's German for "binding of languages" ('sprach' is the Old English word for 'speak', and is still used in German). This is the principle that, when you have two or more languages in contact for a large period of time (and, especially, when there is a high degree of multilingualism in the population), the syntax (word order) of unrelated languages will come into sync. Other things also happen, such as word borrowing and language mutation, but those are beside the point.

What if, at some point in the past, Japanese and Korean (for the purpose of this hypothesis, we'll assume the languages are unrelated; the relation of the two - or lack thereof - is still in dispute, so this is not a radical assumption) populations mixed extensively. It's possible that Japanese acquired the Korean syntax of adjectives, transforming Japanese adjectives into intransitive verbs.

If this were the case, it's possible Japanese acquired other aspects of Korean, as well. For example, I saw in one book from the early 1900s that you could use the '[subject] [verb]' form in Japanese as well as the modern forms '[topic] wa [verb]' and '[subject] ga [verb]' ('wa' and 'ga' mark the topic and subject, respectively; at least in these forms, they do) at one point in the past, whereas in current books you only see the 'wa'/'ga' forms. It's interesting to wonder if Japanese might have picked up the topic and/or subject particles from Korean; especially so considering that 'ga' originally meant something completely different, and has been crudely repurposed into the subject particle, in a downright bizarre manner. Though you should take that idea with a grain of salt, as I haven't researched that possibility at all, and don't even have the original book I read about that in anymore (returned it to the library).

In other news, I just lost contact with my computer at work (more than a thousand miles away, on a holiday weekend). I guess that means work's done for this weekend.

UPDATE: Okay, got a reply from a Japanese-speaking classmate (naturally, as I do most of my blogging on a whim, I didn't wait for a reply to the e-mail I sent before posting :P ). He says that the "[subject] [verb]" form is still used in informal speech. So that probably rules out my second item of speculation. I'm still interested in whether there is any truth to my Korean adjectives hypothesis, though.