Anonymous user
Talk:Montgomery reduction: Difference between revisions
→Example numbers?: This is important!
(→Example numbers?: you can't beat GMP) |
(→Example numbers?: This is important!) |
||
| (7 intermediate revisions by 2 users 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)
Line 39 ⟶ 64:
:: Thank you for adding implementation and numerical example in another language. A solution for small numbers such as m=97 and R=100 while finding just the Montgomery Reduction of one number would probably only show that that given source code has correctly implemented the algorithm. The practical advantage of Montgomery reduction is that if there are a lot of multiplications to be done, it is more efficient to perform them on numbers that been reduced, and the final results can then be reconverted back to normal numbers (we do not need to actually divide by the modulus). And by the way how did you do numericals involving such large numbers? I don't know much about Go, is it possible to do such large number operations in Go as basic data types? Do you have any idea of doing this for large numbers in C or C++?--[[User:Mahaju|Mahaju]] 11:47, 25 December 2011 (UTC)
: See [[Arbitrary-precision_integers_(included)]] for examples of big numbers in C and C++. Go has big number support in the standard library. —[[User:Sonia|Sonia]] 18:12, 25 December 2011 (UTC)
::Thank you very much for that helpful post. A general question if you don't mind. Why am I not getting any email notifications, or any kind of notifications at all when new contents are added to the pages that I have created or edited? If I get involved with a lot of pages in the future I need to have some way of knowing which pages have been edited since last visit, without having to go look at each of them. And yes, I have checked "Watch this page" for the pages I am interested in, for example, this Talk Page. However, I have not received any kind of notification for any edit's that were made to this talk page, nor did I receive it when the original Montgomery Reduction page that I created was moved. How do I enable notifications? Thank you.--[[User:Mahaju|Mahaju]] 03:05, 26 December 2011 (UTC)
::Also, Happy New Year to you all--[[User:Mahaju|Mahaju]] 03:09, 26 December 2011 (UTC)
----
--[[User:Mahaju|Mahaju]] 03:09, 26 December 2011 (UTC)
| |||