# Freeing Algorithms

Discussion in 'Java' started by Stefan Ram, Mar 18, 2006.

1. ### Stefan RamGuest

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
state what the meaning of this operation is.

Stefan Ram, Mar 18, 2006

2. ### RhinoGuest

"Stefan Ram" <-berlin.de> wrote in message
news:-berlin.de...
> 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
> 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.

--
Rhino

Rhino, Mar 18, 2006

3. ### Luc The PerverseGuest

"Rhino" <> wrote in message
news:6kYSf.7740\$...
>
> "Stefan Ram" <-berlin.de> wrote in message
> news:-berlin.de...
>> 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
>> 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.

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.

--
LTP

Luc The Perverse, Mar 18, 2006
4. ### Stefan RamGuest

"Rhino" <> writes:
>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.

Stefan Ram, Mar 18, 2006
5. ### Luc The PerverseGuest

"Stefan Ram" <-berlin.de> wrote in message
news:-berlin.de...
> "Rhino" <> writes:
>>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.

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

--
LTP

"I'm not part of the problem; I'm Republican." - Dubyai Bush

Luc The Perverse, Mar 18, 2006
6. ### Alan KruegerGuest

Stefan Ram wrote:
> 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.

Alan Krueger, Mar 18, 2006
7. ### Stefan RamGuest

"Luc The Perverse" <> writes:
>>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.

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

Stefan Ram, Mar 18, 2006
8. ### Luc The PerverseGuest

Re: [OT]answer style (was: Freeing Algorithms)

"Stefan Ram" <-berlin.de> wrote in message
news:-berlin.de...
> "Luc The Perverse" <> writes:
>>>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.

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

--
LTP

Luc The Perverse, Mar 18, 2006
9. ### RhinoGuest

"Stefan Ram" <-berlin.de> wrote in message
news:-berlin.de...
> "Rhino" <> writes:
>>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.
>

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

--
Rhino

Rhino, Mar 18, 2006
10. ### RhinoGuest

Re: [OT]answer style (was: Freeing Algorithms)

"Luc The Perverse" <> wrote in message
news:...
> "Stefan Ram" <-berlin.de> wrote in message
> news:-berlin.de...
>> "Luc The Perverse" <> writes:
>>>>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.

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

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

--
Rhino

Rhino, Mar 18, 2006
11. ### Luc The PerverseGuest

Re: [OT]answer style (was: Freeing Algorithms)

"Rhino" <> wrote in message
news:yy_Sf.7787\$...
>
> "Luc The Perverse" <> wrote in message
> news:...
>> "Stefan Ram" <-berlin.de> wrote in message
>> news:-berlin.de...
>>> "Luc The Perverse" <> writes:
>>>>>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.
>>>
>>> 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.
>>

> 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

--
LTP

Luc The Perverse, Mar 18, 2006
12. ### Patricia ShanahanGuest

Stefan Ram wrote:

> 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

Patricia Shanahan, Mar 18, 2006
13. ### Stefan RamGuest

Patricia Shanahan <> writes:
>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.

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.

Stefan Ram, Mar 19, 2006
14. ### Stefan RamGuest

-berlin.de (Stefan Ram) writes:
>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.

Stefan Ram, Mar 19, 2006
15. ### Roedy GreenGuest

On 18 Mar 2006 17:29:53 GMT, -berlin.de (Stefan Ram)
wrote, quoted or indirectly quoted someone who said :

>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
--
http://mindprod.com Java custom programming, consulting and coaching.

Roedy Green, Mar 19, 2006
16. ### Roedy GreenGuest

On Sat, 18 Mar 2006 13:29:35 -0500, "Rhino"
<> wrote, quoted or indirectly
quoted someone who said :

>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.
--
http://mindprod.com Java custom programming, consulting and coaching.

Roedy Green, Mar 19, 2006
17. ### Patricia ShanahanGuest

Stefan Ram wrote:
> Patricia Shanahan <> writes:
>
>>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.

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

Patricia Shanahan, Mar 19, 2006
18. ### Timo StammGuest

Roedy Green schrieb:
> On Sat, 18 Mar 2006 13:29:35 -0500, "Rhino"
> <> wrote, quoted or indirectly
> quoted someone who said :
>
>> 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.

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

Timo Stamm, Mar 19, 2006
19. ### Stefan RamGuest

Roedy Green <> writes:
>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

I know.

That's why, within my source tree, this is placed into the
package »gregorian«. This was not visibly from my post.

Stefan Ram, Mar 19, 2006
20. ### Luc The PerverseGuest

"Timo Stamm" <> wrote in message
news:441caac9\$0\$21660\$-online.net...
> Roedy Green schrieb:
>> On Sat, 18 Mar 2006 13:29:35 -0500, "Rhino"
>> <> wrote, quoted or indirectly
>> quoted someone who said :
>>
>>> 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.

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

--
LTP

Luc The Perverse, Mar 19, 2006