Wednesday, February 28, 2007

We're going to China

My wife and I leaving for China in the very near future. We're both really excited, I've never been to the eastern hemisphere before and I'm looking forward to experiencing a different culture. The trip will also give Vanessa plenty of opportunities to practice her Chinese.

I'll have a vast array of experiences to share with you, gentle reader, upon our return. So for now I'll leave you with some half finished thoughts. I started no less than three blog posts over the past two weeks, but they are all sitting as unfinished drafts. Here's a brief summary of one of the things I started to talk about. (In the end it turned out to be not quite so brief.)

Cellular Automata
I've been looking into Cellular Automata recently as a source for complex data interactions. There has been some discussion among cryptographers about the use of cellular automata as possible pseudo random number generators. The best known example of a cellular automata is John Conway's Game of Life and I think it illustrates the kind of complex interactions which can occur within a cellular automaton, even though it is a "universe" with very few rules.

I started to look at the behaviors in Wolfram's rule 30 and rule 110 cellular automata because those have been selected as possible candidates for cryptographic systems. I wrote a program to evaluate patterns produced by these rules in a finite two dimensional field which wraps on both ends. I think I may have found other rules which may also prove promising for cryptographic use, but I need to do more evaluating. I'd ultimately like to use a three, four, or five dimensional system to see if I could build a useful PRNG but I will need to spend considerably more time ensuring that the patterns created by the rules remain complex. In the 2D system I evaluated, the vast majority of rules produces very predictable patterns.

See you when I get back.

Friday, February 02, 2007

Simulating Classes in C - Part 2

Well the $1 C contest has come to an end after generating lots of interest but no full blown solutions. I'm okay with that, thanks to all of you who expressed interest and started on it. From conversations with several of you over chat, I know that there were some great ideas out there. If you don't mind taking the time, please describe your idea in the comments section. As my friend Matt can attest, I love discussing software, ideas, designs, and just about anything related to creative problem solving. This is probably why I really enjoyed math in high school and college. I looked at each problem as a logic puzzle which could be solved multiple ways. Finding the most elegant solution made me feel like I had just written a poem of supreme beauty.

/* JSObject functions */
void InvokeObjectMethod(JSObject* object, char* methodName,
JSListOfObjects* inputParams,
JSListOfObjects* outputParams) {
int i;
JSClass* class_of_object;
int method_index = -1;

/* Impossible to invoke a method on a NULL pointer */
if(object == NULL) {
/* ToDo: send a "NULL object" error code in the outputParams. */
return;
}

class_of_object = (JSClass*)(object->type);

if(class_of_object == NULL) {
/* ToDo: send a "NULL class" error code in the outputParams. */
return;
}

/* Find the index of the methodName in the object's class. */
/* This part of the code is O(n) efficient, but this could be
improved if the function names were sorted or if a hash
algorithm was used. Hashing could reduce to O(1). */
/* I could also allow the calling code to specify the desired
method directly by index to avoid requiring a string
lookup for each invocation. */
for(i = 0; i <>method_count; i++) {
if(strcmp(class_of_object->method_names[i], methodName) == 0) {
method_index = i;
break;
}
}

/* If the method name was not found in the list of class methods,
return an error code. */
if(method_index == -1) {
/* ToDo: send a "method not found" error code in the
outputParams. */
return;
}

/* Invoke the method at the index corresponding to the method
name. */
(*(class_of_object->methods[method_index]))(object, inputParams,
outputParams);
}

I wrote my solution a few weeks ago, then started researching how other object oriented schemes are implemented. I found out that my code has several disadvantages and some significant advantages as well. For example, I started to comapre the likelyhood of missing the RAM cache to solutions in C++ and Java. There were a few other intersting comparisons but I won't go into all of the nitty gritty details. Overall, I'm very pleased because I learned a lot. Lets discuss!