Talk:Multiplicative order

Clarification

There's more than one way to determine the multiplicative order. While my J is next to non-existant, I can tell you're not using one of the naive ones :-) As the point of Rosetta is to compare equal algorithms in different languages (and not different algorithms in different languages), please state in the task which algorithm you'd like to be used. Also, IMHO the tasks should be chosen to allow a meaningful comparison of languages, and I am not sure if this is a good task for this purpose, because it's more centered on the algorithm than on the possible different ways different languages work. Dirkt 03:57, 8 December 2007 (MST)

The J solution implements the algorithm described in Bach & Shallit, Algorithmic Number Theory I, exercise 5.8, page 115.

If you implement a specific algorithm, it would be nice to describe the algorithm for those who don't happen to have this book lying around.

Judging by the other programming tasks, the submissions in the various languages don't always implement the same algorithm, but use algorithms that are "natural" to the language. That too is a meaningful comparison. Roger Hui 08:28, 8 December 2007 (MST)

But they should implement the same algorithm as far as mathematical principles, say, are concerned. (And if they don't, it's bad, and it should be changed.) Using different mathematical principles to arrive at the same result has nothing to do with what's "natural" for one language. And that's exactly my criticism here: I don't see how this task brings out features that are "natural" to a language. Instead it highlights features of a different algorithmic approach. It's of course tempting to show off with a clever "deep" algorithm, but it misses somehow the point.

And J has enough interesting features that require a different "natural" approach than in other languages that it would be really worthwhile to pick tasks which highlight this. And if you'd add a bit of explanation to really point this out in the implementation, for those not familiar with J, all the better.

One thing this Wiki is really good for is to try to get up to speed in an unfamiliar language, by comparing the approaches with those in a familiar language. This doesn't work if all similarity is suppressed, because the algorithms are essentially incomparable.Dirkt 13:46, 8 December 2007 (MST)

I'll see what I can do about an algorithm description. I'd prefer to upload a jpeg image of the pages in question as my LaTex skills are probably not up to reproducing the formulae. Implementation of the Bach-Shallit algorithm is facilitated by having

• primes and factoring
• extended precision arithmetic
• a^b modulo c
• vector operations

It would be interesting to see how the algorithm would be implemented in a language that lacks one or more of these features. Roger Hui 18:06, 8 December 2007 (MST)

There's no need to upload any image - it just takes a few sentences to describe the algorithm. And this algorithm has NOTHING, absolutely NOTHING that makes it in any way "natural" to J - I could write a C version as easily as the Haskell version, even for large numbers. Just a matter of using the right libraries (for example gmp, in the C case). Sorry to shout, but I am really angry I head to spend several hours learning enough J to figure out the algorithm, for what you could have done in five minutes. And I hate wasting my time. And I hate even more playing silly hide-and-seek games just because people want to show off "their" language.

J, like APL, has lots of interesting features. The maybe two most prominent are IMHO that you can use HOFs to combine existing functions (in J terminology, adverbs and conjunctions), and that the nearly only data structure are arbitrary-rank tensors, so you have to organize the program around that. I'd love to see simple examples that illustrate this in comparison to other languages. But IMHO implementing each of the zillion algorithms of moderate difficulty from number theory or other maths fields is just a waste of time, because it tells you NOTHING about the language whatsoever. Again, sorry for shouting, but I am still quite angry. Dirkt 07:40, 9 December 2007 (MST)

I accept your apologies for being angry and for shouting. Nothing happened here that merited it.

You asked for a description of the algorithm. I provided a reference to a well-known text. Then you asked the description in the text. I promised to provide a reproduction of the text, but before I was able to do so (and within less than 12 hours) you spent a few hours learning enough J to derive an English description from the J program. That is a testament to your skill, to how well the J program is written, and to J itself. Fine. But then you complained and shouted that you wasted a few hours. Well, how you spend or waste your time is your choice.

The main reason I did not simply describe what the J program did (as you did) is that the solutions in the other languages should not be influenced by the J solution. (Unless their authors choose to be so influenced.) I have now typed in the description from Bach & Shallit and will replace your description with theirs. I was not playing hide-and-seek games. If I were, I would not have provided a reference, nor provided a solution in a notation as clear as J, nor written the best J program that I could.

I disagree with your comment that "implementing each of the zillion algorithms ... from number theory or other math fields is just a waste of time". The presence of the "Prime number" and "Sieve of Eratosthenes" programming tasks too argue against your position. Examples that compare and contrast J against other languages can be found by following the links in the J page (17 articles so far). Roger Hui 23:26, 9 December 2007 (MST)

Java solution

There is currently a mismatched left paren in the line:

for(;x.modPow(retVal, y) != BigInteger.ONE;retVal = retVal.add(BigInteger.ONE);

Roger Hui 21:27, 7 December 2007 (MST)

You're allowed to fix it too if you know how. No one will be angry. --Mwn3d 09:43, 8 December 2007 (MST)