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