# How to draw lines, circles and other curves

These ideas were developed more than 30 years without knowing that they were already known at that time…

Today the graphics cards can easily do things like this in very little time. And today’s CPUs are of course really good at multiplying. So this has lost a lot of its immediate relevance, but it is a fun topic and why not have some fun…

Let us assume we have a two dimensional coordinate system and a visible area that goes from to and to . Coordinates are discrete.

In this world we can easily measure an angle against a (directed) line parallel to the -axis, for example up to an accuracy of :

• < \alpha < \frac{\pi}{2}(=90^\circ)x = 0 \land y > 0\implies \alpha = \frac{\pi}{2}x < 0 \land y > 0 \land |x| < |y|\implies \frac{\pi}{2}

So let us assume we have a curve that is described by a polynomial function in two variables and , like this:

We have to apply some math to understand that the curve behaves nicely in the sense that it does not behave to chaotic in scales that are below our accuracy, that it is connected etc. We might possibly scale and move it a bit by substituting something like for and for .

For example we may think of

• line:
• circle:
• eclipse:

We can assume our drawing is done with something like a king of chess. We need to find a starting point that is accurately on the curve or at least as accurately as possible. You could use knights or other chess figures or even fictive chess figures..

Now we have a starting point which lies ideally exactly on the curve. We have a deviation from the curve, which is . So we have . Than we move to and with . Often only two or three combinations of need to be considered. When calculating from for the different variants, it shows that for calculating the difference becomes a polynomial with lower degree, because the highest terms cancel out. So drawing a line between two points or a circle with a given radius around a given point or an ellipse or a parabola or a hyperbola can be drawn without any multiplications… And powers of -th powers of can always be calculated with additions and subtractions only from the previous -values, by using successive differences:

These become constant for , just as the th derivatives, so by using this triangle, successive powers can be calculated with some preparational work using just additions.
It was quite natural to program these in assembly language, even in 8-bit assembly languages that are primitive by today’s standards. And it was possible to draw such figures reasonably fast with only one MHz (yes, not GHz).

We don’t need this stuff any more. Usually the graphics card is much better than anything we can with reasonable effort program. Usually the performance is sufficient when we just program in high level languages and use standard libraries.

But occasionally situations occur where we need to think about how to get the performance we need:
Make it work,
make it right,
make it fast,
but don’t stop after the first of those.

It is important that we choose our steps wisely and use adequate methods to solve our problem. Please understand this article as a fun issue about how we could write software some decades ago, but also as an inspiration to actually look into bits and bytes when it is really helping to get the necessary performance without defeating the maintainability of the software.

# Intervals

Intervals are subsets of a universe, that are defined by upper and lower boundaries. Typically we think about real numbers, but any totally ordered universe allows the definition of intervals.

Intervals are defined by lower and upper boundaries, which can be a limiting number or unlimited, typically written as for the upper bound and for the lower bound. The boundaries can be included or excluded. So the following combinations exist for a universe :

unlimited
half open, lower unlimited
open, lower unlimited
half open, upper unlimited
open, upper unlimited
open
half open
half open
closed
it is sometimes useful to consider the empty set as an interval as well

The words „open“ and „closed“ refer to our usual topology of real numbers, but they do not necessarily retain their topological meaning when we extend the concept to our typical data types. , , and in the notation above do not have to be members of , as long as the comparison is defined between them and all members of . So we could for example meaningfully define for the interval .

As soon as we do not imply we always have to make this clear… And is kind of hard to really work with in software on computers with physically limited memory and CPU power.

Intervals have some relevance in software systems.

We sometimes have a business logic that actually relies on them and instead programming somehow around it, it is clearer and cleaner to actually work with intervals. For example, we can have a public transport scheduling system and we deal with certain time intervals in which different schedules apply than during the rest of the day. Or we have a system that records downtimes of servers and services and these are quite naturally expressed as intervals of some date-time datatype. It is usually healthy to consider all the cases mentioned above rather than ignoring the question if the boundary with probability zero of actually happening or having ugly interval limits like 22:59:59.999.

The other case is interval arithmetic. This means, we do floating point calculations by taking into account that we have an inaccuracy. So instead of numbers we have intervals . When we add two intervals, we get . In the same way we can multiply and subtract and even divide, as long as we can stay clear of zero in the denominator. Or more generally we can define .
It does of course require some mathematical thinking to understand, if the result is an interval again or at least something we can deal with reasonably. Actually we are usually happy with replacing the result by an interval that is possibly a superset of the real result, ideally the minimal superset that can be expressed with our boundary type.

At this point we will probably discover a desire to expand the concept of intervals in a meaningful way to complex numbers. We can do this by working with open disks like or closed disks like . Or with rectangles based on two intervals and like .

These two areas are quite interesting and sometimes useful. Libraries have been written for both of them.

Often we discover, that intervals alone are not quite enough. We would like to do set operations with intervals, that is

union
intersection
set difference

While the intersection works just fine, as long as we include the empty set as an interval, unions and differences lead us to non-intervals. It turns out that interval-unions, sets that can be expressed as a union of a finite number of intervals, turn out to be a useful generalization, that is actually what we want to work with rather than with intervals. In this case we can drop the empty set as interval and just express it as the union of zero intervals.

There are some questions coming up, that are interesting to deal with:

normalization
Can we normalize interval-unions to some canonical form that allows safe and relyable comparison for equality?
is our universe actually discrete, so we can express all unlimited boundaries with closed boundaries?
interval lengths
Do we have a meaningful and useful way to measure the length of an interval or the total length of an interval-union, as long as they are limited? Or even for unlimited intervals?
collection interfaces
Do we want to implement a Set-interface in languages that have sets and an understanding of sets that would fit for intervals
implementation
How can we implement this ourselves?
implementation
Can we find useful implementations?

Having written a java library to support interval-unions on arbitrary Comparable types once in a project and having heard a speech about an interval library in Scala that ended up in using interval-unions in a pretty equivalent way, it might be interesting to write in the future about how to do this or what can be found in different languages to support us. For interval arithmetic some work has been done to create extensions or libraries for C and Fortran, that support this, while I was a student. So this is pretty old stuff and interesting mostly for the concepts, even if we are not going to move to Fortran because of this.

If there is interest I will write more about actual implementations and issues to address when using or writing them.

# Carry Bit, Overflow Bit and Signed Integers

It has already been explained how the Carry Bit works for addition. Now there was interest in a comment about how it would work for negative numbers.

The point is, that the calculation of the carry bit does not have any dependency on the sign. The nature of the carry bit is that it is meant to be used for the less significant parts of the addition. So assuming we add two numbers and that are having and words, respectively. We assume that and make sure that and are both words long by just providing the necessary number of 0-words in the most significant positions. Now the addition is performed as described by starting with a carry bit of 0 and adding with carry , then and so on up to , assuming that is the least significant word and the most significant word, respectively. Each addition includes the carry bit from the previous addition. Up to this point, it does not make any difference, if the numbers are signed or not.

Now for the last addition, we need to consider the question, if our result still fits in words or if we need one more word. In the case of unsigned numbers we just look at the last carry bit. If it is 1, we just add one more word in the most significant position with the value of , otherwise we are already done with words.

In case of signed integers, we should investigate what can possibly happen. The input for the last step is two signed words and possibly a carry bit from the previous addition. Assuming we have -Bit-words, we are adding numbers between and plus an optional carry bit . If the numbers have different signs, actually an overflow cannot occur and we can be sure that the final result fits in at most words.

If both are not-negative, the most significant bits of and are both . An overflow is happening, if and only if the sum , which means that the result „looks negative“, although both summands were not-negative. In this case another word with value 0 has to be provided for the most significant position to express that the result is while maintaining its already correctly calculated result. It cannot happen that real non-zero bits are going into this new most significant word. Consequently the carry bit can never become 1 in this last addition step.

If both are negative, the most significant bits of and are both . An overflow is happening, if and only if the sum , which means that the result „looks positive or 0“, although both summands were negative. In this case another word with value or , depending on the viewpoint, has to be prepended as new most significant word. In this case of two negative summands the carry bit is always 1.

Now typical microprocessors provide an overflow flag (called „O“ or more often „V“) to deal with this. So the final addition can be left as it is in words, if the overflow bit is 0. If it is 1, we have to signal an overflow or we can just provided one more word. Depending on the carry flag it is for C=0 or all bits 1 ( or , depending on the view point) for C=1.

The overflow flag can be calculated by .
There are other ways, but they lead to the same results with approximately the same or more effort.

The following table shows the possible combinations and examples for 8-Bit arithmetic and :

x<0 or x≥0y<0 or y≥ 0(x+y)%2^8 < 0 or ≥ 0Overflow BitCarry Bitadditional word neededvalue additional wordExamples (8bit)
x≥0y≥0≥000no-0+0
63+64
x≥0y≥0<010yes064+64
127+127
x≥0y<0≥000 or 1no-65+(-1)
127+(-127)
x≥0y<0<000 or 1no-7+(-8)
127+(-128)
0+(-128)
x<0y≥0≥000 or 1no--9 + 12
-1 + 127
-127+127
x<0y≥0<000 or 1no--128+127
-128+0
-1 + 0
x<0y<0≥011yes-1-64 + (-65)
-128+(-128)
x<0y<0<001no--1 + (-1)
-1 + (-127)
-64 + (-64)

If you like, you can try out examples that include the carry bit and see that the concepts still work out as described.

# How to calculate transcendental functions

There is sometimes need to calculate transcendental functions like , , or . We get them from the library and the library relies on implementations in the CPU for most of them. This is true, if we like to do them in „double“ format, which is the standard way of doing floating point arithmetic. But it can be interesting how these can be calculated to a given precision or to calculate functions that are not in the library and not easily composed from the library functions. There are many ways to do this and actually the naïve way of using the Taylor-series

is often not such a bad idea, if done correctly.
We know from math what to use for the coefficients and for which ranges of this converges. For limited fixed precision it is possible to tune the coefficients a bit and get better results with a fixed number of summands. For arbitrary precision we need to be more flexible and cannot be prepared for this exact precision.

Now mathematically we can often have a converging series, for example if we have

This converges for , but the convergence is not necessarily computer friendly. It can be proved easily, that this series converges for , but for it converges slowly. To give an idea, if we are calculating with 100 digits after the decimal point then we would still have single terms in the area of our desired precision for and since they get smaller only slowly, we would have to go much further. This is impossible to use.

As a rule of thumb the coefficients are not our friends. They may or may not converge towards zero, but we really have to rely on the -part to get diminishing summands. A good idea is to consider if the coefficients are bounded, which they usually are in real life examples. That means that there is a boundary such that for each we have . So we absolutely need to use some mathematical knowledge about the function in order to get reasonable convergence.

In case of periodic functions like the trigonometric functions, we can normalize x to values within one „period“, but that will reduce or only to a range of . Using some common trigonometric formulas, we can actually reduce this to the range , which is still not good enough. In this case we have to use formulas like and similar formulas for other trigonometric functions. These allow us to move to smaller values of . For the exponential function, we have even easier ways. Let be a natural number such that . Then we let and we can calculate . Now we have and we just need to take the -th power of the intermediate result. This can be calculated using algorithms like square and multiply or even some improvements over that.

In the end we will end up writing a lot of code for different cases which are optimized in different ways for some function. For example the power is a function in two parameters, that has quite a wild behavior and for writing an implementation that provides reasonable performance and precision we need to handle a lot of cases. Just look at the power function of the standard Java library, which is written in native C-code. Its beauty is not the conciseness, but having some understanding about what it takes to do this well you might eventually appreciate the given implementation, even if you not only use it, but also read it.

Now dealing with the precision is a delicate question, which again requires mathematics. As a general rule we usually need to use more precision for intermediate results. A good tool is to take the derivative or the partial derivatives in case of functions with multiple parameters to see how much changes in that parameter influence changes of the value. The Taylor theorem gives some definite, but possibly hard to apply answers. And it can also be useful to look at lower and upper bounds for the operations performed.

When writing such functions, unit tests are a big deal. Often they are not so hard to write, if we have inverse functions to rely on or if we can increase the precision and see that the lower precision is at least as precise as it claims to be. In some cases existing implementations for double can be used to check if the calculation is correct for smaller precisions.

Most of all it is important to think and use some mathematics or get help for this from somebody with appropriate knowledge.

Just to give you a hint: There are tons of transcendental functions that do not exist in standard libraries and that may be interesting to use. For some of them there are libraries. For some we still need to find libraries or write them.

# Modular Arithmetic

We have some articles in this blog about integers of typical programming languages and how they work. Time to introduce the underlying mathematical concepts, that have been covered implicitly until now, since they are also interesting in many other aspects. And besides, this is a very beautiful area of mathematics.

Mathematics that we learn in school is mostly inspired by what is needed for physics. This was quite a good choice 100 years ago, because it gave some motivation to why we do certain things and it was the area, where math was applied. Of course also chemistry and engineering, but these are somewhat similar aspects of mathematics as we use in physics. Now physics and chemistry make use of quite interesting areas of mathematics like group theory or non Euclidean geometry, but these are kind of advanced areas beyond what we typically learn in school. at least in the countries where I went to school. So it is about real numbers, some trigonometry, real analysis (calculus) and maybe complex numbers.

Since more than 50 years mathematics is heavily used in informatics as well, if we abstract informatics away from computers, even longer, because for example algorithms and cryptography have been used for several thousand years already, but that was a small niche and became main stream by the existence of computers. And for informatics and computer science we need different areas of mathematics. Analysis is not the so important, though not irrelevant. One area is information theory, which is based on probability theory and statistics. Numerical calculations have to a great extent remained a domain of mathematics itself, so this connection may be strong, but it is applied mathematicians using computers and using knowledge from IT to program them better, not the other way round. Still numerical analysis is somewhat important, but not really what most of us need very often.

The areas of mathematics that are really interesting for informatics are discrete mathematics, algebra and number theory. There is enough material about this on the web, but for now we will deal with modular arithmetic, which is kind of in the intersection of discrete mathematics, algebra and number theory.

Now we take any positive integral number with .
We say that two integral numbers and are congruent modulo :

if and only if can be divided by . We might also say that there is a such that .
Now we can make interesting observations:
We assume, that we have pairs of numbers such that

and

Then we can observe that also

This can be proven easily.
We assume as above

and similarly

Then we have

We call a set of all numbers of that are congruent to each other a remainder class and write this as

There are exactly remainder classes modulo and usually we use a representation system of

or for even we often use

or for odd we often use

We observe these representation systems when we do division with remainder, written as % in many programming languages, but it is necessary to do some quick research on which representation system % uses and which one we want to use and possibly adjust the result. The corresponding division may not be /, but we can obtain it by subtracting our remainder from the dividend and dividing that, which should be an exact division.

Now we need to define a ring. A ring is a set with operations and such that the following rules apply:

1. For any members we also have , and . This is usually not mentioned, because it is part of how we define these operations in the first place in most mathematical texts.
2. Addition is communicative: For any members we have .
3. Addition has a neutral element 0: For any member we have .
4. Addition has inverse elements: For any member we have a member such that . Usually we write for this inverse element of and we write instead of .
5. Addition is associative: For any members we have . We can omit the parentheses here and write instead.
6. Multiplication has a neutral element 1: For any member we have .
7. Multiplication is associative: For any members we have . We can omit the parentheses here and write or even instead.
8. Multiplication in conjunction with addition is distributive: For any members we have and .

If the multiplication is also communicative, we call it a commutative ring. If there is a multiplicative inverse for any element other than 0, we call it a skew field. And if both conditions hold, we call it a field.

Now we can see that is actually a communicative ring.

And these remainder classes modulo also form a ring. We call it or sometimes also , but I do not use the second form, because it is ambiguous with something else (p-adic numbers). If is a prime number, then is actually a field and in this case we may write instead of . Or in some literature, if you prefer that. Why is it a field?

Now we have an extension of the Euclid algorithm to calculate the gcd of two numbers. This also yields numbers and such that . So these numbers exist. For a prime number and a remainder class we know that is not a multiple of and since is prime we know that

. This yields a multiplicative inverse for because

.

Now we often see as a power of and the modular arithmetic, at least +, -, *, is what is sold to us as integer arithmetic of Java, C or C#.

On the other hand it can be interesting and useful to use modular arithmetic for other values of . Interesting are mostly prime numbers, which can be relatively small like , or , but also really big. For non-primes we have null-factors, that is numbers such that . This breaks some fundamental mathematical assumption for integers and fields, but is perfectly correct for this modular ring.

In our daily life modular arithmetic is actually quite common. We have the week days with , the hours of the clock with or , the minutes and seconds of the clock with and quite a bit of , which we do not really see as modular arithmetic, but maybe as boolean arithmetic with being the „exclusive or“, being the „and“ etc.

# Integers in Perl 6

The language Perl 6 has been announced to be production ready by the beginning of this year. Its implementation is Rakudo, while the Perl 6 programming language itself is an abstract language definition that allows any language implementation that passes the test suite to call itself an Perl 6 implementation. The idea is not totally new, we see the Ruby language being implemented more than once (Ruby, JRuby, Rubinius, IronRuby), but we can also learn from the Ruby guys that it is a challenge to keep this up to date and eventually it is likely that one implementation will fall back or go its own way at some point of time.

Perl 6 is also called „Perl“ as part of its name, but quite different from its sister language Perl, which is sometimes called „Perl 5“ to emphasize the distinction, so it is absolutely necessary to call it „Perl 6“ or maybe „Rakudo“, but not just „Perl“.

Even though many things can be written in a similar way, a major change to Perl 5 is the way of dealing with numeric types. You can find an article describing Numeric Types in Perl [5]. So now we will see how to do the same things in Perl 6.

Dealing with numeric types in Perl 6 is neither like in Perl 5 nor like what we are used to in many other languages.

So when we just use numbers in a naïve way, we get long integers automatically:

my $f = 2_000_000_000; my$p = 1;
loop (my Int $i = 0;$i < 10; $i++) { say($i, " ", $p);$p *= $f; }  creates this output: 0 1 1 2000000000 2 4000000000000000000 3 8000000000000000000000000000 4 16000000000000000000000000000000000000 5 32000000000000000000000000000000000000000000000 6 64000000000000000000000000000000000000000000000000000000 7 128000000000000000000000000000000000000000000000000000000000000000 8 256000000000000000000000000000000000000000000000000000000000000000000000000 9 512000000000000000000000000000000000000000000000000000000000000000000000000000000000  This is an nice default, similar to what Ruby, Clojure and many other Lisps use, but most languages have a made a choice that is weird for application development. Now we can also statically type this: my Int$f = 2_000_000_000;
my Int $p = 1; loop (my Int$i = 0; $i < 10;$i++) {
say($i, " ",$p);
$p *=$f;
}


and we get the exact same result:

0 1
1 2000000000
2 4000000000000000000
3 8000000000000000000000000000
4 16000000000000000000000000000000000000
5 32000000000000000000000000000000000000000000000
6 64000000000000000000000000000000000000000000000000000000
7 128000000000000000000000000000000000000000000000000000000000000000
8 256000000000000000000000000000000000000000000000000000000000000000000000000
9 512000000000000000000000000000000000000000000000000000000000000000000000000000000000


Now we can actually use low-level machine integers which do an arithmetic modulo powers of 2, usually or :

my int $f = 2_000_000_000; my int$p = 1;
loop (my Int $i = 0;$i < 10; $i++) { say($i, " ", $p);$p *= $f; }  and we get the same kind of results that we would get in java or C with (signed) long, if we are on a typical 64-bit environment: 0 1 1 2000000000 2 4000000000000000000 3 -106958398427234304 4 3799332742966018048 5 7229403301836488704 6 -8070450532247928832 7 0 8 0 9 0  We can try it in Java. I was lazy and changed as little as possible and the "$" is allowed as part of the variable name by the language, but of course not by the coding standards:

public class JavaInt {
public static void main(String[] args) {
long $f = 2_000_000_000; long$p = 1;
for (int $i = 0;$i < 10; $i++) { System.out.println($i + " " +  $p);$p *= $f; } } }  We get this output: 0 1 1 2000000000 2 4000000000000000000 3 -106958398427234304 4 3799332742966018048 5 7229403301836488704 6 -8070450532247928832 7 0 8 0 9 0  And we see, with C# we get the same result: using System; public class CsInt { public static void Main(string[] args) { long f = 2000000000; long p = 1; for (int i = 0; i < 10; i++) { Console.WriteLine(i + " " + p); p *= f; } } }  gives us: 0 1 1 2000000000 2 4000000000000000000 3 -106958398427234304 4 3799332742966018048 5 7229403301836488704 6 -8070450532247928832 7 0 8 0 9 0  If you like, you can try the same in C using signed long long (or whatever is 64 bits), and you will get the exact same result. Now we can simulate this in Perl 6 also using Int, to understand what int is really doing to us. The idea has already been shown with Ruby before: my Int$MODULUS = 0x10000000000000000;
my Int $LIMIT = 0x8000000000000000; sub mul($x, $y) { my Int$result = ($x *$y) % $MODULUS; if ($result >= $LIMIT) {$result -= $MODULUS; } elsif ($result < - $LIMIT) {$result += $MODULUS; }$result;
}

my Int $f = 2_000_000_000; my Int$p = 1;
loop (my Int $i = 0;$i < 10; $i++) { say($i, " ", $p);$p = mul($p,$f);
}


and we get the same again:

0 1
1 2000000000
2 4000000000000000000
3 -106958398427234304
4 3799332742966018048
5 7229403301836488704
6 -8070450532247928832
7 0
8 0
9 0


The good thing is that the default has been chosen correctly as Int and that Int allows easily to do integer arithmetic with arbitrary precision.

Now the question is, how we actually get floating point numbers. This will be covered in another blog posting, because it is a longer story of its own interest.

# What do +, – and * with Integer do?

When using integers in C, Java or Scala, we often use what is called int.

It is presented to us as the default.

And it is extremely fast.

Ruby uses by default arbitrary length integers.

But what do +, – and * mean?

We can rebuild them, in Ruby, kind of artificially restrict the integers to what we have in other programming langauges as int:

 MODULUS = 0x100000000; LIMIT   =  0x80000000;

 def normalize(x)   r = x % MODULUS;   if (r < -LIMIT) then     return r + MODULUS;   elsif (r >= LIMIT)      return r - MODULUS;   else     return r;   end end def intPlus(x, y)   normalize(x+y); end def intMinus(x, y)   normalize(x-y); end def intTimes(x, y)   normalize(x*y); end 

x = 0x7fffffff; y = intPlus(x, x); z = intPlus(x, x); puts("x=#{x} y=#{y} z=#{z}"); 

What is the outcome?

Exactly what you get when doing 32-Bit-Ints in C, Java, Scala or C#:
 x=2147483647 y=-2 z=-2 

int is always calculated modulo a power of two, usually . That is the
x % MODULUS  in normalize(). The Rest of the function is just for normalizing the result to the range .

So we silently get this kind of result when an overflow situation occurs, without any notice.
The overflow is not trivial to discover, but it can be done.
For addition I have described how to do it.

See also Overflow of Integer Types, an earlier post about these issues…

I gave a talk that included this content adapted for Scala at Scala Exchange 2015.

# Creating Unique Numbers

Many software systems rely on some kind of unique numbers. Uniqueness is always a question in what universe this uniqueness is required. We do see the different kinds of universes in the case of the IP-addresses. In theory they are world wide unique. In practice we have mechanisms in place like NAT, that use certain dedicated IP-ranges for an intranet and map them to publicly available addresses for internet traffic outside the intranet. So we already have two kinds of universes… This is typical.

A common case are database IDs, that are often used as primary keys in databases. I do challenge this by the question, if there is a natural key already available in the data, which might make this db internal id unnecessary, but more often than not DB tables do have these ID columns as primary keys. They have to be unique within the DB table. Which can mean across several servers, because somewhat distributed databases are common.

Other examples are message ids of emails. They may be quite long, a short line of text is acceptable and they should be world wide unique. Combining the fully qualified publicly accessible hostname and a time stamp and a counter is usually good enough. They look like this 5AE.630049D.2EA050907@gmx.net or 5AE.630049D.2EA050907@ms-93424.gmx.net, where the part after the „@“ stands for the mail server and the part in front is a unique id for the message created by the mail server and looking slightly different depending on its software.

Often the length is not arbitrary and the UUIDs are a good compromise for this. They have 128 bits, some of which are used to specify the type of UUID. One type combines a hostname and timestamp like the message ids. But since in some contexts the generation of the UUID should not reveal the hostname and the time, some implementations prefer random UUIDs. It can very well be argued that with good random numbers duplicates of such random UUIDs are less likely than events that would bother us much more than having a duplicate. For randomly generated UUIDs six bits are used up for expressing the version and the fact that it is a random UUID, leaving 122 bits, which is a total of different possible values. Generating billions of UUIDs for many years leaves the risk of creating duplicates acceptably low.

But the issue of the quality of the random generator and the issue of potential duplicates remain something that needs attention. So it is worth to consider the path of using the host and timestamp. Now the host can not be identified by an IP address or fully qualified domain and host name, because these tend to be either too long or not unique enough. The MAC address used to be a good possibility. But I would not be so sure about this any more. Most server systems are virtualized these days and the MAC address is configured by software, so duplicates can occur accidentally or deliberately. Using a time stamp by itself can be a problem too because sooner or later it will happen that two IDs are generated at the same time, within the given granularity. Machines have several processors, run several processes and several threads within each process.

So achieving the goal of a real globally unique UUID value remains a difficult question. Following a more local uniqueness within an application or application landscape might be more reasonable. The number of servers may be large and may vary, but it should be possible to assign numbers to virtual or real servers. In case there are multiple different processes on the same (virtual) machine to assign numbers to these as well. This can be used as a replacement for the host part of the UUID. If it does not use up all the bits, these can be filled up with random numbers.

Timestamps can be obtained easily and relatively reliably for a granularity of msec (Milliseconds). The UUID timestamp allows up to a granularity of 100 nsec, which is 10’000 sub divisions of the msec. A thread safe counter that may reset during program start or with its overflow can be used to count and its positive remainder modulo 10’000 can be used instead of the 100 nsec part in conjunction with the msec.

Often a uniqueness within an application or application landscape can be achieved by using some kind of unique counter. The best choice is often the sequence of a database, which is good in this task and well tested. It is not too hard to create such a functionality. Handling of multiple processes and threads needs to be addressed. For persistence, it can be an improvement to reserve blocks of 100 or 1000 numbers and persist less often. This will result in skipping some numbers when restarting, but otherwise work out well. The same idea can also be applied for a distributed unique number generator, where each instances gets ranges from some master generator and gets new ranges, when they are used up.

Such unique numbers or identifiers are needed quite often. It is usually best to use something that works reliably, like the DB sequence. But it can be developed with adequate care, if there is a need. Testing and especially automated testing is off course very important, but only sufficient if the whole implementation is conceptionally sound and robust.

# Find the next entry in a sequence

In Facebook, Xing, Google+, Vk.com, Linkedin and other of these social media networks we are often encountered with a trivial question like this:
 1->2 2->8 3->18 4->32 5->50 6->72 7->? 
There are some easy patterns. Either it is some polynomial formula or some trick with the digits.
But the point is, that any such sequence can easily be fullfilled by a polynomial formula. That means we can put any value for 7 and make it work. Or any answer is correct. So what would probably be the real question is the most simple function to full-fill the given constraints. Simplicity can be measured in some way… If the solution is unique is unclear, but let us just look at the polynomial solution.

A function is needed that takes as parameter a list of key-value-pairs (or a hash map) and that yields a function such that the function of any of the key is the associated value.

Assuming a polynomial function in one variable we can make use of the chinese remainder theorem, which can be applied to univariate polynomials over a field as well as to integral numbers. For a polynomial p(X) we have

where is the polynomial variable and is a concrete value.

We are looking for a polynomial such that for given values we have

or in another way

which is exactly the Chinese remainder theorem.
Let

and

We can see that for all the polynomials

have the properties

or

where is the Kronecker symbol, which is 0 if the two indices differ and 1 if they are equal.
Or as congruence:

Then we can just combine this and use

This can easily be written as a Ruby function
 def fun_calc(pairs)   n = pairs.size   result = lambda do |x|     y = 0     n.times do |i|       p_i = pairs[i]       x_i = p_i[0].to_r       y_i = p_i[1].to_r       z = y_i       n.times do |j|         if (j != i)           p_j = pairs[j]           x_j = p_j[0]           z *= (x - x_j) / (x_i - x_j)         end       end       y += z     end     y   end   result end 
This takes a list of pairs as a parameter and returns the polynomial function als lambda.
It can be used like this:
 lop = [[0, 0], [1, 1], [2, 4], [3, 9], [4, 16], [5, 25], [6, 36], [7, 64]]

 f = fun_calc(lop) 

20.times do |x|   y = f.call(x)   puts sprintf("%6d -> %6d", x, y) end 
Put this together into a ruby program and add some parsing for the list of pairs or change the program each time you use it and all these „difficult“ questions „that 99.9% fail to solve“ are not just easy, but actually soluble automatically.

This is interesting for more useful applications. I assume that there will always be situations where a function is needed that meets certain exact values a certain inputs and is an interpolation or extrapolation of this.

Please observe that there are other interesting and useful ways to approach this:

• Use a „best“ approximation from a set of functions, for example polynomials with a given maximum degree
• use cubic splines, which are cubic polynomials within each section between two neighboring input values such that at the input values the two adjacent functions have the same value (, of course), the same first derivative and the same second derivative.

For highway and railroad construction other curves are used, because the splines are making an assumption on what is the -axis and what is the -axis, which does not make sense for transport facilities. They are using a curve called Clothoid.

Use Java, C, Perl, Scala, F# or the programming language of your choice to do this. You only need Closures, which are available in Java 8, F#, Scala, Perl, Ruby and any decent Lisp dialect. In Java 7 they can be done with an additional interface as anonymous inner classes. And for C it has been described in this blog how to do closures.

# How to multiply long numbers

Assuming we have a multiplication of n-bit-numbers already available.
Other than typical compiled languages, which assume that the multiplication result fits into the same size as the two factors, we should take a closer look.
Unsigned n-bit-numbers as factors and fullfill

So we have for the product

So we should be prepared for a 2n-bit long result. Assembly language provides for this. In Java we are kind of running out of luck, because we have the 64-bit-long as the largest possible value, so we cannot make use of the 64-bit capabilities of our CPU by getting a 128-bit-result. Even worse we do not have unsigned primitive types. For addition and subtraction it is possible to cheat by assuming that the longs are unsigned, because the addition for signed and unsigned numbers is almost the same, but for multiplication this is slightly more complex.

In C we do have better chances, but we need to go compiler and OS-specific to some extent. gcc on 64-bit platforms has a type __uint128_t and we can hope that something like this
 __uint128_t mul(unsigned long long x, unsigned long long y) { __uint128_t xx = (__uint128_t) x; __uint128_t yy = (__uint128_t) y; __uint128_t z = xx*yy; return z; } 
is optimized by the compiler to one assembly language instruction that multiplies two unsigned 64-bit-integers into one unsigned 128-bit integer.

Multiplication of longer numbers is achieved by just assuming

with

Now the product is

where each summand needs to be split into a lower and an upper part such that

All these half products need to be added with propagating the carry bits to the next higher level.
This can be sorted out and done with a lot of additions with carry-bit, finally giving the desired result.

For reasonably short numbers this is a good approach, if it is done well, but it can be replaced by better algorithms for larger numbers.

The most obvious next step is to move to the Karatsuba algorithm.
Assuming we have two factors and the naïve approach of having to calculate the four products
, , , can be replaced by calculation of only three products , , , because what is actually needed is the sum which can be obtained by

That can be iterated by subdividing the numbers subsequently into halves until a size is reached that can be handled well enough by the naïve approach.
An issue that needs to be observed is that and need one bit more than their summands.

For even larger numbers the so called Toom-Cook algorithm, an extension of the idea of the Karatsuba-algorithm for more than two summands, can be useful and for numbers larger than that the Schönhage-Strassen multiplication proves to be faster. It is implemented in some libraries for long integer arithmetic, like GMP. Since around 2007 this can be improved by using the Fürer algorithm which is assymptotically faster, but I do not know of any useful implementations and for practical purposes the improvement does not seem to be very relevant.