Preferred languages?

[Peter Hackman]

After a period of devoting my energy to non-mathematical interests I recently looked over my programs, including a simple MPQS, an even simpler ECM (I took stage 2 from Crandall-Pomerance), and a Pohlig-Hellman+rho DL routine.

I had even started working on SIQS but shelved the project for lack of good ideas on generating the a factors (I think I know better now). All my programs are in python (2.5) which is fairly easy to write (no declarations, nice list constructions, etc.). However, they're slow, about 10-20 times slower than some of the slicker programs. In fact, going beyond 50 digits they're too slow to allow much experimenting with parameters - which is the whole point, otherwise I could just copy someone else's program.

It was pointed out to me in an earlier thread that python is really too slow for these applications, so I've been contemplating re-writing everything in some low-level language. Before retiring I worked in and taught pure math at Linköping University, a position that obviously didn't call for much programming. My previous experience was mainly in Fortran77,
way back. Most of the
programs I've seen seem to use C. Sam Wagstaff kindly sent me a very long QS program in ratfor (which looks pretty readable).
Dario Alpern has been using Java. Someone has suggested Pyrex.
I've no idea about the relative merits of these languages, or their potential
for speeding up things.

What would you suggest, taking into account
1) performance
2) compatibility with Mac OSX
3) ease of learning
4) readability
?

[xilman]

Originally Posted by Peter Hackman

After a period of devoting my energy to non-mathematical interests I recently looked over my programs, including a simple MPQS, an even simpler ECM (I took stage 2 from Crandall-Pomerance), and a Pohlig-Hellman+rho DL routine.

I had even started working on SIQS but shelved the project for lack of good ideas on generating the a factors (I think I know better now). All my programs are in python (2.5) which is fairly easy to write (no declarations, nice list constructions, etc.). However, they're slow, about 10-20 times slower than some of the slicker programs. In fact, going beyond 50 digits they're too slow to allow much experimenting with parameters - which is the whole point, otherwise I could just copy someone else's program.

It was pointed out to me in an earlier thread that python is really too slow for these applications, so I've been contemplating re-writing everything in some low-level language. Before retiring I worked in and taught pure math at Linköping University, a position that obviously didn't call for much programming. My previous experience was mainly in Fortran77,
way back. Most of the
programs I've seen seem to use C. Sam Wagstaff kindly sent me a very long QS program in ratfor (which looks pretty readable).
Dario Alpern has been using Java. Someone has suggested Pyrex.
I've no idea about the relative merits of these languages, or their potential
for speeding up things.

What would you suggest, taking into account
1) performance
2) compatibility with Mac OSX
3) ease of learning
4) readability
?

I know people are going to shout at me about this, but here goes:

I write quite a lot of my stuff these days in Perl. Not everything is cpu-bound and those things which aren't are best run in a language which is easy to write and easy to debug. It really doesn't matter if a program would run 3 times faster when it either runs to completion in 3 seconds or spends 95% of its time waiting for a disk to turn round or for bytes to dribble out of a network connection.

Even CNT tasks which are CPU-bound I often prototype in Perl, though I do use the GMP bignum module, of course, rather than implementing the primitives in raw Perl. Once again, the ease of debugging almost always makes up for a slowdown at runtime. Once the code is correct, and if the performance is inadequate, I translate the code to C and the GMP library.

I happen to like Perl and I acknowledge it's not to everyone's taste. However, I also believe strongly in the zeroth law of optimization: first get it right, and then get it fast.


Paul

(I've done image processing in Perl too . Some of the hairier manipulations may take 5 times as long to runin Perl as in C, but the ease of prototyping various ideas and debugging them more than makes up for it. Re-writing for performance is invariably easier once you have a correct implementation of a good algorithm.)

[jasonp]

Originally Posted by xilman

(I've done image processing in Perl too . Some of the hairier manipulations may take 5 times as long to runin Perl as in C, but the ease of prototyping various ideas and debugging them more than makes up for it. Re-writing for performance is invariably easier once you have a correct implementation of a good algorithm.)

Seconded, prototyping in a higher-level language often makes it much easier to make the correct big-picture decisions, so that switching to low-level stuff lets you concentrate on the fun optimization.

My problem has always been that the stuff I want to write is so complex for me that the only hope I have to even finish, let alone do a good job, is to use the language I know best, which is C. I've tried to teach myself languages like Ocaml, but learning very different languages from scratch means spending a huge amount of time noodling around with the basics, and if there's not enough time for both noodling and advanced stuff, invariably I choose to continue on the advanced stuff.

[bsquared]

Originally Posted by xilman

(I've done image processing in Perl too . Some of the hairier manipulations may take 5 times as long to runin Perl as in C, but the ease of prototyping various ideas and debugging them more than makes up for it. Re-writing for performance is invariably easier once you have a correct implementation of a good algorithm.)

Thirded, but I don't see the need to do such prototyping in an entirely different language as long as decent debugging tools exist (which they do, IMO, in MSVC (not sure what's available in Mac OSX)). Once it's working, the porting of data structures that may not have equivalents in the faster low level language can create its own problems, to the point where getting it right in the higher level language is moot (assuming the final desired feature is speed). You'd just be debugging all over again in the lower level language.

[xilman]

Originally Posted by bsquared

Thirded, but I don't see the need to do such prototyping in an entirely different language as long as decent debugging tools exist (which they do, IMO, in MSVC (not sure what's available in Mac OSX)). Once it's working, the porting of data structures that may not have equivalents in the faster low level language can create its own problems, to the point where getting it right in the higher level language is moot (assuming the final desired feature is speed). You'd just be debugging all over again in the lower level language.

My take on this is that you would have to debug the data structures in the lower-level language anyway. Personally I find prototyping and debugging the algorithms easier in Perl than in C. First get the correct algorithm and then implement it correctly without having to worry about the low level details. Then, and only then, and if the performance isn't adequate, do you implement the low-level stuff and debug that.

You should always what works best for you, but keep an open mind to alternatives. I would program directly in C until a few years ago (and before that, in BCPL, FORTRAN Algol68, Algol 60 and BASIC) until I discovered the ease of prototyping in Perl.

Paul

[bsquared]

Originally Posted by xilman

My take on this is that you would have to debug the data structures in the lower-level language anyway. Personally I find prototyping and debugging the algorithms easier in Perl than in C. First get the correct algorithm and then implement it correctly without having to worry about the low level details. Then, and only then, and if the performance isn't adequate, do you implement the low-level stuff and debug that.

You should always what works best for you, but keep an open mind to alternatives. I would program directly in C until a few years ago (and before that, in BCPL, FORTRAN Algol68, Algol 60 and BASIC) until I discovered the ease of prototyping in Perl.

Paul

For some reason, I've never found Perl to be to my taste, although to be fair I probably haven't given it a serious look in a while. Therefore it's easier for me to prototype in C, and just write a new optimized function for speed later.

I'm interested in your take on what specific features/abilities of Perl you really like, and why those or other features make it great for prototyping algorithms. Not sure if I'll have time/energy to invest in giving it a serious study, but it might be worthwhile to do.

[henryzz]

i personally program in c# as it is easy to understand and learn
if u got gmp working with it a lot of maths things would be at high speed

[pstach]

C

[paulunderwood]

Recently I have been prototyping in Pari/GP because it is a rich language and easy to edit at the command line interface. Later I might convert programs to C which can be optimized for speed. The GMP library is a nice add-on if numbers exceed 2^32 etc.

Perl I use when I can not get something done in Bash.

My favorite language of all time has to be INTERCAL, especially C-INTERCAL

[Chris Card]

I mostly write stuff in C++, since that's the language I use in my day job, and I also use Perl for scripts and high-level stuff. I use Pari to check mathematical results, although I find the syntax annoying.

Chris

[Xyzzy]

We use Logo.

We don't get much done but we have fun doing it.