0
votes
0answers
24 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
1
vote
1answer
67 views

Making a logarithmic equation that starts at $(0,0)$ and passes through $(x, y)$?

I'm writing a computer program and for fading sound, it's best to do it in a logarithmic equation. What I need it to find a graph of the "volume" that starts at (0, 0) [x is the time, y is the volume] ...
5
votes
1answer
234 views

Explain this code to compute $\log(1+x)$

It's well known that you need to take care when writing a function to compute $\log(1+x)$ when $x$ is small. Because of floating point roundoff, $1+x$ may have less precision than $x$, which can ...
0
votes
1answer
121 views

first 1 in a bitmask using log2

I am trying to get the last 1 in a bitmask. More mathematically speaking, I have a number k, that can be written in its binary form as a sequence of 1 and 0. I want the "weight" or "index" of the last ...
1
vote
3answers
77 views

Simplifying logs?

Would $\log_2 (n+1)$ simplify to $\mathcal{O}(\log_2 n)$? I wasn't sure if this was valid since logs aren't distributive and I couldn't find a constant $c$ relating the expressions. If this turns ...
4
votes
1answer
88 views

A logarithmic equation?

$$\mathcal{O} \left(3^{\log_2(n)} \right) = \mathcal{O} \left(n^{\log_2(3)} \right)$$ Does anyone have any idea how the right side was arrived at? (The $\mathcal{O}$ is Big-$\mathcal{O}$ notation)
3
votes
1answer
282 views

predicting runtime of $\mathcal{O}(n \log(n))$ algorithm, one “input size to runtime” pair is given

I'm given the runtimes for input size $n=100$ of some polynomial-time (big-Oh) algorithms and an $\mathcal{O}(n \log(n))$ one. I want to calculate the runtimes for: $200$, $1000$ and $10000$. For the ...
5
votes
4answers
240 views

Mathematical notation/name for the number of times a number can be divided by 2

I am using this simple snippet of code, variants of which I have seen in many places: for(int k = 0 ; n % 2 == 0 ; k++) n = n / 2; This code repeatedly ...