mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-08-12, 15:45   #1
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

2010 Posts
Default Preferred languages?

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
?
Peter Hackman is offline   Reply With Quote
Old 2008-08-12, 16:07   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22·3·883 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
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.)
xilman is offline   Reply With Quote
Old 2008-08-12, 16:17   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Quote:
Originally Posted by xilman View Post
(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.
jasonp is offline   Reply With Quote
Old 2008-08-12, 17:08   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,371 Posts
Default

Quote:
Originally Posted by xilman View Post
(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.
bsquared is offline   Reply With Quote
Old 2008-08-13, 11:43   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22·3·883 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
xilman is offline   Reply With Quote
Old 2008-08-13, 13:12   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,371 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
bsquared is offline   Reply With Quote
Old 2008-08-13, 19:49   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·41·71 Posts
Default

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
henryzz is online now   Reply With Quote
Old 2008-08-14, 05:11   #8
pstach
 
Aug 2008

1316 Posts
Default

C
pstach is offline   Reply With Quote
Old 2008-08-14, 12:17   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E0A16 Posts
Default

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

Last fiddled with by paulunderwood on 2008-08-14 at 12:31
paulunderwood is offline   Reply With Quote
Old 2008-08-14, 13:49   #10
Chris Card
 
Chris Card's Avatar
 
Aug 2004

8216 Posts
Default

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
Chris Card is offline   Reply With Quote
Old 2008-08-14, 20:54   #11
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

24×499 Posts
Default

We use Logo.

We don't get much done but we have fun doing it.
Xyzzy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Learning languages is the new fashion... LaurV LaurV 3 2019-11-05 10:25
Modern Foreign Languages in schools f1pokerspeed Soap Box 10 2013-12-28 16:27
"99 Bottles of Beer" in hundreds of languages ixfd64 Programming 4 2005-03-29 02:59
How many languages do you speak? Danath Lounge 34 2005-01-15 10:39

All times are UTC. The time now is 13:10.

Mon Mar 8 13:10:47 UTC 2021 up 95 days, 9:22, 0 users, load averages: 2.17, 2.49, 2.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.