Post Reply 
modular exponentiation?
06-24-2018, 09:08 PM (This post was last modified: 06-24-2018 09:15 PM by Valentin Albillo.)
Post: #12
RE: modular exponentiation?
.
Hi, all:

(06-23-2018 11:49 PM)Bill Duncan Wrote:  A colleague recently posed a question for hiring new programmers..

"What is the least significant 10 digits of the series: 1^1+2^2+3^3 .. 1000^1000" ?
[...]
I flunked the test as my two solutions weren't the java code he was looking for.. Wink

A few comments:

1) Executing this command-line expression (not even a program) in interpreted BASIC

      t=0:m=10^10:for i=1 to 1000:t+=modpow(i,i,m):next i:print t@m

will output 9110846700 in 1 millisecond. For the least 20 digits it outputs 67978[...]46700 in 4 ms, the least 100 digits (69769[...]46700) take 10 ms and the least 1000 digits (39747[...]46700) just 0.1 seconds.

2) I find somewhat lame that if he was looking for Java code he wouldn't tell so beforehand, or else if he actually specified that he was after a Java programmer then I don't get why people taking the test wouldn't produce exactly that or else leave to avoid wasting everybody's time.

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 not only expect correct code from people who want a job as professional programmers, I would also expect that the code is efficient and runs as fast as posssible. I take it for granted that such people were taught to compute powers using binary multiplication chains to dramatically minimize the number of multiplications needed, and failing to use the technique in this particular test would immediately disqualify them for the job.

For comparative purposes, I ran a typical solution similar to the ones posted here counting the total number of multiplications computing each N^N by performing N multiplications in a loop (500,500 multiplications in all) or else by using binary multiplication chains (12,925 mults in all)

The difference between performing more than half a million multiplications or less than 13 thousand means the code runs 38x faster and I wouldn't settle for less when hiring.

V.
.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
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? - Valentin Albillo - 06-24-2018 09:08 PM
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)