Lagrange polynomial solver

lagrange polynomial solver
Attempts to fit a lagrange polynomial through the give data points using the matrix solver library, which has also been updated to be cleaner and better. Output is in a form that is easily copy and pasted into various mathematical packages for plotting.

Features

• Small
  
• Works :D
  
• Portable to almost everything under the Sun
• Outputs in a format that can be easily pasted into mathpad or matlab for plotting
  

Download

• lagrangeSolver.zip[src]

matrix solver update

• matrix solver
  Update 7/5/2005 solves for parametric matrices. Update 4/5/2005 - proper detection of the nature of solutions, code clean up, as well as fixing the infinite loop that occurs for certain matrices. A simple program I wrote after learning about matrixes. It performs Guassian elimination on a given matrix, then uses what I considered a very elegant loop to perform back subtitution to solve the system of equations where a solution exists.
  
  Features
  
  • Command line based
  • Detects unique, parametric solutions, as well as no solutions
  • Prints unique and parametric solutions
    
  • Works! :)
  • Will print out working
  • Small
    
  
  Download
  
  • matrixSolver.zip [src]

Example:

solaris:~/code/matrixSolver steve$ ./matrixSolver 3 1 0 -2 1 3 1 -6 1 0 0 0 0
Solving below matrix
0 [ 1.000 0.000 -2.000 1.000 ]
1 [ 3.000 1.000 -6.000 1.000 ]
2 [ 0.000 0.000 0.000 0.000 ]

0 [ 1.000 0.000 -2.000 1.000 ]
1 [ 0.000 1.000 0.000 -2.000 ]
2 [ 0.000 0.000 0.000 0.000 ]

matrix has parametric solution:
unknown0: 1 + 2 * s0
unknown1: -2
unknown2: s0

Cheers,
Steve

Self charging behaviour of electrolyte capacitors

During my physics lab this afternoon, I found that discharged electrolyte capacitors re-charges to a percentage of its original voltage when left alone as open circuit. I was informed this effect is called dielectric relaxation by one of the tutors, but no explanation was forth coming.

So I did some research and here is what I have found:

"A capacitor exhibiting dielectric absorption acts as if during its long precharge time the dielectric material has soaked up some charge that remains in the dielectric during the brief discharge period. This charge then bleeds back out of the dielectric during the relaxation period and causes a voltage to appear at the capacitor terminals. Fig 2 depicts a simple model of this capacitor: When 10V is applied for 1 min, the 0.006-µF capacitor gets almost completely charged, but during a 6-sec discharge period it only partially discharges. Then, over the next minute, the charge flows back out of the 0.006-µF and charges the 1-µF capacitor to a couple of dozen millivolts." [http://www.national.com/rap/Application/
0,1570,28,00.html]

"An electrolytic capacitors is, amongst other things, an electrochemical
cell, and as such can store energy as polarization of the electrolyte/electrodes, and as chemical change. Discharging the surface charge briefly does not release this stored energy, which will subsequently give rise to a terminal voltage as the cell settles back to equilibrium. " [http://www.du.edu/~jcalvert/phys/caps.htm#Diel]

The following are posts to sci.physics newsgroup thread regarding the same topic:

"The way I remember it was that the capacitors had TWO "neutral" states: electrically neutral and mechanically neutral.

Upon discharge the capacitor plates were electrically neutral, but as they mechanically relaxed the diaelectric became polarized and thus produced a charge difference on the plates."

"The situation in electrolytics is complicated by the active nature of the electrolyte, i suspect. If this is correct, an initial zero volt indication merely means that the charge closest to the electrofes has been bled off. If investigating, leaving a milliameter (other wise known as a "calibrated short sircuit... 8)>>) and reading it at intervals (or equivalent datalogger, for the instrumentally endowed...) would be instructive."

The same thread also offered alternatives to the dielectric relaxation explanation

"What you have experienced is common- you have to think about what you have there, an ELECTROLYTIC capacitor. Electrolytics contain "electrolyte", a fluid dielectric betweenn the plates. This fluid is not pure, and it is the impurities that
cause the "battery" action you have noticed. Short the pins for a couple of days and THEN retry. Chemically the impurities in the oil will neutralize and the capacitor will no longer "charge itself up". The action is similar to a very poor battery (try
sticking dissimilar metal nails into an orange and measure the voltage across the nails- you should get about half a volt or more)."

"If one can buy electrolytics with pure electrolyte, and plates made of pure aluminum, then such reactions would not be seen. However, traces of copper and other metals in the plates as small as they may be, are responsible for this "battery" action. As long as industrial grade metals and electrolyte oils are used, we will constantly see this effect...............sq"

It would seem there are two schools of thought on this subject:

1. Dielectric relaxation is responsible for the self-charging behaviour of electrolyte capacitors.
2. Chemical reaction similar to that of a battry causes the self-charging behaviour of electrolyte capacitors.
   

Personally the results of the "memory" effects of capacitors observed supports the theory of dielectric relaxation being responsible. If the effect is due to a reversible chemical reaction, then by conservation of energy the longer the capacitor is held at a certain potential, stronger the self-charged voltage.

The following is my own uninformed and most likely wrong explanation of why this happens, as I interpret it:

When a capacitor initally charges its dielectric material's structure is "stressed" or polarised due to the presence of the electric field. This causes a small amount of energy to be stored in the inter-molecular bonds with in the dielectric material. When the capacitor discharges rapidly, the dieletric material's structure is still under stress even though the potential across the terminals is 0 due to its slower response. As it reverts back to its normal, minimal-energy state in the absence of an electric field, a small increase in electric potential develops across the capacitor's terminals after some time. If the dielectric material is held by an electric field for a long period of time the internal structure will re-arrange graduly itself as to achieve minimal-energy under influence. Thus when discharged after a long time with in an electric field the self-charging effects are smaller as a lower amount of stress is present in the molecular structure.

Should any one more knowledgeable stumble on this topic, please correct any mistakes I have made.

Cheers,
Steve

Better communication, better world

Its hard to believe having grown up in China witnessing the exploitation of immigrant workers (people who move to Guang Zhou, where I grew up) that the same companies are facing a shortage of workers, a far cry from the days where the sons of farmers were willing to work in construction sites with out any safety gear (friend and I used to play in construction sites at night, the half finished buildings and stock piles of materials provided the settings for many imaginary adventures).

New York times attributed this to the aging working population, and its true. Many of my other's co-workers have retired when my mother and I visited them in 2000. This can be seen even in rural areas which once produced a seemingly unending stream of young people, a tradition breed into the farmer class in a culture where health care is non-existent and death comes early. I visited the village where my dad grew up, a backwater area reached by driving along a poor excuse for a road, then trekking along a muddy track. Where once a thriving village was, an entire section is now abandoned, houses falling into disrepair inhibited by animals. Family planning has finally extended its long arm and curbed the growth of humanity.

Despite this decrease however there are still more than enough people in China. What has changed the status quo in my opinion is better communication. Rural youths are no longer disillusioned with promises of easy money and adventures in the Big City having been told by those who ventured before them due to the improved telephone services. Youths are more technology literate, they utilise emails and SMS to regularly keep in touch with friends and family. The effect of improved communication is that people are able to compare their respective pay and living conditions and gain knowledge of better conditions elsewhere. They are no longer trapped in isolation, living in what facilities provided by the management, cut off and made to think they are having it better. In the same way that privatisations of businesses opened up markets for competition, the advance of communication technology has made the hiring market competitive.

Similarly better communication will eventually brush aside the "iron curtain" around the Chinese government and its people. With some 2 billion people, it will take considerable effort to keep anything from a population that can instant message, send anonymous messages, and post to public viewable noticeboards. Censorship of information so effectively used during the cultural revolution to control the masses, will not work in a world that is becoming ever more connected. The Chinese government now faces a dilemma: the advance tide of communication networks is granting its citizens more power, more knowledge, more freedom. Yet its also moving China forwards in technology and science, essential for its continued growth to become a world power. To restrict such communication is to cut itself off, and in this day and age its no longer a viable option. Its export economy will collapse as its manufacturing technology falls behind and increased reliance on imported technology will strip any fat on its balance sheets gain from the recent years of rapid growth and place it at the mercy of more advanced societies. On the other hand if continued exchange of knowledge is to be allowed, it will need to significantly restructure itself in order to survive in a country where its citizens are free to compare their conditions against the rest of the world, to express opinions and exchange ideas.

Time will tell how the government will react, but regardless of what they do the people has already tasted the first fruits of improved connectivity, and will not willing allow their connections to be cut.

The case against VSU

The driving logic and motivation behind VSU can be summed up in the following quote from a report produced by the Student Association Inc:

Federal Education Minister, Dr David Kemp, referred to Western
Australia as a working example of Voluntary Student Unionism (VSU) in its purest
form, stating ‘when campus organisations cannot take their customers for granted,
they will have to provide a better service or they will lose their customers…In
Western Australia, which has had VSU since 1995, we have already seen change in
the services provided’

Despite Dr David Kemp's claims the result was far removed from the idealistic projections as the following extract from the same report shows:

In reality however, VSU resulted in a significant demise in
the services that were provided to students in Western Australia . Although the
legislation has been significantly repealed by the current WA Government since then, at the time it resulted in the collapse of campus life at Edith Cowan University and a severe cut back of it at Murdoch and Curtin Universities.

Further more the introduction of VSU will also undermine student's authority in educational institutes:

Under the proposed legislation, the Student Association would lose
approximately 75% of its net income. This would almost certainly result in the
winding up of the organisation, terminating the delivery of services and activities
currently provided and also terminating any prospect of development of improvement of campus facilities in the future. In addition, the SA’s representational role in the university decision making processes would be lost.

Proponents of VSU like to tout that people will join the union if they want its services. The following data show instead that people will value their money over even basic services, even if the buildings are falling around their ears.

From the a report produced by University of Queensland Union:

In 1995, the following percentage of students joined their respective student unions:

• Curtin - 10%
• Edith Cowan - 13%
• Uni of WA - 28%
• Murdoch - 38%

After 4 years of cost cutting and aggressive advertisement, the figures improved:

• Edith Cowan - 6%
• Curtin - 30%
• Uni of WA - 30%
• Murdoch - 35%

However during this 4 year period:

Most of the commercial services continued to operate after 1997 but the profits were insufficient to continue to the comprehensive range of non-cost recovery services,publications and advice/support normally offered by the guilds...universities had to step in to provide financial assistance to the guilds to ensure the maintenance of a basic level of student services, and in the case of Edith Cowan the university took on a role the role of direct administration after the Guild collapsed.

As you can see, despite the disintegration of services due to lack of members, students still would keep their money rather than improve their university services. This attitude is born from greed and the mentality "I can put up with this because eventually others besides me will join and make things better. Then I can reap the benefits with out any personal cost." To make matters worst the current VSU legislation prevents universities from funding non-academic activities, all student services would vanish following the collapse of student guilds.

There is an interesting table on page 5 and 6 detailing the effects of 4 years of VSU. Its a despairing sight as it forecasts the losses we will be expected to endure. Specifically:

• Student Emergency loans - lost from 3 universities
• Full program of cultural events - lost from 3 universities
• Student conference funding - lost from all 4 universities.

This puts lie to the claim that university life would not be significantly affected by VSU's introduction.

If the past is any indication the introduction of VSU nationally will see the deterioration of student services, student representation, university life and basic services.

Google talk by Rob Pike

Yesterday Rob Pike, from the Google Systems Lab (he's also worked at Bell labs and done a lot of work on Unix), came to do a seminar at the University of Sydney.

The main topic was the language Google uses to handle all its data processing, querying etc, though there were lots of other interesting things in there too. He started off by going through his past work in designing concurrent programming languages and then onto his work at Google.

Google uses a filesystem called GFS to store their data. I was surprised to find out that all those zillions of bytes are stored as flat files - not as SQL databases. To query etc they use a special language devised primarily by Rob Pike, though other people were of course involved. :)

Basically, to facillitate the distribution of the workload across all their machines, jobs are carried out in the following way:
- First, the information is stored using IDL (information descriptive language I think (?)) which he said was "like XML, but without all the XML stuff". So pretty much fulfilling the same purpose as XML - storing data in a structured format
- This structured information is transmitted through a number of protocols: Google's system relies a lot on message passing to accomplish its work, so the protocols are important. Basically, this is just so the program that receives the information knows what form it is in, what data/variables it can access etc.
- The program that receives the information, written in Google's own language (which I never did catch the name of unfortunately), deals with one record only. There is no way to access what was done on previous records, no inter-record operability at all
- The results from each record are emitted to the aggregator, where all the inter-record stuff happens. The aggregator collates all the data, combining it into the final output.

In order to do this, the operations on each record have to be commutative - i.e. order doesn't matter. This means there is no need for Google to store its data in an ordered way: the files are all indexed to make them easy to get, but not in any particular order. Also, the operations performed by the aggregator have to be assosciative - i.e. it doesn't matter which records' results it gets first, it can collate data in any order. So for instance, it can aggregate the data from machines X and Y, and then combine the data from machine Z, or it can do X and Z and then add in Y. This is important as then each machine is independent, so the work can be easily distributed.

The language itself is designed specifically for Google's purposes, so it has some features not present in other languages and is missing other features that are unnecessary. Some of the interesting points are:
- Data types are appropriate to Google's purposes, e.g. string, url, time, int.
- Syntax makes it easy to express operations Google would want to do, such as compiling tables indexed by time, country, etc; getting the geographical location of a query from the ip address; getting information about a search query such as country, search terms, etc.
- Special function called sawzall() that uses regex to do all sorts of funky parsing stuff, like splitting a string into tokens or lines in different formats
- No standard I/O. This means Google's sensitive data is protected since it's actually impossible to view anything the protocol doesn't allow. Even if protecte data is present in a file, if the protocol used doesn't deliver it, it can't be accessed.
- Parsing of data is primarily done by preprocessing using the protocols. At the top of the program is a line [code]proto: "some_protocol.proto"[/code] which is a bit like a #include line and tells the program what data is present to be worked with. The programmer then doesn't have to worry about parsing and can just use the data, since all this work has been hidden at a lower level.
- Data type 'undef' indicates an error - there aren't any exceptions in the language. There is a flag that says either stop the program if undef is found, or ignore it and drop that data. During debugging, they stop the program, but when they are actually running it, the data is simply dropped. Since Google has such an enormous amount of data, it is statistically insignificant to drop the few cases where there are errors.
- Syntax of the language is kind of like C, but much more concise: it is an interpretive scripting type of language.

A notable point about this language is that there are no threads, locks, sychronisations etc. Considering how much concurrent processing Google does, that's pretty amazing. However, this is achieved by building these ideas into the fundamental design of the language. The program gets run once for each record and order doesn't matter, so it doesn't have to worry about multiple threads or anything. It just emits the result to the aggregator, then gets the next record and runs again. The aggregator doesn't care which order it gets the data in because all its operations are assosciative, so it doesn't particularly have to worry either.

The work load is distributed by Google's work queue, which he didn't go into much detail about since it wasn't the topic of the talk, but essentially it just works out which jobs get done on which machine and when.

So here's an example of how powerful yet simple this language is. Rob Pike showed us a program that he'd written which was about 15 lines long. It got all Google searches for a day and built a table of them, indexed by time they occured, and lattitude and longitude they came from (using ip address to get the location). This was then plotted as a world map which varied over time. The output was a black background, with white dots of varying intensity showing how many searches there were in each location. So it was like looking at the world at night time, with the lights indicating use of Google. As the hour of the day changed, you could see night time going across the world by the decrease in activity. It took 9 minutes to generate that map from all Google's searches for 24 hours.

One other anecdote I thought was interesting, which just illustrates the sheer scale of Google's operation: As in any good system, there is redundancy to protect their data. Once a rack holding about 60 TB, iirc, got completely wiped, and they didn't lost any data at all. Not a single byte.

We also got to talk to him after the seminar and he explained GFS a bit more and told us about Pagerank and how Google decides which results are most relevant. All in all, definately a worthwhile lecture to attend. :)

Joke of the day

After receiving his first ever paycheck, a young man went down to the club his dad worked at to meet him at the end of the day. They decided to have a few drinks before heading home for dinner.

One thing led to another and the father decided he'd like to have a go on the pokies. So there they were, playing away, not winning much, but enjoying themselves. It was getting pretty late and the son was wondering when they'd be going home...after all, they'd already missed dinner and his mother wouldn't be happy.

Towards the end of the night, they were playing on a machine that proclaimed "WIN A CRUISE" on the front - line up four cruise boats to win. The son pulled the lever and they watched breathlessy as the slots spun...one cruise ship, two, three...but the last one stopped just short!

"Phew, that's a relief!" said the father. Puzzled and disappointed that they hadn't won, the son turned to him. "What do you mean dad? We could have won a cruise!"
Dad replied, "Yeah, and how would we have explained that to your mother??"

By M

M(i|a)croscopic

This blog's been neglected, so I think I'll post some musings from the past few weeks.

Having recently returned to the city from a small country town, the difference amazes me. I've never lived in the country before in my life and it was a totally new experience.

Everyone's friendly, people get to know you quickly, yet for some reason that tends to make me uncomfortable and vaguely paranoid. There is a sense of security in the anonymity of the city that I was hitherto unaware of. And yet, out there, the atmosphere is more relaxed. World events push at the same rate, but somehow the country absorbs them more slowly. The days do not rush, they meander.

But the biggest difference is the people. In the city, a business suit and a laptop bag are marks of status, of acceptibility, There, I felt self-conscious walking down the street with my mp3 player and mobile phone. Here, people hurry, honed in on their targets, dodging and ducking through the obstacle course that is the city pavements. There, they stroll along, pausing to have a chat or see what takes their eye, and amicably give way to each other. Here, a university degree is how you get a decent career. There, leaving school at Year 10 and helping your father work the farm is the sign of a good future.

In this day and age, what makes the difference? A country town is no less connected than the city, news reaches there as quickly as it does here, so wherein lies the vastly separated mindset? I think it's because it's always been like that, and now it's self-perpetuating. People go to the city to be connected, to be on the cutting edge, at the centre of things. People go to the country to slow down, to get back to the land, to enjoy a sense of community.

Out there, the world is at once very big and very small - and sometimes it's hard to tell the difference.

M.

Creating OS X application bundles step by step

Introduction

This guide is the result of attempting to package a network visualiser (tcprose) I wrote so that it can be distributed as an application bundle. I gathered information from many places, and while I try to be accurate as possible should you notice any bugs feel free to contact me.

Step 1 - The folder hierachy

Each application bundle is on disk a file that ends in .app and contains a strict folder hierachy. The folder hierarchy is the form:

• application.app
• Contents
• Info.plist
  
• Frameworks
• dependent non-standard libraries
  
• MacOS
• executable binary
  
• Resources
• icons and other support files
  

The first thing you need to do then is to create such a folder tree somewhere.

Step 2 - The binaries

The binaries of your program reside in the MacOS folder. If your program depends on libraries that are not present by default, then you need to do the following:

1. Figure out what libraries your application depends on, and figure out what libraries need to be distributed with the program. In order to see the dynamic libraries your binaries depend on, use the otool thus:

   otool -L binary

   In my case:

   solaris:~/code/tcprose steve$ otool -L tcprose
   tcprose:
   /sw/lib/libSDL-1.2.0.dylib (compatibility version 8.0.0, current version 8.1.0)
   /System/Library/Frameworks/Cocoa.framework/Versions
   /A/Cocoa (compatibility version 1.0.0, current version 9.0.0)
   /System/Library/Frameworks/OpenGL.framework/Versions
   /A/OpenGL (compatibility version 1.0.0, current version 1.0.0)
   /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 71.1.1)
   /sw/lib/libpcap.0.dylib (compatibility version 0.8.3, current version 0.8.3)
   solaris:~/code/tcprose steve$
   

2. Anything in /System or /usr can be safely assumed to be present on all default systems. Notice then the 2 libraries in /sw/lib. For those unfamiliar with fink, its where it installs all its packages. Those 2 libraries need to be copied into the Frameworks folder. Do be careful however that you copy the actual file, not the symbolic links. For example:

   solaris:/sw/lib steve$ ls -l libpcap.0.dylib
   lrwxr-xr-x 1 root admin 19 20 Aug 03:35 libpcap.0.dylib -> libpcap.0.8.3.dylib
   solaris:/sw/lib steve$

   Notice that libpcap.0.dylib is in fact a symlink to libpcap.0.8.3.dylib, thus you need to copy /sw/lib/libpcap.0.8.3.dylib, not /sw/lib/libpcap.0.dylib.
3. Once the required libraries have been copied into Frameworks folder, its time to do some linking manipulation. Use the install_name_tool to remapped the dynamically linked libraries so your binary links against the libraries in Frameworks folder. To do this you issue the command:

   install_name_tool -change old_library_path new_library_path binary

   In tcprose's case:

   solaris:/sw/lib steve$
   install_name_tool -change /sw/lib/libpcap.0.dylib @executable_path/../Frameworks/libpcap.0.8.3.dylib ./tcprose

   Notice the use of @executable_path: this is what makes it "tick". @executable_path will automatically map to the path where the executable is located. Now if you move the binary into the MacOS directory, it will link against the libraries you have copied into the Frameworks folder

Word of caution: as far as I know there is no way to re-map the paths of any files in the binaries. Thus if you open files by using fopen("file", "rw"); then it will fail, because the working directory will be the directory that contains the application bundle, not the directory where the binary is stored. You will therefore need to take this into account, and adjust your paths accordinly.

Note: It might be possible to set the environmental variable PWD via Info.plist (see next step) to certain directory so that the working directory is somewhat more manageable. I didn't have any luck with this, so kindly let me know if you figure something out.

Update - 6/3/05: as pointed out by a reader, you can extract the path of the executable from argv[0], and thus determine the relative paths of whatever resources your program needs.

Step 3 - Info.plist

Now we come to the most important step of creating an application bundle: creating a proper Info.plist inside the Contents folder. Info.plist is an xml file that describes properties that finder reads Info.plist and determines many things, including which binary inside MacOS to execute, what icon inside Resources to display, etc. The best tool to use for editing it is no doubt Property List Editor in /Developer/Applications/Utilities. You can of course do this by hand. Apple has a detailed document on how to create a proper Info.plist file, but at the absolute minimum the following keys are required:

• CFBundlePackageType
  
• CFBundleExecutable

Extra: if you want to specify a custom icon, first create a .icns file with Icon Composer found in /Developer/Applications/Utilities then save the .icns file in the Resources folder, and add the CFBundleIconFile key.

Conclusion

Creating an application bundle is a relatively easy affair, the most difficult part being remapping the dynamically linked libraries and adjusting any hardwired paths and generating a proper Info.plist file. Have fun, and if you have any suggestions or bug reports, do let me know!

Cheers,
Steve

Preserving stdin when using SDL

SDL has a "feature" where by it redirects stdin/out/err on certain platforms, including OS X. This presented problems since tcprose (an opengl network visualiser) depended on stdin for interprocess communication. After much mucking about, I arrived eventually at a 3 line solution to the problem:

First we duplicate the stdin file descriptor so when SDL calls close() on 0 the stream remains open.

int dup_fd = dup(0);

Then we initalise SDL, and let it redirect stdin as it does.

SDL_Init(SDL_INIT_VIDEO);

Here is where we do our little trick: close 0, then duplicating the original stdin stream back onto 0, so scanf etc will continue to work.

close(0);
dup2(dup_fd,0);

And viola! We have stdin back again, no longer redirected. This solution won't work for window users though. See discussion at gmane.org.
Cheers,
Steve

FSAA using SDL

Taking a break from working on emmap, I got back into the wonderful of C/OpenGL/SDL programming again.

SDL is a wonderful library that does... well a lot, but in a portable fashion that works on many platforms. One of these include Full Screen Anti Aliasing (FSAA), which makes things Look Good. I won't go into detail on how its done via SDL, there are resources a plenty. What I will impart is however a small piece of knowledge I gained after debugging a visualisation I am writing: FSAA through SDL will only work reliably cross platform only if the screen color depth is 24 or less.

Its a small thing, but it took a while to work out. Hope this helps some one :-)

Cheers,
Steve

bugmenot

Some news sources, like the new york times and sunday morning herald, have an annoying "feature" - they require the viewer to first register before allowing them to view the contents. Many other sites are guilty of the same, and bugmenot was setup so one doesn't have to lose one's privacy to these data sinks.

To aid in a better, faster, and more private surfing experience, there exists a bugmenot pluging for firefox, which will fill out any required forms with valid usernames and passwords contributed by its members.

Now thats what I call user friendly.

Cheers,
Steve