Sage code "for educational purposes only"?

[Jeroen Demeyer]

Hello,

Should there be code in Sage which is extremely slow and for educational
purposes only? I am talking about eratosthenes() which is just a very
slow alternative to prime_range().

I would just remove that code, but maybe people have other opinions...

Jeroen.

[Michael Orlitzky]

It's nice to leave in code like this and use it as part of the test
suite. It would be easy to check that the sieve of Eratosthenes is
correct, but prime_range() is a long chain of dark magic to me.

A good test would be that they agree on the primes below (say) 1,000:

sage: eratosthenes(1000) == prime_range(1000)
True

There are some tests for prime_range() already, e.g.

sage: L = prime_range(25000,2500000)
sage: len(L)
180310

but who knows if the results are correct.

[William Stein]

On Wed, Feb 25, 2015 at 10:15 AM, Michael Orlitzky <mic...@orlitzky.com> wrote:
> On 02/25/2015 12:55 PM, Jeroen Demeyer wrote:
>> Hello,
>>
>> Should there be code in Sage which is extremely slow and for educational
>> purposes only? I am talking about eratosthenes() which is just a very
>> slow alternative to prime_range().
>>
>> I would just remove that code, but maybe people have other opinions...

I also agree it is OK to have such *code*. However, to have it just
there without a name that strongly emphasizes its toy nature is very
bad. People often think that if f is a function defined in a
respectable math software system (Magma or Sage), then the performance
of f(n) is at least reasonable.

I think it's best to name any functionality that is "is extremely slow
and for educational
purposes" explicitly with "toy" somewhere in the name. If you do:

sage: search_src("toy")

you'll see this convention often in sage.

I would be for deprecating eratosthenes() and replacing it by something like


toys.eratosthenes()

or possibly eratosthenes_toy()...

I like the idea of a toys.[tab] that gathers together toy implementations...

>
> It's nice to leave in code like this and use it as part of the test
> suite. It would be easy to check that the sieve of Eratosthenes is
> correct, but prime_range() is a long chain of dark magic to me.
>
> A good test would be that they agree on the primes below (say) 1,000:
>
> sage: eratosthenes(1000) == prime_range(1000)
> True
>
> There are some tests for prime_range() already, e.g.
>
> sage: L = prime_range(25000,2500000)
> sage: len(L)
> 180310
>
> but who knows if the results are correct.
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.



--
William (http://wstein.org)

[David Joyner]

On Wed, Feb 25, 2015 at 2:10 PM, William Stein <wst...@gmail.com> wrote:
> On Wed, Feb 25, 2015 at 10:15 AM, Michael Orlitzky <mic...@orlitzky.com> wrote:

...

>
> I think it's best to name any functionality that is "is extremely slow
> and for educational
> purposes" explicitly with "toy" somewhere in the name. If you do:
>
> sage: search_src("toy")
>
> you'll see this convention often in sage.
>
> I would be for deprecating eratosthenes() and replacing it by something like
>
>
> toys.eratosthenes()
>
> or possibly eratosthenes_toy()...
>
> I like the idea of a toys.[tab] that gathers together toy implementations...
>

+1

>>

...

[Andrey Novoseltsev]

Um, can it be perhaps slightly less diminishing? Like education.[tab] or edu.[tab]?

E.g. I wrote
http://sagemath.org/doc/reference/numerical/sage/numerical/interactive_simplex_method.html
which is certainly not designed for production work, but it was quite a bit of work on its own ;-)

I am also not a fan of prefixing/suffixing all names with something or grouping it into a special folder - toy number theory should still go into number theory tree and included into its documentation, just perhaps exported through a dedicated module somewhere.

Andrey

[kcrisman]

Um, can it be perhaps slightly less diminishing? Like education.[tab] or edu.[tab]?

We have a number of crypto examples of "toy" things, and David J. long ago wrote quite a few things like Euler's method and so forth.  It is very, very worthwhile (if for no other reason than to have opportunities for people to understand how to code math!).

 

 

I am also not a fan of prefixing/suffixing all names with something or grouping it into a special folder - toy number theory should still go into number theory tree and included into its documentation, just perhaps exported through a dedicated module somewhere.

I don't think we need toy.[tab] or number_theory.toy.[tab] or anything.  Who on earth thinks that the Sieve of Eratosthenes is designed for modern production work???  Or Euler's Method (well, I'm not a numerical analyst, so maybe, but I assume other integration is more prominent).  In some cases of course this is useful to prefix, and we have http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/toy_buchberger.html and things like that for such cases.

If the documentation of any given method says it's for educational purposes only - and there are a number of those - then that seems fine to me.

- kcrisman

[Michael Orlitzky]

On 02/25/2015 02:10 PM, William Stein wrote:
>
> toys.eratosthenes()
>
> or possibly eratosthenes_toy()...
>

In this case, the name refers to the implementation, not the
functionality, so I don't think it's a big deal. It's not a "prime
number routine" that just happens to be slow -- it's the sieve of
Eratosthenes, running as fast as it can. Any other implementation will
be just as slow.

[William Stein]

I'm not sure I agree. This eratosthenes function is pure Python code.
It would probably be 100 times faster if rewritten in Cython using
int's or long's. In fact, this is (more or less) the canonical first
example of a function that benefits directly from being compiled
rather than pure Python -- it's the first example on the Pyrex page:

http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/

That you would think "it's the sieve of Eratosthenes, running as fast
as it can. Any other implementation will be just as slow" is in fact
to me a very strong argument for why it *should* have toy in the name.
Since if it did, it's highly unlikely you would think it is "running

as fast as it can".

William


--
William (http://wstein.org)

[Vincent Delecroix]

I also feel like we should remove it from the source code. The purpose
of eratosthene is very different from what Andrey pointed out with his
module about the simplex method. The function eratosthene is just an
illustration of "how you code a nice Python function". While the
simplex module is more of "exploration and experimentation of an
algorithm". For eratosthene you need to read the code while for the
simplex module you just experiment the functionalities of the object.

So I propose to move eratosthene from the source to the documentation
("where" is another question). And, as William pointed out, it would
be a good example to illustrate the power of Cython. And I definitely
think that Andrey simplex stuff has its place inside the source.

Vincent

[Michael Orlitzky]

On 02/25/2015 03:04 PM, William Stein wrote:
>
>> Any other implementation will be just as slow.
>
> I'm not sure I agree. This eratosthenes function is pure Python code.
> It would probably be 100 times faster if rewritten in Cython using
> int's or long's. In fact, this is (more or less) the canonical first
> example of a function that benefits directly from being compiled
> rather than pure Python -- it's the first example on the Pyrex page:
>
> http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/
>
> That you would think "it's the sieve of Eratosthenes, running as fast
> as it can. Any other implementation will be just as slow" is in fact
> to me a very strong argument for why it *should* have toy in the name.
> Since if it did, it's highly unlikely you would think it is "running
> as fast as it can".
>

Surely we aren't going to start naming things "toy" just because they're
written in Python?

I tested in Cython and was going to post numbers, but looking back, you
only suggested it would be "100 times faster". The speedup is actually
better than that (looks sublinear) -- I just don't consider a factor of
100 on a silly algorithm to be a big difference. You still hit a running
time of (1/100)*forever pretty quickly.

[Simon King]

Hi!

On 2015-02-25, Jeroen Demeyer <jdem...@cage.ugent.be> wrote:
> Should there be code in Sage which is extremely slow and for educational
> purposes only?

I believe such code is valuable.

Best regards,
Simon

[Jori Mantysalo]

On Wed, 25 Feb 2015, Jeroen Demeyer wrote:

> Should there be code in Sage which is extremely slow and for educational
> purposes only?

As an additional package "educational-algorithms"?

--
Jori Mäntysalo

[Pedro Cruz]

+1 for the  package "educational-algorithms" but called "educational-packages" or "educational-library".

MathSciNet catalog has the category "Mathematics education"

    http://www.ams.org/mathscinet/msc/msc2010.html?t=97-XX

being the last topic after all the mathematical edge cutting works.

This could inspire an "educational-library" (this name is maybe more general than just "algorithms").

Pedro

[parisse]

Le mercredi 25 février 2015 20:56:06 UTC+1, kcrisman a écrit :

Who on earth thinks that the Sieve of Eratosthenes is designed for modern production work???

Me. I´m using it for the ithprime function in Giac. ithprime(700000) returns 10570841 in 0.07 second while in sage prime_range(1,10570841) takes about the same time (0.08s) to compute (much more to display).

[Jori Mantysalo]

On Thu, 26 Feb 2015, Pedro Cruz wrote:

> +1 for the  package "educational-algorithms" but called
> "educational-packages" or "educational-library".

Yes, '-packages' or '-library' is better name.

Hmmm... actually there could be, in principle, three kind of algorithms:

1) Fast ones, that we normally use.

2) Educational, algorithms that made it easy to see some computational
proof etc.

3) Most basic and directly from formal definition made algorithms to
cross-check fast ones.

Usually type 2 and 3 are same thing. Always?


--
Jori Mäntysalo

[Niles Johnson]

I'm in favor of moving such toys to an educational-library.

[Vincent Delecroix]

I really do not see the point of an educational-library if the code
will not appear in the documentation. It is precisely the code which
is interesting!

Vincent

[mmarco]

I don't like the "educational" name, since it can be misleading. Some could think that they are functions that are useful for teaching (in this case, for teaching basic concepts about prime numbers), whereas what we would be meaning is that its educational value would be in looking at the code itself and learning how to code.

It is not the case of the Erathostenes sieve, but in some other cases (like buchberger), these toy methods are not only there for people to learn about them, but also can be used as a fallback for the cases where no fast implementation is available (yes, they can be horribly slow, but horribly slow is sometimes better than nothing). 

[kcrisman]

In general, I think it is FAR more useful to spend our time on making the documentation for any "educational"/"toy" functions very clear than to creating some huge change of a new directory that no one will know about, deprecation, broken links, ... Unless people feel that Sage is *only* a research tool, there is no reason not to have such functions, as long as it is very clear what they do and don't do.  Anyone who is looking for speed will presumably be able to bother to read documentation that starts "The function easy_squirrel() is only to demonstrate the existence of a squirrel; for various algorithms used in actually finding squirrels, please see sage.squirrel.blazing_fast()".

[Travis Scrimshaw]

> Should there be code in Sage which is extremely slow and for educational
> purposes only?

I believe such code is valuable.

I believe so as well. As Michael said, at the very least it's useful as a testing tool. (Also we have done something similar by having an "algorithm" keyword for various methods.) I also agree with Karl-Dieter that we should spend much more time documenting the functions than moving them to a separate folder (much less deciding on which functions should go into such a folder).

Best,
Travis

[Robert Bradshaw]

I would say such a function belongs in the documentation only, and we
should have an easy way of testing (and perhaps importing) code
defined there.

[Nathann Cohen]

Um, can it be perhaps slightly less diminishing? Like education.[tab] or edu.[tab]?

E.g. I wrote
http://sagemath.org/doc/reference/numerical/sage/numerical/interactive_simplex_method.html
which is certainly not designed for production work, but it was quite a bit of work on its own ;-)

It is "certainly not designed for production work", yet you import things like `LPProblem` in the global namespace ? I will write a patch right now that adds "interactive" in front of all these classes.

Nathann

[Nathann Cohen]

It is "certainly not designed for production work", yet you import things like `LPProblem` in the global namespace ? I will write a patch right now that adds "interactive" in front of all these classes.

See http://trac.sagemath.org/ticket/17867 (needs_review)

Nathann 

[Thierry]

Hi,

An issue is that names of functions/methods are usually about /what/ is
being done, not /how/, hence i am in favor to deprecate eratosthenes()
function and move the code as an 'algorithm' option of prime_range(). It
should be noticed that the other algorithms depend on pari, hence having
at least one self-contained implementation could be of some help, e.g.
for consistency testing (and hypothetically for far-future
modularization).

Recording such self-contained implementations is not only interesting for
educational purpose (this is sometimes frustrating to do function?? and
only see some calls to an external lib whose source code is not easily
available from Sage), but also in a context such as
http://wiki.sagemath.org/GSoC/2015#Generic_Dispatcher

I remember a discussion with Luca at Orsay during preparation of H2020
stuff, about using Sage as a research tool, where being able to tell Sage
"i want to rely only on such libs" makes sense. So, having a way to record
which lib is called in a dispatcher (in particular when "no lib" is
required) is pretty interesting, in particular about reproductibility
concerns.

Further (and less directly related), i would have proposed to move most
*_prime or prime_* functions from the global namespace to methods of the
Primes() class (e.g. primes_first_n() vs Primes().__getitem__() or
is_prime() vs Primes().__contains__() and so on). This is indeed easier to
find primes-related methods, for example, how can i discover the existence
of the next_prime() function from the tab completion ?

Ciao,
Thierry



> Jeroen.