# Borrow and Carry Bit for Subtraction

Similar to the usage of the carry bit when adding there are mechanisms for subtracting that allow to integrate the result of subtraction of the lower bits into the subtraction of the next higher block of bits, where necessary.

There are two ways to do this, that are trivially equivalent by a simple not operation:

• borrow bit (also borrow flag)
• carry bit (also carry flag)

Often CPUs use what is the carry bit for addition and interpret it as borrow bit for subtraction.

Here are the two ways:

## Borrow Bit

It is assumed, that the CPU-word is bits long, so calculations are performed modulo . Further it is assumed, that the range is preferred, so all sign issues are excluded for the moment.

When subtracting two numbers , from each other like and , the provided result is

and the borrow bit is set (), to indicate that the subtraction caused „underflow“, which had to be corrected by added in order to get into the desired range.

In the „normal“ case where , the provided result is simply

and the borrow bit is not set ().

The next round of subtraction takes the borrow bit into account and calculates , where the condition becomes and the result is

or

respectively. This is how some of the older readers used to do it in school on paper, but of course with .

Now the typical integer arithmetic of current CPUs uses Two’s complement, which means that . Combining this with the previous results in calculating

At this point some CPU-designers found it more natural, to use the carry bit instead of the borrow bit .

## Carry Bit

When subtracting two numbers , from each other like and we have , the provided result is

and the carry bit is not set (), to indicate that the subtraction caused „underflow“, which had to be corrected by added in order to get into the desired range.

In the „normal“ case where , the provided result is simply

and the carry bit is set ().

The next round of subtraction takes the borrow bit into account and calculates , where the condition becomes and the result is

or

respectively.

Now two’s complement with this can be written as

or with

These two ways are really equivalent and easily transformed into each other. Neither of them provides big advantages, apart from the fact that we have the unnecessary confusion, because it depends on the CPU design, which of the two variants is used.

## Recovery of Borrow or Carry bit

The borrow bit is calculated and used during subtractions that are done at assembly language level, but higher languages like C or Java do provide access to this information. It is relatively easy to recover the carry bit in the case of addition based on , and .

This possible as well for the subtraction. Quite easily the comparison between and or could be done before the subtraction. This would work, but it is kind of inefficient, because under the hood the comparison is just a subtraction with discarding the result and keeping the flags. So the subtraction is performed twice. This might not be such a bad idea, because a compiler could recognize it or the work of subtracting twice could be neglectable compared to the logic for an „optimized“ recovery, based on some logic expression of certain bits from , and .

# 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 :

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.

# Logging

Deutsch

Software often contains a logging functionality. Usually entries one or sometimes multiple lines are appended to a file, written to syslog or to stdout, from where they are redirected into a file. They are telling us something about what the software is doing. Usually we can ignore all of it, but as soon as something with „ERROR“ or worse and more visible stack traces can be found, we should investigate this. Unfortunately software is often not so good, which can be due to libraries, frameworks or our own code. Then stack traces and errors are so common that it is hard to look into or to find the ones that are really worth looking into. Or there is simply no complete process in place to watch the log files. Sometimes the error shows up much later than it actually occurred and stack traces do not really lead us to the right spot. More often than we think logging actually introduces runtime errors, that were otherwise not present. This is related to a more general concept, which is called observer effect, where logging actually changes the business logic.

It is nice that log files keep to some format. Usually they start with a time stamp in ISO-format, often to the millisecond. Please add trailing zeros to always have 3 digits after the decimal point in this case. It is preferable to use UTC, but people tend to stick to local date and time zones, including the issues that come with switching to and from daylight saving time. Usually we have several processes or threads that run simultaneously. This can result in a wild mix of logging entries. As long as even multiline entries stay together and as long as beginning and end of one multiline entry can easily be recognized, this can be dealt with. Tools like splunk or simple Perl, Ruby or Python scripts can help us to follow threads separately. We could actually have separate logs for each thread in the first place, but this is not a common practice and it might hit OS-limitations on the number of open files, if we have many threads or even thousands of actors as in Erlang or Akka. Keeping log entries together can be achieved by using an atomic write, like the write system call in Linux and other Posix systems. Another way is to queue the log entries and to have a logger thread that processes the queue.

Overall this area has become very complex and hard to tame. In the Java world there used to be log4j with a configuration file that was a simple properties file, at least in the earlier version. This was so good that other languages copied it and created some log4X. Later the config file was replaced by XML and more logging frame works were added. Of course quite a lot of them just for the purpose of abstracting from the large zoo of logging frameworks and providing a unique interface for all of them. So the result was, that there was one more to deal with.

It is a good question, how much logic for handling of log files do we really want to see in our software. Does the software have to know, into which file it should log or how to do log rotation? If a configuration determines this, but the configuration is compiled into the jar file, it does have to know… We can keep our code a bit cleaner by relying on program functionality without code, but this still keeps it as part of the software.

Log files have to please the system administrator or whoever replaced them in a pure devops shop. And in the end developers will have to be able to work with the information provided by the logs to find issues in the code or to explain what is happening, if the system administrator cannot resolve an issue by himself. Should this system administrator have to deal with a different special complex setup for the logging for each software he is running? Or should it be necessary to call for developer support to get a new version of the software with just another log setting, because the configurations are hard coded in the deployment artifacts? Interesting is also, what happens when we use PAAS, where we have application server, database etc., but the software can easily move to another server, which might result in losing the logs. Moving logs to another server or logging across the network is expensive, maybe more expensive than the rest of this infrastructure.

Is it maybe a good idea to just log to stdout, maintaining a decent format and to run the software in such a way that stdout is piped into a log manager? This can be the same for all software and there is one way to configure it. The same means not only the same for all the java programs, but actually the same for all programs in all languages that comply to a minimal standard. This could be achieved using named pipes in conjunction with any hard coded log file that the software wants to use. But this is a dangerous path unless we really know what the software is doing with its log files. Just think of what weird errors might happen if the software tries to apply log rotation to the named pipe by renaming, deleting, creating new files and so on. A common trick to stop software from logging into a place where we do not want this is to create a directory with the name of the file that the software usually uses and to write protect this directory and its parent directory for the software. Please find out how to do it in detail, depending on your environment.

What about software, that is a filter by itself, so its main functionality is to actually write useful data to stdout? Usually smaller programs and scripts work like this. Often they do not need to log and often they are well tested relyable parts of our software installation. Where are the log files of cp, ls, rm, mv, grep, sort, cat, less,…? Yes, they do tend to write to stderr, if real errors occur. Where needed, programs can turn on logging with a log file provided on the command line, which is also a quite operations friendly approach. Named pipes can help here.

And we had a good logging framework in place for many years. It was called syslog and it is still around, at least on Linux.

A last thought: We spend really a lot of effort to get well performing software, using multiple processes, threads or even clusters. And then we forget about the fact that logging might become the bottle neck.

# 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.

# Virtual machines

We all know that Java uses a „virtual machine“ that is it simulates a non-existing hardware which is the same independent of the real hardware, thus helping to achieve the well known platform independence of Java. Btw. this is not about virtualization like VMWare, VirtualBox, Qemu, Xen, Docker and similar tools, but about byte code interpreters like the Java-VM.

We tend to believe that this is the major innovation of Java, but actually the concept of virtual machines is very old. Lisp, UCSD-Pascal, Eumel/Elan, the Perl programming language and many other systems have used this concept long before Java. The Java guys have been good in selling this and it was possible to get this really to the mainstream when Java came out. The Java guys deserve the credit for bringing this in the right time and bringing it to the main stream.

Earlier implementations where kind of cool, but the virtual machine technology and the hardware were to slow, so that they were not really attractive, at least not for high performance applications, which are now actually a domain of Java and other JVM languages. Some suggest that Java or other efficient JVM languages like Scala would run even faster than C++. While it may be true to show this in examples, and the hotspot optimization gives some theoretical evidence how optimization that takes place during run time can be better than static optimization at compile time, I do not generally trust this. I doubt that well written C-code for an application that is adequate for both C and Java will be outperformed by Java. But we have to take two more aspects into account, which tend to be considered kind of unlimited for many such comparisons to make them possible at all.

The JVM has two weaknesses in terms of performance. The start-up time is relatively long. This is addressed in those comparisons, because the claim to be fast is only maintained for long running server applications, where start-up time is not relevant. The hotspot optimization requires anyway a long running application in order to show its advantages. Another aspect that is very relevant is that Java uses a lot of memory. I do not really know why, because more high level languages like Perl or Ruby get along with less memory, but experience shows that this is true. So if we have a budget X to buy hardware and then put software written in C on it, we can just afford to buy more CPUs because we save on the memory or we can make use of the memory that the JVM would otherwise just use up to make our application faster. When we view the achievable performance with a given hardware budget, I am quite sure that well written C outperforms well written Java.

The other aspect is in favor of Java. We have implicitly assumed until now that the budget for development is unlimited. In practice that is not the case. While we fight with interesting, but time consuming low level issues in C, we already get work done in Java. A useful application in Java is usually finished faster than in C, again if it is in a domain that can reasonably be addressed with either of the two languages and if we do not get lost in the framework world. So if the Java application is good enough in terms of performance, which it often is, even for very performance critical applications, then we might be better off using Java instead of C to get the job done faster and to have time for optimization, documentation, testing, unit testing.. Yes, I am in a perfect world now, but we should always aim for that. You could argue that the same argument is valid in terms of using a more high-level language than Java, like Ruby, Perl, Perl 6, Clojure, Scala, F#,… I’ll leave this argument to other articles in the future and in the past.

What Java has really been good at is bringing the VM technology to a level that allows real world high performance server application and bringing it to the main stream.
That is already a great achievement. Interestingly there have never been serious and successful efforts to actually build the JavaVM as hardware CPU and put that as a co-processor into common PCs or servers. It would have been an issue with the upgrade to Java8, because that was an incompatible change, but other than that the JavaVM remained pretty stable. As we see the hotspot optimization is now so good that the urge for such a hardware is not so strong.

Now the JVM has been built around the Java language, which was quite legitimate, because that was the only goal in the beginning. It is even started using the command line tool java (or sometimes javaw on MS-Windows 32/64 systems). The success of Java made the JVM wide spread and efficient, so it became attractive to run other languages on it. There are more than 100 languages on the JVM. Most of them are not very relevant. A couple of them are part of the Java world, because they are or used to be specific micro languages closely related to java to achieve certain goals in the JEE-world, like the now almost obsolete JSP, JavaFX, .

Relevant languages are Scala, Clojure, JRuby, Groovy and JavaScript. I am not sure about Jython, Ceylon and Kotlin. There are interesting ideas coming up here and there like running Haskell under the name Frege on the JVM. And I would love to see a language that just adds operator overloading and provides some preprocessor to achieve this by translating for example „(+)“ in infix syntax to „.add(..)“ mainstream, to allow seriously using numeric types in Java.

Now Perl 6 started its development around 2000. They were at that time assuming that the JVM is not a good target for a dynamic language to achieve good performance. So they started developing Parrot as their own VM. The goal was to share Parrot between many dynamic languages like Ruby, Python, Scheme and Perl 6, which would have allowed inter-language inter-operation to be more easily achievable and using libraries from one of these languages in one of the others. I would not have been trivial, because I am quite sure that we would have come across issues that each language has another set of basic types, so strings and numbers would have to be converted to the strings and numbers of the library language when calling, but it would have been interesting.

In the end parrot was a very interesting project, theoretically very sound and it looked like for example the Ruby guys went for it even faster than the the Perl guys, resulting in an implementation called cardinal. But the relevant Perl 6 implementation, rakudo, eventually went for their own VM, Moar. Ruby also did itself a new better VM- Many other language, including Ruby and JavaScript also went for the JVM, at least as one implementation variant. Eventually the JVM proved to be successful even in this area. The argument to start parrot in the first place was that the JVM is not good for dynamic languages. I believe that this was true around 2000. But the JVM has vastly improved since then, even resulting in Java being a serious alternative to C for many high performance server applications. And it has been improved for dynamic languages, mostly by adding the „invoke_dynamic“-feature, that also proved to be useful for implementing Java 8 lambdas. The experience in transforming and executing dynamic languages to the JVM has grown. So in the end parrot has become kind of obsolete and seems to be maintained, but hardly used for any mainstream projects. In the end we have Perl 6 now and Parrot was an important stepping stone on this path, even if it becomes obsolete. The question of interoperability between different scripting languages remains interesting…

# 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.

Addition 2019-10-08: In 2019 an algorithm has been discovered, that is assumed to be assymptotically , which is according to a conjecture of Schönhage the best possible result. It has not yet been proven rigorously and the conjecture is still a conjecture. The question is, if for practical purposes of multiplying numbers that still fit into real computers, there is a real gain from these algorithms. So the questions is, if they become faster than Schönhage-Strassen on numbers that are not too long to be practically multiplied. So right now this is really mostly an issue of mathematics and theoretical informatics. See also Maths whiz solves 48-year-old multiplication problem.. And see for the paper.

# How to recover the Carry Bit

As frequent readers might have observed, I like the concept of the Carry Bit as it allows for efficient implementations of long integer arithmetic, which I would like to use as default integer type for most application development. And unfortunately such facilities are not available in high level languages like C and Java. But it is possible to recover the carry bit from what is available in C or Java, with some extra cost of performance, but maybe neglectable, if the compiler does a good optimization on this. We might assume gcc on a 64-Bit-Linux. It should be possible to do similar things on other platforms.

So we add two unsigned 64-bit integers and and an incoming carry bit to a result

with

using the typical „long long“ of C. We assume that

where

and

. In the same way we assume and with the same kind of conditions for , , or , , , respectively.

Now we have

and we can see that

for some

.
And we have

where

is the carry bit.
When looking just at the highest visible bit and the carry bit, this boils down to

This leaves us with eight cases to observe for the combination of , and :

x_hy_huz_hc
00000
10010
01010
11001
00110
10101
01101
11111

Or we can check all eight cases and find that we always have

or

So the result does not depend on anymore, allowing to calculate it by temporarily casting , and to (signed long long) and using their sign.
We can express this as „use if and use if „.

An incoming carry bit does not change this, it just allows for , which is sufficient for making the previous calculations work.

In a similar way subtraction can be dealt with.

The basic operations add, adc, sub, sbb, mul, xdiv (div is not available) have been implemented in this library for C. Feel free to use it according to the license (GPL). Addition and subtraction could be implemented in a similar way in Java, with the weirdness of declaring signed longs and using them as unsigned. For multiplication and division, native code would be needed, because Java lacks 128bit-integers. So the C-implementation is cleaner.

# Restklassenrundung

English

Das Konzept der Rundung kennt man grundsätzlich. Aber versuchen wir es etwas systematischer zu erfassen.

Man hat eine Menge von Zahlen und eine Teilmenge davon, deren Elemente in der verwendeten Programmierumgebung dargestellt werden. Dazu hat man noch eine Metrik . Man verlangt normalerweise noch gewisse Eigenschaften von :

• Positive Definitheit:
• Symmetrie:
• Dreiecksungleichung:

Typischerweise sind die Zahlen, mit denen wir uns meistens beschäftigen, in der Welt der reellen und komplexen Zahlen gedacht, man kann also fast immer sicher sein, dass ist, meistens sogar oder wenn wir ehrlich sind sogar . Dann ist normalerweise . Wer die komplexen Zahlen noch nicht kennt, denke einfach an reelle und rationale Zahlen, das ist das, womit wir normalerweise bewusst zu tun haben. Dabei sind natürlich Konzepte wie Rundung speziell in -adischen Zahlen hochinteressant, aber dafür muss ich die erstmal erklären und das lasse ich heute…

Was stellen wir uns nun unter einer Rundung vor?
Vielleicht eine Abbildung
,
die mit gewissen Nebenbedingungen für jedes x jeweils so gewählt wird, dass minimal ist.
Die Nebenbedingungen brauchen wir einerseits, um es eindeutig zu machen, wenn mehrere Werte existieren, für die minimal ist. Der klassische Fall ist das Runden auf ganzzahlige Werte und die Frage mit der . Wenn eine Teilmenge der reellen Zahlen ist, was ja „meistens“ der Fall ist, hat man eine Anordung. Da kommen dann die folgenden Constraints zum Tragen (Beispiel immer mit Rundung auf ganze Zahlen):

ROUND_UP
Z.B. und und
ROUND_DOWN
Z.B. und und
ROUND_CEILING
Z.B. und und
ROUND_FLOOR
Z.B. und und
ROUND_HALF_UP
Minimiere , aber wenn es mehrere optimale Werte für gibt, wähle den am weitesten von 0 entfernten, z.B. und und und
ROUND_HALF_DOWN
Minimiere , aber wenn es mehrere optimale Werte für gibt, wähle den am nächsten an 0, z.B. und und und
ROUND_HALF_CEILING
Minimiere , aber wenn es mehrere optimale Werte für gibt, wähle den größten, z.B. und und und
ROUND_HALF_FLOOR
Minimiere , aber wenn es mehrere optimale Werte für gibt, wähle den kleinesten, z.B. und und und
ROUND_HALF_EVEN
Minimiere , aber wenn es mehrere optimale Werte für gibt, wähle den mit gerader Endziffer. Achtung, dieser Constraint ist im „klassischen“ Fall anwendbar, aber nicht allgemeingültig. Z.B.: und und und und
ROUND_UNNECESSARY
Dieser Constraint ist im mathematischen Sinne nicht geeignet (oder nur mit hässlichen Verrenkungen), aber programmatisch können wir das: Wir nehmen und schmeißen eine Exception wenn nicht schon gilt.

Typischerweise denken wir im Dezimalsystem und dann wählen wir eine Zehnerpotenz mit , also . Nun ist einfach
,
also umgangsprachlich sind in alle Zahlen aus mit maximal Stellen nach dem Komma. Diese Rundung funktioniert ganz gut mit so etwas wie LongDecimal in Ruby oder BigDecimal in Scala oder Java, wobei BigDecimal weniger Rundungsmodi anbietet als LongDecimal für Ruby.

Nun kommen wir zur Restklassenrundung. Wir gehen wieder von dieser Zehnerpotenz aus. Dann brauchen wir noch eine natürlich Zahl und eine Menge von Resten . Nun ist
.
Das bedeutet, wenn wir mit Nullen auf die angegebene Anzahl von Nachkommastellen auffüllen, das „Komma“ (normalerweise als „.“ geschrieben) weglassen und dann diese Zahl mit Rest durch teilen, der dabei herauskommende Rest in liegt.
In diesem Fall wird es mit dem ROUND_HALF_EVEN eventuell schwierig, da es undefiniert oder mehrdeutig werden kann. Aber wir müssen auch den Fall abdecken, dass die 0 nicht in ist und Regeln angeben, wohin die 0 gerundet werden soll. Die Kandidaten sind hier mit selbsterklärenden Namen versehen:

• ZERO_ROUND_TO_PLUS
• ZERO_ROUND_TO_MINUS
• ZERO_ROUND_TO_CLOSEST_PREFER_PLUS
• ZERO_ROUND_TO_CLOSEST_PREFER_MINUS
• ZERO_ROUND_UNNECESSARY

Ein wichtiger Anwendungsfall ist hier und . So kann man in der Schweiz Geldbeträge auf Vielfache von 5 Rappen (0.05 CHF) runden. Dies wurde in Rundung bei Geldbeträgen bereits genauer beschrieben.

# Scala Exchange 2014

English

Ich war am 8. und 9. Dezember 2014 auf der Konferenz Scala Exchange ( #scalaX ) in London.

Von mir besuchte Vorträge waren etwa folgende:

# The Binary Compatibility Challenge

## Martin Odersky

Es gibt Beispiele von allen vier Kombinationen von Sourcecode- und Binärkompatibilität.
Man wünscht sich von beidem mehr, Schwerpunkt heute aber Binärkompatibilität.
Konflikt für Scala: Innovation vs. Kompatibilität. Java hat den einen Extrempfad gewählt, Kompatibilität über alles, hat es aber auch leichter gehabt, weil Java die JVM mit „kontrolliert“. Clojure, Ruby, JRuby, Perl,… haben alle kein Problem mit Binärkompatibilität, weil sie in der Regel „just in time“ compiliert werden, also nur Quelltexte herumgereicht werden.
Reproduzierbare Builds sind in Scala schwierig, man denke alleine an die viele Build-Tools (ivy, gradle, maven, sbt,…)
Idee: nach etwa 10 der etwa 30 Schritte des Kompilierens den Baum des Programms in einem cleveren Binärformat speichern. Dieses Format ist ein bessere Kompromiss und von dort kann man leichter fertig-kompilieren.

# REST on Akka: Connect to the world

## Mathias Doenitz

Akka-http ist quasi Spray 2.0 oder Nachfolger für Spray.
Das sollte wegen der reactive Streams in Akka sein.
Verwende TCP-Flow-Control für „Backpressure“.

# Bootstrapping the Scala.js Ecosystem

## Haoyi Li

Scala wird nach Javascript statt JVM compiliert. Target ist eindeutig der Browser, weniger serverseitiges JS, wo man ja die JVM meist einsetzen kann.
Vorteil für Web-Applikationen: selbe Tag-Generierung, Validierung etc. auf Browser- und Serverseite. Eleganter als zwei Sprachen.
Einschränkungen: Libraries zu übertragen ist schwierig, da sie groß sind.
Keine Reflection auf scala.js verfügbar. Damit geht vieles nicht, aber es bleibt genug, was geht. Serialisierung eine Herausforderung, aber gelöst.
Testing riesige Herausforderung, gelöst halbwegs mit Teilmenge von scalatest.
Integer-Typen sind ein bisschen ein Gebastel, weil JS nur double kennt, was 53 bit entspricht. Long muss also mit zwei doubles nachgebildet werden.

# Introduction to Lambda Calculus

## Maciek Makowski

Sehr theoretischer Vortrag. Lambdacalculus wie Programmiersprache, Berechenbarkeitstheorie etc. Viele schöne Beweise möglich. Die theoretische Essenz der funktionalen Programmierung ist das. Stichworte: „Church Rosser Theorem“, „Programmierung mit Lambda-Kalkül“, „Zahlen als Lambda-Ausdrücke“ (church encoding), „y combinator“, „fixed point combinator“, „lambda cube“, „vierte Dimension für Subtypen“, ….
Sehr kleine Sprache, toll für Beweise, nicht für die Praxis brauchbar.

# State of the Typelevel

## Lars Hupel

Typelevel ist von Haskell inspiriert. Bibliotheken u.a. scalaz, shapeless, spire, scalaz-stream, monocle,….
Wir sollten anstreben, korrekte Programme zu schreiben und optimieren wenn nötig.
Die JVM-Integer-Typen sind nicht gut. Fließkommazahlen sind gut für numerische Mathematiker und in dem Bereich gebildete Wissenschaftler, die sich mit Fehlerfortpflanzung auskennen.
Natürlich behandeln wir Zahlen als Funktionen, z.B.
mit
Gleichheit von Reelen Zahlen ist nicht in endlicher Zeit entscheidbar.
Was ist „Costate command coalgebra“? Monocle behandelt „lenses“ und ähnliche Dinge, die man aus Haskell kennt…
Gute binäre Serialisierungsformate sind in der JVM-Welt rar.
Wie geht man mit der Angst vor scalaZ und Monaden um?

# Slick: Bringing Scala’s Powerful Features to Your Database Access

## Rebecca Grenier

Slick ist eine Library, die SQL-Queries generiert und dann ausführt. Die konzeptionellen Schwächen von JPA werden geschickt umgangen.
Hat Treiber für die fünf großen DBs und einige kleinere. Aber für Oracle, DB2 und MS-SQL-Server nicht frei.
Innere und äußere Joins sind verfügbar und elegant zu schreiben. Slick kann mit dem Datenbank-Dictionary sogar Code generieren.

# Upcoming in Slick 2.2

## Jan Christopher Vogt

Monaden kommen auch hier vor. Zeit das endlich zu lernen. Ich werde einen Vortrag in der Ruby-on-Rails-Usergroup darüber halten, dann muss ich es lernen.
Sessions in Kombination mit Futures gibt lustige Albträume.
Wenigstens ist Slick theoretisch korrekt, im Gegensatz zu JPA.
Mehrere Statements kombinieren mit andThen oder for. Achtung, default verschiedene Sessions.
Threads sind teuer, Reactiveness ist wichtig. Futures und Threadpools, geht aber schief beim „blocking“.
JDBC kann nicht assynchron. Workaround oberhalb von JDBC scheint aber ausreichend zu sein und nur ein paar mehr Threads zu brauchen als die richtige Lösung, also verantwortbar.
Statisch gechecktes SQL?

# No more Regular Expressions

## Phil Wills

Ich mag Regex in Perl sehr. Warum also so etwas aufgeben?
Nun, man gibt es nicht wirklich auf, ändert nur die Schreibweise.
Die Schreibweise als String ist in Perl natürlich, in Scala ein Fremdkörper.
Daher typische programmatische Schreibweise angemessener, aber auch robuster bei Fehlern.
Verwende org-paraboiled2
Capture lieder positionell, tut aber viel weniger weh als bei klassischen regex.

# Scala eXchange – Q&A Panel

## Jon Pretty, Kingsley Davies, Lars Hupel, Martin Odersky, and Miles Sabin

Einige interessante Diskussionen…

# Why Scala is Taking Over the Big Data World

## Dean Wampler

Zitat (übersetzt): ‚“Hadoop“ ist das „EJB“ unserer Zeit.‘
MapReduce ist konzeptionell eigentlich schon funktionales Programmieren. Warum also Java und nicht Scala??
Stichwörter: „Scalding“, „Storm“, „Summing bird“, „Spark“.
Scala kann performanter als Python sein, das hier beliebt ist. Aber nicht überstürzt ablösen.

# Case classes a la carte with shapeless, now!

## Miles Sabin

Beispiel: Baum mit Rücklinks. Schwierig mit konsequenter Immutability. Shapeless hilft.

# Reactive Programming with Algebra

## André Van Delft

Algebra kann Spaß machen und nützlich für die Programmierung sein. Algebraische Interpretation eingeführt.
Webseite subscript-lang.org.
Algebra der kommunizierenden Prozesse. Sehr mächtig, auch für andere Gebiete anwendbar, etwa Betrieb von Bahnsystemen.
Jedes Programm, das Eingaben behandelt, ist auf eine Art ein Parser, also Ideen von yacc und bison interessant auch hier.

# High Performance Linear Algebra in Scala

## Sam Halliday

Lineare Algebra ist sehr gut gelöst, also sollte man das Rad nicht neu erfinden.
TL;D, Netflix und Breeze. Anwendungsbeispiel: Kalman Filter.
netlib hat Referenzimplementierung in Fortran. Wie bringt man das in die Scala-Welt?
Fortran mit C-Wrapper versehen, für JNI erreichbar. (cblas)
Fortran nach Java kompilieren. Ja.
Alternative Implementierung mit derselben Testsuite in C.
High-Performance geht nicht nur um Geschwindigkeit per se, sondern immer unter dem Aspekt der Korrektheit, Genauigkeit und Stabilität.
Hardware ist interessant: Die CPU-Hersteller reden mit dem netlib-Team.
Kann man GPU benutzen? Ja, aber Transfer der Daten schwierig.
FPGA? Vielleicht bald?
Oder sowas wie GPU, aber ohne echte Grafik und mit dem normalen RAM?

# An invitation to functional programming

## Rúnar Bjarnason

Referenzielle Transparenz, etwa die Kompatibilität mit dem Memoize-Pattern.
Pure Functions…
Parallelisierung
Verständlichkeit ist das ewige Versprechen. Warum wird es diesmal gehalten?
Funktionale Programmierung ist nicht gut für die „Schützengräben“ der reellen Aufgaben.
Aber gut, um aus den Schützengräben rauszukommen in vernünftigere Welten… So der Anspruch…

# Building a Secure Distributed Social Web using Scala & Scala-JS

## Henry Story

Spargl ist wie SQL für das „semantic web“.
Entwickelt mit Unterstützung von Oracle.
Wir können Relativität der Wahrheit haben, während wir die absolute Wahrheit aufrechterhalten. Der Vortrag war recht philosophisch.
Graphen können isomorph sein, aber verschieden hohes Vertrauen genießen, je nachdem, wo sie liegen.
Linked Data Protocol kommt ins Spiel
Wie verhindert man Spam und Missbrauch? WebID?
Hier geht es nicht um „Big Data“, sondern um massiv verteilte und parallele „small data“.

# TableDiff – a library for showing the difference between the data in 2 tables

## Sue Carter

Was ist für ein Diff die richtige Semantik?
Was will man sehen? Wie werden Zahlen und Zeichenketten in den Feldern verglichen?

# Evolving Identifiers and Total Maps

## Patrick Premont

Idee ganz kurz: eine Map, deren Get immer etwas zurückgibt. Durch geschickte Typ-Konzepte wird verhindert, dass ein Aufruf, der ins Leere greifen würde, überhaupt compiliert.
Interessante Idee, finde sie aber eher theoretisch nützlich.

# Devoxx 2014

Im Jahr 2014 habe ich die Devoxx in Antwerpen besucht.

Hier sind ein paar Notizen dazu:

# Was ist Devoxx?

• Devoxx ist eine Konferenz der belgischen Java-User-Group
• Belgien ist dreisprachig, Konferenz aber 100% in Englisch
• Lokation in riesigem Kinokomplex guter Sound, gute Sitze, gute Projektoren, „cool“
• 8 tracks, bei Keynotes „overflow“
• Gut organisiert (dies Jahr sicher), unterhaltsamer als andere Konferenzen…
• Schwesterkonferenzen:
• Devoxx FR
• Devoxx PL
• Devoxx UK
• Voxxed (Berlin, Ticino,….)

• Java / Oracle
• Android / Oracle
• Startups, Business, IT in Großfirmen / ING-Bank
• Java-Server, JBoss, Deployment / Redhat
• JVM-Sprachen
• Web
• SW-Architektur
• Security
• Was sonst noch so ins Umfeld passt und sich jemand traut, vorzutragen…

# Scala und Java8

• Viele Features von Scala sind mit java8-Lambdas auch in Java verfügbar
• Problem: verschiedene Implementierung, Interoperabilität
• Bestrebung Scala weiterzuentwickeln damit lambdas von Java und von Scala besser miteinander interoperabel sind.

• Konzept aus der Kategorientheorie (5% der Mathematiker machen Algebra, 5% der Algebraiker machen Kategorientheorie, aber für funktionale Programmiersprachen plötzlich relevant)
• Monoid (+, *, concat,…)
• Funktor
Wikipedia de
Wikipedia en
• Beispiel List mit einem Functor
ist flatten: ;

# Probability & Decisions

• Thema: Software für automatische Steuerung
• Heuristik auf Wahrscheinlichkeitstheorie
• False positives / false negatives: was tut weh? (meistens beide…)
• Wahrscheinlichkeitstheorie und Verwendung gut erklärt

# Clojure

• Clojure ist eine andere JVM-Sprache
• Ein Lisp-Dialekt, zu erkennen daran, dass der Quelltext überwiegend aus runden Klammern besteht (+ (* 3 4) (* 5 6))…
• Dynamische Typisierung (für uns: Alles als „Object“ deklariert, implizite Casts bei Methodenaufrufen)
• Nach Java selbst, Scala, Groovy und Javascript die mir am fünfthäufigsten begegnende JVM-Sprache

# MapReduce

• „No one at Google uses MapReduce anymore“
• Optimierungen: spare Schritte, fasse zusammen etc.
• Als Cloud-Service angeboten (Cloud Dataflow)

# Key Note ING

• ING versteht sich als „open bank“
• Nicht gemeint, dass das Geld „offen“ rumliegt, aber offen für neue Ideen
• Schnittstelle zur Bank ist Mobile-App
• IT hat viel Einfluss („IT driven business“)
• Man schaut, was gut machbar ist
• Agile Prozesse (Scrum) vs. Enterprise IT
• Umbau der IT auf diese agilen Prozesse schrittweise
• „Enterprise IT is what does not work“

# Material Design

• Vortrag über GUI-Design mit Android und Web
Material Design
• Visuelle Ideen für beide Plattformen verfügbar
• Polymerdesign für Web

# SW-Architektur mit Spring

• Spring 4.1
• „works with WebSphere“
• DRY
• Lambda aus Java8 kann viele APIs vereinfachen statt anonymen inneren Klassen mit einer Methode
• Generic Messaging Interface (war JMS nicht schon das???)
• Caching, Achtung beim Testen abschaltbar
• Testen auf http://start.spring.io/
• Spring funktioniert mit Java gut, mit Groovy auch (aus demselben Haus…) mit Scala „experimentell“

# Lambda_behave

• High-Level testing-Framework
• Verwendet Java8-Features (Lambda etc)
• Beschreibung in natürlicher Sprache
• Failure-Meldungen lesbar
• Wie Cucumber…
• Zufallsquelle konfigurierbar (extrem wichtig für manche Tests!!)

# Builtin Types of Scala and Java

• In Java gibt es „primitive“ (long, int, byte, char, short, double,…)
• Probleme bei Arithmetik mit int, long & Co:  Überlauf findet unerkannt statt
• Mit float und double Rundungsfehler
• Mit BigInteger, BigDecimal, Complex, Rational fehleranfällige, umständliche und unlesbare Syntax
• In Scala kann man a=b*c+d*e auch für neu definierte numerische Typen schreiben.
• Anmerkung dazu: Oracle-Java-Leute finden Idee von Operator-Überladen für numerische Typen inzwischen interessant, solange man nicht Exceptions mit Collections multipliziert und durch Swing-Komponenten dividiert…
• Spire library

# Zukunft von Java (9, 10, …)

## Teil I

• Q&A-Sitzung (Fragen per Twitter schreiben)
• Numerische Typen sind Thema. Dass primitive Typen sich so verhalten wie heute und quasi der „default“ sind, wird sich nicht ändern
• Thema Generics und Type-Erasure (wo ist das Problem)?
• Jigsaw vs. Jars vs. OSGi  noch offen, aber jar bleibt
• Jigsaw-Repository  Wird man wohl bei maven-Central, Oracle funktioniert nicht so, dass sie jigsaw-Repository für third-Party bei sich hosten

## Teil II

• Benchmarking mit Java schwierig wegen hotspot-Optimierung
• JMH gutes Tool dafür
• Neue Ideen immer schwierig umzusetzen, weil man kompatibel zu alten Versionen sein will.
• Java bekommt vielleicht „repl“

## Teil III

• Collection literals (für Java 7 versprochen!!!) sind für Java8 nicht gekommen, für Java9 unwahrscheinlich
• Mit Value-Types aber eher zu haben, daher nicht vorher…
• Für Set und List mittels
new TreeSet(Arrays.asList(m1, m2, m3,…., mn))
schon heute einigermaßen darstellbar
• Für Maps wenn man sowas wie Pair-hätte, was wiederum auf „Tupel“ aufbaut, die kommen werden, wenn es Value-Types gibt

## Teil IV

• Tail-Recursion kann nun optimiert werden
• Wegen Security-Manager, der Stacktrace analysiert hat, lange nicht möglich
• C und Lisp können das seit Jahrzehnten…
• Aussage: Generics sind schwierig, aber wenn man sie mal verstanden hat, sind sie leicht… Also „dranbleiben“
• Covarianz und Contravarianz (Bei Array falsch gelöst)

## Teil V

• Arrays 2.0: Indizierung mit long möglich, ein bißchen wie List, aber mit Array-Syntax… (Studien und Papers, nicht konkret)
• Listen haben heute extrem-Implementierung ArrayList und LinkedList. Wir wollen „sophisticated“ List vielleicht Hybrid
• Checked-Exceptions: kritisches Thema, schwierig mit Generics und mit Lambda. Zu viele Exceptions sind checked. Z.B. bei close()

# Semantische Quelltextanalyse

• Hilfreich für High-Level-Testing-Tools
• Statische und dynamische Analyse
• Dataflow-Analyse: ungeprüfte Daten von außen  SQL-injection, aber auch CSS, HTML, JavaScript, JVM-Sprachen/Bytecode

# Funktionale Ideen in Java

• Funktional:
• Funktionen oder Methoden sind „first class citizen“
• Higher order Functions (konnte schon C)
• Closure
• Immutability (Funktion gibt immer dasselbe raus)
• Unter der Tischdecke „lazy“-Konstrukte
• Bei großen Strukturen immer Frage: Immutability vs. Performance

# 50 new things in Java8

## Teil I

• Lambda (s.u.)
• Streams (s.u.)
• Default-Implementierungen in Interfaces
• Date/Time (wie Joda-Time)
• Optional (besser als null)
• Libraries können mit Lambda arbeiten
• Parallel (mit Vorsicht verwenden)

## Teil II

• String.join()
• So was wie „find“ in Unix/Linux
• Comparator schreiben einfacher
• Maps of Maps, Maps of Collections einfacher
• Sortieren besser: quicksort statt mergesort, parallelisierbar

# Groovy für Android

• Problem bei JVM-Sprachen außer Java: Bibliothek muss in jeder App mitkommen
• Lösung: Tool zum jar-optimieren
• Zweites Problem: dynamische Sprachen müssen auf Device „on demand“ kompiliert werden
• Lösung: „statisch“ Programmieren, dynamische Features möglich, aber nicht performant

# Lambdas

• Lambdas sind anonyme Funktionen
• Idee gegeben: Interface XY mit einer Methode uvw()
• Statt
XY xy = new XY() {
public long uvw(long x) { return x*x }
};
neu
XY xy = x -> x*x;
• kürzer, lesbarer, wartbarer, man kann Interface oft sparen
• Closure bedeutet, dass (final-)Variablen aus dem umgebenden Kontext dort eingebunden werden
• Instanz-Methoden sind eigentlich auch Closure, sie binden die Instanz in der sie definiert sind Closure-mäßig ein.

# Streams

• Streams sind im Dunstkreis von Collection, Iterable, Iterator, aber was anderes
• Erlauben Methoden, die „Funktion“ auf alle Elemente loslassen
• Elegant programmierbar sind Dinge wie
• Summe
• Produkt
• Maximum
• Erstes / Letztes Elment mit Eigenschaft
• alle mit Eigenschaft
• alle transformierten Elemente
• Sinnvoll: nicht dasselbe wie Iterable, Iterator, Collection,…