0
votes
1answer
34 views

Big-Oh of exponent of exponent

How does one whether an exponent of an exponent is the big-Oh of the other? For example, if I have $a^{b^n}$ and $b^{a^n}$, how would i determine and prove which is a big oh of another? I'm thinking ...
1
vote
0answers
47 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
1
vote
0answers
55 views

Algorithm for finding power

I has been searching for a high precision library in PHP to do calculations like $$232323232323^{121212.2232323232}$$ etc (ie, with very large numbers, including decimals), but failed to get any. ...
41
votes
2answers
2k views

Fastest way to check if $x^y > y^x$?

What is the fastest way to check if $x^y > y^x$ if I were writing a computer program to do that? The issue is that $x$ and $y$ can be very large.
7
votes
1answer
87 views

Finding $x^n$ patterns

I noticed the other day while computing consecutive powers of $2$ that for $n \geq 1$, the numbers in the ones place of the values of $2^n$ repeat every 4 terms $(2, 4, 8, 6,\ldots)$. In the tens ...
0
votes
1answer
395 views

What better way to check if a number is a perfect power?

What better way to check if a number is a perfect power? Need to write an algorithm to check if $ n = a^b $ to $ b > 1 $. There is a mathematical formula or function to calculate this? I do not ...
1
vote
1answer
72 views

How to calc $ a^{2^n}$ mod $m$ in less than O(n) time?

a,m are positive integers. if needed, you can assume m is a prime. Is there any fast algorithm? I'm sorry for my not clear description.
2
votes
1answer
104 views

Proof of correctness of Putzers algorithm

I have a question regarding the proof (seen below) of Putzers algorithm for matrix exponentiation. It's written by our danish lecturer at the university, so I translated the important parts into ...
1
vote
0answers
173 views

Power sums, fast algorithm

I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm ...
3
votes
2answers
1k views

How to handle big powers on big numbers e.g. $n^{915937897123891}$

I'm struggling with the way to calculate an expression like $n^{915937897123891}$ where $n$ could be really any number between 1 and the power itself. I'm trying to program (C#) this and therefor ...
1
vote
1answer
40 views

Formula to scale a series that is being bent with a root / power.

I have a reference number, Rx, and a series of numbers, Sx[], to compare to it. Let's call the output Ox[]. I am using a simple square root to accelerate the apparent difference between the reference ...
1
vote
5answers
171 views

How can I find $c=d^x$ using only basic computer functions?

Since this seems more like a math question than programming, I'm placing it here instead of on SO I'm trying to find $x$ when $c$ and $d$ are known constants (user input and iteration counter, ...
66
votes
4answers
2k views

Complexity class of comparison of power towers

Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
1
vote
1answer
150 views

Computing the power of real algebraic numbers

I'm looking for an efficient algorithm to compute the $n$-th power $\alpha^n$ of a real algebraic number $\alpha$ given by an interval representation for $n \in \mathbb{N}$. An interval representation ...
0
votes
1answer
239 views

Recursive algorithm for calculating powers

I am working on a maths exercise and got this question: Make a recursive algorithm on the calculation of $x^p$, where $x$ is a real number and $p$ is a natural number of $n$ bits. I really don't ...
3
votes
3answers
302 views

Algorithm for computing powers

I was challenged by one of my fellow students to write a mini-library in the programming language called C that enables you to work with very large numbers (the numbers that the language offers ...
1
vote
0answers
83 views

Integer exponentiation algorithm for the special case $3^n$

Is there any known integer exponentiation algorithm to compute $x^y$ for the special case $x = 3$ which is faster than the general case algorithm found in [1], section 4.6.3? [1] D. E. Knuth, The Art ...
8
votes
3answers
495 views

Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently

Per the title, what is the fastest way to compute exactly the exponent $m$ of the largest power of 2 such that $2^m < 3^n$? Is it possible to do this in time that is sub-linear in the value of $n$? ...
0
votes
2answers
231 views

An exponential function between zero and one

Alrighty, math noob here, so be nice :P. We're building an app and need an exponential function that exists between zero and one, and, depending on the importance we give it, will fluctuate between ...
5
votes
1answer
966 views

Algorithm for computing square root of a perfect square integer?

My question is the following: Is there a polytime non-numerical algorithm for computing square root of perfect square integers? The more elementary the algorithm is, the better! EDIT: ...
0
votes
1answer
115 views

Bending algorithm needed

Can someone help me with the formula needed to obtain the following. I need to discount products on a sliding scale. If a customer purchases 2 products, he must get a 15% discount. If he purchases 10, ...