modular exponentiation?

06252018, 04:31 PM
(This post was last modified: 06252018 04:44 PM by Thomas Klemm.)
Post: #21




RE: modular exponentiation?
Finally a solution for Java that might be accepted:
Map Reduce Code: import java.math.BigInteger; Parallel Streams With this small change we can run the calculation in parallel: Code: import java.math.BigInteger; Will it be faster on a MacBook with 4 cores? Guess what: it makes it even a bit slower. These are the results for the real time of 20 runs: Sequential Code: 0.2100 # Parallel Code: 0.2300 # We have to increase the upper limit to 10000000 to notice the difference: Sequential Code: real 0m35.134s Parallel Code: real 0m17.546s During this run the CPU was used up to 350% by this program: Code: PID USER PRI NI VIRT RES S CPU% MEM% TIME+ Command Premature Optimization Quote:Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. Donald Knuth My Python program above runs in about 0.045s. It's not^{1} optimised but doing so wouldn't gain that much. It took me much longer to write the Java program. And today the biggest cost is our time. Not only the time that you spend to implement a piece of code. But also the time you or others must spend debugging and maintaining your code. Contrary to what others might think I consider this a reasonable interview question. Because it could lead the discussion into different directions. [1]: Ok, it's a bit optimized in that instead of a listcomprehension (using []) the corresponding generator (using ()) is used. Thus not the whole list has to be kept im memory. Instead summation and producing the arguments can be interleaved. But even this doesn't change much. 

06252018, 05:42 PM
(This post was last modified: 06252018 05:44 PM by StephenG1CMZ.)
Post: #22




RE: modular exponentiation?
(06252018 02:44 AM)Thomas Okken Wrote:(06252018 02:04 AM)brickviking Wrote: Man, am I glad I've never tried to apply for a professional programmer's job. I've never even heard of binary multiplication chains. I've certainly heard of powersoftwo multiplication by bitshifting though. I don't know if this is the same thing, nor would I have any idea how to apply that to the OP. Oops: New Reply is inserting a Quote! I too would have flunked that math test... My A level math covered modular arithmetic and exponentiation, but it was too long ago to remember them ever being combined. The straightforward for loop has the advantage of clarity and easily predictable performance (assuming an average execution time for each loop), whereas the mathematical shortcut relies on memory of a trick  and is harder to test for errors if your memory lets you down. Back at the start of my software engineering career, I don't remember doing well on any math algorithms in interviews, but in the job itselfI did implement a 100% performance gain in a sqrt function. The trick there was to choose a good guess for the initial root. I also implemented DSP software in assembler, which I understood well enough to code and test  but couldn't begin to talk about in interviews (apart from explaining the code, rather than the math) Stephen Lewkowicz (G1CMZ) 

06252018, 10:09 PM
Post: #23




RE: modular exponentiation?
(06242018 09:08 PM)Valentin Albillo Wrote: 3) Actually, I've been sometimes in charge of selecting programmers to hire and if I were to pose this same question to the people applying for the job and some of them would produce code which computed the integer powers N^N by performing N multiplications in a loop, both their code and their application would've been thrown to the garbage bin at once, for being so utterly inefficient. I'd choose people who are resourceful, even if they don't know every algorithm off by heart. I've been programming professionally for 34 years and never had any reason to use modular exponentiation, let alone implement it efficiently. (If I specialized in cryptography, it would be a different matter!). I only really discovered the fast binary algorithm for modular exponentiation through solving challenges on HackerRank, since I figured there probably had to be a faster than O(n) algorithm so I went looking on Wikipedia to find it. — Ian Abbott 

06252018, 10:21 PM
Post: #24




RE: modular exponentiation?
(06252018 02:44 AM)Thomas Okken Wrote:(06252018 02:04 AM)brickviking Wrote: (Post 249) It's a post counter, and I use it to give me a rough idea of what threads I visited and what order I replied in. It also lets me know how many posts I've actually made on a particular forum; although most forums now have a handy post counter nearby the username, some older forums don't (i.e. the good old newsgroup days). And besides, it makes a great conversation starter. Or at least a puzzler. You're not the first to ask me, and I'll be willing to be you won't be the last. Now, let's see if I've got a rough idea of the mathematical concept behind this. (Post \( 3^3*3^2+2^2+3\)) Regards, BrickViking HP50g Casio fx9750G+ Casio fx9750GII (SH4a) 

06252018, 10:45 PM
Post: #25




RE: modular exponentiation?
(06252018 10:09 PM)ijabbott Wrote:(06242018 09:08 PM)Valentin Albillo Wrote: 3) Actually, I've been sometimes in charge of selecting programmers to hire and if I were to pose this same question to the people applying for the job and some of them would produce code which computed the integer powers N^N by performing N multiplications in a loop, both their code and their application would've been thrown to the garbage bin at once, for being so utterly inefficient. I'm with you on that. I didn't know what "modular exponentiation" was myself. I just intuitively knew what I wanted, did "man dc" and found the phrase there.. My colleague was just looking for someone that could "think" and basically know how to get there.. Cheers! 

06282018, 12:42 AM
Post: #26




RE: modular exponentiation?
(06242018 09:18 AM)Didier Lachieze Wrote: On the HP Prime in CAS mode: Wow, almost instantaneous! My HP 50 version, Code:
is rather slow and clunky due to the HP 50's quirky POWMOD function. It takes about 130 seconds to run, or about 2.5 seconds on the emulator. John 

06282018, 06:07 PM
Post: #27




RE: modular exponentiation?
(06282018 12:42 AM)John Keith Wrote: My HP 50 version, I wonder why POWMOD is so slow? Does it do POW followed by MOD? — Ian Abbott 

06282018, 09:40 PM
Post: #28




RE: modular exponentiation?
(06282018 06:07 PM)ijabbott Wrote: I wonder why POWMOD is so slow? Does it do POW followed by MOD? No, it works in the usual way but it is more primitive than the Prime's version, thus requiring the check for negative values. Also integer comparisons are very slow for some reason. About 20 seconds of that run time is taken by the < function. Additionally, the prime is almost 100 * as fast as the HP 50 which accounts for most of the difference. 

06282018, 09:56 PM
Post: #29




RE: modular exponentiation?
(06282018 09:40 PM)John Keith Wrote: Also integer comparisons are very slow for some reason. About 20 seconds of that run time is taken by the < function. You could probably just ditch the following: Code: IF DUP 0 < I have no HP 50g thus I can't verify my assumption. But the final MODULO MOD should take care of possible negative values. 

06292018, 12:47 AM
Post: #30




RE: modular exponentiation?
(06282018 09:56 PM)Thomas Klemm Wrote: You could probably just ditch the following: You're right, it returns the correct value in 93.4 seconds without the test clause. 

07082018, 09:50 PM
Post: #31




RE: modular exponentiation?
Has anyone written a POWMOD like function for the HP48? Just wondering before I go off and try it myself..


07092018, 02:32 AM
Post: #32




RE: modular exponentiation?
(07082018 09:50 PM)Bill Duncan Wrote: Has anyone written a POWMOD like function for the HP48? Just wondering before I go off and try it myself.. There's a "Fast Powering algorithm f exponentiation (mod n)" program called PWR in Anthony Shaw's "MODULO" package for the 48: https://www.hpcalc.org/details/6015 <0ɸ0> Joe 

07092018, 05:18 AM
Post: #33




RE: modular exponentiation?
(07082018 09:50 PM)Bill Duncan Wrote: Has anyone written a POWMOD like function for the HP48? Cf. Modular Arithmetic for the HP48 Since PLUS is only used by TIMES it can be inlined. And then you can keep TIMES in a local variable leading to: Code: @POWER ( a b n  a ^ b % n ) (07092018 02:32 AM)Joe Horn Wrote: There's a "Fast Powering algorithm f exponentiation (mod n)" program called PWR in Anthony Shaw's "MODULO" package for the 48: https://www.hpcalc.org/details/6015 Quote:MODPND Thus I assume that it will work only up to 10^{9}. Quote:Just wondering before I go off and try it myself. Just go for it! And post your result. Cheers Thomas 

07092018, 09:55 AM
Post: #34




RE: modular exponentiation?  
07092018, 01:37 PM
Post: #35




RE: modular exponentiation?
(03152015 08:22 AM)Gerald H Wrote: The programme MMOD finds Stealing this idea I reduced the TIMES program: Code: @POWER ( a b n  a ^ b % n ) Thanks to Gerald and kind regards Thomas 

10262018, 06:08 PM
Post: #36




RE: modular exponentiation?
I just want to mention, that my favorite HP16C is also able to solve the original problem.
With the modular exponentiation function, which I presenetd in this thread http://www.hpmuseum.org/forum/thread11674.html in the "General Software Library", it is possible to compute the last (up to) 18 digits of \(\Bigg(\sum_{n=1}^{1000} n^{n} \bmod 10^{10}\Bigg) \bmod 10^{10}\) very easily. There is only one smal problem left: The computation lasts for about 8 hours. Best regards Hartmut 

10262018, 07:37 PM
Post: #37




RE: modular exponentiation?
(10262018 06:08 PM)wynen Wrote: There is only one smal problem left: The computation lasts for about 8 hours. Wow. I'd hate to see a big problem.... Bob Prosperi 

10272018, 12:24 AM
Post: #38




RE: modular exponentiation?
Here is a poor man's version, using old luajit 1.18
No 64bits integer (only 53bits float), no builtin powmod ... PHP Code: function powmod1e10(x,y)  x^y % 1e10 PHP Code: function modsum(n)  sum(i^i, i=1..n) % 1e10 Some benchmark from my 20 years old Pentium 3: modsum(1e3) ==> 9110846700 (0.00 seconds) modsum(1e4) ==> 6237204500 (0.04 seconds) modsum(1e5) ==> 3031782500 (0.57 seconds) modsum(1e6) ==> 4077562500 (7.10 seconds) 

10272018, 05:46 AM
(This post was last modified: 10272018 05:51 AM by Ángel Martin.)
Post: #39




RE: modular exponentiation?
(06252018 03:43 PM)Thomas Okken Wrote:(06252018 02:49 PM)Bill Duncan Wrote: When did this forum get so serious? I for one understand Bill's sentiments. More often than none there's a certain Damocles sword pending over always ready to be let loose. So I too claim the right to goof up. Modular exponentiation, of all things is a tricky one to grasp  more so if you had no exposure to Modular math. Thank you Thomas for your informative responses and clarifications, I'm sure that helped may folks. Cheers, ÁM 

10272018, 05:55 AM
(This post was last modified: 10272018 05:56 AM by Ángel Martin.)
Post: #40




RE: modular exponentiation?
(10262018 06:08 PM)wynen Wrote: I just want to mention, that my favorite HP16C is also able to solve the original problem. This picked my curiosity: I'm going to try running your program on V41 Turbo mode, using the 16C Simulator Module... will keep you all posted 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)