HP Forums
Modular exponentiation with a noninteger base - Printable Version

+- HP Forums (https://archived.hpcalc.org/museumforum)
+-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html)
+--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html)
+--- Thread: Modular exponentiation with a noninteger base (/thread-203395.html)



Modular exponentiation with a noninteger base - Oliver Unter Ecker - 10-30-2011

I'd like to compute "floor(3.8^98) mod 100" for the latest Project Euler problem (#356). Does someone know how to do this?

Fast modular exponentiation using the binary method doesn't seem to work for noninteger bases (I may well be overlooking the clever modification that will make it work), and I'm finding nothing that can do the job. I tried replacing the power function with exp(exponent * ln base) and a Taylor series for exp(), using modular aggregation. This converges a million times too slowly, and just can't be the way to do this.

WolframAlpha will gladly do the calculation (the result is "20"), but it fails for greater exponents.

For exponent 9876543 and modulus 100000000 it still produces output. For exponent 98765432, it appears to bring down a server (!); for exponent 987654321, it switches its input interpretation over to stocks...

Any ideas or keywords that would help to research this? Thanks!

EDIT: Here's the link to PE problem 356. Warning: enormous time sink. Largest root for n=2 is '1/3*(4+16/(37+3*i*sqrt(303))^(1/3)+(37+3*i*sqrt(303))^(1/3))'.


Edited: 30 Oct 2011, 10:20 p.m.


Re: Modular exponentiation with a noninteger base - Eric Smith - 10-30-2011

Use the "Russian Peasant" method of exponentiation. Iterate to compute b^2, b^4, b^8, b^16, etc. Then b^98 = b^64 * b^32 * b^2. Even for the problem 356 exponent like 987654321, this takes only 29 squarings (log2 of 987654321), so no more than 58 multiplications in total for each exponential.


Re: Modular exponentiation with a noninteger base - Crawl - 10-30-2011

I'm getting 60, not 20, for that problem, with both the HP50g and TI89.

Basic idea: You can calculate 3.8^98 exactly as (38/10)^98.

You can also get the approximate value of that.

And then convert that approximate value to an exact value (eg., 6.558e50 becomes 6 followed by 50 zeroes), and subtract.

Repeat until you get a value that's small enough (less than a billion, say) that you can read all the values down to the decimal point exactly.

And then you read the last two digits.

In fact, Wolfram Alpha seems to give the same thing (...160.982...)

So why is it giving 20?


Re: Modular exponentiation with a noninteger base - Crawl - 10-30-2011

Utterly bizarre.

658858978275742440319523292513429252482438987872804536320
658858978275745389910397903226911721462945575230733045160

The top is what Wolfram Alpha gives for floor of 3.8^98.

The bottom is what Wolfram Alpha gives for 3.8^98 (truncated at the same number of digits)

This seems like a bug in Wolfram Alpha.

Edited: 31 Oct 2011, 12:01 a.m.


Re: Modular exponentiation with a noninteger base - Paul Dale - 10-31-2011

Using bc I get:

scale=150
3.8^98
658858978275745389910397903226911721462945575230733045160.9820465028\
70158400628629120383359841551012084671432225137467649553611674541077\
38631648377416187904


- Pauli


Re: Modular exponentiation with a noninteger base - Paul Dale - 10-31-2011

Might it be the floating point number (3.8) confusing things?

Calculate it as floor( (19/5)^98 ) mod 100 and it gets the correct answer.


- Pauli


Re: Modular exponentiation with a noninteger base - Oliver Unter Ecker - 10-31-2011

Thanks, Crawl and Pauli!

I never thought for a minute that WolframAlpha could be wrong. The query "floor((38/10)^98) mod 100" computes the correct value.

EDIT: Interestingly, while I now have floor-result harmony between WolframAlpha, bc (thanks, Pauli, for the steps!), and a BigFloat result in my calculator, they each (!) go their own way when it comes to 987 as a power. Shared digits in the beginning and divergence further on.

The 50g, following the steps by Crawl (thanks!), actually accepts to EVAL '(19/5)^987', but didn't finish after a long time, so won't be providing a result to compare. (The resulting number has 500+ digits.)

Edited: 31 Oct 2011, 9:15 a.m.


Re: Modular exponentiation with a noninteger base - Oliver Unter Ecker - 10-31-2011

Thanks, Eric. "Russian Peasant" == "binary method". So, that's what I tried.


Re: Modular exponentiation with a noninteger base - Crawl - 10-31-2011

This by itself doesn't solve the problem -- even with this approach, even with a CAS, you need to figure out how to truncate the results so you still get the correct result and so the computer doesn't have to handle billion-digit arithmetic.


Re: Modular exponentiation with a noninteger base - Oliver Unter Ecker - 10-31-2011

Ok. Notwithstanding the WolframAlpha bug, the problem remains how to calculate the modular result, without calculating the whole number.

When I hear "exponentiation" and "8 digits", I hear modpow with 10^8.

A 50g will easily tell you the result for 4^98 mod 100:

<< 100 MODSTO 4 98 POWMOD >>
If I try this with '19/5' instead of 4, "No solution in ring" is returned. (3.8 yields "Bad Argument Type".)

It returns a negative number (?) for "4^987654321 mod 100000000" (i.e. 100000000 MODSTO 4 987654321 POWMOD) but WolframAlpha and my other calc return the correct result, in no time.

If I do modpow(3.8, 98, 100), with a standard implementation for modpow

	// credit: book "Applied Cryptography" by Bruce Schneier
result = 1;
while (exponent > 0) {
if ((exponent & 1))
result = (result * base) % modulus;
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
an incorrect result is returned. (Note, for floats, "%" becomes an "fmod" and that may be the catch here.)

This works correctly for integer bases.

It also works for a small power (such as 9), suggesting that precision issues could be the problem.

(123.456 mod 100 == 23.456000000000003 in IEEE 754.)

For solving this PE problem, this is likely a wrong attack angle altogether. Brute-force hardly suffices with these problems, and the roots will likely not do, expressed as reals. Purely symbolic solutions are rare in PE, but I'm not optimistic that the task is as straightforward as it may look at first glance.

At any rate, I'd still like to know how to compute the last few digits of a fraction, or real, raised to a large power.

To spell out the PE problem, the complete calculation becomes:

floor(1/3*(4+16/(37+3*i*sqrt(303))^(1/3)+(37+3*i*sqrt(303))^(1/3)) ^ 987654321) mod 100000000

That's for the second(-simplest) root. The last term in full:

floor(1/3 * (1073741824+1152921504606846976/(1237940039285380274899123819+
9*i*sqrt(12379400392853802748991240215))^(1/3)+(1237940039285380274899123819+
9*i*sqrt(12379400392853802748991240215))^(1/3)) ^ 987654321) mod 100000000

WolframAlpha will not compute the results for these.

I'd like to do this on my calculator...

[EDIT: On reflection, as a noninteger float is multiplied the digits are spreading in both direction. So, a large exponent would cause an enormous amount of spread, and all digits needed to be retained to not cause wildly different results in the output. So... inaccurate representation reasons aside, I think it's safe to say this cannot be solved with floats. A fraction would require huge numbers, too, for the result to be accurate. The solution will be a different method, and I guess properties of those roots may well come into play.

Too bad PE doesn't let you "give up" and look at the solution thread to learn from it.]


Edited: 31 Oct 2011, 8:48 p.m.


Re: Modular exponentiation with a noninteger base - Paul Dale - 10-31-2011

For the larger exponent, you'll need to increase the scale parameter significantly in bc. 1000 or 1500 ought to be enough but err cautiously and go for e.g. 2500


- Pauli


Re: Modular exponentiation with a noninteger base - Crawl - 10-31-2011

I wonder if the multinomial expansion could help here. If the term is greater than 100000000*, it can be dismissed immediately. You still have to figure out how many terms to start with.


*-that is, the power of ten that multiplies the integers is greater than that.


Re: Modular exponentiation with a noninteger base - Oliver Unter Ecker - 10-31-2011

I don't know what that is, but will read up on it. Thanks, Crawl. (Learning new stuff sure is a fun part of PE.)