modular exponentiation?

[StephenG1CMZ]

(06-25-2018 02:44 AM)Thomas Okken Wrote:  

(06-25-2018 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 powers-of-two multiplication by bit-shifting though. I don't know if this is the same thing, nor would I have any idea how to apply that to the OP.

It's not the same thing. The idea is that, for example,

a^10 = (a^5)^2 = (a*a^4)^2 = (a*(a^2)^2)^2

meaning: you can compute integral powers by a sequence of multiplications and squares. This is more efficient than a sequence of multiplications; the repeated-squaring approach takes O(log n) operations, as opposed to n-1 multiplications for the simplistic approach.

Is this the kind of knowledge that you would require a job applicant to have, where you would toss their application in the trash if they don't implement an integral power this way? I doubt it. I've never been asked this kind of question in a job interview (and I am a programmer, not a scientist or engineer who dabbles in programming). The only time in my life where knowing the repeated-squaring algorithm was useful to me was when I implemented Y^X in Free42.

Your mileage may vary.

(06-25-2018 02:04 AM)brickviking Wrote:  I'm a bit lost as to what modular exponentiation is, too. I guess I haven't been kicking around the maths courses long enough.

Taking something to the power of something, and then taking the remainder of that, modulo something else. When the exponents get large, this requires clever algorithms to get accurate results. Again, not something programmers tend to encounter. Mathematicians, maybe, but anyone else? Seems like a weird interview topic to me, for any job that isn't pure mathematics.

(06-25-2018 02:04 AM)brickviking Wrote:  (Post 249)

I have to ask: why do you do that?

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)