1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Exponentials under a floor function?

  1. Oct 31, 2011 #1
    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
     
  2. jcsd
  3. Oct 31, 2011 #2

    dlh

    User Avatar

    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.
     
  4. Nov 1, 2011 #3
    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?
     
  5. Nov 1, 2011 #4

    I like Serena

    User Avatar
    Homework Helper

    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 2log 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?
     
    Last edited: Nov 1, 2011
  6. Nov 1, 2011 #5
    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?
     
    Last edited: Nov 1, 2011
  7. Nov 1, 2011 #6

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  8. Nov 1, 2011 #7
    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.
     
  9. Nov 1, 2011 #8

    I like Serena

    User Avatar
    Homework Helper

    Yes.


    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.
     
  10. Nov 1, 2011 #9
    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?
     
  11. Nov 1, 2011 #10

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  12. Nov 1, 2011 #11
    I don't understand, doesn't it solve that part first anyway due to the parentheses?
     
  13. Nov 1, 2011 #12

    I like Serena

    User Avatar
    Homework Helper

    Code (Text):
    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;
       }
    }
     
     
  14. Nov 1, 2011 #13

    I like Serena

    User Avatar
    Homework Helper

    Taking a power takes priority over multiplying.
     
  15. Nov 1, 2011 #14
    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.
     
    Last edited: Nov 1, 2011
  16. Nov 1, 2011 #15
    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.
     
  17. Nov 1, 2011 #16

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  18. Nov 1, 2011 #17
    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).
     
  19. Nov 1, 2011 #18

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  20. Nov 1, 2011 #19
    Yeah, that's what I was afraid of, though. Seems like it shouldn't require something so bruteforce
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Exponentials under a floor function?
  1. Exponential functions (Replies: 2)

Loading...