Record regional heat wave
Today, the temperature reached 33°C (at 2m) at the official weather station
Twenthe. It is the twentythird day that the temperature is above 25°C and
there have been (at least) nine days that the temperature reached 30°C.
(On four days the weather station was out of order.) The highest temperature
was 35.7°C. According to the definition of the Royal Netherlands Meteorological Institute, we have a heat wave when
for five days in a row the temperature is above 25°C and at least three
days are above 30°C. Never before since the measurements started, has it
happened that there was a regional heat wave of 23 days or more. According
to the ensemble
forecast of the European Centre for Medium-Range Weather Forecasts, there is a more
than 50% chance that the temperature will be reach 25°C for another five
days, with a great likelihood that on three of these days it will reach
30°C. Sunday, will be the most likely day that the temperature will not
reach 25°C. So, the record will either be 24 or 28 days according to the
prediction.
Interval set
Tuesday, July 23, I set myself the challange to implement a set of integer
intervals using a balanced tree, and trying to finish the code without drawing
trees on paper. I did some drawing on trees for implementing the persistent 'balanced' tree, which I finished last Tuesday, and which I did
partially borrow for the implementation in IntervalSet.cpp. In the end, it felt less hard to implement all
the methods, than I had thought. The code looks pretty straight forward to me.
I did not really optimize the calls to the private methods for balancing the
tree. The tree also does not stay optimal balanced after each operation. This
is due to the fact that adding or removing a large range, could potentially
remove many nodes in the tree, and the implementation does not do a balancing
after each node removal. (To keep the tree optimal balanced, it needs to be
balanced after each node insertion and removal.)
29 day long heat wave
Around noon, the temperture reached 25.8°C. For 29 days, the maximum
temperature during the day (between 8 and 8) has reached above 25°C,
which means that we have had a regional heat wave for 29 days, which breaks
the last record of 22 days by a whole week. A second national heat wave also
has occured during the same period. The latest forcast for tomorrow predict
that the maximum temperature will be about 21°C. About 4.3mm of rain was
predicted for today. At 12:51, it started raining after we already had heard
some thunder in the distance. At 13:16, the sun started to shine again and the
rain stop soon thereafter. Later in the afternoon, there was some rain as well.
I wonder if it was 4.3mm in total.
Palindrome dates
Today is a palindrome date
when written in the (M)M/(D)D/(YYY)Y format: 8/10/2018.
When the (M)M/(D)D/YY format is used, this is also a palindrome
date: 8/10/18 and this is the case for all dates up to and including
8/19/18 and also the date 8/1/18.
With respect to palindrome text, I found the interesting article:
World's longest palindrome?
Zomergasten - Marleen Stikker
This evening, I watched Zomergasten, a TV show where a guest can show
his favourite fragments and discuss them. This evening, the guest was
Marleen Stikker, who is
the daughter of the artist-scientist Uipko Gerrit Stikker and Gerda Meijerink.
(Marleen and her mother are mentioned in the
diaries of Dutch novelist Doeschka Meijsing, because she had a relationship with Meijerink.) Marleen
Stikker and Carolien Nevejan founded the Waag:
technology & society, which operates at the intersection of science,
technology and the arts. They are known for the Fairphone. The fragments that where shown where from:
(August 20 update:) See also her own list of the fragments with description and links.
The
long list of framents the did not make the show.
Books
At 9:56, I got the book Het feest de mislukking written, illustrated
and published by Nadie van Wijk in
June 2018. I bought it for € 15.00.
At 10:31:28, I bought the book Solve for Happy: Engineer Your Path to Joy
written by Mo Gawdat in English and published by Simon and Schuster in 2018,
ISBN:9781501157585, from bookshop Broekhuis
for € 7.50.
Caching
In the past weeks, I have been thinking about caching as mechanism to improve
program execution. The speed of IParse depends on
caching all intermediate results. Lately, I am thinking about using caching in
a data oriented programming language with transactions and back-tracking. I
realized that in IParse, I simple cache all intermediate results. I wondered
how IParse would behave if not all intermediage results are cached. The idea
of a cache is to remember some results in a special place, and search that
place first, before getting it from the normal place. The idea is that the
number of results in the cache is much smaller than the normal place. In
hardware the size of a cache is usually fixed. So, if the cache is full, you
have to clear some element. A lot of research has be done with respect to
picking the result that has to be cleared. For caching algoritms in software,
there is often not a hard limit, but if the larger the cache becomes, the
longer it takes to determine if it contains a certain result. At some point
the time saved to find the result in the cache could be too small to be
useful. For example, it is useless to create a cache for multiplication,
because multiplying to numbers does not cost much, so trying to remember the
result of the last ten multiplications you performed, is probably not going to
help you much, because it probably takes longer to search the cache than
performing the calculation itself. It is interesting to think about would be
a clever algorithm for dynamically adjusting the size of a cache for optimal
performance.
The Monads
In the end of the afternoon, I went to Tetem art
space, knowing that the had nothing new on display. I spend about ten
minutes experiencing The Monads, an installation by Gabey Tjon a Tham. I was all alone and in the right state of mind to enjoy
it.
I have been working on a new programming language with a focus on manipulating
data. I also had thought about it having a transaction mechanism. Six years ago, I came up with the idea of a back-tracking language, as a
generalization of a parsing language, which would reset the value of variables,
in case some part of the execution had failed. Actually, this is comparable to
how database transactions work: when the transaction commits, the changes are
made permanent and when the transaction fails, all changes are rolled-back. I
already feel for a long time that the distinction between programming language
and database storage system, to be a bit artificial. In the new programming
language, it is possible that some operations on a complex value fail, because
they cause a inconsistency. First I was thinking that in such a case, the
value should not change at all. When thinking about the implementation, which
I am working on right now, I realized that I would need an undo mechanism. But
then, this afternoon, I realized that that would be similar to a transaction
mechanism. Why, in case of a failure, not replace the whole complex value with
a value indication failure (and possibly some information about the nature of
the cause). Then the transaction mechanism could be used to revert the change,
if needed.
Existence proof
Yesterday, I met with a mathematician and I told him about the Irregular Chocolate Bar. He asked me about the existence proof, namely
whether for each n there exists at least one solution. I had never
thought about such a proof, because of the multitude of solutions that were
found by one of the early programs, there was
no reason to doubth whether there would be some n for which there would
be no solution. But mathematicians are not satified with such a remark, they
want to have a proof. I immediately started working on a proof by induction,
but it was only this afternoon, when I biked home that I found a way to
proof it. So the proof goes as follows: Assume you have a solution P for
n-1, can you construct a solution P' for n. Lets define set for
any even k larger than 2n, the set S_{k} as
{k/2-n, k/2-n+1, .. , k/2-1, k/2+1, .. , k/2+n-1, k/2+n}
It is clear that this set consists of 2n different positive natural
numbers and can be divided into n pairs that add up to k. Now we
can construct P'_{k} with:
{sp | s∈S_{k}, p∈P}. If there does not
exist any two s_{1} and s_{2} in S_{k}, and
p_{1} and p_{2}, such that s_{1}p_{1} equals
s_{2}p_{2}, than each product of a p and s, results in a unique
natural number and we have constructed a solution P'_{k}, which can be
partitioned into n set that sum to the same value. It is also clear that
for each partitioning of P, a partitioning of P'_{k} exists, where each
set adds up to the same value, multiplied with kn. Now we only have to
come up with a lower bound for k such that the each multiplication of p
and s result in a unique number. For this we have to find some p_{1}
and p_{2}, with p_{1} smaller than p_{2}, such that
p_{1}/p_{2} is maximal. If the smallest value in S_{k}
multiplied with p_{2} is larger than the largest value in S_{k}
multiplied with p_{1}, than all values in S_{k} multiplied with
p_{2} are larger than all values in S_{k} multiplied with
p_{1}. So, all combinations of multiplications lead to unique numbers.
Because p_{1}/p_{2} is maximal, it follows that for all
combinations of two values from P all products with the values from
S_{k} are unique. From the equation we can calculate that k
needs to be larger than
2n(p_{1}+p_{2})/(p_{2}-p_{1}) for
P'_{k} to be a solution for n. This completes the proof.
It is an open question whether there exists a solution for each n larger
than six, such that the numbers of the solution sum up to the LCM of integers upto and including n.
I played The Nand Game, a game where you
learn how a primitive CPU can be constructed from NAND gates. It is based on the ideas from From Nand to Tetris: Building a Modern Computer From First Principles.
Similar games with a textual interface are
MHRD and
Digital Logic Design.
I did not complete The Nand Game yet. I finished many of the levels in one try.
If I needed a second try it was often that I only had to change some of the
connections to the inputs, due not to fully have understood the description.
But there were also some levels that I found hard (without reading the hints),
mostly due to them being rather contrived, like having to construct the
increment with addition, substraction, and inversion. But for the rest it is
fun and educational game.
Lower bound
I have been thinking about a proof with respect to the Irregular Chocolate Bar problem that there exists a solution for each
n larger than six, such that the numbers of the solution sum up to
lcm(1,..,n). It seems that for
each n there exists a solution for the numbers 1 upto and including
k, except for some l, such that these numbers add up to
lcm(1,..,n). I modified the program from June 21, 2017 to find some more solutions. For 17 and 18, the program
found: 1 upto and including 4950 except for 1485. For 19 to 22 (including),
the program found: 1 upto and including 21577 except for 1693. For 23 the
program did not finish within a reasonable period. I tried to use the
alternative knapsack algorithm that seems faster, but it turned out to be much
slower. I have been thinking about a better algorithm for finding a solution.
There are some small values for n for which there is no solution where
the values add up to the 'minimal' value, simply because there are not even
enough different values for a partitioning in n parts. I wondered if
this could also be the case for larger values of n. According to Collary 3 in
the paper An identity involving the least common multiple of binomial coefficients and
its application by Bakir Farhi that lcm(1,..,n) is smaller than 2^{n-1}.
This leads to the following table:
n lcm(1,..,n) 2^(n-1) n(2n-1)
1 1 1 1
2 2 2 6
3 6 4 15
4 12 8 28
5 60 16 45
6 60 32 66
7 420 64 91
8 840 128 120
It is clear that the fourth column will be lower than the third column for
n larger or equal than eight. Note that the four cases where
lcm(1,..,n) is smaller than n(2n-1), match with the cases
where there is no 'minimal' solution.
Proof?
I think I found a proof or at least a proof sketch to show that there does
exist a solution for the Irregular Chocolate
Bar problem with size lcm(1,..,n) for large enough n. For
given n, there is a possible solution S consisting of 1 upto and
including some k without some l, such that the numbers add up to
lcm(1,..,n). (It is possible that l is 0.) To prove that this
possible solution is indeed a solution, we need to show that for every i
larger than n/2 and smaller and equal to n, the solution can be
partitioned into i parts, where the numbers in each part add up to
lcm(1,..,n)/i. Now trying each i, we can define for
j from 1 to i S_{j} as smallest subset of the largest
numbers from S, such that the sum of numbers in S_{j} is larger than
lcm(1,..,n).j/i. It is clear that S_{j} is subset
of S_{j+1}. The question is: Can we construct a partitioning
consisting of p_{1} to p_{i}, such that p_{j} for
j smaller than i only consists of numbers from
S_{i+1}? If this is the case, we have a correct partitioning,
assuming that the partitioning of p_{i-1} and
p_{i} with the remaining numbers will be no problem, because
all the smallest numbers from S will be available. Now, take the subset of the
largest numbers from S such that the sum is equal or smaller than
lcm(1,..,n)/i. If it is equal, we have constructed p_{1}.
If the remainder is not in S_{2}, we find the largest number in the
subset that can be replaced by a smaller number in S, but not in the subset,
and replace it. This will make the remainder larger. We repeat this process
until the remainder is S_{2}. It seems that for large enough n
this can indeed be done. Once we have constructed p_{1}, we can
continue constructing p_{2} by repeating this process with
S/p_{1}, which is a subset of S_{3}. I think, I will write a
program, that implements this algorithm, to see if it indeed works. If it does
not work for some small value of n, the proof might be incorrect, and
there is no reason to work out the details.
Fractal Jigsaw
In the past week, someone reported problems with the program for generating
Fractal Jigsaw puzzles. It appeared that the
used_pieces subcommando returned rubbish, due to a glaring bug in an
initialization function. (I must have forgotten to test the whole sequence of
subcommands, for which I stand guilty.) This morning, I improved the program to report minimal and maximal values for the
used_pieces subcommand in case the conditions are too strong and no
results are returned. (I have also fixed the bug in the two earlier versions, I
published, not to cover up, but to prevent people downloading the older version
getting stuck as well without realizing that it is due to a bug.)
Book
At 9:45, I bought the book De Stijl - 100 jaar inspiratie: de Nieuwe
Beelding en de internationale kunst 1917-2017 written by Anton Anthonissen
and Evert van Straaten in Dutch and published by Waanders Uitgevers in 2016,
ISBN:9789462620858, from charity shop Het Goed
for € 9.95.
Book
At 10:23, I bought the book Verzameld Werk: Examen 2005 / Collected Work:
Graduation 2005 written by Hans van Kooten (and others) in Dutch and
English, and published by Hogeschool voor de Kunsten Utrecht in 2005
from charity shop Het Goed for
€ 2.50.
In the beginning of 1981, I thought about writing a program to generate the
elements of a
(mathematical) group using it basic identity rules. I wrote whole sheets
full with expression, but could not find an easy algorithm. This evening, I
realized that this can be done with the rule that if XY=W and YZ=V than XV=WZ.
One way to prove this is to append Z to XY=W resulting in XYZ=WZ and then
replace the occurence of YZ in the left-hand by V, resulting in XV=WZ.
Tilburg
I went to TextielMuseum in
Tilburg with Peter Struycken, who worked in the
TextielLab from in the years 2002
to 2005, and in cooperation produced a number of wall carpets. We met with a number of people who knew him from that
period. We also looked at the exhibitions
Simply Scandinavian | Nordic Design 1945 -2018 and
Colour & Abstraction | Generations in Dialogue at the museum. The
last exhibition also included the carpet Boulez - 22 - 30 mei 04 - 06 maart 05 - 03 by Peter Struycken and also
sample with all different colours that he created to test out the
possibilities. Left of the wallcarpet is the work Abstract Browsing 17 08
10X by Rafaël Rozendaal. We also met with him, because we was creating
colour samples on one of the weaving machines in the Lab. He too has made the
transition from computer generated images to wall carpets. Peter and I also
liked the wall carpets by Reinoud van
Vught. Although they are less colourful than the works by Peter, they are
similar with respect to patterns.
Afterwards, we went to De Pont Museum of Contemporary Art, which is only ten minutes walking
from TextielMuseum. I liked the works by:
The most important thing I learned, while looking around with Peter, is that I
should ask the why question more often. Why did an artist make something? Why
do I (dis)like it? Why does it interest or bore me?
This months interesting links
Home
| July 2018
| September 2018
| Random memories