Algorithm collection

Hello,

I created a collection of algorithms which is available under

http://seed7.sourceforge.net/algorith/algorith.htm

If somebody is interested in

- Heap sort, Merge sort or other sorting algorithms
- Computing PI with 1000 decimal digits
- How to encode and decode with Base64, Quoteded-printable and
Uuencode
- Computing the easter date or the julian day number
- The Lempel Ziv Welch (LZW) compression
- Mersenne prime numbers
- The peasant multiplication

and other algorithms, this is the right place.
If you have some algorithms, I would be glad
to add them (when they are GPL / LGPL).

Greetings Thomas Mertes

Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

<thomas.mertes@gmx.at> wrote in message
news:f305add1-1e23-465b-8174-244a684f27c4@k30g2000hse.googlegroups.com...
> Hello,
>
> I created a collection of algorithms which is available under
>
> http://seed7.sourceforge.net/algorith/algorith.htm
>

People who use recursion to calculate Fibonacci numbers shouldn't be allowed
on sci.math. Or the Internet, for that matter.
(In case you don't know why, try your algorithm to calculate the 100th
Fibonacci number.)

On Sat, 6 Sep 2008 17:58:24 +0200, "Steven"
<steven_504@telenet.be> wrote:

><thomas.mertes@gmx.at> wrote in message
>news:f305add1-1e23-465b-8174-244a684f27c4@k30g2000hse.googlegroups.com...
>> Hello,
>>
>> I created a collection of algorithms which is available under
>>
>> http://seed7.sourceforge.net/algorith/algorith.htm
>>
>
>People who use recursion to calculate Fibonacci numbers shouldn't be allowed
>on sci.math. Or the Internet, for that matter.

You might want to qualify that by specifying which recursion
formula is being used. The algorithm he uses is perfectly
horrid; however there are recursive formulas that are much better
for large n than the iterative algorithm.

>(In case you don't know why, try your algorithm to calculate the 100th
>Fibonacci number.)


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

On Sep 6, 8:07*pm, c...@tiac.net (Richard Harter) wrote:
> On Sat, 6 Sep 2008 17:58:24 +0200, "Steven"
>
> <steven_...@telenet.be> wrote:
> ><thomas.mer...@gmx.at> wrote in message
> >news:f305add1-1e23-465b-8174-244a684f27c4@k30g2000hse.googlegroups.com....
> >> Hello,
>
> >> I created a collection of algorithms which is available under
>
> >>http://seed7.sourceforge.net/algorith/algorith.htm
>
> >People who use recursion to calculate Fibonacci numbers shouldn't be allowed
> >on sci.math. Or the Internet, for that matter.
>
> You might want to qualify that by specifying which recursion
> formula is being used. *The algorithm he uses is perfectly
> horrid; however there are recursive formulas that are much better
> for large n than the iterative algorithm.
There's no need of an iterative algorithm either. An explicit formulae
can be used :

http://en.wikipedia.org/wiki/Fibonac...orm_expression

> >(In case you don't know why, try your algorithm to calculate the 100th
> >Fibonacci number.)
>
> Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
> Save the Earth now!!
> It's the only planet with chocolate.

On Sep 6, 8:07*pm, c...@tiac.net (Richard Harter) wrote:
> On Sat, 6 Sep 2008 17:58:24 +0200, "Steven"
>
> <steven_...@telenet.be> wrote:
> ><thomas.mer...@gmx.at> wrote in message
> >news:f305add1-1e23-465b-8174-244a684f27c4@k30g2000hse.googlegroups.com....
> >> Hello,
>
> >> I created a collection of algorithms which is available under
>
> >>http://seed7.sourceforge.net/algorith/algorith.htm
>
> >People who use recursion to calculate Fibonacci numbers shouldn't be allowed
> >on sci.math. Or the Internet, for that matter.
>
> You might want to qualify that by specifying which recursion
> formula is being used. *The algorithm he uses is perfectly
> horrid; however there are recursive formulas that are much better
> for large n than the iterative algorithm.

There's no need of an iterative algorithm either. An explicit formulae
can be used :

http://en.wikipedia.org/wiki/Fibonac...orm_expression
> >(In case you don't know why, try your algorithm to calculate the 100th
> >Fibonacci number.)
>
> Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
> Save the Earth now!!
> It's the only planet with chocolate.

"stdazi" <stdazi@gmail.com> wrote in message
news:f0b09aee-2429-455c-a22b-0e60ee6d4aac@2g2000hsn.googlegroups.com...
> There's no need of an iterative algorithm either. An explicit formulae
> can be used :
>
> http://en.wikipedia.org/wiki/Fibonac...orm_expression

I think most of the time it's not about the actual value, but rather about
the programming logic as an illustration of recursion.
Teachers often fail to make a difference between the recursive definition
and the algorithm implementation. In the Fibonacci case the definition is
perfectly fine, while the implementation is indeed horrid.

[OT, programming]
Students seem to underestimate the cost of parameter passing in function
calls. They test their program for F10 or F20, and everythings seems fine.
At F50 they are puzzled why calculating F50 takes such a long time. Some
have the guts to try F100, and think the program goes into in infinite loop.
Programmers remember from class that "recursion can be extremely powerful",
and apply tail recursion where iteration is so much simpler and more
efficient.

One of the best recursion examples I know is Towers of Hanoi: the recursive
solution is easy to understand, and it makes sense to actually solve it
recursively (though I'm aware that there are iterative solutions).
[/OT]

> Richard Harter,
> c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
> Save the Earth now!!
> It's the only planet with chocolate.

Prove it!! (though you're probably right :-))

Steven

On 6 Sep., 17:58, "Steven" <steven_...@telenet.be> wrote:
> <thomas.mer...@gmx.at> wrote in message
>
> news:f305add1-1e23-465b-8174-244a684f27c4@k30g2000hse.googlegroups.com...
>
> > Hello,
>
> > I created a collection of algorithms which is available under
>
> >http://seed7.sourceforge.net/algorith/algorith.htm
>
> People who use recursion to calculate Fibonacci numbers shouldn't be allowed
> on sci.math. Or the Internet, for that matter.
This seems to be a little bit exaggerated...

> (In case you don't know why, try your algorithm to calculate the 100th
> Fibonacci number.)
Thank you, for pointing that out.
Normally I use fib(20) as simple benchmark to test the
performance of recursive calls. Adding the recursive fibonacci
function to the algorithm collection without any comment was
a bad idea. The possibility that someone could seriously use it
instead of an iterative algorithm never came to my mind.
Now I added the following comment:

This algorithm just uses the recursive definition of the fibonacci
function. It can be used as benchmark to test the performance
of recursive calls. For a solution with better scalability use the
iterative fibonacci function below.

I added also an iterative fibonacci function. See here:
http://seed7.sourceforge.net/algorit...#iterative_fib

for the people who are not able to extract an iterative
fibonacci algorithm from my other fibonacci example:
http://seed7.sourceforge.net/algorit...nacci_sequence

Greetings Thomas Mertes

Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

On Mon, 8 Sep 2008 12:14:22 +0200, "Steven"
<steven_504@telenet.be> wrote:

>"stdazi" <stdazi@gmail.com> wrote in message
>news:f0b09aee-2429-455c-a22b-0e60ee6d4aac@2g2000hsn.googlegroups.com...
>> There's no need of an iterative algorithm either. An explicit formulae
>> can be used :
>>
>> http://en.wikipedia.org/wiki/Fibonac...orm_expression
>
>I think most of the time it's not about the actual value, but rather about
>the programming logic as an illustration of recursion.
>Teachers often fail to make a difference between the recursive definition
>and the algorithm implementation. In the Fibonacci case the definition is
>perfectly fine, while the implementation is indeed horrid.

Quite often people do a superficial take (or none at all) on the
costs of an algorithm, e.g., the number of calls that must be
made, the storage usage per call, the incremental storage use per
call, and the time usage per call. One value of this task is to
illustrate the analysis of different alternatives for students.

For example, the closed form expression is superficially
attractive, but what are the costs? The wikipedia article has
all of the necessary information laid out for us. There we
discover that the number of bits in F(n) is approximately
n*log2(phi), i.e. O(n) bits. The closed form requires that we
compute phi**n/sqrt(5) with sufficient accuracy to produce the
O(n) bits of F(n).

This creates a new problem; how do we raise phi to the n'th power
and what are the costs? Here the hapless students may be well
out of their depth. It turns out that the costs are slightly
worse than O(n*log n).

The costs of the simple recursion grow exponentially with n.
Enough said.

The simple iterative formula has an O(n^2) execution cost. It
will profit the student to discover why.

Finally, the recursive alogorithm that computes (F(n),F(n-1))
from (F(n/2),F(n/2-1)) again is slightly worse than O(n*log n),
depending on the efficiency of the long multiplication algorithm
used. (However it will be faster than the closed form algorithm;
it will profit the student to discover why.) The conversion to
an iterative version is simple.


>
>[OT, programming]
>Students seem to underestimate the cost of parameter passing in function
>calls. They test their program for F10 or F20, and everythings seems fine.
>At F50 they are puzzled why calculating F50 takes such a long time. Some
>have the guts to try F100, and think the program goes into in infinite loop.
>Programmers remember from class that "recursion can be extremely powerful",
>and apply tail recursion where iteration is so much simpler and more
>efficient.
>
>One of the best recursion examples I know is Towers of Hanoi: the recursive
>solution is easy to understand, and it makes sense to actually solve it
>recursively (though I'm aware that there are iterative solutions).
>[/OT]
>
>> Richard Harter,
>> c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
>> Save the Earth now!!
>> It's the only planet with chocolate.
>
>Prove it!! (though you're probably right :-))
>
>Steven
>
>

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

<thomas.mertes@gmx.at> wrote in message
news:41313eef-dc98-49d8-86cd-e8e0ee3b0145@z72g2000hsb.googlegroups.com...
> On 6 Sep., 17:58, "Steven" <steven_...@telenet.be> wrote:
>> <thomas.mer...@gmx.at> wrote in message
>>
>> news:f305add1-1e23-465b-8174-244a684f27c4@k30g2000hse.googlegroups.com...
>>
>> > Hello,
>>
>> > I created a collection of algorithms which is available under
>>
>> >http://seed7.sourceforge.net/algorith/algorith.htm
>>
>> People who use recursion to calculate Fibonacci numbers shouldn't be
>> allowed
>> on sci.math. Or the Internet, for that matter.
> This seems to be a little bit exaggerated...


Ah, don't make heavy weather of it; this is the internets! ;-)

"Steven" <steven_504@telenet.be> writes:
> <thomas.mertes@gmx.at> wrote in message
> news:f305add1-1e23-465b-8174-244a684f27c4@k30g2000hse.googlegroups.com...
>> Hello,
>>
>> I created a collection of algorithms which is available under
>>
>> http://seed7.sourceforge.net/algorith/algorith.htm
>>
>
> People who use recursion to calculate Fibonacci numbers shouldn't be allowed
> on sci.math. Or the Internet, for that matter.
> (In case you don't know why, try your algorithm to calculate the 100th
> Fibonacci number.)

I can happily use recursion to calculate the 1000000th Fibonacci number.

People who are unable to efficiently calculate Fibonacci numbers
using a recursive algorithm shouldn't be allowed on comp.theory.

Phil
--
The fact that a believer is happier than a sceptic is no more to the
point than the fact that a drunken man is happier than a sober one.
The happiness of credulity is a cheap and dangerous quality.
-- George Bernard Shaw (1856-1950), Preface to Androcles and the Lion