Post Reply 
modular exponentiation?
06-25-2018, 02:44 AM
Post: #15
RE: modular exponentiation?
(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. Smile

(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? Smile
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
modular exponentiation? - Bill Duncan - 06-23-2018, 11:49 PM
RE: modular exponentiation? - Thomas Klemm - 06-24-2018, 12:21 AM
RE: modular exponentiation? - Bill Duncan - 06-24-2018, 03:20 AM
RE: modular exponentiation? - Thomas Klemm - 06-24-2018, 12:33 AM
RE: modular exponentiation? - Thomas Okken - 06-24-2018, 12:48 AM
RE: modular exponentiation? - mfleming - 06-24-2018, 02:46 AM
RE: modular exponentiation? - mfleming - 06-24-2018, 02:58 AM
RE: modular exponentiation? - Paul Dale - 06-24-2018, 03:42 AM
RE: modular exponentiation? - J-F Garnier - 06-24-2018, 08:41 AM
RE: modular exponentiation? - John Keith - 06-28-2018, 12:42 AM
RE: modular exponentiation? - ijabbott - 06-28-2018, 06:07 PM
RE: modular exponentiation? - John Keith - 06-28-2018, 09:40 PM
RE: modular exponentiation? - J-F Garnier - 06-24-2018, 11:32 AM
RE: modular exponentiation? - sasa - 06-24-2018, 10:21 PM
RE: modular exponentiation? - ijabbott - 06-25-2018, 10:09 PM
RE: modular exponentiation? - Bill Duncan - 06-25-2018, 10:45 PM
RE: modular exponentiation? - brickviking - 06-25-2018, 02:04 AM
RE: modular exponentiation? - Thomas Okken - 06-25-2018 02:44 AM
RE: modular exponentiation? - brickviking - 06-25-2018, 10:21 PM
RE: modular exponentiation? - Bill Duncan - 06-25-2018, 02:49 PM
RE: modular exponentiation? - Thomas Okken - 06-25-2018, 03:43 PM
RE: modular exponentiation? - Bill Duncan - 06-25-2018, 04:06 PM
RE: modular exponentiation? - Thomas Klemm - 06-25-2018, 04:31 PM
RE: modular exponentiation? - StephenG1CMZ - 06-25-2018, 05:42 PM
RE: modular exponentiation? - Thomas Klemm - 06-28-2018, 09:56 PM
RE: modular exponentiation? - John Keith - 06-29-2018, 12:47 AM
RE: modular exponentiation? - Bill Duncan - 07-08-2018, 09:50 PM
RE: modular exponentiation? - Joe Horn - 07-09-2018, 02:32 AM
RE: modular exponentiation? - Thomas Klemm - 07-09-2018, 05:18 AM
RE: modular exponentiation? - Gerald H - 07-09-2018, 09:55 AM
RE: modular exponentiation? - Thomas Klemm - 07-09-2018, 01:37 PM
RE: modular exponentiation? - wynen - 10-26-2018, 06:08 PM
RE: modular exponentiation? - rprosperi - 10-26-2018, 07:37 PM
RE: modular exponentiation? - Albert Chan - 10-27-2018, 12:24 AM
RE: modular exponentiation? - pier4r - 10-27-2018, 07:28 PM



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