modular exponentiation?

[Bill Duncan]

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" ?

Fairly easy, and I wrote about my solutions here:
billduncan.org.

I flunked the test as my two solutions weren't the java code he was looking for..

It was interesting that "dc" (the command line "reverse polish calculator") had a modular exponentiation operator while the algebraic "bc" command didn't. (At one time, "bc" was a wrapper around "dc", which suggests that this was a recent addition.)

I also got thinking about how I'd solve it on my calculators.. HP-48 wouldn't be a big deal, but it might be tricky on earlier calcs like the HP-41..

Thoughts?

One other thing came to mind, is there a way to insert LaTeX code for formulaes in this forum similar to the way I did it in my blog post?

[Thomas Klemm]

(06-23-2018 11:49 PM)Bill Duncan Wrote:  One other thing came to mind, is there a way to insert LaTeX code for formulaes in this forum similar to the way I did it in my blog post?

Yes. Just write it in escaped brackets:

Code:

\[ ... \]

\[\LARGE\Bigg(\sum_{n=1}^{1000} n^{n} \bmod 10^{10}\Bigg) \bmod 10^{10}\]

But you have a typo in your formula: \(1^{10}\) should rather be \(10^{10}\).

[Thomas Klemm]

(06-23-2018 11:49 PM)Bill Duncan Wrote:  I flunked the test as my two solutions weren't the java code he was looking for..

With my solution using Python I'd probably flunked as well:

Code:

>>> sum((n**n for n in range(1, 1001))) % 10**10
9110846700L

[Thomas Okken]

Flunking the test, Free42 style:

Code:

00 { 46-Byte Prgm }
01▸LBL "BD"
02 0
03 STO 00
04 1ᴇ3
05 STO 01
06▸LBL 01
07 RCL 01
08 STO 02
09 1
10▸LBL 02
11 RCL× 01
12 1ᴇ10
13 MOD
14 DSE 02
15 GTO 02
16 STO+ 00
17 DSE 01
18 GTO 01
19 RCL 00
20 1ᴇ10
21 MOD
22 END

[mfleming]

APL
\[1e10|+/(\iota1000)*\iota1000\]

[mfleming]

(06-24-2018 02:46 AM)mfleming Wrote:  APL
\[1e10|+/(\iota1000)*\iota1000\]

Or, generalized via an anonymous function
\[1e10\ \{\alpha|+/(\iota\omega)*\iota\omega\}\ 1000\]

No, I didn't drop my keyboard on the floor

[Bill Duncan]

(06-24-2018 12:21 AM)Thomas Klemm Wrote:  

(06-23-2018 11:49 PM)Bill Duncan Wrote:  One other thing came to mind, is there a way to insert LaTeX code for formulaes in this forum similar to the way I did it in my blog post?

Yes. Just write it in escaped brackets:

Code:

\[ ... \]

\[\LARGE\Bigg(\sum_{n=1}^{1000} n^{n} \bmod 10^{10}\Bigg) \bmod 10^{10}\]

But you have a typo in your formula: \(1^{10}\) should rather be \(10^{10}\).

Indeed! Thank you!!

[Paul Dale]

The WP 34S makes this easy, it has a modular exponentiation function in integer mode.
Unfortunately, the summation function doesn't work in integer mode. Regardless, the program is fairly short:

Code:

01: LBL A
02: BASE 10
03: STO I
04: Clx
05: LBL 00
06: RCL I
07: RCL I
08: # 10
09: 10^x
10: ^MOD
11: RCL+ Y
12: # 10
13: 10^x
14: MOD
15: DSZ I
16: GTO 00
17: END

1000 XEQ A -> 9110846700


Pauli

[J-F Garnier]

The HP-71B can compute the least 9 significant digits easily (well at least in Emu71 -for the speed):

Code:

  10 S=0 @ M=10^9
  20 FOR I=1 TO 999
  25   X=1
  30   FOR N=1 TO I
  40     X=MOD(X*I,M)
  50   NEXT N
  60   S=MOD(S+X,M)
  70 NEXT I
  80 DISP S

 110846700

J-F

[Didier Lachieze]

On the HP Prime in CAS mode:
\[\LARGE irem( \sum_{n=1}^{1000} (powmod(n,n,10^{10})), 10^{10})\]
or, if you want to copy/paste to the emulator:

irem(Σ(powmod(n,n,10^10),n,1,1000),10^10)

[J-F Garnier]

A slightly modified version of the HP-71B program, that provides the full requested 10 digits:

Code:

  10 S=0 @ M=10^10
  20 FOR I=1 TO 999
  25   X=1 @  K=MOD(I,10)
  30   FOR N=1 TO I
  40     X=MOD(MOD(X*(I-K),M)+X*K,M)
  50   NEXT N
  60   S=MOD(S+X,M)
  70 NEXT I
  80 DISP S

 9110846700

J-F

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

[sasa]

(06-24-2018 09:08 PM)Valentin Albillo Wrote:  A few comments:

I just prepared to comment similar, thus I will just add several other issues:

4. It is not clear what is asked for applicant - to be junior or senior programmer. It is a big difference. For junior Java programmer may be asked to know Java and many packages - thus BigInteger package is trivial approach to satisfy that requirement for this task.

If searching for a skilled senior programmer this task formulation is certainly unclear and this may be taken as a challenge to make approach from ground, without any specialized library and take care to optimization etc. In that case, Java have several basic flaws in design and relevant here is lack of unsigned types. Thus, to make optimize approach from ground Valentine noted in point (3), this may not be that simple task...

5. Note that integer overflow means big problem, not only in Java with all his lack in design, but also in C/C++ and other languages. Program will usually continue to work, however result will be incorrect and unpredictable.

6. Recursion. Something used everywhere and without real needs. As well very good reason for rejection.

7. Brute force approach perhaps can be tolerant for a junior programmer, otherwise it is clear sign for rejection.

However, many companies does not care too much about what is actually there and priority is loyality to the company and signed permission to work overtime and during weekends without extra paying. And actually many of them forces technical mediocrities. It is pointless to show concrete code and practice in some examples I have personally found in commercial software from someone earn $70-100.000 or more per year. even in critical software (car industry, medical equipment...).

[brickviking]

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.

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.

(Post 249)

[Thomas Okken]

(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?

[cyrille de brébisson]

Hello,

>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

Yes, they are. When you do "powers-of-two multiplication by bit-shifting", you do things like:
res= 0
while a!=0
if a is odd then res= res+b
a= a shift right (divide by 2)
b= b+b (or b shift left: multiply by 2)
end

power of 2 power by bit shifting is
res= 0
while a!=0
if a is odd then res= res*b // Note the + changed into a *
a= a shift right (divide by 2) // no changes there
b= b*b // Multiply by 2 changed into a square (the power equivalent of +)
end

So, same algo, different functions...

Where this is interesting and applies to the original "question" is that breaking the power loops allows you to add the modulo function in the innerloop and never end up with large numbers.

The net result is that you will have to perform
sum(ln(n)*1.5) multiplications and modulo calculations (=~8800) assuming that bits are odd with 50% probability...

With some luck your CPU does have a build in / or % function...
The main issue is that you need to do calculations with numbers that can be as big as 10^20 (2 10 digits number being multiplied) which takes 67 bits... and this overflows a 64 bit register :-(
So you will have to create a longer precision arithmetics for the multiplication and modulo...

Cyrille
Cyrille

[Maximilian Hohmann]

Hello!

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

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.

You beat me with your answer because this is 100% of what I had in mind to write :-) Luckily they didn't ask about such things when I was contracted to write software for money some 30 years ago. The only thing they actually asked was "Is our offer good enough in terms of hourly pay and would it be possible that you start as early as next week?". Those were the days! Nobody ever criticised my waste of computer cycles by inefficient programming in the years to follow.

Regards
Max

[Bill Duncan]

Hey everyone,

When did this forum get so serious?

AFAIK, it's a place that we can share ideas, pass on a little knowledge, learn new things and most of all, have some fun!

To answer a few questions,
- I wasn't actually taking the test, so I didn't actually "flunk". I was trying to be funny..
- I believe my colleague actually did stipulate that the bigint library couldn't be used
- He was using it as one of many interview questions, and simply looking for the mental leap. He wasn't looking for the most efficient, just something that worked.

Yes, modular exponentiation can be done more efficiently. Used in cryptography etc. Some information here: Wikipedia: Modular exponentiation
There is also some code for different languages on this site, rosettacode.org

Recursion inefficient? Sure. Was it fun and did it work? Yes.

Recursion is often not very efficient, agreed.. Some problems are way easier to design recursively however. My AWK sudoku solver I think is a good example of something far easier with a recursive design. Inefficient? Perhaps. Fast enough? Works for me. And, it was easy to translate to C for more speed. I wrote some articles about the process referenced here:

awk and C sudoku solvers

So seriously, let's get back to having fun with the friendly exchange of ideas in the forum?
Thanks!

[Thomas Okken]

(06-25-2018 02:49 PM)Bill Duncan Wrote:  When did this forum get so serious?

AFAIK, it's a place that we can share ideas, pass on a little knowledge, learn new things and most of all, have some fun!

[...]

So seriously, let's get back to having fun with the friendly exchange of ideas in the forum?

I honestly have no clue what you are complaining about. Sure, sometimes discussions get heated and even name-calling may happen... but I see no trace of anything like that in this thread. Where do you think we went wrong?

[Bill Duncan]

(06-25-2018 03:43 PM)Thomas Okken Wrote:  

(06-25-2018 02:49 PM)Bill Duncan Wrote:  When did this forum get so serious?

AFAIK, it's a place that we can share ideas, pass on a little knowledge, learn new things and most of all, have some fun!

[...]

So seriously, let's get back to having fun with the friendly exchange of ideas in the forum?

I honestly have no clue what you are complaining about. Sure, sometimes discussions get heated and even name-calling may happen... but I see no trace of anything like that in this thread. Where do you think we went wrong?

Sorry, maybe I'm being a little oversensitive with the recent incidents. I thought I detected some subtle undertones, but it was probably just my misinterpretation.

Thanks.