Talk:Montgomery reduction: Difference between revisions
m
Split comments on relative timings out from those on Example numbers...
No edit summary |
m (Split comments on relative timings out from those on Example numbers...) |
||
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)▼
== Relative Timings ==
:: 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)▼
▲
▲
▲
: 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)
| |||