Timeline for Modular arithmetic - efficiently calculating the remainders of factorials
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2015 at 15:07 | history | edited | Michael E2 | CC BY-SA 3.0 | Simplified code |
| Jun 15, 2015 at 15:07 | comment | added | Michael E2 | @J. M. I can't remember...Probably because I think of Fold in a pedestrian manner in terms of #1 and #2 -- not seeing the forest for the trees, so to speak. Thanks. | |
| Jun 15, 2015 at 12:53 | comment | added | J. M.'s missing motivation | Is there any reason why you used #1 #2 & instead of Times? | |
| Mar 27, 2013 at 13:20 | vote | accept | Vincent Tjeng | ||
| Mar 26, 2013 at 14:05 | comment | added | Michael E2 | @VincentTjeng It's a good idea to delay. More people are likely to look at the question, and we all would like to see a better answer, if there is one. | |
| Mar 26, 2013 at 13:46 | comment | added | Vincent Tjeng | @MichaelE2 I hope you don't mind me delaying awarding you the answer; I hope someone might come around and come up with an even better way to do so, and I think marking the question as answered will serve to discourage people from looking here! | |
| Mar 26, 2013 at 12:16 | comment | added | Michael E2 | @VincentTjeng Not off hand. The speed up comes from storing the sums of factorials. If for instance you reduced the factorials mod $p$ before summing, you would save a lot of space but would have to computed the factorials over and over (for each prime $p$). The factorials take as much space to store as their sums. Well, maybe something will occur to somebody. | |
| Mar 26, 2013 at 12:11 | comment | added | gpap | @MichaelE2 Yes, worked it out myself in the meantime - you multiply the previous result and don't calculate a factorial at every step. Thanks | |
| Mar 26, 2013 at 12:04 | comment | added | Michael E2 | @gpap Calculating factorial so many times costs a lot. Since we know we want all the factorials up to Prime[toPrime]-1, we ultimately gain a lot keeping the intermediate results with FoldList. | |
| Mar 26, 2013 at 11:23 | comment | added | gpap | +1 (that's freaking fast!) Can you explain why Accumulate@FoldList[#1 #2 &, 1, Range[n] is so much quicker to Accumulate@Array[#! &, n] + 1? I really don't get it. | |
| Mar 26, 2013 at 6:03 | comment | added | Vincent Tjeng | you are way too humble! calculating your sum for even the first 2000 primes takes less than a second. However, is there a way to get around storing large numbers in sums in memory? It keeps crashing my computer when I try toPrime=5000. | |
| Mar 26, 2013 at 5:41 | history | answered | Michael E2 | CC BY-SA 3.0 |