cool
before anything let me tell you a story
this picture was short for the movie
Cleopatra but sadly it didn't make the
cuts
still I believe I know what this scene
is about and I recognize some historical
references including to a dinner party
that had a profound impact in human
history let's see the plot is this
they are in Alexandria 48 BC
in the middle we have sozogenes a Greek
astronomer to whom we owe a great deal I
will talk more about his work later but
in this movie he's the most stressful
advisor to Cleopatra was having a power
struggle against her brother and
desperate needs Caesar's help to resolve
the situation Julius Caesar the Roman
dictator then became Cleopatra's lover
and made her Queen of Egypt
so to celebrate her essential to the
throne Cleopatra in real life through
this lavish dinner party described by
the Roman Puerto Rican in his book
farsalia Lucan tells us this the room
was the size of a temple it was filled
with a wonderful smell of Exquisite food
not only the issues the food was
colorful with the zotchke birds and
fruits serving golden platters the water
increased the viewers and the whiny
Jewish goblins but he also says that
Cleopatra was dressed to impressed but
still what really caught Caesar's
attention that night was an old wise man
by the name of Aquarius
but perhaps there is a reference here
because the koreas talked a long time
about astronomy
the floods of the Nile and the relation
between this shoe and the Egyptian
calendar
that might have been a half moment for
Caesar look at his face
so that when he returned to Rome
[Music]
the reform of the very messy Roman
Calendar
and that finish the first story of my
presentation
my name is casinary I'm a PhD
mathematics former Professor University
currently I work in finance in London in
the next hour or so I'll talk about
calendar algorithms and along the way I
will cover topics and take this
decisions taking hundreds or even
thousands of years ago that deeply
impacts the performance of these
algorithms on very modern CPUs
this is a research collaboration with
Professor Lauren Schneider of emilion
in my part of this work was carried out
in my spare time has nothing to do with
my current job previous employers I'm
here in a personal capacity and all the
opinions that are going to express our
mind and do not necessarily reflect that
of my employer so I'm going to cover
four algorithms and we are going to
spend more time with the most complex of
the four which is this
digital devices including my humble cast
watch here
they display dating timing Fields like
this but that's not how they internally
keep track of time so let's take a
closer look usually they keep a counter
of ticks since some specific points in
time for instance in this slide we are
counting the number of seconds since
zero hours of First January 1970 that's
the so-called Unix Epoch as said by Ken
Thompson Dennis rich and other creators
of Unix
the Unix Epoch is also used by stood
Chrono system clock but other system I
use different epochs and also the
resolution of the cheek might change
so the question is how do we convert
from ticks to dates and time
for the time part is easy it just
involves a bunch of Divisions and models
operations and the working states where
in each stage we get the value for one
field and inputs for the next stage and
what makes this problem easy is the
constancy of durations every minute has
six seconds if I will have hour has 60
minutes and every day has 24 hours and
also every week has seven days but sadly
this patterns breaks when we get to the
date part because the number of days in
a month or in a year is variable
so the main problem we wish to solve is
this given the number of days since some
epoch
finds the corresponding date
of course Lawrence and I were not the
first to solve this problem so let me
contrast our solution to that of.net 6.
here we are never mind if you cannot
read the code but pay attention to the
slow moving Parts okay I'm just showing
this code to point out some programming
constructs that harm the performance of
these codes namely Brands and Loops this
code also contains two lookup tables and
it is true that these lookup tables
might help the performance this code but
the cache is a precious and very limited
resource so this code is competing for
cash with all the running pieces of
software so it's really hard to tell but
it has a possibility that overall the
performance your application degrades
because of cash thrashing and here is
our solution again never mind if you
cannot read that we will see that in
details later
I just want to tell you that it contains
no branch no loops and no hookup tables
it's entirely thematic and involves
basically a bunch of Divisions and
models operations and the work on stage
where in each stage we get the value of
fields and inputs for the next stage so
it's no coincidence is very similar what
you we do for times indeed I'm going to
present you a mathematical setting under
which both problems the dates and the
time problem can be tackled in exactly
the same way it just happens that for
the time part there are further
simplifications but the mathematical
setting is the same so but since I talk
about performance C
let me contrast the performance with
these two and other implementations but
if I tell you my code runs in five
nanoseconds that doesn't mean much right
five nanoseconds a very short period of
time and is unreachable to our senses
and I want you to feel it so this
animation rescales time as if Michael
takes five seconds to run let's see how
long the order is taken please bear with
me
president
sorry
seriously
okay finally fine I hope this was the
most boring part of my talk and the
entire conference okay so let me
elaborate a little bit further and so
those are the seasons that use these
algorithms some of them are just
academics and as you can see our is in
Chronos uh
we've studied C plus plus Chrono is also
in two subsystem of the Linux kernel
Implement myself and then Sergey Pavlov
implementing C sharp for the dot NET
Framework it has been released with
dotnet c 7.
so having seen the performance now let
me talk about the overview of this
presentation and its three pillars the
history the maths and the coding I'm
gonna start with the fascinating history
of the Egyptian sorry the Julian and
Gregorian calendar and especially for
the Julian calendar my main reference is
the classical work of saturnaga by
macrobius the other classical reference
but they divert between them so there is
still a lot of debate among historians
about what really happened
and they are going to move to the math
side and I'm going to introduce this
mathematical setting under which the two
problems the date and time can be
tackling exactly the same way and
involve integer functions of this form
and notice the division if that division
was the usual rational divisions between
integer numbers F will be called an
assigned functions but here in that
presentation forward slash denotes
and for that reason the orange and I
call this type of function including a
fine function
then we're going to move to code and see
some transformation that largely improve
the performance of our algorithms so it
starts with the history let's go it's
very interesting and fascinating
so Romulus the first king of Rome is
credited for this calendar
as you can see the name of the months
are quite familiar and some even spell
exactly the same in English and relaxing
except for Queen series and six Six
Theories and actually from quintix
awards from the fifth month onwards
months are named after the position so
Queen series means the fifth month sex
series the sixth month September the
seventh month so it made sense back then
it doesn't make today but it made sense
back then what doesn't make sense in
this calendar is that it only contains
10 months account for 304 days the
remain days of the year was part of the
winter period but since winter was a
period of low activity rumors didn't
bother splitting two months
what is even crazy is that the duration
of the Year winter was not prescribed it
was decided by the pontificis the high
priest of Rome and they were supposed to
call the end of winter in the beginning
of Matthews and the New Year close to
the Spring Equinox should keep the
calendar aligned with the seasons okay
but then Luma the second king he split
win thank you januaryus in February he
made the envirus the first month and he
changed a little bit the duration for a
few months and look at February's the
last month it usually had 28 days but
every now and then it could have 50 or
51. so that the duration of the Year
could be 355 377 or 3078 states there
was a rule this prescribing the duration
of each specific year but was too
complicated for the people and the
punches they just
and they still decide the duration of
the year as they pleased then februarys
was moved to its current position by The
Chain video the commission of temen who
wrote the first Roman code of law they
might have some kuritzko and Military
reasons for that move but from the
algorithm point of view that was a
mistake and we are going to deal with
that mistake later
but what is really crazy here is that at
that time
Rome was a Republic and the duration of
the government was one year so since the
Pontius they decide the duration of the
year they decided the ratio of the
government so either by ideology or
simply bribery they abuse the power and
at some point the calendar got complete
out of sync with the seasons and that's
the problem that Julius Caesar said
himself to solve and as I told you he
hired soulsygienists and that's what the
the calendar that societies come up with
so it's very similar to our calendar
nowadays not just February it had 28
days and every now and then 29.
every four years is and before she will
have uh 29 the February you would have
29 days so that's three out of four
years would have
365 days and the other one would have
3066 so the duration the calendar
duration of the year will be 365 days
and a quarter for the days and in the
balloon I put the real duration of the
year it's quite close not exactly but
quite close
but again the punches they screw up they
didn't understand the rule and they
apply that to every 30 years so they
made every 30 year a leap year so soon
after they realized it was again design
misaligned with the seasons so Augustus
Caesar and the Senate they first renamed
Queen series and six Series in one or
two seasons himself they suspended the
leap years for a while until the
calendar got back in syncs with the
seasons and
since then the rule was correct applied
and despite the small adjustments made
by Augustus in the Senate that calendar
is so called the Julian calendar
and the error of this calendar is about
11 minutes per year which doesn't sound
much but it adds up to one day every
132 years so after 16 centuries the
arrow was quite noticeable that's why
the pope Gregorius the 13th called for
reform and he hired the mathematician
called Christopher Claudius to read the
reform but the main ideas of the reform
came from another mathematician called
Aloysius rigos
decide to set the calendar year the
average calendar year to that number 365
days 0.2425 and again in the balloon you
can see the real number it's very close
and it can get closer of course and some
calendars do achieve that but at some uh
aspects of reviews reform that made it
brilliant in my opinion let's see so
first he look at that number as a
correction of the old rule so
365.25 was the previous average of the
the during average of the year so then
he subtract 0.01 and he had
0.0025 and these two numbers can be
conveniently written as 1 over 100 and
01 over 400 doesn't seem special but
that allows to explain the rule when to
write it in very simple words as a
correction of the old one so a leap year
is one that is multiple four exactly as
used to be but then there is this
addendum except those that are multiple
of 100 but not multiple of 400.
so
now look at that so we can see that the
two rules the Julian leap year Rule and
the Gregorian leap year rule only
diverge 3 out of four centurial years
and the first search year after the
reform in 1582 was 1600 which is also a
multiple of 400 so is the exception of
the exception so it it was
calendar and it was a repeater in the
Julian calendar so four people alive at
that time they didn't see any difference
the only time the first time it they
really diverged the true leap year rules
were in 1700s
118 years after the reform so people had
plenty of time to adapt to the new rule
so a review of The Clarity of the rule
and the forward looking the preparedness
that always allow us to have so and that
finished my crash course in the history
of the calendar I could spend here two
hours talking just about that but I know
we are here for C plus plus conference
you want to see code you want to see
algorithms so let's bring your own so
that's a quote from the gcc's manual I
love that I am such a programmer and I
want to show you one example where the
that really illustrates that code so the
first algorithm is is very simple and
one line that's the code that I found
virtually everywhere I look at e3p is
implemented like that anyone has an idea
why this is so what is the argument
behind this implementation
nope though okay so let me just rewrite
this in terms of Ethan Nails it's the
same logic because it you this one use
uh
short circuiting of The Logical
operators but it's easy to reason about
if we see the ethanel's version so the
argument for this implementation tells
that in 25 percent of the case we have a
return we just do one divisibility check
and then we return
it's only 25 percent of the case that we
have to carry on with all the
calculations but that's what I Implement
in GCC it always does two divisibility
checks so for many people that might be
optimization but then I measure and I
was surprised I confess I was surprised
that my code was closer to three times
I'm not saying three percent I'm saying
three times faster than the classical
implementation that is everywhere
and I was surprised like why is that
because the the argument for the
classical implementation
ignores the cause of branching so if if
you can see mine
it splits also the execution it Branch
but in branches in two paths one with 99
of the time and another one with one
percent of the time so it's much
friendly to the branch predictor the
branch practical can make a better job
with the the hour code than with the
article the classical code and there is
more
we always do just one branch the the
classical code
75 percent of the time is one branch but
then there is another one so sometimes
it runs twice our Branch just once
we didn't stop there I changed the 400
with 16 that's not a book that's allowed
and I leave you the the phone to prove
that if your number is multiple of 100
and
pay attention that that the last line is
executed only one when
and so if a number is multiple of 100 it
is multiple 400 if and only if it's
moved off 16 so this is a valid
transformation and obviously device of a
power of two is much cheaper to evaluate
these models operation but then
suggests why not
change just the deciding the divisor of
the second expression
and do this so we use the ternary
operator just to decide the divisor of
the second divisibility check and I'm no
I'm sure your own herds that despite the
D in either case would be a power of two
so we don't need to worry about the
model's operation of power of 2 because
the compiler is going to change for us
use a bit wise and trick and we don't
need to do anything unfortunately not in
that case no compiler could figure that
out so we have to do it manually so we
wrote something like that that's I did
more optimization but it's another story
so with that expression with that code
all the major C plus plus compilers they
generate efficient Branch free code not
with the classical implementations there
is every tree virtually everywhere so
that's the first one
now second algorith of the day the last
day of the month
so February is special needs some
special treatment
anyway but then for the other Maps
that's Costco also almost everywhere we
find something like that small
variations but the idea is this one
using a lookup table that gives the
right uh answer but so if you use a
lookup table remember that there is a
competition for cash so it might be
worse somewhere else
and there is worse these codes if m is
not B21 and 12 then we do out of bound
access to the array which with all its
undefined Behavior it's bad is not
memory safe C plus plus is bad C is bad
blah blah blah so can we do better so
that's why implementing GCC again
February is a special needs a special
treatment but then I came up with these
scripts codes and between them there and
I leave you the phone to prove that this
Pro gives the right answer when m is
between 1 and 12. if m is not between 1
and 12
it produce rubbish but it's still well
defined according to the rules of the
language there is no one defined
behavior in that code okay there was my
original implementation there was an
extra age with one at the end
but then uh Dr Matthias Kratz realized
that we did not need this end with one
because a very fortunate facts about the
binary expression of 30 so we could also
remove that and there is an alternative
so this code is fast and is safer
and but there is an alternative that is
also fast and safe which is this one and
again I review the phone to prove that
that works and performance wise
basically the same there's not much
difference but I want to point out that
we have the very last line nine times M
divided by 8 is the first including a
fine function of this talk we are going
to see plenty more
okay now we are up for some cool maths
please bear with me don't don't
don't go away so I'm going to result to
solve the problem our main problem given
the name of the number of days in
support find the date but I'm going to
solve it first in yet another calendar
the Egyptian calendar the one that a
Koreans explained to Julius Caesar okay
so it's a very simple calendar where
every year has 365 days no repeat you're
involved okay so suppose that any days
have passed since the first day of year
zero that's our import here and I'm
going to introduce three functions y of
n gives the year of the date the Y
circle of n gives the day of the year or
and why and why star of capital Y gives
the number of days before y
okay and pay attention also to the
quarrels but I will keep
calling the function by the name for the
benefit of those who perceive color
differently but I'm going to use this
color consistency to those functions and
the relatives that will appear and that
bear the same relationships so since
every year has 365 days that problem is
very similar to the time problem and
probably you already figure out the
three formulas for these three functions
but let's put the formula aside and
let's try to understand the relation
between these three functions in that
graph here it will help us understand
the algorithms that come so on the
x-axis I count the number of days since
Epoch so zero represents their Pock and
N is a number on this axis
y of n output on the y-axis very
conveniently
and it's obvious that it's not that but
just that particular value of n that use
the same value of y the 3065 values of n
that gives the same year so it's easy to
see that this function y of N is a step
function and the length of this step is
365.
now y star of Y here in the bottle it
counts the days before e y so
this value corresp is the end that
corresponds to the beginning of eoy is
there in the graph and the day of the
year is the number of days from the
beginning of the year to the date so
that's the difference between this true
number here's n and y is start so that's
the representation of Y third
now if we do the same analysis but
within a year and we use any y as the
input essentially everything that I said
for years also work for months let's see
in detail
so again on the x-axis I put the number
of days but now from the beginning of
the year and let me talk about the
Egyptian calendar the months in the
Egyptian calendar there were 12 months
of 30 days each
so which accounts for
306 days the five remaining days was not
part of a month was a period called
epagomino day similar to winter at
Romulus time so it was not part of a
month but we don't need to care about
that we can just think it was a
fictitious month a 13th month okay all
we care about is find the number between
0 and 12 that represents that month
either real orphic tissues and again so
we know that any white days have passed
since the beginning of the year we
introduced the three functions M of M of
NY which gives the math M search of NY
which gives the day of the month or
simply day and M star of M gives the
number of days before month m
in the way we built the previous graph
is exactly the same we built this one
the relationship between these three
functions is exactly the same and again
because the months the real months had
30 days you might have already figured
out the formulas for these three
functions
but there's something interesting here
the number five doesn't appear anywhere
only 30 days
and one way to see that is look at any
Star it counts the number of day before
month end
the month the fictitious month with five
days is the last month so it's number of
days in the last month is never
accounted for because we never go any
star of M for M after the last month
because it doesn't make sense that's the
last step so the lesson here is that a
shorter month if at last doesn't create
any trouble for us
the in that Spirit February is
complicated only because it's not the
last month and we can blame that the
champion for that mistake if they have
kept February the last month would have
simpler algorithms today but we don't
so we did one thing for a year and we
did the same thing for month and one
mathematicians do the same thing twice
they try let's generalize a week one
will write code right when we see two
things together say let's factor out
greater functional class and that's it
so let's do that
they generalized that and instead of
talking about year or month let's say
about the period
so we introduced the three functions
F of n
which gives the period Q so suppose that
any days have passed since the first day
of the first period that will be our
Epoch now so introduce f n that gives
the period F sort of n that gives the
day within the periods and F is star of
Q gives the number of days before period
Q so the graph is exactly like those the
two that we saw before but here the only
difference is that now we allow these
steps to be variable not to have either
30 or 300 six files but to be variable
that will allow us to apply these ideas
to the Julian and Gregorian calendar
so
the graph is enough for us to understand
what is going on but in the paperware
Lawrence and I wrote and we show all the
formulas they make sense we prove all
the tyrants we need more than the graph
so we have these equations here and we
use this equation they translate
everything that you see in the graph are
translated by these two equations but
don't worry with the equation I'm
putting here just for completeness we
need that in the paper but the mental
model given by the graphs are enough for
this presentation
so let's apply these ideas to the
juvenile calendar before going to the
more complicated Gregorian calendar so I
recall the leap year rule is on the top
and here the step can be 365 or 366 and
let's see what is the the formula for y
star of Y which I recall it counts the
number of days before year why so a
resultant is this I take y the number of
e is from 0 to Y is y I multiply that by
365 as if every year I had 3065 days and
I had the correction that accounts for
one day every four years that is y
divide by 4 and we end up with that
formula there are two bad news here
first one
is not a multiplication as used to being
the Egyptian calendar and it's the
equivalent in time what the time problem
would be also just a multiplication it's
a bit more complicated but the worst
news is that this formula is wrong
hey let me explain why so here I have a
table of Y star of Y for y between 0 and
4. so the difference between two lines
is supposed to give the number of days
in each particular year but for zero is
giving
3065 but 0 is multiple four so it should
be a leap year and should have 366 days
so this is wrong and also for three it
gives 366 days but three is not multiple
four three is not a repeat so this is
all wrong but we can figure out that our
form is off by one if the repair rule
was expressed like that our formula will
be correct
but that's not how the Julian calendar
works but no reason for panic attacks
the fix so that formula is correct for
the Julian calendar and
but bear with me we can do better than
that we are not going to use this form
we can do better than that
okay but I want to point out that the
true formulas that we found for y star
they have the form of an including a
fine function so it's time now to try to
do more analysis on those functions and
see what what goes on so in the general
case f has this form but in the
particular case when a is equal to 1 and
b equal to zero that's the the case when
we work with times and that's the case
when we work with the Egyptian calendar
so F becomes just a division F sort is
just a model's operation and F star is
just a multiplication now we want to
find F Circle and F star in the general
case that bear the same relations as the
tree in the particular case and these
relations are those given by the graphs
that we saw and given by these equations
but again don't worry with the equations
but using these equations we are able to
prove to find the functional forms of f
Circ and F star and notes that F star is
also including a fine function
so let's apply that
to
our calendars but first I want to
propose something radical here let's
reform the calendar okay let us reform
the column so we don't have the powers
of a Roman dictator and we don't have
the powers of a pope but that's what we
are going to do and that's what
Christian's allergies in 1882 introduced
a new calendar the so-called
computational calendar okay true is not
a calendar used by any country but is a
very mathematically convenient calendar
so what I'm going to do is all our
problems we are going to solve on the
computational calendar and then map back
either to the Julian or the Gregorian
calendar so just to give you an idea
what the Gregorian the computational
calendar is he picturing two consecutive
years in the Gregorian slash Julian
calendars Y and Y plus one and as usual
they are split in 12 months number for 1
to 12 and I'm going to show this
corresponding months and years in the
computational calendar so first and
foremost
Christian Zeller fixed the chambering
mistakes and he plays February at last
so the years are a bit shifted they run
from March to February okay
from March to December he kept the same
number as of the month from 3 to 12 but
since January and February I suppose to
follow December of the same year they
take the values of 13 and 14. so that's
the computational calendar and notice so
and one last thing so the days which are
not pictured here they are zero base so
the first day of the year or the month
is day Zero not day one in the
computational calendar so with all that
in mind it's very simple to deduce this
mapping here from the computational
calendar from a date on the
computational calendar to the
corresponding dating that Julian islash
Gregorian calendar now pay attention to
the ear that February Falls on
the computational card and the
gregorians
are off by one that's exactly the
problem we had a few sides before when
we try to find y star
of the Julian for the Julian calendar
what we end up finding was why staff for
the computational calendar so that's the
formula that you are going to use the
one that was wrong now it's correct for
the computational calendar
and let me be a bit more precise I'm
saying Greg Gordon is Russia Julian
but actually there are two computational
calendars there is the computational
calendar based on the Julian card such
that the leap year rule of the two these
two are off by one and the same thing
for the computational calendar based on
the Gregorian calendar so let's see why
star again for the computational
character based on the Julian calendar
so I insist this formula was wrong for
the Julian calendar but it's correct for
the computational calendar based on the
Julian calendar and here is the repeater
rule exactly as we wish it was now it is
and
if you equate the coefficients of this
particular form of Y star with the
general form of Y star we can easily
find the coefficients a b and d and
since we have a D and B we have the
formulas for the Y and for y search so
that's the year and
the day of the year so just basically
divisions and models operations now
let's go for the Gregorian calendar
again the leap year rule is off by one
in the computational calendar based on
the Gregorian calendar and here again a
reasonable attempt
for y star multiply y by 365 and do the
correction one day at every four years
minus one day every hundred years plus
one day every 400 years
this form is correct but
it is not a nuclear find function so
should I throw away our beautiful
mathematical setting and try to
generalize even further
maybe we can do something along those
lines but that's why not what we did
what we did was we introduced the Sentry
actually we are just acknowledging Leo's
idea that every Century every fourth
Century should get an extra day we are
just technology what really you said we
should do so we introduce a century as a
first-class citizen this whole
calendrical calculation business not all
algorithms out there they do that they
try direct to go today we take a step
back let's find first the century and
then carry on later so we introduced the
century the leap Century those that had
one extra day and the the the rule is
again off by one respect to the
Gregorian calendar
and then the exercise is the same
multiply the number of days in a common
Century by c as the correction we find
this formula and the same exercise again
we
compare that to the general is form of
the star function we equate the
coefficients we find the coefficients
and with the coefficients we find the
formula for this entry and the day of
the century so I'm skipping the details
I leave it for you so let's take a step
back and see what got we got so far so
if any days have passed in the first day
of year 0 of the computational calendar
so now our book now is the first day of
the computational calendar which is
first March of year zero
decide that we just saw gave us these
two formulas for this century and for
the day of the century so NC counts the
number of days since the beginning of
the century so any second States within
a century it never crossed a central
boundary right and if he never cross a
central boundary so they repeal in the
juvenile calendar and in the Gregorian
calendar that they they are the same
they match that means the formula that
we found before also apply here
okay it's the same fault the only
difference is now we use NEC which is
the day
within the century and we get Z which is
not this the year is the year within the
center of the year of the center but we
have the century and we have the year of
the century the year is just that okay
so now only the month and the day remain
to be found and the input for that is
the day of the year and why
so again we start with the star function
M Star I'm putting a table here it
counts the number of days before m
so for March which is the first years
there are zero days before March for
April there are 31 days before April
which are the 31 days of March and so on
and so forth and not just that for
February it doesn't matter if the year
is repeated or not
February might have different durations
but M star of 14 is always 337 okay
and it turns out that that M Star is
also known a pleading a fine function
this one here there are some ways to get
that formal is not out of the sky we can
find this formula and then again doing
the same exercise we find the formula
for M and for d
so
that's here everything together this is
a full
functional calendar algorithm for their
port which is first March of year zero
we have these formulas on the
computational calendar and when we have
the why mng on the computational
calendar we mount back to the Gregorian
calendar that's it but the two main
divisions here and they bother me they
bother us me and Lauren so I'm going to
do something about that so we have
solved three problems
is repeat last day of the the month and
now
find the date given the days after uh
any days after a park
but incidentally in the middle of
everything we also resolve the
reciprocal problem to this one which is
given the date say 1G mg DG so the year
month and the integration calendar how
many days there are between the a park
and that date so how do we solve that
first we move to the computational
calendar we map to the computational
calendar is the inverse of the other map
and then recall that y star on the
computational calendar why star counts
the number of days from a park to the
first day of the year M Star counts the
number of days from the beginning of the
year to the beginning of the month and G
is the number of days between the
beginning of the month and the date so n
is just the sum of these three numbers
and here are the formulas that we found
before so here is the solution our
fourth algorithm okay but this one again
has some divisions and they bother me so
what we can do about that so what's my
issue with division
among
before we get to the division
that's a lot of history and mathematical
history I'm wondering
how much of this was known to all the
other algorithmic stuff and what did you
what did you actually contribute to
mashing this together
okay so our contribution basically some
of the the computational calendar they
are known okay it's using the causal
congruence Christians there invented
that in 1882 and both use that lib C
plus plus use that okay our contribution
was just these relationships given by
the euclidean fine functions from y star
getting y from C star getting C and the
relationship between those functions
that's one of our contributions okay and
you you can see for instance this for ah
this is here this formula for M Star we
are going to see on Boost Android C plus
plus but not the formula for the century
because they try to get direction to the
year and that helps performance okay so
my problem with division is because it's
the hardest of the four arithmetic
operations and not only for me also for
the CPUs they take far more Cycles if
you remember what the math go got both
joinings his lightning talk division is
much much more expensive not for just
for us also for the CPU so I'm not good
with mental calculations but when I have
to divide and by five I do this trick I
multiply by 10 divided by 5 which is 2
and then I divide by 10 and divide by 10
for me is easy divide by powers of 10 is
this because it's just a shift of digits
the same thing happens for the CPU but
if you use binaries right so here is how
the CPU can calculate and divide by 5
multiply by two to the power of 34
divided by 5 and then divide by 2 to the
power of 34 which is just a bit shift
but unfortunately 2 to the power of 35
divided by 5 is not an integral number
so the formula is just an approximation
the big number that you see on the in
the numerator is uh approximation it's
rounding up to the near integer 2 to the
32 to the power 34 divided by five so
I'm rounding up
so the result is a bit higher than
should be but that when you use rational
Division and we do not interesting
rational division we are interested in
intersection Division and the internship
division truncakes down so maybe the
error of the rounding up is compensated
by the truncation down and that's
exactly what happened grego de
Montgomery showed that in 1994 and major
compilers they apply this transformation
so you write that in your code and
divide by five if you see the assembly
code
with optimization Zone you are going to
see that it actually multiplied by this
huge number there and then it shifts by
34 bits and that works for all numbers
all unsigned integer numbers with 32
bits okay there's something similar for
integers there's something similar for
six four bits numbers but that's the
idea
so let's see what it brings to our
codes okay so this is for instance a
formula that we can find the Boost and
leave ellipse plus plus and also Ms VC
STL Okay so
we can see there are two divisions but
I've just explained the compiler replace
those two divisions with a
multiplication and some
cheaper operations and that after that
the number of multiplication becomes a
proxy for the performance of this code
so we counted the number of
multiplications this one has two very
explicit and two after the ground with
the monogram transformation it has four
multiplications also notice that in the
expression for D we use n so there is a
data dependency here the CPU needs to
find D
to find Amy before it can start D
so if we use our formulas especially the
the alternative form for f Circ use here
using the models operations now we have
just three multiplications one that
explicits from the five
and the true after the multigomery
uh
transformation transformation
and there is no more the data dependency
between m and d so the CPU can start the
calculation of G before I finish that of
M right
I'm lying
unfortunately the model's operation
greater than Montgomery they don't say
anything on how to optimize that so what
the compilers do is they just use that
expression on the right and if I replace
that expression back into the code it
gives a fair assessment of what goes
behind the scene what the CPU really
calculates and again we have four
multiplications and the data dependency
is back on so we didn't make any
Improvement not yet because another
contribution of us was to generalize the
results of groundwater Montgomery to
include and find functions for the
particular function that gives the month
that's what we we found so and as you
can see the division the first division
the model's operation is by a power of
the divisor is a power of two so much
better for the CPU there is another
division but for the last division by
2141 we don't need
the models so we are okay just using
Greenwood and Montgomery but when we
need both then our results
helps a lot to improve the performance
after we do that then now we have only
two multiplications lot four and we
broke the data dependency between m and
d as soon as N3 is obtained the CPU can
and our modern CPUs they do start the
calculation of m and d at the same time
in parallel so it speed UPS a lot
so that's the final version that's what
is EGCC in the Linux kernel
Etc but if you pay attention we'll see
that I didn't use our beautiful
optimization result for equilibrium fine
function in the first block for the
century and for the second block we use
half of that there are two reasons for
that one is ugly let's put aside but
there is another one that I find
beautiful I want to share with you and
for me this is historical bits we're
doing let me explain why so I'm
interested in these two expressions here
okay so and notice that any c is
something divide by four let's call this
something r
okay and the expression for P2 I'm more
interesting in the the part that is
inside the bracket so it's interest on
that so if I replace NC in the second
expression so we conclude that at some
point the CPU evaluates that expression
let's think about that in binary
so here I'm
picturing the bits of representing the
bits of RS boxes and I pay special
attention I'm highlighting the two right
most bits or boxes so first thing we do
is we divide R by 4 which is just
shifting two bytes to the right then we
multiply by four sorry we multiply by
four which shifts back to the left and
fill the gaps with zeros and then we had
to add three which in binary is one one
and that sum zero zero plus one one has
no carry so the result is the same as
just taking R and making an or with
three so these three operations can
collapse through just one and the good
news is some compilers can even figure
out by themselves that's why we left
as it was because some compilers can
figure that out themselves but now here
I'm talking some compilers later because
of this work I also took a look at uh
c-sharp compilers and rust compilers so
some of them some of the C plus plus
compilers they can or this cannot so and
sometimes you have to do that manually
to get the best performance
possible and why do I call that
historical between
look at that these four here we can
pinpoint that this four comes from
society in this decision that every
fourth year should get an extra day and
that was a decision taking to more than
2 000 years ago these four here comes
from real use decision that every fourth
Century should get an extra day a
decision that was taking more than 400
years ago
these three here comes from the fact
that the great the computational
calendar and the normal calendar they
are off by one
with respect to four
and that's the invention the
computational calendar was invention by
Zelda more than 140 years ago and put
everything together is our modest
contribution from two years ago and
that's it I want to thank you for being
here I want to thank all those people
who helped me especially my wife
Christina Costa and I'm happy to take
questions thank you
[Applause]