Exponentials under a floor function?

[SeventhSigma]

Say I have some exponential function floor(a^b)=x where a is irrational and b is an integer.

Is there a way to rewrite this as an exponential expression c^d without the need for a floor function where c is an integer?

For instance, floor(2.67^10) is 18,412, but I could also rewrite it as 2^14.1683587272239 or so but I only found that by arbitrarily choosing 2 as my base and solving for the exponent as log(18,412)/log(2). In this example, 2.67 is still rational but my point is that I want to change the base to an integer.

My question is whether or not I can rewrite the exponential given only floor(2.67^10) -- aka without using the "answer" of 18,412

 

[dlh]

I've had a look at this for a few minutes, and I'm not sure it can be done.

On re-arranging, it seems to boil down to knowing in advance what irrational number x will make 2^x an approximate integer.

 

[SeventhSigma]

I ask because I'm facing a scenario where I need to extract the last 8 digits (i.e. the modulus) of x = floor(a^b) where a is irrational and b is very, very, very large. Simply plugging it into a computer program won't work because there isn't enough precision in the a-variable to carry it out (analogy: it'd be like trying to find the answer to 4.34564899976^10 but only having realistic access to precision level 4.3). However, it's easy to do floor(a^b) mod m, but not if a is non-terminating and b is huge.

Are there other ways to solve floor(a^b) mod m?

 

[I like Serena]

Standard method of obtaining the modulus of an expression in which the numbers get too big, is by reducing the power.

If b is even:
a^b mod m = (a^2 mod m)^(b/2) mod m

If b is odd:
a^b mod m = a (a^2 mod m)^((b-1)/2) mod m

Repeat the process until the power is 1 (order of algorithm is ²log b).EDIT: If "a" is also a whole number, there's a few shortcuts you can take.
Since you are working with a limited precision, can I assume you might as well represent "a" as a fraction?

 

[SeventhSigma]

I wonder, though, if that may still prove a problem though if a needs to be sufficiently long? My b is odd, so the translation process involves an a* a^2 mod m term. Won't this, over time, start to diverge from the real answer if my first a term lacks sufficient precision, or will this not matter?

EDIT: And my a term is a root of a cubic polynomial, so it's not exactly easy to express as a fraction. So the a (a^2 mod m)^((b-1)/2) mod m becomes the next iteration's new a^b mod m ?EDIT: So, for instance, say I wanted the last four digits of 2^100,000,001 but wanted to solve it via your method.

a=2
b=100000001
m=10**4

while b>=1:
if b%2==0:
a = (pow(a,2) % m)
b=(b)/2
else:
a = a*(pow(a,2) % m)
b=(b-1)/2

Something like this?

 

[I like Serena]

Actually there's one more formula to use:
a^b mod m = (a mod m)^b mod m

But yes, basically need you to be able to multiply a by itself without loss of precision, and take the modulus without loss of precision.
The up side is that you don't need to be able to calculate a^n for n≥3 without loss of precision.

 

[SeventhSigma]

Lost me with that last one, haha. I'm really not sure if I am quite understanding. I'll play around with lower exponents first or something.

 

[I like Serena]

EDIT: And my a term is a root of a cubic polynomial, so it's not exactly easy to express as a fraction. So the a (a^2 mod m)^((b-1)/2) mod m becomes the next iteration's new a^b mod m ?

Yes.

EDIT: So, for instance, say I wanted the last four digits of 2^100,000,001 but wanted to solve it via your method.

a=2
b=100000001
m=10**4

while b>=1:
if b%2==0:
a = (pow(a,2) % m)
b=(b)/2
else:
a = a*(pow(a,2) % m)
b=(b-1)/2

Something like this?

Well, I'd use a = mod(a*a, m) or something like that.

And for b odd, you'd want to use the step:
a = mod(a * mod(a*a, m), m)
to keep the result small.

But yes, that's it.

 

[SeventhSigma]

So I try something like

a=2
b=100000001
m=10**4

while b>=1:
if b%2==0:
a = (a*a % m)
b=(b)/2
else:
a = (a*(a*a % m)) % m
b=(b-1)/2
print "a=" + str(a) + " b=" + str(b) + " answer =" + str(pow(a,b) % m)

And I get a=7296 b=0 answer =1 which seems wrong, or am I only looking at the a-term, here?

 

[I like Serena]

Oh, I'm sorry, the step
a = (a*(a*a % m)) % m
is wrong.

You're left with a * (a*a %m)^b.
You need to evaluate the right part of this first.
For instance with a recursive function call.

 

[SeventhSigma]

I don't understand, doesn't it solve that part first anyway due to the parentheses?

 

[I like Serena]

int f(int a, int b, int m)
{
   if (b==1) return a;
   if (b%2=0)
   {
      return f((a * a) % m, b/2, m);
   }
   else
   {
      return (a * f((a * a) % m, (b-1)/2, m)) % m;
   }
}

 

[I like Serena]

I don't understand, doesn't it solve that part first anyway due to the parentheses?

Taking a power takes priority over multiplying.

 

[SeventhSigma]

Ahhhh, that makes a lot more sense. I will take some time to look over this and try to understand how it works. Thanks so much for your help -- I'll see how it works against the real deal.

EDIT: Unfortunately doesn't work, but that still may be because of the precision issues, I'm guessing. It works for non-huge cases, though.

 

[SeventhSigma]

Just to note:

This is the function I am looking at: http://www.wolframalpha.com/input/?i=x^3%2B%282^n%29*x^2%2Bn

If you scroll down to "Roots for the variable x," (the items I am using for the "a" term in my floor(a^b) thing), you'll see why they are fairly gross if not impossible to use in their current forms.

 

[I like Serena]

Just to note:

This is the function I am looking at: http://www.wolframalpha.com/input/?i=x^3%2B%282^n%29*x^2%2Bn

If you scroll down to "Roots for the variable x," (the items I am using for the "a" term in my floor(a^b) thing), you'll see why they are fairly gross if not impossible to use in their current forms.

Uhm, I don't understand.
I get: n≈-0.116319, x≈Root[#1^3+#1^2 2^n+n&, 1].

But that is because n is not known.
For specific values of n, you get a regular root.

 

[SeventhSigma]

I actually wrote that wrong, should be minus, not plus, but sure, say n=2: x^3 - 4x^2 + 2


http://www.wolframalpha.com/input/?i=x^3-4*x^2%2B2

I'm after the largest root here, so 3.8662 -- but if you look at the underlying equation that yields it, it's rather crazy (if you click Exact Forms).

But I'm basically trying to raise that root to a very high power (987654321) such that I can extract the last 8 digits from it after the decimals are lopped off. This would normally be no problem with integer bases, but since the root is a non-terminating decimal, it doesn't do much use to try to raise it to that kind of power due to the insufficient precision.

So I am trying to see if there's some other way to get to that answer (either through modular arithmetic or by some utilization of the fact that I'm dealing with floor(a^b) here).

 

[I like Serena]

Yeah, well, I think you would need to keep approximately 987654321 digits of your root and do multiplications with that to find the last 8 digits.

 

[SeventhSigma]

Yeah, that's what I was afraid of, though. Seems like it shouldn't require something so bruteforce