Spline Approximation (Introduction)

We sometimes encounter a situation where a number of points with coordinates (x,y) are given and we want to find a function such that for all of these points we have f(x)=y (interpolation) or f(x) \approx y (approximation). Most often we say that we want on average |f(x) - y| to be as small as possible and for whatever reasons usually the quadratic mean. The most simple and well known approximation is probably linear regression, where a straight line is found that tries to approximate the points. This can be extended to other function, for example polynomials of a fixed maximum order. For something that is supposed to be periodic, linear combinations of functions of the form f(t)=\sin(at) and f(t)=\cos(at) might be useful.

Now it may not be easy to express the whole extent by one function. So the interval, in which the x-coordinates lie, might be subdivided into subintervals and linear regression or whatever is being used can be performed in each subinterval separately. This results in a polygon-like curve or worse in a curve that „jumps“ at the interval borders. This can well be good enough and it is relatively easy to implement. With the additional constraint, that it should be continuous at the interval borders, it becomes a bit more difficult.

Now there is some preference for smooth curves. For example it might be desirable that the function is continuous (i.e. it does not jump at interval boarders) and even its first and second derivative should be continuous. This roughly resembles a mechanical spline as it was used in the old days for drawing and constructing. Kind of an elastic ruler.

This is where Splines are often used to interpolate a smooth curve that passes through some given points. More precisely cubic splines, but the concept is of course more general. A lot of material can be found on the internet about spline interpolation.

But they can also be used for approximation. So we want a curve that is smooth and that approximates our given points and that is expressible as a simple third degree polynomial in each subinterval.

Just to make it clear, the subintervals are not used as a „divide et impera“ strategy, but we consider all the points at once, just give ourselves the freedom to have different functions in different subintervals to get a combined function that behaves better than polynomials of very high degree. We do need to think also a bit about the inaccuracy of floating point arithmetic. So polynomials of degree three are still somewhat precise within the subinterval, but a higher order polynomial that is applied to a large interval will become less accurate with normal floating point arithmetic („double“).

I will leave this as a starting point for thinking. In some of the next articles, the spline approximation will be derived mathematically and then there will be a cookbook how to use it programmatically. My advice is to experiment with the implementation and its parameters until you are confident that it give sufficiently precise result, have a look at the math behind it to understand the question of the precision or have someone else have a look. With floating point arithmetic it is always a bad idea just to program something that looks right and totally ignore the rounding errors of floating point arithmetic, that can have huge impact on the result.

There is a lot of material on spline interpolation on the internet. On spline approximation there have been some papers, but very little can be found on the internet.

A followup article covering the mathematics behind spline approximation has been written.

Share Button

Addresses

Postal addresses seem to be easy:
– Name and/or Company
– Street and/or PostBox
– ZIP Code
– Municipality
– Country

This is true in Germany or Switzerland and a few other countries. I would like to add, that in some large buildings it can be a good idea to add the apartment number, but these buildings are rare in these two countries and the name is really almost always sufficient.

For relational databases please keep in mind, that these fields may get just a bit or even a lot longer than we anticipated. US-ZIP-Codes are now something like NY-11713-5532. And others may be longer. How long are names, street names and names of villages and towns? Even the country part, which seems to be relatively easy, brings some challenges. Countries like Switzerland and Germany and Canada are no problem. But what about semi-independent countries like Guernsey, Jersey, …? And what about areas, that are de-jure part of another country, but de-facto an independent country? Or an independent country that is not accepted by each country? There are lists of countries that we can find and usually they include also the „semi-independent“ and „semi-accepted“ countries. But it is a good idea to check if the list is complete enough for our purpose. I would not recommend to define it yourself.

But now the other parts of the address: If we want to describe the location where a person lives, and this person does not live in a housing area, but for example in a nomadic life style, it becomes a bit harder. Or we might observe a different number of lines for the address. Or even that streets are not named consistently and the only relyable address is a postbox. Many countries do not write the names on the door and on the letterbox, but just an apartment number. So this number with some word for „apartment“ that is understood by the local post officer with possibly limited language skills is needed. Also in some countries there are a lot of buildings for „streetname 3053A“, so we need to add the building number also.

My point is, that postal addresses are not as easy as it might seem. So I recommend to do some research in the internet to find a library or a documentation that handles this or can be used as a basis instead of trying to invent a new wheel that will probably be incomplete and suffer from its insufficiencies at some point. It is sometimes more important to recognize which seemingly trivial problems are actually harder than being able to invent solutions for such problems. We should invest our energy on solving problems that have not been solved with publicly available documentations or even libraries and that make up our business. In this case the actual implementation is rather trivial, but the specification of the requirements is the hard part, so it is enough to find some useful documentation for this. It might of course be sufficient to handle only for example French addresses, if the system will never be dealing with foreign addresses, but the experience shows that at least some thinking about what it means to extend the system later are a good idea.

And please, handle too long entries properly instead of displaying a stack trace on the end users screen or even providing a spot to attack the server.

Share Button

Happy New Year 2021

Un an nou fericit! — Happy new year! — Срећна нова година! — Frohes neues Jahr! — Onnellista uutta vuotta! — С новым годом! — Gullukkig niuw jaar! — FELIX SIT ANNUS NOVUS — ¡Feliz año nuevo! — Feliĉan novan jaron! — عام سعيد — Щасливого нового року! — Gott nytt år! — Bonne année! — Καλή Χρονια! — Felice anno nuovo! — Godt nytt år!

This was generated with JavaScript using Rhino:

a = ["Frohes neues Jahr!",
"Happy new year!",
"Gott nytt år!",
"¡Feliz año nuevo!",
"Bonne année!",
"FELIX SIT ANNUS NOVUS",
"С новым годом!",
"عام سعيد",
"Felice anno nuovo!",
"Godt nytt år!",
"Gullukkig niuw jaar!",
"Feliĉan novan jaron!",
"Onnellista uutta vuotta!",
"Срећна нова година!",
"Un an nou fericit!",
"Щасливого нового року!",
"Καλή Χρονια!"];
b = a.map(function(x) { return Math.floor(1000000000 + Math.random()*1000000) + " " + x; });
b.sort();
c = b.map(function(x) { return x.replace(/^\d+\s+/, ""); });
print(c.join(" — "));

Share Button

Christmas 2020

¡Feliz Navidad! — καλά Χριστούγεννα! — Buon Natale! — З Рiздвом Христовим! — クリスマスおめでとう ; メリークリスマス — Natale hilare! — Merry Christmas! — ميلاد مجيد — Hyvää Joulua! — С Рождеством! — Joyeux Noël! — God Jul! — Feliĉan Kristnaskon! — Crăciun fericit! — God Jul! — Frohe Weihnachten! — Срећан Божић! — Prettige Kerstdagen!


This was generated by a bash script. I am using Perl instead of sed, but not for program logic:

#!/bin/bash
set -e

mkfifo /tmp/tmp_pipeA-$$
mkfifo /tmp/tmp_pipeB-$$

cat << EOTXT |head -18 > /tmp/tmp_pipeA-$$ &
С Рождеством!
Hyvää Joulua!
καλά Χριστούγεννα!
Buon Natale!
Prettige Kerstdagen!
З Рiздвом Христовим!
Merry Christmas!
Срећан Божић!
God Jul!
¡Feliz Navidad!
ميلاد مجيد
クリスマスおめでとう ; メリークリスマス
Natale hilare!
Joyeux Noël!
God Jul!
Frohe Weihnachten!
Crăciun fericit!
Feliĉan Kristnaskon!
EOTXT

od -x /dev/urandom \
|head -18 \
|perl -p -e ’s/^\d+\s//;‘ > /tmp/tmp_pipeB-$$ &

paste /tmp/tmp_pipeB-$$ /tmp/tmp_pipeA-$$ \
|sort \
|cut -f 2 \
|perl -p -e ’s/\n/ — /g;‘ \
|perl -p -e ’s/ — $/\n/;‘

rm -f /tmp/tmp_pipeA-$$
rm -f /tmp/tmp_pipeB-$$

Share Button

Functional Scala

I participated online in the conference „Functional Scala 2020“ in London. That it was in London had mostly one relevance, which was the time zone. There was no physical location and all talks were done online. An interesting idea was a virtual location. It consisted of rooms and we could move a dot representing ourselves around. Each room consisted of a beautiful landscape as a map of a different climate zone. I could hear what others said, when I moved my dot, representing myself, closer to them, as in real life, and do some nice conversations like that.

A lot of things were said about Scala 3, which will be a big step forward, but also a big step, because it is not compatible with Scala 2. So some work will be necessary to move on to Scala 3, but we will gain a better language for beginners, intermediates and advanced Scala developers.

I am really looking forward to Functional Scala 2021, hopefully in London.

Share Button

How to disable touchpad (on Linux/X11)

For me it is much better to use an external mouse than the touchpad, which I sometimes touch accidentally.

So, here is how to disable it with a short Perl-Script. A bash script with a bit of Perl would do the same, btw.


#!/usr/bin/perl
my $tp = `xinput list | egrep -i touch`;
chomp $tp;
$tp =~ s/.+id=(\d+).+/$1/;
system "xinput set-prop $tp 'Device Enabled' 0";
print "Touchpad disabled\n";

Share Button

Devoxx UA 2020 (talks)

I watched the conference onlie and picked the following talks:

And on the second day:

Share Button

Devoxx UA

Most conferences have been cancelled, since it is difficult to hold a conference these days. The idea to move the conference online has been obviously around, but it was rejected by most organizers, because it it not the same and the all important chance to meet other people is just not the same.  So the Devoxx in Antwerp, which I like to visit every year, did not happen.  But Devoxx Ukraine decided to go for online.

So how did it work:  There were three tracks.  Each track was represented by a youtube channel, on which the live talk was transmitted.  Before and after the talks, professional moderators appeared in these channels, announced the speakers and did what moderators do in normal conferences.  The devoxx App worked on my cell phone and that seemed to be the most up to date schedule.

Some talks were really excellent.  I enjoyed them a lot even online.  For talks that are not so good, it requires more discipline to stay tuned.

The discussion was done in zoom channels that belonged to the three tracks.  So discussions could technically last until the end of the next talk.  The discussions in zoom also worked quite well, which was a surprise.

I think it is probably the right reaction, to have fewer conferences than usually in a year and to cancel some and move some to online, exactly as it is happening.  I think DevoxxUA had around 10’000 visitors, so they absorbed audiences of several conferences.  Also some common speakers at Devoxx conferences were not giving talks, so I assume that also part of the speakers decided that the online format is not ideal for them.

About the contents I will write in another Blog article.

Share Button

How to rename files according to a pattern

We often encounter situations, where a large number of files should be copied or renamed or moved or something like that.
This can be done on the Linux command line, but it should be possible in almost the same way on the Unix/Linux/Cygwin-command line of newer MS-Windows or MacOS-X.

Now people routinely do that and they have developed several ways of doing it, which are all valid and useful.

I will show how I do things like that. It works and it is not the only way to do it.

So in the most simple case, all files in a directory ending in ‚.a‘ should be renamed to ‚.b‘.

What I do is:


ls *.a \
|perl -p -e 'chomp;$x = $_;s/\.a$/.b/;$y = $_; s/.+/mv $x $y\n/;' \
|egrep '^mv '\
|sh

You can run it without the last |sh, to check if it really does what you want.

So I use the files as input to a short perl script and create shell commands. It would be possible to do this actually in Perl itself, without piping it into a shell:


ls *.b \
|perl -n -e 'chomp;$x = $_;s/\.b$/.c/;$y=$_;rename $x, $y;'

You could also read the directory from perl, it is quite easy, but for just quickly doing stuff, I prefer getting the input from some ls.

To go into sub directories, you can use find:


find . -name '*.c' -type f -print \
| perl -n -e 'chomp;$x = $_;s/\.c$/.d/;$y=$_;rename $x, $y;'

a
You can also rename all the files that contain a certain string:

find . -name '*.html' -type f -print \
|xargs egrep -l form \
|perl -n -e 'chomp; $x=$_;s/\.html$/.form/;$y=$_;rename $x, $y;'

So you can combine with all kinds of shell commands and do really a lot of things in one line.

Of course you can use Raku, Ruby, Python or your favorite scripting language instead, as long as it allows some simple pattern matching and an efficient implicit iteration over the lines.

For such simple tasks there are also ways to do it directly in the shell like this

for f in *.d ; do mv $f `basename $f .d`.e; done

And you can always use sed, possibly in conjunction with awk instead of perl for such simple tasks.

Another approach is to just pipe the files into an texteditor that is powerful enough and create a one time script using powerful editing commands.
On Linux and Unix servers we almost always use vi, even people like me, who prefer Emacs on their own computer:

ls *.e > tmpscript
vi tmpscript

and then in vi


:0,$s/\(.*\)\(.e\)$/mv \1\2 \1.f/
ZZ

and then

sh tmpscript
rm tmpscript

So, there are many ways to achieve this goal and they are flexible and powerful enough to do really a lot more than just such simple pattern renaming.

If you work in a team and put these things into scripts, it might be necessary to follow a team policy about which scripting languages are preferred and which patterns are preferred. And you need to know the stuff that you write yourself, but also the stuff that your colleagues write.

Please, do not do

mv *.a *.b

It won’t work for good reasons.
On Linux and Unix systems the shell (usually bash) expands the glob expression (the stuff with the stars) into a list of strings and then starts mv with these strings a parameters. So calling mv with some file names ending in .a and .b, mv cannot have any idea what to do. When called with more than two parameters, the last one needs to be a directory where to move the stuff, so usually it will just refuse to work.

Share Button

GIMP

In spite of working mostly for server software and server setup using powerful non-graphic command line tools and scripting languages, it is sometimes fun to work with something very graphical. I did talk about Clojure Art, which is fun and creates interesting visual results and helps getting into the phantastic language Clojure. But more than twenty years ago I have discovered GIMP, which is the main image editor on Linux computers. I keep hearing that Photoshop is even a bit better, but it does not work on my computers, so I do not really care too much about it.

To be clear, I am not a professional image editing specialist, I just do it a bit for fun and without the claim of putting in all the knowledge about colors and their visual appearance, the functionality of gimp and image editing in general… I am just experimenting and finding out what looks interesting or good to me and how to work efficiently. Actually it brings together my three interests, programming, photography and bicycle touring, the combination of the latter two being the major source of my input material.

Now you start working with layers and with tools that increase or decrease the brightness, contrast and saturation of an image or of the layer being worked on. Now I would like to explore how certain functions can be brought into this. Either by putting them into my fork of gimp or into a plugin or into a script within gimp or a standalone script or program.

Some things that I find interesting and would like to explore: additional functions for merging layers. The function has the input of n (for example n=2) pixels from the same position and different layers and it produces another pixel. These are the twenty or thirty layer modes, that describe how a layer is seen on top of the next lower visible layer. So two images of the same size or two layers could be merged. It could be as nicely as in Gimp or just desctructively to make things easier. If it is worth anything for anybody else, maybe making it work as the current modes would be a noble goal. But for the moment it is more interesting what to do. A very logical thing to do is taking just the average of the two layers. So for rgb it could be the arithmetic mean of the r, g and b values of the n layers (or images) belonging to the same x-y-position. Now what would alpha values mean? I would think that they are weighting the average and the new alpha value could be the average of the input alpha values. Now we could use geometric, quadratic and cubic means and with some care concerning the 0 even harmonic means. Very funny effects could be created by combining these byte-values with functions like xor.

When working with any functions, it is always annoying that the r-g-b-values are always between 0 and 255 (or something like that). So this can be changed to real numbers, by doing something like

    \[s = \tan(\frac{(r-127.5)\pi}{256})\]

or to the non-negative real numbers by doing something like

    \[s = \tan(\frac{r\pi}{512})\]

Then some functions can be applied to these double values and in the end the inverse function will just be applied and result in a rounded and limited integral value from 0 to 255.

Do we need this? I do not know. But I think it would be fun to be able play around with some functions on one pixel, a vicinity of pixels, the same pixel-position from different layers and the like.

The nice thing is: we can see the result and like it or throw it away. Which function is correct or useful can be discussed and disagreed on. That is more fun than formally proven correctness, assuming of course, that the functions itself are implemented correctly.

I have not looked into the source code of plugins to tell what can reasonably be done without too much effort. But if someone reading this has some ideas, this would be interesting to hear about.

And finally we have one more advantage of GIMP, because it is open source and it is possible to make changes to it.

Share Button