Freeing Algorithms

S

Stefan Ram

Here is an algorithm for the determination of the leap-year
property of a year:

public static boolean
isLeapYear( final int yearNumber )
{ final boolean isQuad = yearNumber % 4 == 0;
final boolean isCentury = yearNumber % 100 == 0;
final boolean isQuadcentury = yearNumber % 400 == 0;
final boolean isCanceled = isCentury & !isQuadcentury;
final boolean isLeapYear = isQuad & !isCanceled;
return isLeapYear; }

But this will only handle years up to about 2^31-1 or so!

What will happen, when wants to use BigInteger for years?

The algorithm actually only uses the property of years to
be congruent to a number modulo another number:

public interface IsCongruentModuloIntInt
{ public boolean isCongruentModulo( int comparand, int modulus ); }

So there is no need to bind it to the special type »int« that
has many more features which are not needed here. The
following untested draft shows how the algorithm can be freed
from this binding.

public static boolean
( final IsCongruentModuloIntInt yearNumber )
{ final boolean isQuad = yearNumber.isCongruentModulo( 0, 4 );
final boolean isCentury = yearNumber.isCongruentModulo( 0, 100 );
final boolean isQuadcentury = yearNumber.isCongruentModulo( 0, 400 );
final boolean isCanceled = isCentury & !isQuadcentury;
final boolean isLeapYear = isQuad & !isCanceled;
result isLeapYear; }

If an algorithm needs more features of a year than just a
single feature, it can be written as follows stating exactly
which operations it needs (untested draft):

<T extends AddInt & IsPositive & DividedByInt >
public static int
difference( final T yearParameter )
{ if( yearParameter.isPositive() )yearParameter.addInt( - 1 )
quads = yearParameter.DividedByInt( 4 ); /* ... */ }

So each algorithm is generic to the maximum extend possible,
if it binds itself to the smallest interface it needs.

The interfaces »IsCongruentModuloIntInt« still is somewhat
bound to »int«, but the generalization achieved here
usually will be sufficient. A more general version could be:

public interface IsCongruentModulo<T,U,V>
{ public boolean isCongruentModulo( T comparand, U comparand1, V modulus ); }

An important part of this programming style was removed
in this posting for brevity: The JavaDoc-comments which
state what the meaning of this operation is.
 
R

Rhino

Stefan Ram said:
Here is an algorithm for the determination of the leap-year
property of a year:

public static boolean
isLeapYear( final int yearNumber )
{ final boolean isQuad = yearNumber % 4 == 0;
final boolean isCentury = yearNumber % 100 == 0;
final boolean isQuadcentury = yearNumber % 400 == 0;
final boolean isCanceled = isCentury & !isQuadcentury;
final boolean isLeapYear = isQuad & !isCanceled;
return isLeapYear; }

But this will only handle years up to about 2^31-1 or so!

What will happen, when wants to use BigInteger for years?

The algorithm actually only uses the property of years to
be congruent to a number modulo another number:

public interface IsCongruentModuloIntInt
{ public boolean isCongruentModulo( int comparand, int modulus ); }

So there is no need to bind it to the special type »int« that
has many more features which are not needed here. The
following untested draft shows how the algorithm can be freed
from this binding.

public static boolean
( final IsCongruentModuloIntInt yearNumber )
{ final boolean isQuad = yearNumber.isCongruentModulo( 0, 4 );
final boolean isCentury = yearNumber.isCongruentModulo( 0, 100 );
final boolean isQuadcentury = yearNumber.isCongruentModulo( 0, 400 );
final boolean isCanceled = isCentury & !isQuadcentury;
final boolean isLeapYear = isQuad & !isCanceled;
result isLeapYear; }

If an algorithm needs more features of a year than just a
single feature, it can be written as follows stating exactly
which operations it needs (untested draft):

<T extends AddInt & IsPositive & DividedByInt >
public static int
difference( final T yearParameter )
{ if( yearParameter.isPositive() )yearParameter.addInt( - 1 )
quads = yearParameter.DividedByInt( 4 ); /* ... */ }

So each algorithm is generic to the maximum extend possible,
if it binds itself to the smallest interface it needs.

The interfaces »IsCongruentModuloIntInt« still is somewhat
bound to »int«, but the generalization achieved here
usually will be sufficient. A more general version could be:

public interface IsCongruentModulo<T,U,V>
{ public boolean isCongruentModulo( T comparand, U comparand1, V
modulus ); }

An important part of this programming style was removed
in this posting for brevity: The JavaDoc-comments which
state what the meaning of this operation is.
Do you really think the average Java programmer will ever care whether the
year 23456543215678908765432124354667 is a leap year? Surely no one alive
today is likely to care whether any given year much beyond their lifetime is
a leap year; barring truly miraculous achievements in medical science, no
one on this newsgroup is likely to live much past 2100, let alone to a time
where the year exceeds 2^31.

Now, if you simply started this thread to make a purely intellectual
programming point and then chose a questionable example, forgive my remarks.
 
L

Luc The Perverse

Rhino said:
Do you really think the average Java programmer will ever care whether the
year 23456543215678908765432124354667 is a leap year? Surely no one alive
today is likely to care whether any given year much beyond their lifetime
is a leap year; barring truly miraculous achievements in medical science,
no one on this newsgroup is likely to live much past 2100, let alone to a
time where the year exceeds 2^31.

Now, if you simply started this thread to make a purely intellectual
programming point and then chose a questionable example, forgive my
remarks.

We don't need another Y2K problem!

I don't know if you had airplanes falling out of the sky into your backyard,
but that was scary for me.
 
S

Stefan Ram

Rhino said:
Now, if you simply started this thread to make a purely
intellectual programming point and then chose a questionable
example, forgive my remarks.

To make this point, it was not necessary to quote the full
text of my article. I suggest that you consider to quote only
a relevant part of an article you respond to.

The example was chosen to talk about the usage of algorithms
bound to interfaces only. I agree that there usually is no
need to find the leap year property for very large year numbers.
 
L

Luc The Perverse

Stefan Ram said:
To make this point, it was not necessary to quote the full
text of my article. I suggest that you consider to quote only
a relevant part of an article you respond to.

You should pick your battles - there are people who are top posting and
people not quoting at all that are the real problem.
 
A

Alan Krueger

Stefan said:
But this will only handle years up to about 2^31-1 or so!

That only gives us until 2,147,483,647 AD. That's not enough to last
until our local star goes through its red giant stage.
 
L

Luc The Perverse

Stefan Ram said:
So helping someone to improve his articles is regarded
as a »battle« by you.

You mean you have never fought trolls - who insist that their 3 posts of
usenet experience is vastly superior to the cumulative tens of thousands of
posts by the group regulars?

Yes - telling someone they are posting wrong is an attack. And you
shouldn't attack people for doing everything right except a little trimming.
 
R

Rhino

Stefan Ram said:
To make this point, it was not necessary to quote the full
text of my article. I suggest that you consider to quote only
a relevant part of an article you respond to.
Some people yell at you when you snip posts and some people yell at you when
you don't. It's hard to know what will please people sometimes. Sorry for
guessing incorrectly.
The example was chosen to talk about the usage of algorithms
bound to interfaces only. I agree that there usually is no
need to find the leap year property for very large year numbers.
Fair enough :)
 
R

Rhino

Luc The Perverse said:
You mean you have never fought trolls - who insist that their 3 posts of
usenet experience is vastly superior to the cumulative tens of thousands
of posts by the group regulars?

Yes - telling someone they are posting wrong is an attack. And you
shouldn't attack people for doing everything right except a little
trimming.
Thanks Luc but I don't consider myself attacked; Stefan was making a
reasonable point.

I'm afraid I have been getting lax about snipping lately. I've had people
"yelling" at me for snipping; one guy even _killfiled_ me because I had
snipped a previous poster's _sig_, not the actual content of his post. I
suppose I've been erring on the side of caution as a result.

Netiquette is a bit of a balancing act at the best of times; there is not
always a universal agreement on what is right or wrong. As long as we are
reasonable human beings, we can usually find a middle ground that most
people can live with. I'll try to snip more in future :)
 
L

Luc The Perverse

Rhino said:
Thanks Luc but I don't consider myself attacked; Stefan was making a
reasonable point.

I'm afraid I have been getting lax about snipping lately. I've had people
"yelling" at me for snipping; one guy even _killfiled_ me because I had
snipped a previous poster's _sig_, not the actual content of his post. I
suppose I've been erring on the side of caution as a result.

Netiquette is a bit of a balancing act at the best of times; there is not
always a universal agreement on what is right or wrong. As long as we are
reasonable human beings, we can usually find a middle ground that most
people can live with. I'll try to snip more in future :)

You then are more reasonable than most people
 
P

Patricia Shanahan

Stefan said:
But this will only handle years up to about 2^31-1 or so!
....
So there is no need to bind it to the special type »int« that
has many more features which are not needed here. The
following untested draft shows how the algorithm can be freed
from this binding.

To me, this is a prime example of inappropriate extension.

Before extending a method to a wider domain, it is essential to consider
any underlying assumptions, and decide whether they remain valid over
the new domain. There is often far more to widening the domain than just
picking bigger data types.

In this case, the underlying assumption is the Gregorian calendar, and
its approximation to the relationship between day and year length. Leap
seconds are coming in about one a year, and most of them are in the same
direction. At one second per year, it would only take 86,400 years to
accumulate a day of leap seconds. Obviously, something is going to have
to change in time management well within the next hundred thousand years.

Sometimes generality is free, sometimes it costs, in programming and
testing time, and in runtime efficiency. In this case, the generality
gain from using int rather than short is effectively free, and there is
some risk short would not be wide enough.

On the other hand, int is simple, efficient, and handles very
effectively the entire domain over which the algorithm makes any sense.
It is a fine data type for this job. BigInteger, or even long, would be
overkill.

Patricia
 
S

Stefan Ram

Patricia Shanahan said:
On the other hand, int is simple, efficient, and handles very

I should have chosen a better example in order not to distract
the attention of most readers to the special example of a
determination of the leap year property.

Your criticism addresses another issue regarding the language
Java. One could imagine other languages where a more general
notation in the source code would not exclude using the
notation with the datatype »int«.

For example, I believe, in C++, one can write:

template<typename T> bool is_leap_year( T const year_number )
{ const bool is_quad = year_number % 4 == 0;
const bool is_century = year_number % 100 == 0;
const bool is_quadcentury = year_number % 400 == 0;
const bool is_canceled = is_century & !is_quadcentury;
const bool is_leap_year = is_quad & !is_canceled;
return is_leap_year; }

This now is general insofar as it can be applied to
every type implementing the operation »%« -- not
only »int«. But it can be applied to »int« as is:

#include <iostream> // ::std::cout
#include <ostream> // <<

int main(){ ::std::cout << is_leap_year( 2006 )<< '\n'; }

0

In Java one most prematurely decide between coding for »int«
or coding a more general formulation or write two or more
similar methods by hand.
 
S

Stefan Ram

template<typename T> bool is_leap_year( T const year_number )
{ const bool is_quad = year_number % 4 == 0; (...)
int main(){ ::std::cout << is_leap_year( 2006 )<< '\n'; }

So, how can this be achieved in Java?

My approach was as follows:

interface IsCongruentModuloIntInt
{ boolean isCongruentModulo( int comparand, int modulus ); }

class Int implements IsCongruentModuloIntInt
{ final int value;
public Int( final int value ){ this.value = value; }
public boolean isCongruentModulo
( final int comparand, final int modulus )
{ return( this.value - comparand )% modulus == 0; }}

public class Main
{
public static boolean isLeapYear
( final IsCongruentModuloIntInt yearNumber )
{ final boolean isQuad = yearNumber.isCongruentModulo( 0, 4 );
final boolean isCentury = yearNumber.isCongruentModulo( 0, 100 );
final boolean isQuadcentury = yearNumber.isCongruentModulo( 0, 400 );
final boolean isCanceled = isCentury & !isQuadcentury;
final boolean isLeapYear = isQuad & !isCanceled;
return isLeapYear; }

public static void main( final java.lang.String[] args )
{ java.lang.System.out.println( isLeapYear( new Int( 2006 ))); }}

false

One can hope now that the JIT-optimizer eventually could
inline all the calls to Int-methods so that one will end at
code as efficient as if a special int case would have been
written. So what C++ templates do very early Java would do
very late.

But I have heard often that interface calls in Java still are
somewhat less efficient and might hinder such global inlining
optimizations.
 
R

Roedy Green

public static boolean
isLeapYear( final int yearNumber )
{ final boolean isQuad = yearNumber % 4 == 0;
final boolean isCentury = yearNumber % 100 == 0;
final boolean isQuadcentury = yearNumber % 400 == 0;
final boolean isCanceled = isCentury & !isQuadcentury;
final boolean isLeapYear = isQuad & !isCanceled;
return isLeapYear; }

there are an surprisingly large number of definitions of leap year
besides the Gregorian one we are familiar with. See
http://mindprod.com/jgloss/leap.html
 
R

Roedy Green

Do you really think the average Java programmer will ever care whether the
year 23456543215678908765432124354667 is a leap year?

there will likely not be any humans beyond the year 3000 and certainly
by then the calendar used on earth will have changed.
 
P

Patricia Shanahan

Stefan said:
I should have chosen a better example in order not to distract
the attention of most readers to the special example of a
determination of the leap year property.

On the contrary, it brought out beautifully the key point, that there is
far more to extending the range of a method than merely changing its
data types. The need to analyze the appropriateness of the method to the
new range is not a strange artifact of the leap year program. It needs
to be done whenever you extend a method to a range other than the one
for which it was designed, written, and tested.

Patricia
 
T

Timo Stamm

Roedy said:
there will likely not be any humans beyond the year 3000 and certainly
by then the calendar used on earth will have changed.

You imply that the algorithm is only used on past or present years. What
if I want to know whether the sun will implode in a leap year?


SCRN,
Timo
 
L

Luc The Perverse

Timo Stamm said:
You imply that the algorithm is only used on past or present years. What
if I want to know whether the sun will implode in a leap year?

If you possess the knowedge to narrow down to within a specific year when
the sun will implode I would think you would have the knowledge to switch
your java program to using 64 bit integers
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top