modular exponentiation?

[Valentin Albillo]

.
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..

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.
.