Anonymous user
Talk:Montgomery reduction: Difference between revisions
→Example numbers?: This is important!
No edit summary |
(→Example numbers?: This is important!) |
||
| (5 intermediate revisions by one other user not shown) | |||
Line 30:
I would like to see some numerical examples. --[[User:Rdm|Rdm]] 15:04, 23 December 2011 (UTC)
: So, I posted some, ... [[User:Sonia|Sonia]] 22:34, 23 December 2011
: So, I posted some, plus some stuff the task doesn't call for, to show some possibilities for how the task might be developed further. Of course the timings have no place in a final version but I left them in to show that it's hard to beat library functions, even if they do use mod. (I checked the Go library source for Exp, and it does simple binary exponentiation calling a mod function at each step.) Also, this is an example with b = 2. I suspect that a library implementation of Montgomery reduction would have b = the machine word size, and that it would do Montgomery multiplication rather than just reduction. —[[User:Sonia|Sonia]] 22:34, 23 December 2011 (UTC)▼
: Ok... based on my current understanding (which, admittedly, doesn't have much time invested), if those numbers are right, I think that the task description should change:
:: Well, you can't make a code vs. library comparison like this, just as you can't compare apples to Yorkshire Terriers. A serious implemention should have access to the innards to the <code>big</code> (your <code>math/big</code>--is that the weekly instead of release build?) package, which means it should be in nat.go and directly operate on the bits of the machine word slices. As presented, the line <code>a.Rsh(a, 1)</code> alone is enough to kill performance, not to mention <code>a.Add(a, m.m)</code>. --[[User:Ledrug|Ledrug]] 05:28, 24 December 2011 (UTC)▼
::: As long as both the code and library tests were done on the same hardware, comparison timings shouldn't be a problem. The real difficulty with timings comes when people try to use results from different environments. (One could even get rid of 'time' output entirely and only display relative percentages for in-example comparison) As for identifying which version of dependent software is used, that's what {{tmpl|works with}} is for. --[[User:Short Circuit|Michael Mol]] 15:38, 24 December 2011 (UTC)▼
:: <math>M</math> should become <math>m</math>
:: <math>n</math> = number of digits in base <math>m</math> should become <math>n</math> = number of digits <math>m</math> needs in base <math>b</math>
--[[User:Rdm|Rdm]] 15:49, 1 August 2012 (UTC)
:: However, even with these changes, it's not clear to me how your numbers correspond to the task description.
:: Present in task description and not in numbers: A, u<sub>i</sub>, m', possibly t
:: Present in numbers but not in task description: x1, x2, possibly t1, t2
:: In other words, it's not clear how x1 and x2 are related to the terms described in the task. (And it doesn't help that I do not understand go well enough to read lines with what look like three argument operations are doing -- things like "x.Sub(x.Lsh(x, n), m)".
:: Note also that I can compute the desired results directly, it's figuring out what the task description is asking for that I am having problems with. --[[User:Rdm|Rdm]] 18:41, 3 August 2012 (UTC)
I'd like to concur; this task needs something in it so that we can verify the correctness of our implementations of it, even if by just comparing the outputs of different languages. (No we don't need ''exact'' equality; just comparable enough for people, not computers.) Without that, I would be unhappy with promoting this to full task status. –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 16:37, 27 April 2014 (UTC)
== Relative Timings ==
▲
:: ''The task is not written procedurally, but it does state that <code>m_dash</code> is pre-computed. So timings which incorporate the computation of m_dash with the computation of the final result conflict with the task definition. --[[User:Rdm|Rdm]] 17:35, 2 January 2012 (UTC)''
▲
▲
: As Ludreg points out, a fair comparison, one that might ultimately show an advantage to Montgomery reduction, would be involved. The task probably shouldn't go in that direction, so my example of exponentiation is probably too much as well. Just showing a single multiplication would be enough to indicate that a particular implementation is correct. Is that enough for the task? Do people want to see the algorithm for b>2, or even arbitrary b, as in the C++ solution? I used big numbers, since that is the application for Montgomery reduction. Should that be a task requirement or is a solution showing m=97 and R=100 enough? —[[User:Sonia|Sonia]] 17:54, 24 December 2011 (UTC)
| |||